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:
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 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.1 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 tradeoff 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 scroll 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.
I admit I haven’t looked at BitCoin, but won’t the scroll get awfully long pretty fast?
posted by Nikita Borisov
on January 6, 2011 #
yea there has already been some thinking about this.
see this forum thread: http://www.bitcoin.org/smf/index.php?topic=1790.0
and this protocol proposal:
http://privwiki.dreamhosters.com/wiki/Bitcoin_DNS_System_Proposal
posted by n
on January 6, 2011 #
What happens when someone launches a DOS attack, registering billions of likely names?
The social problems of DNS are just as hard as the technical ones, unfortunately.
posted by Noel Grandin
on January 6, 2011 #
Another approach to the same issue: http://www.lshift.net/blog/2007/11/10/squaring-zookos-triangle
posted by Adam Langley
on January 6, 2011 #
Nikita: Perhaps. There are some practical optimizations you can probably make to eliminate the need to ship the whole thing around all the time. I was going to write about them, but I’m not sure it’s actually necessary — people routinely download multi-gigabyte movies on the Internet and the text data here will probably weigh a lot less.
Noel: You pick an N so that this is unlike/infeasible. Right now it only costs $5-10 to register a domain name; you could pick an N where it cost $10 to compute.
Adam: Yeah, I liked the lshift post, but it gets much weaker results on the meaningful prong. I mean, “area-fluid-above-movie-start” isn’t really something you’re going to see in movie trailers anytime soon.
posted by Aaron Swartz
on January 6, 2011 #
Noel writes (via email):
If you pick a really high N, it becomes problematic to create a new name.
If you pick a low N, in a couple of years it becomes possible to launch a DOS.
I didn’t go into this in the piece, because it wasn’t directly relevant, but I have a couple ideas.
You can pick a function N=f(t) where t is the date so that N grows over time, then you only have to worry about getting the growth rate wrong.
You can have the network vote in some way on adopting new values of N.
You can have an algorithm for gradually increasing N if new names get minted “too quickly” — i.e. if you see more than X new lines within Y seconds, increase N by 1.
posted by Aaron Swartz
on January 6, 2011 #
How would such a system handle name expiry?
posted by blake8086
on January 6, 2011 #
I’ve been re-reading the bitcoin paper, and it strikes me that some of the changes in the above description (presumably made as simplifications for explanatory purposes) might kind of matter.
You have each line satisfying hash(scroll up to end of line), rather than bitcoin’s chained-blocks paradigm. It seems like this may really start to matter once the size of the scroll gets large?
I also keep having a niggling fear that there’s some relation between the # of names which can be registered per unit time and the N chosen. Specifically, I worry that with N sufficiently large that domain registration costs a reasonable amount, it will be impossible to find the appropriate nonce for it before the world has moved on and you have to start from a new base scroll.
With bitcoin it’s not supposed to cost anything to publish a transaction, and then everyone works on finding the next block which will contain that tx (and earns a coin for being the first to find one.) But here, while lines in the scroll are analogous to transactions, we want people to bear the cost of registering the name themselves. I don’t know. I feel like I’m missing something.
posted by Emile
on January 7, 2011 #
You have each line satisfying hash(scroll up to end of line), rather than bitcoin’s chained-blocks paradigm. It seems like this may really start to matter once the size of the scroll gets large?
Yeah, I guess that’s an engineering optimization?
I also keep having a niggling fear that there’s some relation between the # of names which can be registered per unit time and the N chosen. Specifically, I worry that with N sufficiently large that domain registration costs a reasonable amount, it will be impossible to find the appropriate nonce for it before the world has moved on and you have to start from a new base scroll.
You have this intuition that when the scroll is advanced you have to “start over from the beginning” in looking for a new nonce, but I don’t think that’s true. For any nonce you try, I think the probability of it being correct is the same no matter what the scroll is. So it should take you the same amount of time to find a working nonce no matter how many times the scroll changes while you’re doing it.
posted by Aaron Swartz
on January 10, 2011 #
You have this intuition that when the scroll is advanced you have to “start over from the beginning” in looking for a new nonce, but I don’t think that’s true. For any nonce you try, I think the probability of it being correct is the same no matter what the scroll is. So it should take you the same amount of time to find a working nonce no matter how many times the scroll changes while you’re doing it.
Ah, you’re right, that was exactly my thinking. Thanks.
posted by Emile
on January 10, 2011 #
“When a new valid line is created it’s sent to everyone in the network and they add it to their scroll.”
Realistically, the bigger problem than that of two people creating a name at the same time is less than that of name propagation taking longer than name creation. That is, nodes that are disconnected for a bit too long would not receive a new name before the rest of the network has already moved on to the next.
Effectively you’re fragmenting the network all over the place then. Nodes with a scroll that have the same age (where age is # lines in the scroll) would find it easy to agree on a new name, but they might be several iterations behind the latest version of the scroll.
As to the concerns that some people raise about the length of the scroll (which becomes relevant here, as one solution to the above would be to force nodes to start with a blank scroll as they join):
According to http://en.wikipedia.org/wiki/Domain_name we’ve now reached some 196 million domain names. A line in your scroll would be some 20 or so characters for the domain name (could easily grow larger), let’s make it compact and say no more than 128 bits/16 bytes for an IPv6 address, and oh, some 512 bits / 64 bytes for a hash. Altogether at least 100 bytes per line, times 196 mio = 18 GiB.
Yeah, I don’t see anyone transmitting that every time they join the network.
“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.”
You’re describing a requirement to choose a plaintext such that a particular hash is created. While that’s possible, hash algorithms are designed to make that very, very hard, or you’d have an easy time finding collisions. If you can create collisions, then you have an easy time subverting the name system (or any type of crypto out there).
“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.”
In the practice of P2P networking, it is. How do you verify that they are? Let the user do that?
Also
“Publishing a false scroll is equivalent to fragmenting the namespace and starting a separate network.”
Must be prevented, or the whole thing isn’t a reliable global naming thingamajig anymore.
“And we’re actually slightly safer than that, since the majority needs a fair amount of CPU to stay plausible.”
Rent a few Amazon VMs, they’re cheap these days. Or make 4chan users angry enough to help you.
posted by unwesen
on January 12, 2011 #
I think I missed something, but I can’t find the answer in the article; What is the key? It can’t be an IP address, because I might be paying a third party to host my service, and that third party can be coerced.
I assume that I missed something, and that keys would be digital signatures, and something like the current DNS system would be used to resolve signatures into ip addresses.
I still have doubts about the elegance of the solution offered in the article; here is my alternative:
Instead of trying to invent a system in which name conflicts are impossible, allow conflicts, but use a web-of-trust system to rank human-readable names, which resolve to globally unique signatures.
In essence, the human name is like a “nickname” which is used within my peer group, while the signature is the “real name” which can be used to reference a person outside of my peer group.
Because two people in remote peer networks could use the same nickname to refer to different people, URLs would have to be resolved by the server or operating system as soon as possible, so that the name becomes globally stable.
To address this problem, instead of using only the human readable part, use some number of characters from the signature in the URL: “.” It could be that the signature is optional, otherwise it could be convention that 3 characters minimum is standard, for example. The more characters of the signature are included, the more secure the URL is - up to a maximum of the entire signature.
The human readable part is used to search the peer-network for candidate signatures, which can optionally be ranked by some trust-metric. (The DNS system could discard extremely untrusted names, preventing spamming.) Then, the list of candidate signatures is narrowed by however many digits of the real signature is provided. If at this point there are any conflicts, the user could be notified with an icon, but have the most-trusted option be the default.
The only problem is, I have used the concept of “trust” as a black-box ranking system.
posted by Phillip
on January 12, 2011 #
The blog software mangled my URL scheme description.
In reference to my above post; domain names could be of the form: “$HUMAN_READABLE.$SIGNATURE” where the signature can be truncated.
posted by Phillip
on January 12, 2011 #
There is no decentralized way to manage a global ordered list like this. It’s a basic problem for P2P networks. You’ll inevitably get conflicts as two nodes each publish their own amended version of the list, which then cause conflicts as they propagate gradually across the net. This is only feasible on a theoretical network with zero lag and perfect connectivity, not in the real world.
The ways around the problem are either
(a) Have a central synchronization mechanism to make sure entries get added in known order (which violates decentralization); or
(b) Resolve conflicts by merging divergent lists, which is made impossible by the hashing scheme (and would in any case violate security, because you’re allowing arbitrary parties to edit the list.)
And then there are the more general problems associated with letting anyone reserve any name on a first come first served basis. You just know you’re going to get spammers using their botnets to spew out entries that point every common name (dictionary words, familiar hostnames, common human names…) at their sites, making the “readable” feature useless in practice.
posted by Jens Alfke
on January 12, 2011 #
Jens, have you looked at bitcoin yet? Do you believe that they are doomed to fail if/when the network size/transaction load grows large enough? I haven’t looked closely yet at how they structure the network of nodes.
As to the first come first served — isn’t that exactly how the domain system works right now? If you are willing to steal computer time to “pay” for name registration under this proposal then you can just as easily steal money to pay for domains under the current DNS system.
posted by Emile
on January 12, 2011 #
unwesen, re:hash collisions — you misread the proposal. The idea is to find a hash where the first N bits are zero. Choose N such that this takes an “appropriate” amount of work. Your objection assumes that N == # of bits in the hash.
posted by Emile
on January 12, 2011 #
@Emile: I did not misread the proposal, but after re-reading what I’d written, I understand that it must seem that way. I had skipped a few steps in my thought process in my description.
Yes, finding partial collisions for plain hash functions is feasible.
No, using plaintext + hash(plaintext) is not enough to verify a scroll’s validity, that’s why HMAC etc. exist (to protect against collisions, partial or otherwise).
So in order for nodes to verify the scroll, you’d need to find an HMAC with N leading zeros, which becomes prohibitive again.
The reason you must use an HMAC and not a plain hash is that, as Philip put it, avoiding conflicts “(…) is only feasible on a theoretical network with zero lag and perfect connectivity, not in the real world.”
Ergo, you must allow for nodes having to re-fetch and validate entire scrolls.
(Also, at that point you run into the problem of having too much data.)
Sorry for taking the shortcut through my thoughts previously, hope the above makes my objection clearer.
posted by unwesen
on January 12, 2011 #
I find it much less clear. It doesn’t seem like you understand what HMAC is.
As for other comments, falling behind on the scroll should be modeled as leaving the network and rejoining. If two valid lines are published within the amount of time it takes a line to propagate, the dispute will be settled by the next published line.
posted by Aaron Swartz
on January 12, 2011 #
@unwesen: I think I see the confusion? The hashes aren’t being used to construct a MAC, let alone an HMAC. They pure proofs of work. If each line of the scroll satisfies the stated condition, then you know roughly how much work was required to generate that entire scroll.
The concerns that motivate HMAC as opposed to using H(key || messages) or H(message || key) to authenticate a message are not really relevant to the proposal. We aren’t trying to authenticate the scroll as coming from anyone in particular. (Proving that they have a particular secret key, and thus must have generated the MAC in question.)
Here, the “key” in each line of the scroll is just some arbitrary bit of (cleartext) data that the individual registering the name wishes to associate with it. It is the value part of the key-value store that the proposal defines.
posted by Emile
on January 12, 2011 #
probably best change the word ‘nonce’ as it is slang for a paedo in the UK
posted by jon
on January 12, 2011 #
“Now stealing an old name is impossible, since machines in the network only add new names, they don’t accept replacements for old ones.”
Assuming for a moment that the key is the IP associated with the name, it is important that these be allowed to both expire and be replaced. If you open this door, you could use the web of trust notion to determine when a proposed replacement is valid. I’m not clear on how easy it would be to tune the notion of a majority to find a balance between proliferation of data through the network and security.
If, however, the key is something other than the IP, there still needs to be a system underneath that translates the key to an IP address, and this is open to the triangle from Zooko’s paper.
posted by dominic
on January 13, 2011 #
@Emile:
If hashes are pure proofs of work, then the whole system is very attackable, as CPU power is really cheap these days.
FWIW, there’s a reason most real-world P2P systems are hybrid, and at least for the commercial ones, mechanisms to avoid bad data flooding the network is amongst the most notable.
posted by unwesen
on January 13, 2011 #
@jon: Like it or not, “nonce” is the standard terminology (http://en.wikipedia.org/wiki/Cryptographic_nonce).
posted by Tom Stuart
on January 14, 2011 #
Dominic: Check out the FAQ. There’s no reason going from the key to IP would implicate any Zooko’s triangle issues.
posted by Aaron Swartz
on January 14, 2011 #
Just to follow up on the “CPU power is really cheap”, see the current Sony/PSN debacle. People with enough motivation apparently are happy to rent tons of Amazon VMs. Previously I was only assuming they would, now I know.
posted by unwesen
on May 20, 2011 #
You can also send comments by email.
Comments
I admit I haven’t looked at BitCoin, but won’t the scroll get awfully long pretty fast?
posted by Nikita Borisov on January 6, 2011 #
yea there has already been some thinking about this.
see this forum thread: http://www.bitcoin.org/smf/index.php?topic=1790.0
and this protocol proposal: http://privwiki.dreamhosters.com/wiki/Bitcoin_DNS_System_Proposal
posted by n on January 6, 2011 #
What happens when someone launches a DOS attack, registering billions of likely names? The social problems of DNS are just as hard as the technical ones, unfortunately.
posted by Noel Grandin on January 6, 2011 #
Another approach to the same issue: http://www.lshift.net/blog/2007/11/10/squaring-zookos-triangle
posted by Adam Langley on January 6, 2011 #
Nikita: Perhaps. There are some practical optimizations you can probably make to eliminate the need to ship the whole thing around all the time. I was going to write about them, but I’m not sure it’s actually necessary — people routinely download multi-gigabyte movies on the Internet and the text data here will probably weigh a lot less.
Noel: You pick an N so that this is unlike/infeasible. Right now it only costs $5-10 to register a domain name; you could pick an N where it cost $10 to compute.
Adam: Yeah, I liked the lshift post, but it gets much weaker results on the meaningful prong. I mean, “area-fluid-above-movie-start” isn’t really something you’re going to see in movie trailers anytime soon.
posted by Aaron Swartz on January 6, 2011 #
Noel writes (via email):
I didn’t go into this in the piece, because it wasn’t directly relevant, but I have a couple ideas.
You can pick a function N=f(t) where t is the date so that N grows over time, then you only have to worry about getting the growth rate wrong.
You can have the network vote in some way on adopting new values of N.
You can have an algorithm for gradually increasing N if new names get minted “too quickly” — i.e. if you see more than X new lines within Y seconds, increase N by 1.
posted by Aaron Swartz on January 6, 2011 #
How would such a system handle name expiry?
posted by blake8086 on January 6, 2011 #
I’ve been re-reading the bitcoin paper, and it strikes me that some of the changes in the above description (presumably made as simplifications for explanatory purposes) might kind of matter.
You have each line satisfying hash(scroll up to end of line), rather than bitcoin’s chained-blocks paradigm. It seems like this may really start to matter once the size of the scroll gets large?
I also keep having a niggling fear that there’s some relation between the # of names which can be registered per unit time and the N chosen. Specifically, I worry that with N sufficiently large that domain registration costs a reasonable amount, it will be impossible to find the appropriate nonce for it before the world has moved on and you have to start from a new base scroll.
With bitcoin it’s not supposed to cost anything to publish a transaction, and then everyone works on finding the next block which will contain that tx (and earns a coin for being the first to find one.) But here, while lines in the scroll are analogous to transactions, we want people to bear the cost of registering the name themselves. I don’t know. I feel like I’m missing something.
posted by Emile on January 7, 2011 #
Yeah, I guess that’s an engineering optimization?
You have this intuition that when the scroll is advanced you have to “start over from the beginning” in looking for a new nonce, but I don’t think that’s true. For any nonce you try, I think the probability of it being correct is the same no matter what the scroll is. So it should take you the same amount of time to find a working nonce no matter how many times the scroll changes while you’re doing it.
posted by Aaron Swartz on January 10, 2011 #
Ah, you’re right, that was exactly my thinking. Thanks.
posted by Emile on January 10, 2011 #
“When a new valid line is created it’s sent to everyone in the network and they add it to their scroll.” Realistically, the bigger problem than that of two people creating a name at the same time is less than that of name propagation taking longer than name creation. That is, nodes that are disconnected for a bit too long would not receive a new name before the rest of the network has already moved on to the next.
Effectively you’re fragmenting the network all over the place then. Nodes with a scroll that have the same age (where age is # lines in the scroll) would find it easy to agree on a new name, but they might be several iterations behind the latest version of the scroll.
As to the concerns that some people raise about the length of the scroll (which becomes relevant here, as one solution to the above would be to force nodes to start with a blank scroll as they join):
According to http://en.wikipedia.org/wiki/Domain_name we’ve now reached some 196 million domain names. A line in your scroll would be some 20 or so characters for the domain name (could easily grow larger), let’s make it compact and say no more than 128 bits/16 bytes for an IPv6 address, and oh, some 512 bits / 64 bytes for a hash. Altogether at least 100 bytes per line, times 196 mio = 18 GiB.
Yeah, I don’t see anyone transmitting that every time they join the network.
“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.” You’re describing a requirement to choose a plaintext such that a particular hash is created. While that’s possible, hash algorithms are designed to make that very, very hard, or you’d have an easy time finding collisions. If you can create collisions, then you have an easy time subverting the name system (or any type of crypto out there).
“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.”
In the practice of P2P networking, it is. How do you verify that they are? Let the user do that?
Also
“Publishing a false scroll is equivalent to fragmenting the namespace and starting a separate network.”
Must be prevented, or the whole thing isn’t a reliable global naming thingamajig anymore.
“And we’re actually slightly safer than that, since the majority needs a fair amount of CPU to stay plausible.”
Rent a few Amazon VMs, they’re cheap these days. Or make 4chan users angry enough to help you.
posted by unwesen on January 12, 2011 #
I think I missed something, but I can’t find the answer in the article; What is the key? It can’t be an IP address, because I might be paying a third party to host my service, and that third party can be coerced.
I assume that I missed something, and that keys would be digital signatures, and something like the current DNS system would be used to resolve signatures into ip addresses.
I still have doubts about the elegance of the solution offered in the article; here is my alternative:
Instead of trying to invent a system in which name conflicts are impossible, allow conflicts, but use a web-of-trust system to rank human-readable names, which resolve to globally unique signatures.
In essence, the human name is like a “nickname” which is used within my peer group, while the signature is the “real name” which can be used to reference a person outside of my peer group.
Because two people in remote peer networks could use the same nickname to refer to different people, URLs would have to be resolved by the server or operating system as soon as possible, so that the name becomes globally stable.
To address this problem, instead of using only the human readable part, use some number of characters from the signature in the URL: “.” It could be that the signature is optional, otherwise it could be convention that 3 characters minimum is standard, for example. The more characters of the signature are included, the more secure the URL is - up to a maximum of the entire signature.
The human readable part is used to search the peer-network for candidate signatures, which can optionally be ranked by some trust-metric. (The DNS system could discard extremely untrusted names, preventing spamming.) Then, the list of candidate signatures is narrowed by however many digits of the real signature is provided. If at this point there are any conflicts, the user could be notified with an icon, but have the most-trusted option be the default.
The only problem is, I have used the concept of “trust” as a black-box ranking system.
posted by Phillip on January 12, 2011 #
The blog software mangled my URL scheme description.
In reference to my above post; domain names could be of the form: “$HUMAN_READABLE.$SIGNATURE” where the signature can be truncated.
posted by Phillip on January 12, 2011 #
There is no decentralized way to manage a global ordered list like this. It’s a basic problem for P2P networks. You’ll inevitably get conflicts as two nodes each publish their own amended version of the list, which then cause conflicts as they propagate gradually across the net. This is only feasible on a theoretical network with zero lag and perfect connectivity, not in the real world.
The ways around the problem are either (a) Have a central synchronization mechanism to make sure entries get added in known order (which violates decentralization); or (b) Resolve conflicts by merging divergent lists, which is made impossible by the hashing scheme (and would in any case violate security, because you’re allowing arbitrary parties to edit the list.)
And then there are the more general problems associated with letting anyone reserve any name on a first come first served basis. You just know you’re going to get spammers using their botnets to spew out entries that point every common name (dictionary words, familiar hostnames, common human names…) at their sites, making the “readable” feature useless in practice.
posted by Jens Alfke on January 12, 2011 #
Jens, have you looked at bitcoin yet? Do you believe that they are doomed to fail if/when the network size/transaction load grows large enough? I haven’t looked closely yet at how they structure the network of nodes.
As to the first come first served — isn’t that exactly how the domain system works right now? If you are willing to steal computer time to “pay” for name registration under this proposal then you can just as easily steal money to pay for domains under the current DNS system.
posted by Emile on January 12, 2011 #
unwesen, re:hash collisions — you misread the proposal. The idea is to find a hash where the first N bits are zero. Choose N such that this takes an “appropriate” amount of work. Your objection assumes that N == # of bits in the hash.
posted by Emile on January 12, 2011 #
@Emile: I did not misread the proposal, but after re-reading what I’d written, I understand that it must seem that way. I had skipped a few steps in my thought process in my description.
Yes, finding partial collisions for plain hash functions is feasible.
No, using plaintext + hash(plaintext) is not enough to verify a scroll’s validity, that’s why HMAC etc. exist (to protect against collisions, partial or otherwise).
So in order for nodes to verify the scroll, you’d need to find an HMAC with N leading zeros, which becomes prohibitive again.
The reason you must use an HMAC and not a plain hash is that, as Philip put it, avoiding conflicts “(…) is only feasible on a theoretical network with zero lag and perfect connectivity, not in the real world.”
Ergo, you must allow for nodes having to re-fetch and validate entire scrolls.
(Also, at that point you run into the problem of having too much data.)
Sorry for taking the shortcut through my thoughts previously, hope the above makes my objection clearer.
posted by unwesen on January 12, 2011 #
I find it much less clear. It doesn’t seem like you understand what HMAC is.
As for other comments, falling behind on the scroll should be modeled as leaving the network and rejoining. If two valid lines are published within the amount of time it takes a line to propagate, the dispute will be settled by the next published line.
posted by Aaron Swartz on January 12, 2011 #
@unwesen: I think I see the confusion? The hashes aren’t being used to construct a MAC, let alone an HMAC. They pure proofs of work. If each line of the scroll satisfies the stated condition, then you know roughly how much work was required to generate that entire scroll.
The concerns that motivate HMAC as opposed to using H(key || messages) or H(message || key) to authenticate a message are not really relevant to the proposal. We aren’t trying to authenticate the scroll as coming from anyone in particular. (Proving that they have a particular secret key, and thus must have generated the MAC in question.)
Here, the “key” in each line of the scroll is just some arbitrary bit of (cleartext) data that the individual registering the name wishes to associate with it. It is the value part of the key-value store that the proposal defines.
posted by Emile on January 12, 2011 #
probably best change the word ‘nonce’ as it is slang for a paedo in the UK
posted by jon on January 12, 2011 #
“Now stealing an old name is impossible, since machines in the network only add new names, they don’t accept replacements for old ones.”
Assuming for a moment that the key is the IP associated with the name, it is important that these be allowed to both expire and be replaced. If you open this door, you could use the web of trust notion to determine when a proposed replacement is valid. I’m not clear on how easy it would be to tune the notion of a majority to find a balance between proliferation of data through the network and security.
If, however, the key is something other than the IP, there still needs to be a system underneath that translates the key to an IP address, and this is open to the triangle from Zooko’s paper.
posted by dominic on January 13, 2011 #
@Emile:
If hashes are pure proofs of work, then the whole system is very attackable, as CPU power is really cheap these days.
FWIW, there’s a reason most real-world P2P systems are hybrid, and at least for the commercial ones, mechanisms to avoid bad data flooding the network is amongst the most notable.
posted by unwesen on January 13, 2011 #
@jon: Like it or not, “nonce” is the standard terminology (http://en.wikipedia.org/wiki/Cryptographic_nonce).
posted by Tom Stuart on January 14, 2011 #
Dominic: Check out the FAQ. There’s no reason going from the key to IP would implicate any Zooko’s triangle issues.
posted by Aaron Swartz on January 14, 2011 #
Just to follow up on the “CPU power is really cheap”, see the current Sony/PSN debacle. People with enough motivation apparently are happy to rent tons of Amazon VMs. Previously I was only assuming they would, now I know.
posted by unwesen on May 20, 2011 #
You can also send comments by email.