Published: 2022-01-16

Private and Decentralized Human Readable Names with Fuzzy Message Detection and Delay Towers

Here is an idea for implementing a fair, secure, private, decentralized mapping from human-readable namespace to arbitrary data using delay towers and fuzzy message detection (FMD).

For a brief overview of my previous work on fuzzy message detection see Discreet Log #1: Anonymity, Bandwidth and Fuzzytags.

How to Claim a Name

Let’s say I wanted to claim the name cwtch:sarahjamielewis to do I would need to do two things:

1. Start building a delay tower referencing my claim to cwtch:sarahjamielewis
2. Setup a Cwtch Identifier Responder on the Cwtch Name Resolution Service (which is a Fuzzy Message Detection Server)

Building a Delay Tower

A delay tower is a puzzle tower using Verifiable Delay Functions (VDF) as the puzzle. Our genesis block references the claim, and we maintain our tower by constantly running th solver.

See: Delay Towers

Anyone can build a tower for cwtch:sarahjamielewis but doing so is a constant commitment to computation that cannot be parallelized. Speed-ups can be obtained through running on dedicated hardware or more powerful CPUs, however the longer a delay tower is active, the harder it is to catch-up.

The genesis block for the delay tower references: the name to be claimed, and the public key of the claimer (used to verify signed updates to the delay tower - to prohibit anyone from claiming tower work as their own).

At a constant rate the builder will begin adding levels to their tower for as long as they want to keep their name. More popular names may have competition and so holders have an incentive to invest some amount in computational resources to keep it. However, this competition has a strict limit.

People who start building their tower and claim early have an advantage as long as they keep adding levels to their tower. Because, a tower takes constant work to upkeep then an attacker who wishes the steal the name must plan early to build their tower - at the cost of building another tower to claim another name.

Building an Identifier Responder

cwtch:sarahjamielewis can be transformed into a known Keypair via a key derivation function. This produces a TaggingKey and a DetectionKey

This allows anyone who is interested in requests for resolving cwtch:sarahjamielewis to both derive the tagging key to tag the request. In addition, is allows anyone who is listening to requests tagged that way via the Cwtch Name Resolution Service.

A request consists of a Tag, and an ephemeral Public Key used for encrypting the response.

When requested, an Identifier Responder will send back their delay tower - encrypted to the senders ephemeral key.

Overcoming spam and providing Metadata Resistance (Pin-but-Verify)

Observe that the request contains an inherent piece of metadata - the name we want to look up. Anyone can derive the root secret needed to verify requests to the name. We can restrict the number of bits an adversary can realistically extract from this by reducing the entropy of the tag itself i.e. decrease its length.

This means that any request could be a false positive - and as such we need to choose this parameter such that it will not result in a slew of responses for any request - but low enough that it doesn’t leak the name being queried.

By enforcing a maximum size (e.g. 15 alphanumeric characters) we can place an upper limit on the number of registrable names, and as such define known false positive rates for requests - and tune the expected traffic levels considerably.

This prevents an Identifier Responder or any other observers from knowing the exact name being requested.

It is also worth noting that once a tower has been found it can be looked up out-of-band using any number of methods (assuming the tower still grows at a fixed rate it’s resolver can be pinned-and-verified to prevent costly resolver lookups).

Outline of Protocol Steps for Resolving a Name

For a first time lookup:

1. Alice wants to resolve cwtch:bob so she derives the tagging key tk = TG_KDF(cwtch:bob)
2. With tk alice derives a Tag t = tk.generate_tag() and an ephemeral key pair pk, sk = KeyGen and sends both t and pk to a Fuzzy Message Detection Server (FMDS).
3. The FMDS passes on t and pk to anyone whose detection key verifies on t (there will be true positives for anyone wants to claim cwtch:bob and false positives for  ≈ 2^−γ × N resolvers)
4. Each matched resolver will encrypt their latest Delay Tower Proof with pk and tag ciphertext with pk.generate_tag()
5. The FMDS passes the encrypted result back to the original requester (detection via their ephemeral detection key) (there will be false positive receivers at this step also)
6. The requester can decrypt using their ephemeral key, reject any delay towers that are for the names they do not care about, and then defer to the highest delay tower for the result.

For successive lookups:

1. For future resolutions Alice can pin the public tagging key / out-of-band resolver for the Delay Tower that won the first time lookup and occasionally request updates to the tower.
2. As long as the tower grows at an expected rate then Alice can trust the resolver (even in cases where the value of the namespace lookup changes e.g. mapping a name to a different public key or IP address)
3. If the tower ceases to be updated then Alice can throw away the tower, and fall back the more expensive first time lookup again.

Additional Thoughts

Parameterization of this system is hard, but does seem tractable.

Unlike other potential instances of Fuzzy Message Detection we don’t need to worry about statistical matching for requests (because tags are one-use and uncorrelated).

Because public names and resolvers are 1:1 there is an inherent amount of metadata in the relationship between the public name, the resolver and whatever is being resolved. Care much be taken by resolvers to not leak any other data (e.g. IP address).

Assuming all traffic to-and-from the FMD server is encrypted, then an adversary that can corrupt the FMD node can only relate IP addresses to resolvers. They cannot relate honest requests to honest resolvers (because of the inherent anonymity set provided by FMD false positives).

To prevent this, resolvers who want anonymity much always be behind some form of ACN when communicating with the Fuzzy Detection Server (e.g. via a v3 onion service or utilizing something like Niwl).