Author: Bram Cohen 2017-02-21 22:00:23
Published on: 2017-02-21T22:00:23+00:00
The Merkle set data structure shared in the provided link has a simple format and is a Patricia Trie, which can be useful for any distributed computation requiring an audit trail. It may also come in handy for utxo commitments in Bitcoin blocks. The data structure uses blake2s as its internal hashing function, which is faster than sha256 on 512-bit inputs. However, it sacrifices two bits of security to include metadata inline, reducing the CPU cost of hashing by half. Another clever feature of this data structure is that when one side of a node is empty and the other contains exactly two items, the secure hash of the child is adopted verbatim rather than rehashing it. This reduces the amount of hashing done, makes it more resistant to malicious data, and simplifies implementation details at the cost of some extra complexity. The code has both a simple reference implementation and a performance-optimized non-reference implementation that is more cache coherent, but it needs to be ported to C before the potential performance gains can be realized.
Updated on: 2023-05-20T01:00:00.069758+00:00