# rustreexo - Utreexo in rust

![Build Status](https://github.com/mit-dci/rustreexo/actions/workflows/rust.yml/badge.svg)
![License](https://img.shields.io/crates/l/rustreexo)
![Version](https://img.shields.io/crates/v/rustreexo)
![Downloads](https://img.shields.io/crates/d/rustreexo)

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`:

```rust
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](https://github.com/utreexo/utreexo) lib.

## License

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

## References

- [Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set](https://eprint.iacr.org/2019/611.pdf)
- [Dev++ 03-09-EN | Acumulator Based Cryptography & UTreexo](https://www.youtube.com/watch?v=xlKQP9J88uA)
- [What is UTreeXO? with Calvin Kim](https://www.youtube.com/watch?v=IcHW6RsZR7o)
- [Rustreexo](https://blog.dlsouza.lol/bitcoin/utreexo/2023/07/07/rustreexo.html)

## Contributing

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