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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

//! The tiered commitment tree for Penumbra.
//!
//! ```ascii,no_run
//! Eternity┃           ╱╲ ◀───────────── Anchor
//!     Tree┃          ╱││╲               = Global Tree Root
//!         ┃         * ** *           ╮
//!         ┃      *   *  *   *        │ 8 levels
//!         ┃   *     *    *     *     ╯
//!         ┃  ╱╲    ╱╲    ╱╲    ╱╲
//!         ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Global Tree Leaf
//!                         ▲             = Epoch Root
//!                      ┌──┘
//!                      │
//!                      │
//!    Epoch┃           ╱╲ ◀───────────── Epoch Root
//!     Tree┃          ╱││╲
//!         ┃         * ** *           ╮
//!         ┃      *   *  *   *        │ 8 levels
//!         ┃   *     *    *     *     ╯
//!         ┃  ╱╲    ╱╲    ╱╲    ╱╲
//!         ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Epoch Leaf
//!                  ▲                    = Block Root
//!                  └───┐
//!                      │
//!                      │
//!    Block┃           ╱╲ ◀───────────── Block Root
//!     Tree┃          ╱││╲
//!         ┃         * ** *           ╮
//!         ┃      *   *  *   *        │ 8 levels
//!         ┃   *     *    *     *     ╯
//!         ┃  ╱╲    ╱╲    ╱╲    ╱╲
//!         ┃ ╱││╲  ╱││╲  ╱││╲  ╱││╲ ◀─── Block Leaf
//!                                       = Note Commitment
//! ```

#![deny(clippy::unwrap_used)]
#![warn(missing_docs, rustdoc::broken_intra_doc_links)]
#![cfg_attr(docsrs, feature(doc_auto_cfg))]

#[macro_use]
extern crate derivative;

#[macro_use]
extern crate serde;

#[macro_use]
extern crate tracing;

#[macro_use]
extern crate thiserror;

#[macro_use]
extern crate async_trait;

mod commitment;
mod index;
mod proof;
mod random;
mod tree;
mod witness;

pub mod error;
pub mod storage;
pub mod structure;
pub mod validate;

#[doc(inline)]
pub use {
    commitment::StateCommitment,
    internal::hash::Forgotten,
    internal::hash::DOMAIN_SEPARATOR,
    proof::Proof,
    tree::{Position, Root, Tree},
    witness::Witness,
};

#[cfg(any(doc, feature = "internal"))]
pub mod internal;
#[cfg(not(any(doc, feature = "internal")))]
mod internal;

#[cfg(feature = "r1cs")]
pub mod r1cs;

pub mod builder {
    //! Builders for individual epochs and blocks: useful when constructing a [`Tree`](super::Tree)
    //! in parallel, but unnecessary in a single thread.

    pub mod epoch {
        //! Build individual epochs to insert into [`Tree`](super::super::Tree)s.
        pub use crate::tree::epoch::*;
    }

    pub mod block {
        //! Build individual blocks to insert into [`epoch::Builder`](super::epoch::Builder)s or
        //! [`Tree`](super::super::Tree)s.
        pub use crate::tree::epoch::block::*;
    }
}

// A crate-internal prelude to make things easier to import
mod prelude {
    pub(crate) use super::{
        error::proof::VerifyError,
        index,
        internal::{
            complete::{self, Complete, ForgetOwned, OutOfOrderOwned},
            frontier::{
                self, Focus, Forget, Frontier, Full, GetPosition, Insert, InsertMut, Item,
                OutOfOrder,
            },
            hash::{CachedHash, Forgotten, GetHash, Hash, OptionHash},
            height::{Height, IsHeight, Succ, Zero},
            interface::Witness,
            path::{self, AuthPath, Path, WhichWay},
            three::{Elems, ElemsMut, IntoElems, Three},
            UncheckedSetHash,
        },
        storage::{
            self, AsyncRead, AsyncWrite, DeleteRange, Read, StoreCommitment, StoreHash,
            StoredPosition, Update, Write,
        },
        structure::{self, HashOrNode, HashedNode, Kind, Node, Place},
        Position, Proof, Root, StateCommitment, Tree,
    };

    // We use the hash map from `im`, but with the fast "hash prehashed data" hasher from `hash_hasher`
    pub(crate) type HashedMap<K, V> = im::HashMap<K, V, hash_hasher::HashBuildHasher>;
}

#[cfg(feature = "arbitrary")]
/// Generation of random [`Commitment`]s for testing.
pub mod proptest {
    #[doc(inline)]
    pub use super::commitment::FqStrategy;
}

#[cfg(test)]
mod test {
    #[test]
    fn check_eternity_size() {
        // Disabled due to spurious test failure.
        // static_assertions::assert_eq_size!(Tree, [u8; 32]);
    }

    #[test]
    fn check_eternity_proof_size() {
        // Disabled due to spurious test failure.
        // static_assertions::assert_eq_size!(Proof, [u8; 2344]);
    }
}