HOWTO make a secure, decentralized, human-readable name system

Aaron Swartz has posted a clever proposal for locating things on the Internet (such as web-pages), without having to resort to a centralized authority, while still making the names we give to objects readable by human beings (that is, without assigning them long strings of random crypto-gibberish). This is in answer to Zooko's widely cited paper arguing that Internet names can only have two out of these three properties: secure, decentralized and human readable.

This stuff is more important than ever, especially now that governments are asserting the right to confiscate domain names like wikileaks.org. A decentralized system for naming and locating stuff would be much harder to censor.

Let there be a document called the scroll. The scroll consists of a series of lines and each line consists of a tuple (name, key, nonce) such that the first N bits of the hash of the scroll from the beginning to the end of a line are all zero. As a result, to add a line to the scroll, you need to do enough computation to discover an appropriate nonce that causes the bits of the hash to be zero.

To look up a name, you ask everyone you know for the scroll, trust whichever scroll is the longest, and then start from the beginning and take the key for the first line with the name you're looking up. To publish a name, you find an appropriate nonce and then send the new line to everyone you know.

Be sure to RTFA before commenting; the solution proposed here is quite elegant.

Squaring the Triangle: Secure, Decentralized, Human-Readable Names