Zooko’s triangle proposes that a global naming system can be human meaningful, distributed or impersonation proof - pick 2. Below I look at Pet Names, the traditional way of handling Zooko’s triangle. Then I look at proposals that claim to actually solve Zooko’s triangle and show several attacks that these systems don’t appear to solve and so argue that Zooko’s triangle still stands.
The problem
Zooko's triangle argues that when it comes to securing names in a global namespace one has three choices, only two of which can be realized in a single system. Those choices are:
human meaningful Names are strings short enough for humans to memorize
distributed there is no central authority who can control name allocation
Impersonation proof nobody can successfully pretend to be someone else
Most naming systems want to use names for high value transactions (e.g. spending money, sending secret messages, etc.) so being impersonation proof is pretty much a required property.
Given our practical experience with the abuses that have occurred in centralized systems like DNS within the distributed Internet community I would argue that there is a consensus that any new naming system must be distributed.
So if Zooko’s triangle is correct then we have to give up human meaningful names.
Pet Names
The solution usually adopted for the Zooko triangle trade off is to get human meaningful names via Pet Names. This is, btw, the solution that Thali uses.
Imagine you and your buddy Joe are exchanging identities and Joe sends you his public key. Now some thousand letter long string of stuff isn’t very readable so as soon as the key comes in your system’s address book will prompt you to give the key a memorable, unique name. You type in ’Joe’. Your address book will make sure no other entry has that same name and then will accept it. In this case ’Joe’ is a pet name. It is a name that is unique amongst all the names in your address book.
Now imagine that you are in your email app and you receive an email from a friend with 20 keys in it (i.e. each key represents some person the email was sent to). You could look at the 20 keys but they are huge random looking strings and aren’t going to be very meaningful. So your email app has to look those 20 keys up in your address book. Let’s say 5 keys are in your address book so your email app will show your selected pet names for those 5 keys. But what does it do with the other 15 keys?
Since showing big long unreadable strings isn’t very useful it’s highly likely that the message that listed those 20 keys will have suggested display names for each key. Now imagine that one of the keys that isn’t in your address book has the suggested display name of “Joe”.
What we have is a collision. You already have someone in your address book you call Joe and it isn’t the person that the display name in the email is associated with. Now what?
The answer in Pet Name systems is that all applications have to teach users to recognize two different ways of displaying names. One way is for Pet Names and the other way is for ’random insecure stuff I show you’. And users have to be able to tell the difference or they will do insecure things (like send a message to the wrong Joe).
Pet Names have other problems but mainly they all come down to the same issue - Pet Names aren’t robust. Imagine you have two computers and due to network issues they have slightly different address books. Imagine you are trying to debug an issue or look at some data that contains a field your software doesn’t recognized and you look at the raw data, you won’t see pretty names, just unreadable keys. Imagine one of your clients has a bug in how it uses the address book and displays the wrong Pet Name. Pet Names require a lot of things to go right in order to work.
What if Zooko was wrong?
It has been suggested that Zooko was wrong and in fact it is possible to create a system with all the properties in the triangle. Wikipedia’s entry on Zooko’s triangle points to an article by Nick Szabo and a proposal by Aaron Swartz that both claim to solve Zooko’s triangle.
Dan Kaminsky did a good job of showing a bunch of practical problems with Mr. Swartz’s proposal. Mr. Szabo’s proposal is, I think, more complete. But it also can be subverted if enough bad guy guys start to vote. Still, as Mr. Szabo points out, anytime there are enough bad voters you are going to lose. Unfortunately that is reality.
But, to simplify this conversation, let’s pretend that the majority of voters are good and true. If that is the case, has Zooko been proven wrong?
Namespace Exhaustion
Let’s imagine we have squared Zooko’s triangle and in this wonderful global namespace system someone grabs the name ’Joe’. Well what about the millions of other Joes out there? They can’t be Joe since there can be only one. So now they can be Joe1 or Joe2 or whatever. In other words, nice names run out fast.
This actually happened in the real world with Hotmail. Hotmail had been around long enough and had enough users that every single even remotely reasonable name was taken. Hotmail finally had to start offering email addresses other than ’hotmail.com’ just to open up new namespaces so users could get names that were remotely recognizable to their friends.
Now one could argue that Mr. Szabo and Mr. Swartz’s proposal could work like Hotmail. Someone could grab a ’domain name’ and then sell names within it. Both systems have the property that once a name is transferred any future transfers can only occur with the permission of the previous owner. So we don’t have to worry about the ’domain name’ owner trying to grab the name back (as we do, for example, in DNS).
The problem is - how many useful sub domain names are there? In other words, the exhaustion problem is probably recursive. And sub domains themselves are subject to the malicious names attack described in the next section.
There is also the problem that as people die or abandon names there better be some mechanism for getting those names back in circulation or exhaustion will happen even faster.
Malicious Names
Human readable names are potentially confusing. For example, are Joe and joe the same name or different names? What about the Unicode homograph attack? How about the equivalent of domain squatting? In these attacks a name is created that will cause confusion amongst users and make them do the wrong thing thus making the names not impersonation proof. For an indepth exploration of these impersonation issues please see RFC 6943.
Pet Names handles this kind of attack by putting the user in control. So if the user has two friends who both suggest their Pet Name be ’Joe’ it is up to the user (and the user alone) to decide who gets what name. One might be ’Joe from work’ and the other could be ’Uncle Joe’. The user can also have whatever local rules make the most sense for them. For example, a user who is a native speaker of French might only allow characters for Pet Names from the Latin alphabet and only allow new Pet names that don’t match existing ones in a case insensitive comparison. But however the user resolves the issue it is up to the user to do it in whatever way makes the most sense for them.
But in a system that claims to solve Zooko’s triangle there has to be some mechanism for resolving these attacks that doesn’t require the user’s interaction. After all, if the user has to resolve the conflict then the system cannot claim to be impersonation proof.
Now there might be a solution here. But I don’t know what it would be. All the solutions I can come up with are based on some external authority who decides which names are ’good’ and which names are ’bad’. This means that the system is no longer distributed. There is some authority, somewhere, who can ’undo’ names. This ’undo’ is needed to prevent impersonation attacks. But now we are back to Zooko’s triangle. If you want human memorable names then they can either be impersonation proof (but centralized) or decentralized but not impersonation proof. Note, btw, that introducing multiple different authorities who can mark ’bad names’ doesn’t solve the problem either. If two users choose two different authorities who make different choices then we no longer have a global namespace, the very problem Zooko’s triangle tries to address.
Some real life examples
Namecoin
One system that claims to solve Zooko’s triangle in practice for Internet Naming is Namecoin. Namecoin certainly suffers from namespace exhaustion issue in that, for example the ID space, is a single global space that appears to be first come/first served. They do have a mandatory renewal process so a registration can be lost if not renewed but that actually seems really scary as it opens up a way for a name transfer to occur without the consent of the owner. But even assuming the mechanism works it doesn’t actually address namespace exhaustion since they still have a relatively small global namespace that all names come from. They do have a DNS based solution but it actually depends on DNS and thus doesn’t solve Zooko’s triangle since DNS is centralized.
They also don’t have anything to say on the malicious naming problem. They do try to restrict names to single case, a-z, 0-9, but this doesn’t completely solve the problem and reducing all the world’s languages to the Latin alphabet seems a bit hamfisted. And no, layering Punycode on top doesn’t solve the problem, it actually just makes it worse since Punycode names are not human readable when encoded.
Keybase
Another approach is Keybase. To be clear, unlike Namecoin, I am not aware of Keybase having ever claimed to solve Zooko’s triangle. I only mention it because it is an interesting example of how Zooko’s triangle shows up in real life.
If I am reading their docs correctly their ’name’ system is a global namespace (no sub-domains) and uses Unicode strings. So they don’t address either the namespace exhaustion or malicious names attacks.
They also are completely centralized. Users login via passwords and changes, like adding and removing keys, are not validated through any kind of externally verifiable signature mechanism. The consequence of this is that it is perfectly possible for Keybase to handle the malicious name attack by removing someone’s ownership of the name but of course then Keybase is just another centralized system.
Conclusion
As near as I can tell Zooko’s triangle is still standing. Systems that claim to solve it don’t seem to have good solutions for the namespace exhaustion attack or the particularly evil malicious name attack. I believe anyone who wants to claim they have solved Zooko’s triangle has to show how they solve these attacks.
Interesting topic. To me it seems clear that a global namespace cannot have user friendly names, because of the name conflicts you mentioned.
Pet names is the obvious solution. The danger you identified is to mistake a suggested name for an actual pet name.
I think software should not be allowed to replace the key with a suggested name without user intervention. Maybe replace the key with a link, which loads as much identifying information about the key holder as needed for the user to know who they are dealing with.
Also “relationships” would help set the level of trust in a new contact.
Relationships are interesting because I bet I could hack relationships in such a way that you would end up transitively accepting a name for someone you didn’t expect. :) It’s hard. But I do think it’s solvable in the sense that once people “get” the idea of Pet Names then it all comes down to UX making it painfully clear when a human readable name is a true pet name and what it’s a suggestion from some place else.