3 ms·

On a positive note sharding technology does have great promise because of the problems that it can potentially solve. With Bitcoin you can only validate a trans

On a positive note sharding technology does have great promise because of the problems that it can potentially solve. With Bitcoin you can only validate a transaction by having all of the unspent transactions in memory [1]. With a sharded system you only need to have a subset of those transactions in memory. At a fundamental technological level you are increasing the size of available memory by using the memory of other nodes. And there are ways you can query other nodes about their subset of unspent transactions by using a merkle tree. If you trust the root of a balanced merkle tree you only need O(log(n)) computations [2] to prove that a leaf belongs to it. This sharding mechanism could be added to bitcoin where the root of the merkle tree of the unspent transactions is added to each block. Nodes on the network can store a sub-tree of arbitary size and validate part of each block. Whether this scheme would be robust to dishonest miners is still an open question though. [1] http://gavinandresen.ninja/utxo-uhoh http://gavinandresen.ninja/utxo-uhoh [2] https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a#inclusion-proofs https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee...

hobofan 9y ago
> With Bitcoin you can only validate a transaction by having all of the unspent transactions in memory. I'm somewhat sceptical of that claim, for the reason pointed out in the blog post, and I think you can get away with much simpler solutions for quite some time. - You can use many heuristics to decide which UTXO data to keep in memory. LRU + deprioritizing addresses where the balance is too low to pay the current transaction fees seems like a good start. Research shows that there is a high percentage of stale data[0]. - With a block time as high as 10min, you can definitely spend 1ms on read latency for retrieving UTXO data from disk. - Even if you don't manage to retrieve UTXO data from disk quickly, that just means that the transaction missed its chance to be included in the current block. It could still be ready in time for the next one. Overall, UTXO set growth is, of course, a problem since it increases centralization, but I don't think the problem of _in-memory_ UTXO sets is as big as it is often made out to be. [0]: https://eprint.iacr.org/2017/1095.pdf https://eprint.iacr.org/2017/1095.pdf

hobofan 9y ago

> With Bitcoin you can only validate a transaction by having all of the unspent transactions in memory. I'm somewhat sceptical of that claim, for the reason pointed out in the blog post, and I think you can get away with much simpler solutions for quite some time. - You can use many heuristics to decide which UTXO data to keep in memory. LRU + deprioritizing addresses where the balance is too low to pay the current transaction fees seems like a good start. Research shows that there is a high percentage of stale data[0]. - With a block time as high as 10min, you can definitely spend 1ms on read latency for retrieving UTXO data from disk. - Even if you don't manage to retrieve UTXO data from disk quickly, that just means that the transaction missed its chance to be included in the current block. It could still be ready in time for the next one. Overall, UTXO set growth is, of course, a problem since it increases centralization, but I don't think the problem of _in-memory_ UTXO sets is as big as it is often made out to be. [0]: https://eprint.iacr.org/2017/1095.pdf https://eprint.iacr.org/2017/1095.pdf