warg_transparency/log/
mod.rs

1//! Immutable Log w/ Inclusion and Consistency Proofs
2//!
3//! The main trait in this module is [`VerifiableLog`],
4//! which defines the API of a log where inclusion
5//! and consistency can be verified.
6//!
7//! Implementations:
8//! * [`InOrderLog`] -
9//!
10//! The only implementation in this module is ,
11//! which is a [`VerifiableLog`] whose contents are structured
12//! using binary in-order interval numbering as described in
13//! [Dat - Distributed Dataset Synchronization and Versioning][2].
14
15mod node;
16/// Logic for constructing and validating proofs
17mod proof;
18mod proof_bundle;
19mod sparse_data;
20mod stack_log;
21mod vec_log;
22
23use warg_crypto::{
24    hash::{Hash, SupportedDigest},
25    VisitBytes,
26};
27
28pub use node::{Node, Side};
29pub use proof::{
30    ConsistencyProof, ConsistencyProofError, InclusionProof, InclusionProofError,
31    InclusionProofWalk,
32};
33pub use proof_bundle::ProofBundle;
34pub use proof_bundle::ProofBundle as LogProofBundle;
35pub use stack_log::StackLog;
36pub use vec_log::VecLog;
37
38/// A [merkle tree][0] log data type based on [DAT][1].
39/// where the merkle tree computation is conformant to
40/// [RFC 6962 - Certificate Transparency][2]. This allows
41/// you to efficiently append data and then verify that
42/// it the log is consistent over time and contains a
43/// given entry.
44///
45/// It represents its data using binary in-order interval numbering.
46/// This means that all of the leaf and balanced branch nodes of the tree
47/// are stored in one contiguous array using a particular indexing scheme.
48///
49/// ## Example
50/// ```text
51/// 0 X \
52/// 1    X
53/// 2 X / \
54/// 3      X
55/// 4 X \ /
56/// 5    X
57/// 6 X /
58/// ```
59///
60/// ## Properties
61/// This has various convenient properties for traversing the structure.
62/// * The height of a node is the number of trailing ones in its index.
63/// * For the above reason, leaves always have even indices.
64/// * The side (left/right) of a node can be computed from its index.
65/// * The distance between parent/child indices is a simple function of height.
66///
67/// [0]: https://en.wikipedia.org/wiki/Merkle_tree
68/// [1]: https://www.researchgate.net/publication/326120012_Dat_-_Distributed_Dataset_Synchronization_And_Versioning
69/// [2]: https://www.rfc-editor.org/rfc/rfc6962
70pub trait LogBuilder<D, V>
71where
72    D: SupportedDigest,
73    V: VisitBytes,
74{
75    /// Get the checkpoint (hash and length) of the log at this point.
76    fn checkpoint(&self) -> Checkpoint<D>;
77
78    /// Push a new entry into the log.
79    fn push(&mut self, entry: &V) -> Node;
80}
81
82/// A point in the history of a log, represented by its length
83#[derive(Debug, Clone, PartialOrd, Ord)]
84pub struct Checkpoint<D>
85where
86    D: SupportedDigest,
87{
88    root: Hash<D>,
89    length: usize,
90}
91
92impl<D> Checkpoint<D>
93where
94    D: SupportedDigest,
95{
96    /// The root hash of the log at this checkpoint
97    pub fn root(&self) -> Hash<D> {
98        self.root.clone()
99    }
100
101    /// The length of the log at this checkpoint
102    pub fn length(&self) -> usize {
103        self.length
104    }
105}
106
107impl<D> Eq for Checkpoint<D> where D: SupportedDigest {}
108
109impl<D> PartialEq for Checkpoint<D>
110where
111    D: SupportedDigest,
112{
113    fn eq(&self, other: &Self) -> bool {
114        self.root == other.root && self.length == other.length
115    }
116}
117
118/// A collection of hash data
119pub trait LogData<D, V>
120where
121    D: SupportedDigest,
122    V: VisitBytes,
123{
124    /// Does this hash exist in the collection?
125    fn has_hash(&self, node: Node) -> bool;
126
127    /// Get the hash for a given node
128    /// None if node does not yet exist
129    fn hash_for(&self, node: Node) -> Option<Hash<D>>;
130
131    /// Construct an inclusion proof for this log
132    fn prove_inclusion(&self, leaf: Node, log_length: usize) -> InclusionProof<D, V> {
133        InclusionProof::new(leaf, log_length)
134    }
135
136    /// Construct a consistency proof for this log
137    fn prove_consistency(&self, old_length: usize, new_length: usize) -> ConsistencyProof<D, V> {
138        ConsistencyProof::new(old_length, new_length)
139    }
140}
141
142/// Compute the hash for an empty tree using a given Digest algorithm.
143pub(crate) fn hash_empty<D: SupportedDigest>() -> Hash<D> {
144    Hash::of(())
145}
146
147/// Compute the hash for a leaf in a tree using a given Digest algorithm.
148pub(crate) fn hash_leaf<D: SupportedDigest>(data: impl VisitBytes) -> Hash<D> {
149    let input = (0u8, data);
150    Hash::of(&input)
151}
152
153/// Compute the hash for a branch in a tree using a given Digest algorithm.
154pub(crate) fn hash_branch<D: SupportedDigest>(
155    left: impl VisitBytes,
156    right: impl VisitBytes,
157) -> Hash<D> {
158    let input = (1u8, left, right);
159    Hash::of(&input)
160}
warg_transparency/log/mod.rs

warg_transparency/log/
mod.rs
