Crate rustreexo 

Rustreexo

Rustreexo is a Rust implementation of Utreexo, a novel accumulator that allows for a succinct representation of the UTXO set, using a logarithmic amount of space. It uses a dynamic accumulator that allows for addition and deletion of elements. When spending a UTXO, the element is deleted from the accumulator. When receiving a UTXO, the element is added to the accumulator. During validation, nodes receive an inclusion proof for the input in the UTXO set.

This library implements all the building blocks needed to work with the Utreexo accumulator, by way of the following modules:

• node_hash: the internal representation of a hash in the Utreexo accumulator.
• proof: the inclusion Proof of a leaf in the Utreexo forest.
• stump: the most compact accumulator. It only keeps track of the forest’s roots and can only verify inclusion proofs.
• pollard: a middle ground between the Stump and the MemForest. It allows for keeping track of Proofs for a subset of leafs by keeping a forest of sparse Merkle trees. It can both verify and generate inclusion proofs (proof generation is limited to the leafs that the Pollard accumulator keeps). This makes it possible for a node to only keeping track of Proofs for a wallet’s own UTXOs in an efficient manner, for example.
• mem_forest: an in-memory forest accumulator. It keeps track of every leaf in the forest. It can both verify and generate inclusion proofs for any leaf in the forest.

Modules

mem_forest

A full MemForest accumulator implementation. This is a simple version of the forest, that keeps every node in memory. This is may require more memory, but is faster to update, prove and verify.

node_hash

AccumulatorHash is an internal type for representing Hashes in an utreexo accumulator. It’s just a wrapper around [[u8; 32]] but with some useful methods.

pollard

Pollard is an efficient implementation of the accumulator for keeping track of a subset of the whole tree. Instead of storing a proof for some leaves, it is more efficient to hold them in a tree structure, and add/remove elements as needed. The main use-case for a Pollard is to keep track of unconfirmed transactions’ proof, in the mempool. As you get new transactions through the p2p network, you check the proofs and add them to the Pollard. When a block is mined, we can remove the confirmed transactions from the Pollard, and keep the unconfirmed ones. We can also serve proofs for specific transactions as requested, allowing efficient transaction relay.

prelude

Re-exports std basics plus HashMap/HashSet and IO traits.

proof

A proof is a data structure that proves that a given element is in the accumulator. It is used to validate a transaction. A proof is composed of a list of hashes and a list of integers. The hashes are the hashes need to calculate the root hash for validation. The integers are the position of the element in the accumulator.

stump

A Stump is a basic data structure used in Utreexo. It only holds the roots and the number of leaves in the accumulator. This is useful to create lightweight nodes, the still validates, but is more compact, perfect to clients running on low-power devices.