Re: UNO Commitments
Posted: Sat Apr 04, 2015 11:54 pm
This is awesome. The only comment I have is that we should consider our choice of how many branches are possible. Put in another way, it may be prudent to build the trie more granularity than on byte boundaries.
If we use byte boundaries, it is possible for an attacker to make the proof for a given name take HASHLEN*256*NAMELEN of data. For d/wikileaks this works out to 90,112 bytes of overhead for 256 bit hashes or 56,320 bytes for 160 bit hashes. Best case would be 352 or 220 bytes for 256 or 160 bit hashes respectively.
If we use nybble boundaries, it works out to 11,264/7,040 worst case, 704/440 best case. In other words, we reduce the worst case by a factor of 8 but only increase the best case by a factor of 2. I think this is probably about the right trade-off. We could halve the worst case while doubling the best case another time, but given that an attack would have to buy quite a few names to pull this off, I don't think it's worth it. Using radix trees probably improves the best case further.
These numbers assume no other overhead, which is not strictly true, but they should be a good ballpark.
Tangentially, I think that it may be possible to build a thin client that does not need to remain connected to the network - it could connect to nodes, request block headers only from peers, then once it's caught up, get the UNO proof. It could even support requesting UNO proof+block headers (from the last block it has as a reference) from multiple nodes, most work wins. Based on the estimates here, it should be a few hundred KB of data per day the light client has been inactive. Given that an average web page weighs in at almost 2MB this is not too bad.
Depth of data to trust is an issue with the block headers + UNO validation model. An attacker had a pretty good chance of occasionally making a false block with UNO root hash. A trust depth can be chosen, but then updates are delayed until that block depth is reached. The intervening transactions could be provided by the node being queried, but a dishonest node could simply say they don't exist. A second UNO proof from the latest block plus all the intervening transactions still allows a dishonest node to claim there are no updates, but only if they can mine a fake proof. We need to model this, but I think a good balance is possible.
If we use byte boundaries, it is possible for an attacker to make the proof for a given name take HASHLEN*256*NAMELEN of data. For d/wikileaks this works out to 90,112 bytes of overhead for 256 bit hashes or 56,320 bytes for 160 bit hashes. Best case would be 352 or 220 bytes for 256 or 160 bit hashes respectively.
If we use nybble boundaries, it works out to 11,264/7,040 worst case, 704/440 best case. In other words, we reduce the worst case by a factor of 8 but only increase the best case by a factor of 2. I think this is probably about the right trade-off. We could halve the worst case while doubling the best case another time, but given that an attack would have to buy quite a few names to pull this off, I don't think it's worth it. Using radix trees probably improves the best case further.
These numbers assume no other overhead, which is not strictly true, but they should be a good ballpark.
Tangentially, I think that it may be possible to build a thin client that does not need to remain connected to the network - it could connect to nodes, request block headers only from peers, then once it's caught up, get the UNO proof. It could even support requesting UNO proof+block headers (from the last block it has as a reference) from multiple nodes, most work wins. Based on the estimates here, it should be a few hundred KB of data per day the light client has been inactive. Given that an average web page weighs in at almost 2MB this is not too bad.
Depth of data to trust is an issue with the block headers + UNO validation model. An attacker had a pretty good chance of occasionally making a false block with UNO root hash. A trust depth can be chosen, but then updates are delayed until that block depth is reached. The intervening transactions could be provided by the node being queried, but a dishonest node could simply say they don't exist. A second UNO proof from the latest block plus all the intervening transactions still allows a dishonest node to claim there are no updates, but only if they can mine a fake proof. We need to model this, but I think a good balance is possible.