The Boy Who Could Change the World (12 page)

Postel's Law Has No Exceptions

http://www.aaronsw.com/weblog/001025

August 18, 2003

Age 16

As Mark Pilgrim is fond of saying, “There are no exceptions to Postel's Law.” (Postel's Law is generally quoted as “be liberal in what you accept and conservative in what you put out” or something to that effect.) The message of the law is that interoperability is the primary concern, and that programs should accept things, even things that are against the spec, if necessary to achieve interoperability.

HTML, as you may know, is a mess. It's contorted in a hundred different ways with tons of bugs and their work-arounds encrusted into the web, and browsers are expected to make sense of all of it. The XML people saw this and said, “We have to fix this.” Their solution was to break Postel's Law.

With XML you are supposed to die and never look back if the document you come across violates the spec. The idea was that if everything died on invalid feeds, no one would ever write them. This is wrong for three reasons:

1. Even with the rule, there will be invalid documents. Someone will write some code, test it, see that it works and move on. One day the code will be given data that trips one of XML's exceptions (AT&T is a common example—XML requires it be written AT&T) and an invalid document will be created.

2. XML apps compete for users. Users want to read these documents, even if they're broken. Users will switch to apps that read these documents and the rule will be useless, since folks will likely test with those apps. The only way we can keep
the rule in effect is by getting
everyone
who writes an app to act against the wishes of their users, which seems like a bad idea.

3. Essentially the same effect can be achieved by having a validation display (like iCab or Straw's smiley face that frowns on invalid documents) and an easy-to-use validator.

This is not to say that all apps should have to process invalid documents, or that they should work hard to guess what the author meant, or that we should encourage or tolerate invalid documents. We should still try to get rid of invalid documents, but taking things out on the users is the wrong way to do it.

The creators of XML were wrong. Postel's Law has no exceptions.

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

http://www.aaronsw.com/weblog/squarezooko

January 6, 2011

Age 24

When using computers, we like to refer to things with names. For example, this website is known as “
www.aaronsw.com
.” You can type that into your browser and read these words. There are three big properties we might want from such names:

           
•
  
secure
: that when you type the name in you actually get my website and not the website of an imposter

           
•
  
decentralized
: that no central authority controls all the names

           
•
  
human-readable
: that the name is something you can actually remember instead of some long string of randomness

In a classic paper, my friend Zooko argued that you can get at most two of these properties at any one time.

Recently, DNS legend Dan Kaminsky used this to argue that since electronic cash was pretty much the same as naming, Zooko's triangle applied to it as well. He used this to argue that
Bitcoin
, the secure, decentralized, human-meaningful electronic cash system was impossible. I have my problems with Bitcoin, but it's manifestly not impossible, so I just assumed Kaminsky had gone wrong somewhere.

But tonight I realized that you can indeed use Bitcoin to square Zooko's triangle. Here's how it works:

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.

OK, let's pause there for a second. How do you steal names in such a system? First, you need to calculate a new nonce for the line you want to steal and every subsequent line. Second, you need to get your replacement scroll to the user. The first is difficult, but perhaps not impossible, depending on how many lines ago the name you want to steal is. It requires having some large multiple of the rest of the network's combined CPU power. This seems like a fairly strong constraint to me, but apparently not to Dan. Luckily, we're saved by the second question.

Let there be a group of machines called the network. Each remembers the last scroll it trusted. When a new valid line is created it's sent to everyone in the network and they add it to their scroll.
^*
*
Now stealing an old name is impossible, since machines in the network only add new names, they don't accept replacements for old ones.

That's fine for machines already in the network, but how do you join? Well, as a physical law, to join a network you need the identity of at least one machine already in the network. Now when you join, that machine can give you a fabricated scroll where they've stolen all the names. I don't think there's any way to avoid this—if you don't know anyone willing to tell you the correct answer, you can't will the correct answer out of thin air. Even a centralized system depends on knowing at least one honest root.

You can ameliorate this problem by knowing several nodes when you connect and asking each of them for their scroll. It seems like the best theoretically possible case would be requiring only one node to
be honest. That would correspond to trusting whichever node had the longest scroll. But this would leave you vulnerable to an attacker who (a) has enough CPU power to fabricate the longest scroll, and (b) can co-opt at least one of your initial nodes. The alternative is to trust only scrolls you receive from a majority of your list of nodes. This leaves you vulnerable to an attacker who can co-opt a majority of your initial nodes. Which trade-off you pick presumably depends on how much you trust your initial nodes.

Publishing a false scroll is equivalent to fragmenting the namespace and starting a separate network. (We can enforce this by requiring nodes to sign each latest scroll and publish their signature to be considered members in good standing of the network. Any node that attempts to sign two contradictory scrolls is obviously duplicitous and can be discounted.) So another way of describing scenario (b) is to say that to join a network, you need a list of nodes where at least a majority are actually nodes in the network. This doesn't seem like an overly strenuous requirement.

And we're actually slightly safer than that, since the majority needs a fair amount of CPU to stay plausible. If we assume that you hear new names from some out-of-band source, for them to work on the attacker's network the attacker must have enough CPU to generate lines for each name you might use. Otherwise you realize that the names you type in on your computer are returning 404s while they work on other people's computers, and begin to realize you've been had by an attacker.

So there you have it. The names are secure: they're identifiable by a key of arbitrary length and cannot be stolen. They're human-meaningful: the name can be whatever string you like. And they're decentralized: no centralized authority determines who gets what name and yet they're available to everyone in the network.

Zooko's triangle has been squared.

Release Late, Release Rarely

http://www.aaronsw.com/weblog/rlrr

July 5, 2006

Age 19

When you look at something you're working on, no matter what it is, you can't help but see past the actual thing to the ideas that inspired it, your plans for extending it, the emotions you've tied to it. But when others look at it, all they see is a piece of junk.

You only get one chance to make a first impression; why have it be “junk”? Once that's associated with your name or project, it's tough to scrape off. Even people who didn't see it themselves may have heard about it secondhand. And once they hear about it, they're not likely to see for themselves. Life's too short to waste it on junk.

But when you release late, after everything has been carefully polished, you can share something of genuine quality. Apple, for example, sometimes releases stupid stuff, but it always looks good. Even when they flub, people give them the benefit of the doubt. “Well, it looks great but I don't really like it” is a lot better then “It's a piece of junk.”

Still, you can do better. Releasing means showing it to the world. There's nothing wrong with showing it to friends or experts or even random people in a coffee shop. The friends will give you the emotional support you would have gotten from actual users, without the stress. The experts will point out most of the errors the world would have found, without the insults. And random people will not only give you most of the complaints the public would, they'll also tell you why the public gave up even before bothering to complain.

This is why “release early, release often” works in open source: you're releasing to a community of insiders. Programmers know
what it's like to write programs and they don't mind using things that are unpolished. They can see what you're going to do next and maybe help you get there.

The public isn't like that. Don't treat them like they are.