Let me start by saying I very much appreciate the work that went into this essay. If I count correctly, it has three separate critiques of my argument. Unfortunately, all three of them seem based on misunderstanding. Hopefully I can clarify.

Let me start by explaining that what I wrote is not intended to be a spec for implementers, but merely an existence proof. I think of it as akin to Merkle's signature scheme -- no one uses it today, but it proves public key cryptography is possible. I don't expect a system like the one I outline to actually be used in production; I merely want to prove that Zooko's Triangle isn't a binding constraint.

As a result, there are several implausible (or at least annoying) assumptions. One, as Dan notes, is that we assume keys don't change. Dan seems to be willing to ignore this, if I understand him correctly.

Now to the first objection. Dan asks about the case where two people calculate a valid nonce for the next line of the scroll within the amount of time it takes a line to propagate through the network. The first thing to note is that this should be quite rare. If N is properly calibrated, it should take a large amount of time to find a valid nonce, an amount of time that dwarfs worst-case latency on the Internet.

But still, it could happen. Which is why I explained how to deal with it; unfortunately Dan doesn't seem to have understood my explanation. (To be fair, it was a brief aside in a response to a comment on the post.) Let me elaborate:

Let M be an upper bound on the propagation delay for the network. If you receive two valid lines within M seconds of each other, store both valid lines but don't add either to your trusted scroll. Eventually you will receive another line. But the nonce in this line will only work with one of the two possible lines. Whichever line it works with is the one to believe. The dispute is thus resolved: add the line it works with and then the new line to your scroll.

On to the second objection. Dan seems obsessed with Sybil attacks. I can understand why -- Sybil attacks are very cool and very powerful -- but, sadly, they are totally irrelevant to my proposal since my proposal contains no notion of identity.

Can a Sybil attack affect joining the network? Sybil attacks would only be relevant if we were choosing our list of introductory nodes from the list of total nodes. But this is absurd and borders on impossibility. Think about how someone actually joins a network. Presumably they download a piece of specialized software. The software contains a list of starting nodes in it. That list is not vulnerable to a Sybil attack. Or maybe they get the software from a friend and the friend includes the address of his own node. Again: not vulnerable to a Sybil attack. The point is that to join the system you need to start with some information from outside the system. But since you are still outside the system, Sybil attacks against the system are irrelevant.

Can a Sybil attack affect inserts? No. An insert is done by proof of work. It doesn't matter who finds it; there is no notion of identity attached to the nonce.

Can a Sybil attack affect propagation? Well, it depends on your propagation system. As one of my simplifications, I didn't really discuss an optimized propagation structure -- I assumed that each node was connected to every other node. Now surely one can replace this with a propagation structure that's vulnerable to a Sybil attack, but I don't see why you would and Dan doesn't provide any reasons.

Next Dan does make a good suggestion -- although he incorrectly dismisses it. It would be great to use non-parallelizalble hashcash. I don't know enough about hash design to design one myself, but I'm not convinced it's impossible. You can approach one by changing the assignment from "find x such that H(x) starts with N zeroes" to "find x[1]…x[k] such that H(x[1]), H(x[1] || x[2]), H(x[1] || … || x[3]), … H(x[1] || … || x[k]) all start with N zeroes" and you can twiddle N and k to trade off between verification speed and parallelizability. (The double bars mean string concatenation here.) Also, I believe there are many hash functions where you almost necessarily calculate H(A) as part of calculating H(A || B). (For example, I believe SHA1 has this property.) If that's the case, then there is very little cost in verification speed.

Dan then seems to suffer from an elementary misreading. I say to attack it "you need to calculate a new nonce for the line you want to steal and every subsequent line"; Dan says this isn't true, and then goes on to say exactly what I said: "names after [the one you want] need to be cracked by the attacker". I'm not sure what happened here.

Dan concludes by arguing "the first time a name/key peer [sic] is seen, it is retrieved insecurely" thus reducing my security to that of SSH's known_hosts. But since his attacks above failed, this isn't actually true. The first time a name/key pair is seen, it's retrieved securely. It's then stored and thus can be retrieved securely every time thereafter.

I hope Dan will correct me if I'm missing something, but as best as I can tell nothing remains of his critique.

changed January 14, 2011