Author: Thomas Voegtlin 2014-01-05 18:43:58
Published on: 2014-01-05T18:43:58+00:00
The email thread is discussing a new Merkle-compressed data structure that has many useful applications. This includes committed validation indices, committed wallet indices, efficient document time-stamping, and secure & efficient merged mining. The data structure is based on a binary prefix tree defined in the BIP. It provides a mapping of bitstrings (the keys) to bytestrings (the values). The tree is a hybrid PATRICIA / de la Brandais tree structure, which compresses a long sequence of non-branching nodes into a single interior node with a per-branch 'skip prefix.' There is an available Python implementation of this data structure, and a C++ implementation is also being worked on.The serialization format of the authenticated prefix tree is described in detail, including the format of serialized nodes, flags, and branches. The flags contain single-byte fields whose composite values determine the bytes that follow. They indicate whether or not a node branches, stores a data bytestring, and have three bits used for proof extraction. Branches are either left or right, and their format depends on the value of the flags setting. When serializing a proof or snapshotting tree state and the branch is not pruned, the serialized child node is included directly, and the count and size are omitted as they can be derived from the serialization.The authenticated prefix tree is an efficient data structure that can be used for key-value storage and membership proof generation. Two variations of hashing are used to construct the prefix tree: level-compressed hashing and proof-updatable hashing. Level-compressed hashing uses the child node's hash to construct an interior node's hash digest, whereas proof-updatable hashing expands branches into a series of chained single-branch internal nodes. Both variations have their advantages and disadvantages depending on the application. Inclusion proofs are a pruned version of the prefix tree that contains a subset of its keys. The inclusion proof is serialized as a variant byte indicating the presence of level-compression or proof-updatable hashing, the Merkle compression hash of the tree, the serialized representation of the tree, and finally, the first 4 bytes of the SHA-256 checksum. For ease of transport, the inclusion proof is encoded in internet-standard base64 encoding.Operational proofs are a list of insert/update and delete operations suffixed to an inclusion proof that contains the pathways necessary to perform the specified operations. The inclusion proof must contain the key values to be updated or deleted, and the nearest adjacent key values for each insertion. The serialization of an operational proof includes variant, root_hash, tree, delete list, update list, new_hash, and checksum. The first three fields are the inclusion proof which take same values as described in previous section. Deletes is a list of key values to be deleted; each key value in this list must exist in the inclusion proof. Updates is a list of key, value mappings which are to be inserted into the tree, possibly replacing any mapping for the key which already exists. Either the key itself if it exists (update), or the two lexicographically closest keys on either side if it does not (insert) must be present in the insertion proof. New_hash is the resulting Merkle root after the insertion, updates, and deletes are performed, and checksum is the initial 4 bytes of the SHA-256 hash of the preceding fields.Just like inclusion proofs, an operational proof is also encoded in base64 for display and transport. An example of an operational proof is given, along with its constituent fields - level-compressed hashing, original Merkle root, serialized tree (included keys: '中本'), deletion list ['中本'], insertion list [], new Merkle root, and checksum. It also includes PGP signature at the end. At the end of the context, the Bitcoin-development mailing list is mentioned along with a promotion about AppDynamics that provides 100% visibility into your Java,.NET, & PHP application and a 15-day free trial.
Updated on: 2023-06-07T22:45:34.593888+00:00