Author: Pieter Wuille 2012-11-06 19:14:58
Published on: 2012-11-06T19:14:58+00:00
In a communication thread from 2012, Mike Hearn expressed his confusion over the effort required to create some sort of partial tree encoding. Pieter Wuille responded by sharing his implementation for an efficient representation of partial Merkle trees. This can be found on Github under the "partialmerkle" branch. The encoding and decoding algorithm uses a depth-first traversal of the tree, outputting whether or not anything relevant is beneath each node. If there is nothing relevant beneath a node, its hash is stored without descending into the children. Some hard upper bounds on the size of serialized structures are guaranteed due to properties of the tree. Unit tests are included to verify that encoding and decoding a subset of transactions is an identity, the calculated merkle root matches the existing merkle algorithm in the source code, the calculated merkle root depends on all hashes in the data structure, serialization/deserialization is an identity, and that bounds on the size of the serialization are respected. Pieter Wuille hopes that his implementation is clear enough to port to other languages.
Updated on: 2023-05-19T15:56:17.820372+00:00