Author: Tomas 2017-09-05 14:17:26
Published on: 2017-09-05T14:17:26+00:00
The proposal of an efficient UTXO commitment scheme is being made in order to fast sync a full node and prove the existence or non-existence of a UTXO. Previously, various schemes have been proposed such as Merkle/radix trees and variants, which increase the burden of maintaining the UTXO set, and a "flat" rolling hash, which only solves one of the two problems mentioned above. The proposed hybrid approach involves dividing the UTXO set into buckets based on the prefix of their TXID and maintaining a rolling hash for each bucket. The commitment is then the root of the tree constructed from these bucket hashes. To construct the tree, the hashes of the next depth are grouped per 64 hashes and the rolling hash of each group is calculated, which effectively creates a prefix tree with a fixed branch-size of 64. Bucketcount is determined by calculating the smallest power of 2 larger than the square root of the number of TXIDs in the UTXO set. Overall, this approach has limited extra burden to maintain and reasonably small proofs.
Updated on: 2023-06-12T18:05:51.816949+00:00