Published on: 2014-01-08T01:04:58+00:00
On January 6th, 2014, Gregory Maxwell proposed restructuring the current unspent transaction output (UTXO) index as a Merkle tree. This change would allow nodes without access to the UTXO set to still receive transactions or blocks with prefixed proofs and check their validity.Thomas Voegtlin had developed a Python-levelDB implementation of the UTXO hash tree and suggested creating per-block indexes of all scriptPubKeys, spent or unspent, queryable via partial prefix method. In response, Peter Todd recommended thoroughly testing the implementation on Electrum and adding a C++ implementation to Bitcoin Core. He also mentioned the need for performance testing and usability assessment before any soft-fork.Thomas Voegtlin expressed appreciation for Mark Friedenbach's work on the UTXO hash tree and stated its importance for Electrum. He suggested testing different options before writing a BIP and questioned the possibility of partial prefix queries on the tree.The email thread discussed a new Merkle-compressed data structure that has applications in committed validation indices, wallet indices, document time-stamping, and merged mining. The structure is based on a binary prefix tree and has a Python and C++ implementation. The serialization format of the authenticated prefix tree was described in detail.Gregory Maxwell posted questions regarding the proposed data structure, including the structure of VARCHAR(), extradata position, and the possibility of using SHA-512/256. He raised concerns about the performance cost of validating the structure under a zero-knowledge proof.Mark Friedenbach shared a first draft of a BIP for the new data structure, discussing the nature of VARCHAR(), extradata position, and midstate compression. He mentioned that CPU performance should not be a major consideration but the cost of validating under a zero-knowledge proof should be taken into account. Prefix tree compressed applications were discussed, noting that they could only be used if all verifying nodes had all their data under the tree.Peter Todd expressed his disagreement with UTXO commitments, arguing that they forced miners and full nodes with SPV clients to store the entire UTXO set perpetually. He also raised concerns about security and trust in single confirmations.Mark Friedenbach proposed stateless validation and mining involving prefixing messages with proofs of UTxO state changes. Peter Todd disagreed with UTXO commitments and suggested taking this technology to Namecoin instead.The email exchange on December 20, 2013, discussed authenticated prefix trees and their variations. The BIPs described the application of these trees to committed indices, document time-stamping, and merged mining. Mark Friedenbach mentioned advantages and added bytes to the coinbase transaction. Peter Todd provided feedback on the code examples, suggesting leaving out Unicode.In another email, Mark proposed application-oriented BIPs related to authenticated prefix trees. Stateless validation and mining involved prefixing messages with proofs of state changes. Ultimate blockchain compression involved consensus over an address index queried by lightweight nodes. The structure of the index was an authenticated prefix tree. Mark believed these BIPs affected the interoperability of the bitcoin protocol and clients using these applications.Overall, the email thread discussed various proposals and implementations related to restructuring the UTXO index, creating authenticated prefix trees, and their applications in the bitcoin ecosystem.The article discusses the proposal of introducing additional Bitcoin Improvement Proposals (BIPs) that describe the use of an authenticated prefix tree data structure for various applications. The author questions whether the BIP can stand alone without specific changes to the protocol or end-user accessible features, as BIPs are meant to define interoperability rather than implementation details. However, they express interest in reading about BIPs that utilize the tree to achieve scalability or security benefits.Bitcoin developer Mark Friedenbach has drafted a BIP for a new Merkle-compressed data structure called the authenticated prefix tree. This data structure is ideal for encoding key-value indices that support memory-efficient proofs. It is a hybrid PATRICIA / de la Brandais tree structure that compresses non-branching nodes into a single interior node with a skip prefix. This reduces the serialized size and the number of hash operations required for updates and proof validation. The authenticated prefix tree can be used for committed validation indices, wallet indices, document time-stamping, and merged mining.The article discusses two variations of the authenticated prefix tree presented in the draft BIP, which differ in the construction of hash values for nodes and their branches. The first variation is level-compressed hashing, where the referenced child node's hash is used in the interior node's hash digest. The second variation is proof-updatable hashing, where level-compressed branches are expanded into chained single-branch internal nodes. Both variations trade computational resources for the ability to compose operational proofs.Inclusion proofs, which are pruned prefix trees, are explained in the article.
Updated on: 2023-08-01T06:54:07.665191+00:00