I was reading up on the Microprediction website, and I saw that instead of registering and getting API keys, they were using something called MUIDs that can be generated completely locally.
I wanted to play with their API, so I needed write a tool to generate these keys. The tokens don’t seem to be super well-documented, so I’ll write a little about what I did.
After reading about them, they immediately strike me as very similar to Hashcash and other similar proof-of-work schemes. It actually makes a lot of sense for rate-limiting the creation of API keys.
What is a MUID?
A MUID, or a Memorable Unique Identifier, is a proof-of-work system that generates tokens that have animal name prefixes when hashed with SHA256.
For example; the string 8d9ff7fed0056ed174cb7315135f0b5f when hashed with SHA256 turns into beeca778a6248d9b8725.... If you squint enough, you can see that it starts with “Bee Cat”.
In this example, 8d9ff7fed0056ed174cb7315135f0b5f would be the secret key and the hash beeca778a... would be the public identifier.
As the prefix gets longer, it becomes more difficult to find these MUIDs. The idea is to start with a minimum prefix length for rate-limiting, and then to give the keys with longer prefixes more privileges.
How does it work?
Common proof of work schemes use the number of ‘0’ bits at the start of the string as the difficulty. Similarly, you could use the number of ‘1’ bits if you wanted. This scheme of counting the bits from the start is very universal, and can be communicated easily with a couple paragraphs.
In contrast, MUIDs need a dictionary of the valid prefixes consisting of adjectives and animal names. To verify if a given MUID is valid, you need to have this information. It is available from the repository of the reference implementation. The file is called animals.json in case you want to fetch it as well.
Once you have this file, it is pretty easy to mine and validate MUIDs. I wrote a simple miner in Python. While it’s not a speed demon, it works well enough for my needs.
Here’s a rough sketch of my miner.
import json
import hashlib
import os
# Target difficulty
TARGET_DIFF = 8
prefixes = set()
with open("animals.json") as f:
f = json.load(f)
for key in f.keys():
if len(key) == TARGET_DIFF:
prefixes.add(key)
while True:
buf = os.urandom(16).hex() # 32 random hex digits
h = hashlib.sha256(buf).digest().hex()
if h[:TARGET_DIFF] in prefixes:
print(buf, h)
When I find some time, I’m planning to rewrite it in C to make it truly fast.
