rustreexo - Utreexo in rust

Utreexo is a dynamic hash-based accumulator designed to be used as a set membership proof system. It is used in the Bitcoin network to compress the UTXO set. This is a pure-rust implementation of the accumulator, allowing proving and verifying set membership proofs.

Usage

Rustreexo provides two basic data structures to represent the accumulator, Stump and Pollard. Stump is a lightweight version of the accumulator that only keeps the roots, and therefore only uses O(log n) space. Pollard is a more complete version of the accumulator that keeps the full tree, and therefore uses O(n) space. However, both data structures implements the same algorithms, so a proof generated by a Pollard is meant to be verified by a Stump. Here's how to use the Stump:

use rustreexo::accumulator::stump::Stump;

let stump = Stump::new();
// Modify the accumulator, adding UTXOs and removing STXOs, that are proved by del_proof
let (stump, _) = stump.modify(utxos, stxos, del_proof).unwrap();
// Verify a proof for a UTXO
assert!(stump.verify(utxo_proof).unwrap());

for a complete example, see examples/.

Minimum Supported Rust Version (MSRV)

This library should compile with any combination of features on Rust 1.74.0.

No-std support

The std cargo feature is enabled by default. To build this project without the Rust standard library, use the --no-default-features flag or set default-features = false in your dependency declaration when adding it to your project.

Testing

This library contains an exhaustive test suite that covers all the algorithms implemented. To run the tests, simply run just test, or just test-msrv to test with the MSRV toolchain of 1.74.0. We test for internal code sanity and cross-test with values generated by the utreexo library.

License

rustreexo is released under the terms of the MIT license. See LICENSE for more information, or see https://opensource.org/licenses/MIT.

References

• Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set
• Dev++ 03-09-EN | Acumulator Based Cryptography & UTreexo
• What is UTreeXO? with Calvin Kim
• Rustreexo

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.