Table of Contents
- Introduction
- Security Threat Model
- Design Principles
- Existing Implementations & Ideas
- Conclusion and Open Questions
Introduction
We briefly discussed the format of identifiers in part one. Here we will describe the design considerations in detail. We’re writing this because formats for keypair mnemonics seem to be underexplored. We’d like to present our thoughts publicly in case there are aspects of the problem that haven’t occurred to us, or good solutions we don’t know about.
Zooko’s Triangle
https://upload.wikimedia.org/wikipedia/commons/5/5c/Zooko's_Triangle.svg
The traditional analysis of name and identity in distributed systems is Zooko Wilcox’s triangle of human-meaningful, decentralized, and secure. Zooko conjectured that no distributed system could have more than two of these properties at once. He has since taken this post off the web, but it can still be accessed through the Internet Archive. Zooko was writing in the era when people still used Windows 98, so his analysis was restricted to the state of the art in the early 2000’s. Cryptographic blockchain primitives like proof-of-work and proof-of-stake disprove his conjecture (at least in theory) but it’s still a good place to introduce the problem. The three criteria are:
- Human meaningful means names that people can remember. Perhaps the most stringent version of this requirement is the "moving bus test"0. If you see the name on the side of a moving bus will you be able to remember it long enough to use when you get home?
- Decentralized means there are enough parties that would have to act together to subvert the system that users have reasonable assurance that will never happen. The Certificate Authority (CA) system used by websites for HTTPS fails this test because one corrupt CA can compromise the entire system.
- Secure is the most nebulous of the three criteria. Zooko himself admits that in order to describe your system as disproving the triangle conjecture it would have to start by defining security in a sensible way. Therefore we can only discuss this requirement in the context of a defined threat model. We’ll present our threat model in a bit, but usually properties to consider include resistance to phishing, protections against mimicry and forgery, along with more basic considerations like stable mapping between names and crypto keys.
We don’t have to spend a lot of time thinking about decentralization. Blockhains give us that at the protocol layer. Human meaningful and secure however are worth looking at in detail. Both are deeply impacted by our choice of identifier format.
In part one we discussed the difference between two kinds of name:
- An identity or a stable name tied to the public key of some persona.
- A vanity name which exists for the sake of branding and status.
In the context of a complete name and identity system, human meaningful usually means vanity and the moving bus test makes total sense in that framework. We’re talking about the identity layer though, so maximally meaningful names are not really desirable because they create a vanity dynamic. That means we need some other rule of thumb for “human meaningful”. In this context a name is human meaningful if we can expect people to remember and type it in themselves on forms and login screens. By this standard phone numbers skirt the boundaries of meaning. We know in practice that people can memorize and dial quite a few phone numbers (or at least they could before smart phones automated that away). However we would like something friendlier than that.
Security Threat Model
In order for the rest of this analysis to make sense, we need to be clear about what we are and aren’t considering as part of our threat model. Lets start by examining the adversary, who is this system primarily trying to defend against?
Common Adversaries
- Scammers and Phishers are the most common adversary. These are people who want to trick the user into doing something they rather wouldn’t, like send them money. They’re overwhelmingly the most common adversary, and one of the hardest to thwart so most of this post will focus on them.
- Technical Experts with an adversarial intent. Most of the attack surface this adversary has access to is beyond our control. In strict terms, the Tezos network has more code than any smart contract we’re going to write. The best we can do to protect against these is writing simple code, using tools like unit tests and formal verification when possible, and keeping as much functionality off-chain as we can. Because all of those things are beyond the scope of this post, we’ll only mention this adversary when it’s related to the discussion of name formats.
- Speculators are interesting in that they don’t threaten any individual user as much as they do the system itself. If we’re going to have a name system people use, then identities need to be affordable. That means measures need to be taken at the system level to minimize land-grabs, reselling, and incentives to buy the namespace and resell it at a profit.
We’re also going to make some assumptions:
Security Assumptions
- The Tezos network implementation is more or less correct. That is, there won’t be some epic whole-network exploit that allows someone to steal all the names, etc. Or if there is such an exploit, the social fallback mechanisms available to blockchains will roll it back.
- The crypto primitives involved are basically secure.
- Adversaries have limited financial resources. Scammers, malevolent technical experts and speculators only have so much money to exploit the system with. This assumption could be violated if a nation-state level adversary decided it wanted to damage the identity system.
- Users will have the ability to verify offline identities outside the system. Because we’re looking at formats for stable pseudonymous identities, we do not consider phishing and mimicry of someone’s legal name or established off-chain identity as part of the threat model. That functionality is handled by search engines, directories, and informal social arrangements. Users can submit metadata with their identity registration that provides an alleged legal name, twitter profile, etc. At best this metadata plays the role of a nickname in a petname system, and should not be taken as more than a suggestion of the users off-chain identity.
Even after accounting for these assumptions, we still have threats such as:
Threats
- Phishing that relies on tricking the user into thinking the adversary has control of a name they don’t. A common example of this is using lookalike domain names to fool users into clicking “official” communication from a business that’s actually the phishing login of some fraudster.
-
Issues in the implementation of the ID layer smart contract. This is the most likely threat to be exploited by technically sophisticated adversaries. We can basically distinguish between two kinds of problem:
- Flaws that eventually make the system inoperable. For example, if the contract was implemented by storing mnemonics in a list instead of a big map and the cost of searching the list eventually makes things prohibitively expensive.
- Flaws which can be exploited by experts for gain. For example, if someone found a way to not have to pay for names they could register the entire remaining namespace and then resell it for profit.
- Namespace exhaustion. Depending on how it’s implemented the system could run out of names. This could be done by squatters and speculators looking for a payday, or if the system is implemented very poorly a bored kid with a shell script. It could even be done by legitimate users, if the system is set up to allow fewer name registrations than are desired over its lifespan.
Issues in the implementation of the ID contract are a bit too broad to really address beyond “follow really good defensive programming practices”. But here are some steps we can take to respond to other potential threats:
Response To Threats
- Phishing resistant names: Phishing, trojans, and other attacks based on social engineering can’t really be totally stopped. If the user has the power to authorize something, they can be tricked into doing it. That doesn’t mean we can’t make it harder for attackers, though. Ideal identifiers should be easily distinguishable from each other so that an attempted phish has to do more work to fool users.
- Large Namespace: One way to prevent namespace exhaustion is to have a lot of names. Perform an analysis of how many users might (reasonably) use the system, and then make sure the name format can accommodate that.
- Registration Cost: Another way to prevent namespace exhaustion is to attach a price to names. This price should be low enough that it’s trivial for users to pay but high enough that exhausting the namespace by registering many names would be too expensive.
Design Principles
We’ve learned that identifiers should be memorable and phishing resistant. To achieve these things we’ll need a set of guidelines to evaluate solutions:
Length
All else being equal, shorter is better.
Memorability
Memorability is a spectrum that goes from the Moving Bus Test to raw sha256 hashes. The most memorable names are brands and legal names. But from a user experience perspective, these names can be undesirable because they introduce a status element to the namespace. There can only be one “John”, and the person who gets to control the mnemonic “John” is probably going to be decided by a third party bidding system. That means identifiers are an indicator of wealth, and all the attendant incentives of that become baked into your identity system. Vanity names also impose another user experience cost, which is that since all the simple (and thus desirable) names are taken the user must now try to come up with a status bearing name that is not in use. This is an annoyance to the user that can be avoided by constraining your name format.
We also consider the ability to enter names on forms and give names over the phone to be essential features of memorability. This is the basic reason why we can’t use Identicons. It’s easy to see an Identicon at a glance and know who it belongs to but it is not describable over the phone or on a form.
Phish Resistance
It should be hard to mimic someone’s identifier with a similar looking but separate identifier. If your identifier is a phone number then you might not notice if a five is changed to a six. Ideally identifiers should be pronounceable, so that you can ‘feel’ the wrong sound if something has been changed[1]. Changes should also be visible, and certainly we want to avoid Unicode lookalikes or single character changes to identifiers. Identifiers should have something like the property hashes do, where a one bit change in a hash doesn’t produce a slight difference in the resulting value but an entirely different value which is obviously different at a glance.
From a security perspective vanity names are undesirable because they are not phish resistant. Homographs such as lowercase L (l) vs. uppercase i (I) allow one name to mimic the appearance of another. A vanity name system which is international would almost have to allow Unicode. Unicode in your keypair mnemonic format is an absolute disaster. Unicode has many homographs, and thus many opportunities for two visually indistinguishable names that do not refer to the same persona.
Aesthetics
This aspect of an identifier format is subjective, but important. A name is something that users have to look at many times. The ideal format should not create feelings of unease or aversion. It’s probably possible to measure the aesthetic appeal of a name format with user surveys, or some other market research tool.
User Choice
Users should like their identifier. This is a weaker design requirement than phish resistance, and it trades off against phish resistance so we should expect most good identifier systems to have pretty restricted formats. Even in these restricted formats however there is still a question of how much choice to give users. Should users:
- Pick an identifier within the format?
- Have one assigned to them?
- Be able to ‘skip’ an autogenerated identifier until they get one they like? If so, how do you stop that from exhausting the namespace?
Namespace Size
Your identifier system needs to be able to scale to the number of users it’s expected to have[2]. A few rules of thumb to keep in mind for estimating this:
- There are 7.7 billion people in the world at the time of writing. If your system is going to be used by people you should probably have a socially acceptable name available for each one. We can also expect there to be more people in the future, so the system should be able to scale to a doubling of the human population. It’s difficult to imagine our world supporting more than 15 billion people. Doing so would probably involve significant changes to life that break a lot of our assumptions about this problem anyway.
- **10 billion microprocessors were manufactured in 2008**. You should assume that every one of those is going to get hooked up to a network eventually. When they do, perhaps 10-20% will require a name. So if your system isn’t capable of handling another 2 billion names every year it’s not suitable for use to describe machines in an Internet of Things landscape.
Implementation Complexity
No matter what format you pick, there’s code that has to implement it. You either have to accept or generate a name at creation time, and then other code has to store and validate names. If your smart contract accepts names from the user, that opens up an entire new area of attack surface. Each extra line of code in that validation makes the attack surface wider. Complexity also increases the cost to programs that want to be part of your ecosystem. For example the Urbit name system has a complicated generation scheme. This means any program which wants to interpret the raw integer representing an Urbit name has to have an implementation of this generator. Another example is Unicode domain names. If you have a vanity name system that allows Unicode then clients will generally need some sort of Unicode handling strategy. Because Unicode is complex, this increases the overall complexity of the system. Therefore we prefer simple schemes that are easy to program when possible.
Internationalization
If we’re building a global namespace (and we are) then you can’t just consider users who speak English. Whatever format we choose needs to be usable by people using different writing systems, and who do not consider the same phonemes as significantly different (e.g. some people might consider g and k as easily distinguishable, whereas others might consider these sounds very similar).
Existing Implementations and Ideas
Ethereum Name Service
ENS is a DNS-like system implemented using Ethereum smart contracts. It’s used by Swarm to provide human readable names for nodes. ENS takes a vanity name approach to identity, allowing users to register domains just like you would on normal DNS registrars as a .eth TLD. Because .eth isn’t recognized by ICANN a browser extension is required to view ENS domains. Identifiers were originally handed out through an auction system that tried to prevent bidding wars by hash-commit-revealing bids. This system actually ate some bidders tokens, and confused a lot of people so they eventually switched to instant registration. Despite these aspects ENS has been relatively successful, claiming over 300,000 paid registrations.
Length: To stop the namespace from being immediately consumed, the developers decided to limit initial registrations to 7 characters or longer. Vanity name systems have an initial length advantage because they’re composed of arbitrary character combinations, but this advantage disappears over time. Because these systems incentivize status driven behavior, the theoretical pool of 2-7 character names is larger than the practical pool of desirable names which users exhaust quickly. In the .com TLD the average length of registered domains is about 10 characters. For a system with millions of users that’s pretty good. Phish resistant systems are in general going to do worse than vanity systems on this metric.
Memorability: Vanity names also enjoy the best memorability characteristics, at least for early registrants. Over time as the namespace is occupied the memorability of domains probably goes down. The famous [pets.com](http://pets.com) is an English word, which makes it intrinsically more memorable than [xkcd.com](http://xkcd.com) even if the latter has by this point become well known. Getting something like pets.com is easy if you’re an early registrant, harder if you’re late to the party.
Phish Resistance: This is the real downfall of vanity systems, especially in the context of their use as a mnemonic for a keypair. By this point we’ve probably all experienced the scam emails sent by fraudsters who’ve gotten their hands on a domain with a homograph that looks identical to a well known business. Vanity names are vulnerable to single character changes, sometimes with lookalikes that are imperceptible to users. This makes them deeply unsuitable as the base for an identity layer, even if they do have desirable qualities for branding.
ENS is particularly vulnerable to phishing because it allows names to have Unicode characters. This concern is actually acknowledged in the documentation, where it’s given a brief treatment that essentially says this is a problem for client programs to solve. We are not convinced this is a problem that should belong to the client, but it is definitely a problem for the client.
Aesthetics: This criteria has much the same story as length and memorability. The aesthetics of vanity names are great for early registrants, poor for users that have to make do with the names earlier users didn’t want.
User Choice: Vanity name systems have excellent user choice, and encourage strong emotional attachment.
Namespace Size: In theory the ENS namespace is almost unbounded. Names are stored in the system as 32-byte hashes, allowing very long domain names. Combined with the use of Unicode, there’s no reason to expect the theoretical capacity of this namespace to ever be exhausted. In practice of course vanity systems have status dynamics so it’s difficult to estimate the number of desirable names people would actually like to use.
We also have to consider storage of name records. If names are stored as 32 byte hashes then that’s a roughly 3x storage cost increase over the average domain name length of 10 characters. In the first quarter of 2019 there were 351.8 million domain names on the Internet. Considering just the hash without other metadata, it would require roughly 11gb of storage on the Ethereum blockchain to recreate the current DNS system with ENS. This would make it a significant fraction of the current Ethereum blockchain, which is in the hundreds of gigabytes. For something as important as digital identity however, that’s not an unreasonable cost to pay.
Implementation Complexity: The use of Unicode in names seems to have motivated the developers to store them as hashes. This introduces a weak point to the system. If in the future it becomes possible to find collisions in 256 bit hashes the fundamental security of ENS could be compromised. However these hashes do reduce the complexity for other programs interacting with the system, by allowing them to get out of handling Unicode. Unicode strings are treated as arbitrary bytes, and their lookup is done by hashing them.
Internationalization: Through its use of Unicode ENS is an internationalized name system. While it might come at a significant cost in phish resistance, Unicode vanity names are about as inclusive as you can get. We should be careful about concluding vanity names are the best choice for international users however. The monetary and status aspects of vanity names can present serious problems for users in the 3rd world. In these locales a ‘trivial’ cost of 5 or 10 dollars for a name is not trivial, and that’s just the cost for a name nobody else wants. By using vanity names alone for their namespace ENS inserts the users financial status into every situation where the name is used.
Urbit’s Name System
Urbit is a distributed computing project started by Curtis Yarvin which aims to deprecate the existing computer software stack. That means it intends to “start over” with a new operating system, system programming language, networking model, filesystem and data model, etc. Like Plan9, Urbit is designed with the assumption that it will exist as part of a computer network. The idea is that by making the system primitives simple, peer-to-peer, and encrypted by default you lower the amount of effort necessary to build and run distributed applications. They become the straightforward implementation instead of a hack on top of the cathedral of hacks that is contemporary computing. One of the keystones of this full stack replacement is Urbit’s identity system, where each identity is tied to a virtual machine.
This all makes the name system of particular interest, because it’s not based on vanity names and is deeply woven into the Urbit system. If there are fundamental flaws in the name format, these could actually threaten the overall project. Urbit names look like this:
8 bits galaxy ~lyt
16 bits star ~diglyt
32 bits planet ~picder-ragsyt
64 bits moon ~diglyt-diglyt-picder-ragsyt
128 bits comet ~racmus-mollen-fallyt-linpex--watres-sibbur-modlux-rinmex
The underlying data represented is an unsigned int, which is then encoded as a human readable string from a phoneme table. How exactly this is accomplished is complicated, to say the least. But you should know that it’s based on the hierarchy of the Urbit network. The more bits in your name, the less of the Urbit address space it takes up. The most common names for users would be planets and moons. A planet is the equivalent of an IPv4, there’s 4 billion of them or so and since there aren’t enough for everybody the idea is that friends/family will share a planet. Those other users interact with the network as moons of the planet. Objects and temporary identities associated with moons use the comet name format. Therefore we’ll say that the most likely name most users will interact with is the moon format.
Length: A moon name is 28 characters including the tilde. This is nearly 3 times the length of the average domain name. This metric is traded off against for memorability and phish resistance, but that doesn’t change Urbit moons doing fairly poorly here. Planets are gentler at 14 characters, but just like how most current Internet users do not own a domain name most Urbit users are not expected to have a planet. Comets may as well be a sha256, but that doesn’t matter very much since the design intent is for them to mostly be temporary identities that users interact with through copy-paste.
Memorability: The memorability features of Urbit names are perhaps one of the most puzzling features of the system. They are composed from a syllable table and are at least in principle pronounceable. If this system were to become popular, people would probably become familiar with the name format and it wouldn’t seem quite so weird. Right now however these names are strange, and take some getting used to. The features of the name scheme imply that design effort was focused on encoding the user family tree into names, rather than explicit memorability. Therefore it remains to be seen how memorable these names are in practice. One interesting feature is that because they are not descended from any existing major language, all users are equally disadvantaged by the system. This means Urbit names have at least weak internationalization.
Phish Resistance: Because Urbit names are meant to be pronounced, and use a syllable table for generation they have pretty good phish resistance. Homograph based attacks will not work because users do not have control of their name at the individual character level and there is no Unicode. If users pronounce their name, then changing one of the syllables should make it “sound wrong” when read aloud or with the internal voice. Unfortunately the lack of meaning to these syllables does leave some room for phishing. But that probably can’t be avoided in a system that does not privilege native speakers of one language or another. Overall, Urbit is doing this aspect of their system right.
Aesthetics: These names look odd, and there’s no getting around that. That oddness may actually work in their favor, it is better to be proudly odd than a member of the uncanny valley.
User Choice: How much choice Urbit users have about their name is dependent on multiple factors. At best, Urbit users choose their name from a precomputed set of possibilities. The average Urbit user will probably not have much control over their name.
Namespace Size: Urbit makes the intentional design decision to limit planet names so that not everyone can have one. The idea is that by introducing scarcity around names, people will be less likely to abuse the network.
Implementation Complexity: The implementation complexity of this name system is pretty out there. The authors have even used a custom cipher to obfuscate the relationship between planets and their parent stars.
Internationalization: Urbit names aren’t going to look natural to any user in the world. This puts everyone on an equal footing. There is a certain level of bias in the use of ASCII characters, as it means the syllables are romanized. It would be interesting to do a phoneme analysis and compare the phonemes chosen to the frequency of phonemes across human languages. If the Urbit team has done their homework then they’ve probably avoided the use of uncommon phonemes, and tried to stick closely to the sounds people are used to speaking across languages.
IP Mnemonics
An interesting mnemonic system is proposed by “Adam” using three letter words to replace the range sections of an IP address. For example the address 66.33.193.225 would become far-cab-raw-tap. So one dead simple proposal is to encode an unsigned int from 0 to the end of the address space as one of these IP mnemonic names and assign that to the user. If we used 4 words as in IPv4 we have Urbit’s 4 billion names, but adding a fifth word increases the address space to well beyond the human population.
Length: A 5 word name in this system has 15 characters. This is a little worse than a vanity name’s 10-13 and comparable to an Urbit planet’s 14. The difference is that we can give every user a 14 character name, not just the ones who are privileged enough to own a piece of the limited Urbit address space.
Memorability: For English users at least, this system has excellent memorability. It is comparable to the famous “XKCD passphrase” method of password generation but even better because we use only common English words of short length. Google Scholar finds some studies that look at the memorability of the XKCD method, but most of the analysis seems to be tangential to our purposes.
Phish Resistance: This system does very well on phish resistance. It is short enough to be pronounced out loud, but because each three letter word has its own vocal stress it becomes harder to fool someone who has memorized a mnemonic. Any change in the mnemonic makes it visually distinct. Like Urbit names, users do not have the ability to use homographs and there is no Unicode. One potential weakness is that if names are assigned in order then naming will be “bursty” and users will be able to register multiple names with a similar appearance except for one changed word. This can be mitigated through hashing, or a system that pulls an identity at random from the remaining namespace.
Aesthetics: This is subjective, but for English speakers all three letter words should be familiar and a name made up from them might even be ‘cute’. Words like ace ,cat, and zip invite a certain sort of playfulness. For international users this could be more problematic.
User Choice: This system has some amount of flexibility when it comes to user choice. It might be possible to allow users to submit a request for the specific name they want within the remaining namespace. A simpler system is to do in-order assignment with the ability to ‘skip’ for some small cost if a name is undesirable. The cost has to be high enough to stop adversaries from eating up the namespace by skipping however, assuming the contract does not have a mechanism to ‘reclaim’ skipped names.
Namespace Size: With 15 character names this namespace would have 256 ** 5 possibilities or about a trillion names. This is not enough names that we can assume they’re functionally limitless, but it is enough names that people are not going to be fighting each other over limited namespace. The on-chain storage analysis is fairly similar to the one done for Ethereum Name System, with a few of the numbers changed to produce a single digit multiplier difference in size. Namespace size is not a significant bottleneck for this system.
Internationalization: One of the major shortcomings of this system is that it is not as accessible to non-English speakers. It does have the advantage of only using the most basic components of English, which are commonly taught internationally. Even if the system is as confusing to non-English speakers as the Urbit name syllables are to everyone, it’s only as confusing and has the advantage of being extra meaningful to English speakers. It’s a bit like UTF-8, which privileges English through its compatibility with ASCII but is also a massively convenient system compared to the bloated UTF-32 and sibling encodings. It is also possible that this system could be improved by pruning three letter words which use phonemes that are not common in other languages. This would require some idea of what those phonemes are. The research for that is beyond the scope of this post but of interest if anyone would like to do it.
Conclusion and Open Questions
This is by no means a settled subject. A lot of why we’re writing this is that we’d like to get feedback on our ideas. Did we miss anything? If distributed identity schemes interest you and you have ideas on name formats we’d love to hear them. You can share them in the comments, or send them to the author. Our preferred scheme is the IP Mnemonic format discussed above, but also welcome comments on ENS, Urbit, or any other interesting name scheme out there. We also have some research questions which could be explored in a future post by us or others:
- How do these systems make life harder or easier for international users beyond the ways we’ve outlined?
- Which three letter words are hardest for people who don’t speak English? What are the most common phonemes in global languages?
- Is there a good way to get data on the memorability of different mnemonic formats?
[1]: This could present a problem for deaf users who might not have a good model of how strings should “sound” when pronounced. Because the underlying format for most of these systems is a number, it’s entirely possible a system might use both a textual and graphical representation for a particular name.
[2]: There’s also the question of abuse. In a namespace where identities are cheap, it’s harder to prevent throwaway identities from abusing the system. Consider the notion of an “IP ban” in an IPv6 world where IP addresses cost almost nothing to change. Scarce identities can theoretically be a way of limiting system abuse.
This is the reasoning employed by Urbit in their FAQ for why they only have as many addresses as IPv4. In a smart contract system we don’t have to resort to such measures. Rather than restrict the supply of basic identities, we can separate concerns with a costly signaling contract. Users would “burn” a certain amount of Tezos to prove they have an investment in their identifier. If they spoil that identity with bad behavior, they’re out the value of their costly signal. This allows for flexible permissions and identifier costs without crippling the underlying namespace.
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License. You can attribute the author as “John David Pressman and the LIGO team” or “John David Pressman (ligolang team)”.
