4 releases (breaking)

0.4.0 Feb 6, 2025
0.3.0 Jul 30, 2024
0.2.0 Jun 8, 2024
0.1.0 Aug 14, 2023

#1 in #accumulator

Download history 48/week @ 2024-12-01 63/week @ 2024-12-08 90/week @ 2024-12-15 40/week @ 2024-12-22 60/week @ 2024-12-29 76/week @ 2025-01-05 49/week @ 2025-01-12 80/week @ 2025-01-19 71/week @ 2025-01-26 239/week @ 2025-02-02 147/week @ 2025-02-09 46/week @ 2025-02-16 198/week @ 2025-02-23 410/week @ 2025-03-02 215/week @ 2025-03-09 217/week @ 2025-03-16

1,043 downloads per month

MIT license

215KB
4K SLoC

rustreexo - Utreexo in rust

Build Status License Version Downloads

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

Contributing

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

Dependencies

~365–530KB
~11K SLoC