rustreexo/
lib.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! # Rustreexo
4//!
5//! Rustreexo is a Rust implementation of [Utreexo](https://eprint.iacr.org/2019/611),
6//! a novel accumulator that allows for a succinct representation of the UTXO set, using a
7//! logarithmic amount of space. It uses a dynamic accumulator that allows for addition and deletion
8//! of elements. When spending a UTXO, the element is deleted from the accumulator. When receiving a
9//! UTXO, the element is added to the accumulator. During validation, nodes receive an inclusion proof
10//! for the input in the UTXO set.
11//!
12//! This library implements all the building blocks needed to work
13//! with the Utreexo accumulator, by way of the following modules:
14//!
15//!  * [`node_hash`]: the internal representation of a [hash](node_hash::BitcoinNodeHash) in the Utreexo accumulator.
16//!  * [`proof`]: the inclusion [`Proof`](proof::Proof) of a leaf in the Utreexo forest.
17//!  * [`stump`]: the most compact accumulator. It only keeps track of the forest's roots and can only verify inclusion proofs.
18//!  * [`pollard`]: a middle ground between the [`Stump`](stump::Stump) and the [`MemForest`](mem_forest::MemForest).
19//!    It allows for keeping track of [`Proof`](proof::Proof)s for a subset of leafs by keeping a forest of sparse Merkle trees.
20//!    It can both verify and generate inclusion proofs (proof generation is limited to the leafs that the [`Pollard`](pollard::Pollard)
21//!    accumulator keeps). This makes it possible for a node to only keeping track of [`Proof`](proof::Proof)s for a
22//!    wallet's own UTXOs in an efficient manner, for example.
23//!  * [`mem_forest`]: an in-memory forest accumulator. It keeps track of every leaf in the forest. It can both verify and
24//!    generate inclusion proofs for any leaf in the forest.
25
26#![cfg_attr(any(bench), feature(test))]
27#![cfg_attr(not(feature = "std"), no_std)]
28
29extern crate alloc;
30
31/// This is the maximum size the forest is ever allowed to have, this caps how big `num_leaves` can
32/// be (we use a [`u64`]) and is also used by the [`util::translate`] logic.
33///
34/// # Calculations
35///
36/// If you think: "but... is 63 enough space"? Well... assuming there's around 999,000 WUs
37/// available on each block (let's account for header and coinbase), a non-segwit transaction's
38/// size is:
39/// `4 (version) + 1 (vin count) + 41 (input) + 5 (vout for many outputs) + 10N + 4 (locktime)`
40///
41/// `N` is how many outputs we have (we are considering outputs with amount and a zero-sized
42/// script), for 999,000 WUs we can fit:
43/// - `55 + 10N <= 999,000`
44/// - `N ~= 90k` outputs (a little over)
45///
46/// Since `2^63 = 9,223,372,036,854,775,808`, if you divide this by 90,000 we get
47/// 102,481,911,520,608 blocks. It would take us 3,249,680 years to mine that many blocks.
48///
49/// For the poor soul in 3,249,682 A.D., who needs to fix this hard-fork, here's what you gotta do:
50/// - Change the `leaf_data` type to u128, or q128 if Quantum Bits are the fashionable standard.
51/// - Change `MAX_FOREST_ROWS` to 128 or higher in `lib.rs`
52/// - Modify [`util::start_position_at_row`] to avoid overflows.
53///
54/// That should save you the trouble.
55pub(crate) const MAX_FOREST_ROWS: u8 = 63;
56
57#[cfg(not(feature = "std"))]
58/// Re-exports `alloc` basics plus HashMap/HashSet and IO traits.
59pub mod prelude {
60    pub use alloc::borrow::ToOwned;
61    pub use alloc::format;
62    pub use alloc::string::String;
63    pub use alloc::string::ToString;
64    pub use alloc::vec; // brings `vec!` into scope
65    pub use alloc::vec::Vec;
66
67    pub use bitcoin_io as io;
68    pub use bitcoin_io::Read;
69    pub use bitcoin_io::Write;
70    pub use hashbrown::HashMap;
71    pub use hashbrown::HashSet;
72}
73
74#[cfg(feature = "std")]
75/// Re-exports `std` basics plus HashMap/HashSet and IO traits.
76pub mod prelude {
77    extern crate std;
78    pub use std::collections::HashMap;
79    pub use std::collections::HashSet;
80    pub use std::io;
81    pub use std::io::Read;
82    pub use std::io::Write;
83}
84
85pub mod mem_forest;
86pub mod node_hash;
87pub mod pollard;
88pub mod proof;
89pub mod stump;
90pub(crate) mod util;
rustreexo/lib.rs

rustreexo/
lib.rs
