A Rust implementation of Utreexo, a dynamic hash-based accumulator optimized for the Bitcoin UTXO set.
Utreexo enables constructing a succinct representation of the Bitcoin UTXO in a logarithmic amount of size, by leveraging Merkle trees. Set membership can be proven and verified through Merkle inclusion proofs.
This library implements three accumulator primitives:
-
Stump: keeps the roots of the Merkle forest, using$O(\log{n})$ space -
Pollard: keeps a specific set of leaves of the Merkle forest, using$O(k \cdot \log{n})$ space -
MemForest: keeps all leaves of the Merkle forest, using$O(n)$ space,
where
use rustreexo::node_hash::BitcoinNodeHash;
use rustreexo::proof::Proof;
use rustreexo::stump::Stump;
let utxo = BitcoinNodeHash::from_str("b151a956139bb821d4effa34ea95c17560e0135d1e4661fc23cedc3af49dac42").unwrap();
// Create an accumulator
let stump = Stump::new();
// Add the UTXO to the accumulator
let (stump, _) = stump.modify(&vec![utxo], &[], &Proof::default()).unwrap();
// Create an inclusion proof for the UTXO that was added
let proof = Proof::new(vec![0], vec![utxo]);
// Remove the UTXO from the accumulator by proving its set membership
let (stump, _) = stump.modify(&vec![], &vec![utxo], &proof).unwrap();To see complete usage examples, refer to the examples/ folder.
This project uses just for command running, and
cargo-rbmt
to manage everything related to cargo, such as formatting, linting, testing and CI. To install them, run:
~$ cargo install just
~$ cargo install cargo-rbmtA justfile is provided for convenience. Run just to see available commands:
~$ just
> rustreexo
> A Rust implementation of Utreexo
Available recipes:
[Dependencies]
lock # Generate Lockfiles [alias: l]
[Documentation]
docs # Generate Documentation [alias: d]
docs-open # Generate and Open Documentation
[Quality]
audit # Audit dependencies [alias: a]
check # Check Formatting, Linting and Documentation [alias: c]
check-sigs # Check Commit Signatures
fmt # Format Code [alias: f]
pre-push # Run pre-push suite: lock, fmt, check, and test [alias: p]
shellcheck # Run ShellCheck
zizmor # Run Zizmor Static Analysis
[Setup]
setup-tools-toolchains # Setup Tools and Toolchains
update-tools-toolchains # Update Tools and Toolchains
[Testing]
bench BENCH="" # Run Benchmarks: accumulator, proof, stump
fuzz TARGET="list" TIME="600" # Run Fuzz Targets: list, all, or TARGET
test # Run Tests [alias: t]This library should compile with any combination of features on Rust 1.74.0.
To build with the MSRV toolchain, copy Cargo-minimal.lock to Cargo.lock.
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.