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(not(feature = "std"), no_std)]
27
28extern crate alloc;
29
30/// This is the maximum size the forest is ever allowed to have, this caps how big `num_leaves` can
31/// be (we use a [`u64`]) and is also used by the [`util::translate`] logic.
32///
33/// # Calculations
34///
35/// If you think: "but... is 63 enough space"? Well... assuming there's around 999,000 WUs
36/// available on each block (let's account for header and coinbase), a non-segwit transaction's
37/// size is:
38/// `4 (version) + 1 (vin count) + 41 (input) + 5 (vout for many outputs) + 10N + 4 (locktime)`
39///
40/// `N` is how many outputs we have (we are considering outputs with amount and a zero-sized
41/// script), for 999,000 WUs we can fit:
42/// - `55 + 10N <= 999,000`
43/// - `N ~= 90k` outputs (a little over)
44///
45/// Since `2^63 = 9,223,372,036,854,775,808`, if you divide this by 90,000 we get
46/// 102,481,911,520,608 blocks. It would take us 3,249,680 years to mine that many blocks.
47///
48/// For the poor soul in 3,249,682 A.D., who needs to fix this hard-fork, here's what you gotta do:
49/// - Change the `leaf_data` type to u128, or q128 if Quantum Bits are the fashionable standard.
50/// - Change `MAX_FOREST_ROWS` to 128 or higher in `lib.rs`
51/// - Modify [`util::start_position_at_row`] to avoid overflows.
52///
53/// That should save you the trouble.
54pub(crate) const MAX_FOREST_ROWS: u8 = 63;
55
56#[cfg(not(feature = "std"))]
57/// Re-exports `alloc` basics plus HashMap/HashSet and IO traits.
58pub mod prelude {
59    pub use alloc::borrow::ToOwned;
60    pub use alloc::format;
61    pub use alloc::string::String;
62    pub use alloc::string::ToString;
63    pub use alloc::vec; // brings `vec!` into scope
64    pub use alloc::vec::Vec;
65
66    pub use bitcoin_io as io;
67    pub use bitcoin_io::Read;
68    pub use bitcoin_io::Write;
69    use foldhash::quality::FixedState;
70
71    pub type HashMap<K, V> = hashbrown::HashMap<K, V, FixedState>;
72    pub type HashSet<T> = hashbrown::HashSet<T, FixedState>;
73
74    pub fn new_hash_map<K, V>() -> HashMap<K, V> {
75        HashMap::with_hasher(FixedState::default())
76    }
77
78    pub fn new_hash_set<T>() -> HashSet<T> {
79        HashSet::with_hasher(FixedState::default())
80    }
81}
82
83#[cfg(feature = "std")]
84/// Re-exports `std` basics plus HashMap/HashSet and IO traits.
85pub mod prelude {
86    extern crate std;
87    pub use std::collections::HashMap;
88    pub use std::collections::HashSet;
89    pub use std::io;
90    pub use std::io::Read;
91    pub use std::io::Write;
92}
93
94pub mod mem_forest;
95pub mod node_hash;
96pub mod pollard;
97pub mod proof;
98pub mod stump;
99pub(crate) mod util;
rustreexo/lib.rs

rustreexo/
lib.rs
