3 releases (breaking)
0.3.0 | Jul 30, 2024 |
---|---|
0.2.0 | Jun 8, 2024 |
0.1.0 | Aug 14, 2023 |
#13 in #accumulator
269 downloads per month
150KB
3K
SLoC
rustreexo - Utreexo in rust
Utreexo is a dynamic hash-based accumulator designed to be used as a set membership proof system and 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/
.
Testing
This library contains an exhaustive test suite that covers all the algorithms implemented. To run the tests, simply run cargo test
. We test for internal code sanity and cross-test with values generated by the utreexo lib.
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.
Dependencies
~365–530KB
~11K SLoC