Show Posts
After some digging I've found perhaps the only opinion on this paper for now, and it's from Bram Cohen himself: https://www.reddit.com/r/crypto/comments/3yhwwv/hash_tube_signature_scheme/cye6k29
Here's his take in full:
Quote
I think I know where he's going with this. There are three things going on here: A claim to being the original satoshi, a new-ish primitive and a method of using it. For the sake of clarity, I'll address these in reverse order.
What the author appears to want is a signature scheme which allows any other party to sign arbitrary values if it's used more than once. This provides some disincentive to double-spends, because it turns attempts at double-spends into things which can get stolen by miners. That doesn't block everything, because miners have to be co-consipirators in some double-spending schemes anyway, but it is something. It can also cause problems for adjusting fees with replace by fee, and even worse for transactions which you give up on because the fees are too high, thus rendering the original utxo completely unspendable.
This intention is speculative because of how the paper is truncated though. What I can comment on a bit better is the new-ish primitive. I believe that for signatures the public key should be the bottom of the hash tube, and the signature should consist of two of the three values at the top, followed by one for each of the layers below it until the bottom. The game here is that a verifier can calculate one of the values at each layer based on the two values they have from the previous layer, and which of the two unknown values on the new layer should be revealed is determined by a bit of the value to be hashed. If the value at the very bottom matches with the public key, the signature is accepted.
The clever thing about this is that if someone signs more than one thing, then at each layer of the tube there's a 1/2 chance that the two signatures combined give away all of the layers of the tube afterwards (The top layer at 2/3 is a bit special, and in practice would probably be hacked to be 1/2 for simplicity). If they differ at the very beginning that means that an attacker can literally sign anything.
Unfortunately there's a fairly good attack on this scheme. If you want to sign two things and make it hard for an attacker to sign anything with the result you can make a long-ish partial collision starting at the beginning. The longest such collision you can make is based on a birthday attack where you generate lots of semantically similar versions of the two things you're trying to both sign, sort both lists, and find the longest shared prefix. Because this is a birthday attack, it will generate on average a prefix whose length is about double the scale of the number of operations you did. Unfortunately someone trying to sign another arbitrary value will need to do a full reversal of the specific value you came up with, so this attack might be effective at getting away with solving two values rather than one. It doesn't work for more than two values though, and there may be a way of fixing it but one isn't coming immediately to mind (I only came across this an hour ago and haven't thought about this technique previously.)
I've thought about this problem before and came up with a much cruder but clearly effective technique, which is that rather than having to reveal half the preimage values you have to reveal 99% of them. That can make the signatures much larger, but there's a trick to fix that: Instead of each preimage value being chosen independently, they're all generated off a single root in a tree formation. When there's a long string of values whose preimage is to be included, instead of including them individually you give the branch which generated all of them. This optimization doesn't fix the time required to generate and verify signatures, but it does make them small again.
Both of these techniques completely break winternitz compression, so the signatures are larger than with the most size-optimized secure hash based signatures.
On the final question, of whether this is the original Satoshi: Absolutely not. The thinking about protocols as a whole is too muddled, the emphasis is too much on a new primitive, and the english is way too broken. That said, the author is clearly a very smart person. I've spent some time thinking about the core primitive which hash tubes are trying to make, and while hash tubes may have a serious problem they're a technique which I didn't think of and might have a simple fix and are a lot less ugly than the workable but yuck approach I came up with.
What the author appears to want is a signature scheme which allows any other party to sign arbitrary values if it's used more than once. This provides some disincentive to double-spends, because it turns attempts at double-spends into things which can get stolen by miners. That doesn't block everything, because miners have to be co-consipirators in some double-spending schemes anyway, but it is something. It can also cause problems for adjusting fees with replace by fee, and even worse for transactions which you give up on because the fees are too high, thus rendering the original utxo completely unspendable.
This intention is speculative because of how the paper is truncated though. What I can comment on a bit better is the new-ish primitive. I believe that for signatures the public key should be the bottom of the hash tube, and the signature should consist of two of the three values at the top, followed by one for each of the layers below it until the bottom. The game here is that a verifier can calculate one of the values at each layer based on the two values they have from the previous layer, and which of the two unknown values on the new layer should be revealed is determined by a bit of the value to be hashed. If the value at the very bottom matches with the public key, the signature is accepted.
The clever thing about this is that if someone signs more than one thing, then at each layer of the tube there's a 1/2 chance that the two signatures combined give away all of the layers of the tube afterwards (The top layer at 2/3 is a bit special, and in practice would probably be hacked to be 1/2 for simplicity). If they differ at the very beginning that means that an attacker can literally sign anything.
Unfortunately there's a fairly good attack on this scheme. If you want to sign two things and make it hard for an attacker to sign anything with the result you can make a long-ish partial collision starting at the beginning. The longest such collision you can make is based on a birthday attack where you generate lots of semantically similar versions of the two things you're trying to both sign, sort both lists, and find the longest shared prefix. Because this is a birthday attack, it will generate on average a prefix whose length is about double the scale of the number of operations you did. Unfortunately someone trying to sign another arbitrary value will need to do a full reversal of the specific value you came up with, so this attack might be effective at getting away with solving two values rather than one. It doesn't work for more than two values though, and there may be a way of fixing it but one isn't coming immediately to mind (I only came across this an hour ago and haven't thought about this technique previously.)
I've thought about this problem before and came up with a much cruder but clearly effective technique, which is that rather than having to reveal half the preimage values you have to reveal 99% of them. That can make the signatures much larger, but there's a trick to fix that: Instead of each preimage value being chosen independently, they're all generated off a single root in a tree formation. When there's a long string of values whose preimage is to be included, instead of including them individually you give the branch which generated all of them. This optimization doesn't fix the time required to generate and verify signatures, but it does make them small again.
Both of these techniques completely break winternitz compression, so the signatures are larger than with the most size-optimized secure hash based signatures.
On the final question, of whether this is the original Satoshi: Absolutely not. The thinking about protocols as a whole is too muddled, the emphasis is too much on a new primitive, and the english is way too broken. That said, the author is clearly a very smart person. I've spent some time thinking about the core primitive which hash tubes are trying to make, and while hash tubes may have a serious problem they're a technique which I didn't think of and might have a simple fix and are a lot less ugly than the workable but yuck approach I came up with.
(this is my first post here, so sorry in advance if I unknowingly broke any rules).
