rustreexo 0.5.0

A Rust implementation of Utreexo
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

# rustreexo - Utreexo in rust

<p>
    <a href="https://crates.io/crates/rustreexo"><img src="https://img.shields.io/crates/v/rustreexo.svg"/></a>
    <a href="https://docs.rs/rustreexo"><img src="https://img.shields.io/badge/docs.rs-rustreexo-brightgreen"/></a>
    <a href="https://blog.rust-lang.org/2023/11/16/Rust-1.74.0/"><img src="https://img.shields.io/badge/rustc-1.74.0%2B-orange.svg"/></a>
    <a href="https://github.com/mit-dci/rustreexo/blob/main/LICENSE"><img src="https://img.shields.io/badge/License-MIT%2FApache--2.0-red.svg"/></a>
    <a href="https://github.com/mit-dci/rustreexo/actions/workflows/rust.yml"><img src="https://img.shields.io/github/actions/workflow/status/mit-dci/rustreexo/rust.yml?label=CI"></a>
</p>

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

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

## License

Licensed under either of

- MIT license ([LICENSE-MIT](LICENSE-MIT) or <https://opensource.org/licenses/MIT>)
- Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or <https://www.apache.org/licenses/LICENSE-2.0>)

at your option.

## 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.