Zooko Wilcox O’Hearn pointed something out a few years ago which everybody who studies cryptography in particular or network applications in general has to eventually learn and come to grips with. This arises, in particular, because we build systems where there must be a mapping of entities or objects to unique addresses or keys. And any such mapping is a global name space.

Pick any one of the three bars…. and there’ll be one corner you can’t reach.

A global name space can be secure. It can be decentralized. It can be mnemonic. Or it can be any two of those three things. But it can’t be all three of those things.

If a namespace is secure, then when you get a name associated with a value, then you can verify by yourself whether the two actually belong together, so nobody can give you their own key with someone else’s name or their own name with someone else’s key, and nobody can take over anybody else’s name and key. In a centralized system you can verify it for yourself because you have an authenticated message from an authority that tells you whether it’s a true association. In a decentralized system this can only result from something like the key being a hash of the name.

If a namespace is mnemonic, then the names you use can be meaningful in some human sense; that is, a human being gets to pick what the name is and somebody named Joe who sells Doughnuts can pick the name “Joe’s Doughnuts” to enter into the global system and use.

It is hard for any name space to be both mnemonic and secure, because to the extent that names are meaningful at the human level people will try to fool others into thinking that they mean things they don’t. For example somebody will take the name “Joe’s Dοughnuts” (with a Greek lowercase omicron in the word ‘Doughnuts’) and try to send out bills for food that “Joe’s Doughnuts” actually delivered. They’re not – quite – presenting someone else’s name with their own key, but they are hoping that, because the names are so similar, the people who get the bills won’t notice.

If a namespace is decentralized, then there is no participant who is “special” in that they get to break some or all of the rules everybody else has to follow. For example, early in the web’s history, the World Wrestling Federation and the World Wildlife Fund had a fight over which of them would get to use the domain “wwf.org.” If DNS had been both secure and decentralized, then there would be nobody able to break the rules to take the domain name away from one and give it to the other, so there’d have been no point in fighting. However, DNS is not secure, because you can’t verify on your own whether a name goes with a particular IP address – you have to rely unauthenticated messages from DNS servers, which means DNS spoofing is possible. And DNS isn’t decentralized, because those servers promulgate information that somebody somewhere, who could potentially be coerced or bribed or blackmailed, has the authority to edit.

So let’s look at the combinations.

If your namespace is mnemonic and decentralized, it means anybody can associate any name with any key at any time. — so it can’t be secure. Freenet’s namespace works this way, and is spoofed hundreds of times a day by many many people. In practice if you want reliable connections on Freenet you use CHK’s instead of names.

If your namespace is mnemonic and secure, then someone has to allow or disallow the association of a key with a name and make the list of associations available to all participants. — so it can’t be decentralized, and someone in the wrong place getting coerced, bribed, or blackmailed can break your security. DNSSEC is a protocol that provides mnemonic and secure DNS, but isn’t decentralized.

If your namespace is decentralized and secure, then the names and keys have a mathematical relationship that prevents keys from belonging to a different name or names from belonging to a different key — so it can’t be mnemonic. Freenet’s CHK’s work this way. Bittorrent works internally this way by using hashes as identifiers for files. But nobody can recite a hash nor will they search for it, so in practice people identify content using mnemonic names and meta tags, and other people just plain lie about what mnemonic names and meta tags to associate with given file content and hashes.

Zooko’s Triangle is a law like the Halting Problem. There exist many programs which will definitely halt and you can prove that about them. There exist many programs which definitely won’t and you can prove that about them. But there is not, and never will be, a general and perfectly reliable method for detecting in finite time which programs will and will not halt.

Similarly, It is possible to achieve some degree of all three properties in the same system using some kind of general-agreement protocol. Indeed, the Wikipedia article on this topic claims that Zooko’s Triangle has been solved. But it hasn’t. There is no absolute solution to Zooko’s triangle, in the same way that there is no general and perfectly reliable method for detecting halting programs. There are only particular applications within which some acceptable compromise of these properties can be found.

The most significant work on the topic is due to Nick Szabo, who wrote about secure property titles with owner authority and showed that Zooko’s triangle is solvable within the limits of Byzantine Fault Tolerance. Byzantine Fault Tolerance means the limits within which a protocol for Byzantine Agreement will not fail.

There are, at the moment, two primary approaches for Byzantine Agreement, each with a different set of limitations for Byzantine Fault Tolerance.

The first approach is a small family of related “classical” protocols that use signed messages and a set of public keys to identify protocol participants, which can in general withstand active attempts to subvert the protocol by up to 2/3 of the participants. But they require that all participants are known in advance, that the namespace of participants to public keys does not change during the protocol, and communications overhead that grows polynomially with the number of participants, so they do not scale to large problems.

The second approach is the Nakamoto protocol which was introduced in the application Bitcoin, which uses proof-of-work to secure additions to an agreed-on history. The Nakamoto protocol works assuming that the majority of the proof-of-work is contributed by honest participants, which is a much weaker guarantee and measures processing power which may be wildly uneven in its distribution, rather than numbers of participants which is usually what we actually care about. But it has several advantages; it scales better than the public-key based protocols, allows participants to enter and leave the protocol at any time, and doesn’t require the participants to be known to each other or to any centralized authority. .onion URL’s are an approximation to solving Zooko’s triangle, secured using the Nakamoto protocol.

So to sum things up, Zooko said you can’t have all three of these properties in absolute terms, and Szabo said that may be true but you can have them as long as you stay within the boundaries of Byzantine fault tolerance.

And that in turn brings up a point; A public name space IS a form of Byzantine Agreement. Failure means the same thing in either case; that something you’re trying to agree on looks different to one participant than it looks to another.