Published on: 2016-07-15T23:00:57+00:00
In an email exchange between Peter Todd and Bram Cohen, the topic of discussion revolves around various aspects of UTXO commitments, merkle trees, and optimizations. Todd suggests using BLAKE2b for internal hashing due to its efficiency in omitting padding when the data is exactly one block in size. The implementation of a root branch block with nodes arranged in fixed positions and terminals having outpointers to other blocks is also discussed. The conversation also delves into the efficiency of their implementation when stored on a spinning hard drive. It is estimated that even an underpowered node could keep up with the blockchain if it is full of simple transactions. Validating an entire blockchain history might take a few days, but if some layers are kept in regular memory, validating a whole year of history might only take a few hours. The complexity of the MMR proposal's data structures is acknowledged, and it is suggested that specifying storage media and latency expectations would clarify the reasoning significantly.Cohen considers committing to the prefix as a way of handling cases where multiple keys share parts of the same prefix, but concludes that it would only save about 10% of memory in his implementation. Todd explains that committing to the prefix is a simple but possibly not-optimal way of committing to what data should be accessible under a given node. They discuss the depths of merkbiner trees in proportion to log2(n) against attackers who are choosing keys by grinding hashes. The optimization of hashing time is also explored, with the mention of the efficiency of BLAKE2 compared to SHA256.The conversation then moves on to the implementation of merkle trees and how each node contains metadata byte followed by fixed-size secure hashes and pointers to the children. The structure of branch blocks, terminals, and leaf blocks is explained, along with the overflow mechanism when a leaf block exceeds its capacity. The idea of achieving practical Bitcoin updates with minimal cache misses is discussed, with Cohen explaining the clever placement of nodes in memory to minimize cache misses.Another aspect of the conversation revolves around adding latency to UTXO commitments. It is agreed that adding latency can work in principle but should only be used as a last resort technique when optimization fails. The addition of roots of what's added and deleted in each block allows for proofs of inclusion and exclusion without significant latency. However, it adds complexity and should only be done when necessary for fast validation before block propagation.The discussion also touches upon the indexing of the UTXO set, the possibility of introducing incentives for collecting dust, and the use of variable-sized commitments instead of hash digests for improved efficiency. There is a debate about whether validation before block propagation needs to be done at all, with Todd suggesting that it's reasonable to propagate blocks that have not been fully validated beyond checking PoW. The importance of minimizing the time it takes miners to start mining the next block and collecting fees is emphasized.There are additional conversations discussing the technicalities of TXO commitments, the differences between merkle trees and patricia tries, and the performance and optimization considerations of implementing UTXO, STXO, and TXO commitments. The use of mountain ranges for merkle trees is debated, with suggestions for alternative approaches such as raw merkle trees.In conclusion, the email exchanges provide detailed insights into the discussions surrounding UTXO commitments, merkle trees, optimizations, latency issues, and various implementation considerations within the Bitcoin community. The conversations highlight the complexities and trade-offs involved in designing efficient and secure blockchain data structures.
Updated on: 2023-08-01T18:27:34.546121+00:00