Skip to main content

publet_algorithms/
log.rs

1//! Append-only Merkle log with inclusion and consistency proofs.
2//!
3//! Follows the algorithms of [RFC 6962] so that the constructions are
4//! specified elsewhere and independently testable, rather than being an
5//! invention of this project. Domain-separating leaf hashes (`0x00`) from
6//! interior hashes (`0x01`) is what prevents a leaf from being presented as
7//! an interior node, which would otherwise let one tree claim two shapes.
8//!
9//! [RFC 6962]: https://www.rfc-editor.org/rfc/rfc6962#section-2
10//!
11//! The log's leaves are successive membership roots, so a consistency proof
12//! establishes that generation *m* is a prefix of generation *n*: that
13//! nothing recorded earlier was rewritten.
14
15use sha2::{Digest as _, Sha256};
16
17/// A 32-byte digest.
18pub type Hash = [u8; 32];
19
20/// Hash of an empty tree, per RFC 6962: `HASH()`.
21///
22/// # Example
23///
24/// ```
25/// use publet_algorithms::log::{empty_root, root, to_hex};
26///
27/// assert_eq!(root(&[]), empty_root());
28/// // SHA-256 of nothing, as RFC 6962 defines it.
29/// assert_eq!(
30///     to_hex(&empty_root()),
31///     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
32/// );
33/// ```
34#[must_use]
35pub fn empty_root() -> Hash {
36    Sha256::digest([]).into()
37}
38
39/// Leaf hash: `HASH(0x00 || leaf)`.
40///
41/// # Example
42///
43/// ```
44/// use publet_algorithms::log::{leaf_hash, to_hex};
45///
46/// assert_eq!(
47///     to_hex(&leaf_hash(b"a")),
48///     "022a6979e6dab7aa5ae4c3e5e45f7e977112a7e63593820dbec1ec738a24f93c",
49/// );
50/// ```
51#[must_use]
52pub fn leaf_hash(leaf: &[u8]) -> Hash {
53    let mut h = Sha256::new();
54    h.update([0x00]);
55    h.update(leaf);
56    h.finalize().into()
57}
58
59/// Interior hash: `HASH(0x01 || left || right)`.
60///
61/// # Example
62///
63/// ```
64/// use publet_algorithms::log::{leaf_hash, node_hash, root};
65///
66/// let (a, b) = (leaf_hash(b"a"), leaf_hash(b"b"));
67/// assert_eq!(node_hash(&a, &b), root(&[a, b]));
68/// // Order matters: a log is a sequence.
69/// assert_ne!(node_hash(&a, &b), node_hash(&b, &a));
70/// ```
71#[must_use]
72pub fn node_hash(left: &Hash, right: &Hash) -> Hash {
73    let mut h = Sha256::new();
74    h.update([0x01]);
75    h.update(left);
76    h.update(right);
77    h.finalize().into()
78}
79
80/// Largest power of two strictly less than `n`.
81///
82/// RFC 6962's split point. Defined for `n > 1`.
83fn split(n: u64) -> u64 {
84    debug_assert!(n > 1);
85    // The largest power of two strictly below n is the top bit of n - 1.
86    // Doubling up to it instead never ends for n above 2^63: the shift
87    // wraps to zero, and a peer's proof claiming such a size would hang
88    // the verifier.
89    1 << (u64::BITS - 1 - (n - 1).leading_zeros())
90}
91
92/// [`split`] for a number of leaves held in memory.
93fn split_len(n: usize) -> usize {
94    debug_assert!(n > 1);
95    1 << (usize::BITS - 1 - (n - 1).leading_zeros())
96}
97
98/// Merkle Tree Hash over `leaves`, already leaf-hashed.
99///
100/// # Example
101///
102/// ```
103/// use publet_algorithms::log::{leaf_hash, root, to_hex};
104///
105/// let leaves = [leaf_hash(b"a"), leaf_hash(b"b")];
106/// assert_eq!(
107///     to_hex(&root(&leaves)),
108///     "b137985ff484fb600db93107c77b0365c80d78f5b429ded0fd97361d077999eb",
109/// );
110/// ```
111#[must_use]
112pub fn root(leaves: &[Hash]) -> Hash {
113    match leaves.len() {
114        0 => empty_root(),
115        1 => leaves.first().copied().unwrap_or_else(empty_root),
116        n => {
117            let k = split_len(n);
118            let (left, right) = leaves.split_at(k);
119            node_hash(&root(left), &root(right))
120        }
121    }
122}
123
124/// Audit path proving `index` is in a tree of `leaves.len()` leaves.
125///
126/// # Example
127///
128/// ```
129/// use publet_algorithms::log::{Hash, inclusion_proof, leaf_hash, root, verify_inclusion};
130///
131/// # let leaves: Vec<Hash> = ["a", "b", "c"].iter().map(|e| leaf_hash(e.as_bytes())).collect();
132/// let path = inclusion_proof(&leaves, 2);
133/// assert!(verify_inclusion(&leaves[2], 2, leaves.len() as u64, &path, &root(&leaves)));
134/// ```
135#[must_use]
136pub fn inclusion_proof(leaves: &[Hash], index: usize) -> Vec<Hash> {
137    let n = leaves.len();
138    if index >= n {
139        return Vec::new();
140    }
141    if n == 1 {
142        return Vec::new();
143    }
144    let k = split_len(n);
145    let (left, right) = leaves.split_at(k);
146    if index < k {
147        let mut path = inclusion_proof(left, index);
148        path.push(root(right));
149        path
150    } else {
151        let mut path = inclusion_proof(right, index - k);
152        path.push(root(left));
153        path
154    }
155}
156
157/// Render a hash as lower-case hexadecimal.
158///
159/// # Example
160///
161/// ```
162/// use publet_algorithms::log::to_hex;
163///
164/// assert_eq!(to_hex(&[0xab; 32]), "ab".repeat(32));
165/// ```
166#[must_use]
167pub fn to_hex(hash: &Hash) -> String {
168    use std::fmt::Write as _;
169    hash.iter()
170        .fold(String::with_capacity(64), |mut acc, byte| {
171            let _ = write!(acc, "{byte:02x}");
172            acc
173        })
174}
175
176/// Whether the node carrying the leaf is the left or right child.
177enum Side {
178    Left,
179    Right,
180}
181
182/// Recompute a root from a leaf and its audit path.
183///
184/// [`inclusion_proof`] emits the path from the leaf upward, as RFC 6962
185/// specifies. Which side each sibling belongs on is only known by
186/// descending from the root, so the descent is done first and the sides are
187/// then applied in reverse against the path.
188///
189/// `index` and `size` are `u64`, as RFC 6962's tree sizes are, on every
190/// target: they come with a proof from someone else, whose log may be
191/// larger than this machine's `usize`. A 32-bit or `wasm32` verifier
192/// checks a proof for a log of any size.
193///
194/// # Example
195///
196/// ```
197/// use publet_algorithms::log::{Hash, inclusion_proof, leaf_hash, root, verify_inclusion};
198///
199/// # let leaves: Vec<Hash> = ["a", "b", "c"].iter().map(|e| leaf_hash(e.as_bytes())).collect();
200/// let head = root(&leaves);
201/// let path = inclusion_proof(&leaves, 1);
202/// assert!(verify_inclusion(&leaves[1], 1, 3, &path, &head));
203/// // The same path does not prove a different entry, or a different position.
204/// assert!(!verify_inclusion(&leaf_hash(b"forged"), 1, 3, &path, &head));
205/// assert!(!verify_inclusion(&leaves[1], 0, 3, &path, &head));
206/// ```
207#[must_use]
208pub fn verify_inclusion(
209    leaf: &Hash,
210    index: u64,
211    size: u64,
212    path: &[Hash],
213    expected_root: &Hash,
214) -> bool {
215    if index >= size || size == 0 {
216        return false;
217    }
218
219    let mut sides = Vec::new();
220    let (mut idx, mut sz) = (index, size);
221    while sz > 1 {
222        let k = split(sz);
223        if idx < k {
224            sides.push(Side::Left);
225            sz = k;
226        } else {
227            sides.push(Side::Right);
228            idx -= k;
229            sz -= k;
230        }
231    }
232
233    if sides.len() != path.len() {
234        return false;
235    }
236
237    let mut computed = *leaf;
238    for (sibling, side) in path.iter().zip(sides.iter().rev()) {
239        computed = match side {
240            Side::Left => node_hash(&computed, sibling),
241            Side::Right => node_hash(sibling, &computed),
242        };
243    }
244    computed == *expected_root
245}
246
247/// Proof that a tree of `m` leaves is a prefix of one of `leaves.len()`.
248///
249/// # Example
250///
251/// ```
252/// use publet_algorithms::log::{Hash, consistency_proof, leaf_hash, root, verify_consistency};
253///
254/// # let leaves: Vec<Hash> = ["a", "b", "c"].iter().map(|e| leaf_hash(e.as_bytes())).collect();
255/// // The first two entries form a log that the three-entry log extends.
256/// let proof = consistency_proof(&leaves, 2);
257/// assert!(verify_consistency(2, 3, &root(&leaves[..2]), &root(&leaves), &proof));
258/// ```
259#[must_use]
260pub fn consistency_proof(leaves: &[Hash], m: usize) -> Vec<Hash> {
261    let n = leaves.len();
262    if m == 0 || m > n {
263        return Vec::new();
264    }
265    if m == n {
266        return Vec::new();
267    }
268    subproof(leaves, m, true)
269}
270
271fn subproof(leaves: &[Hash], m: usize, start: bool) -> Vec<Hash> {
272    let n = leaves.len();
273    if m == n {
274        if start {
275            return Vec::new();
276        }
277        return vec![root(leaves)];
278    }
279    let k = split_len(n);
280    let (left, right) = leaves.split_at(k);
281    if m <= k {
282        let mut path = subproof(left, m, start);
283        path.push(root(right));
284        path
285    } else {
286        let mut path = subproof(right, m - k, false);
287        path.push(root(left));
288        path
289    }
290}
291
292/// Decompose an inclusion path into its inner and border parts.
293///
294/// `inner` counts the levels where the path turns, `border` the levels
295/// above where it only ever folds right. Naming them is what lets a
296/// consistency proof be checked without rebuilding either tree.
297fn decompose(index: u64, size: u64) -> (u32, u32) {
298    let inner = u64::BITS - (index ^ (size - 1)).leading_zeros();
299    // `inner` reaches 64 when the size is above 2^63, and shifting a u64 by
300    // 64 overflows: a panic where overflow is checked, a wrong answer where
301    // it is not. Every bit is then inside, so none is on the border.
302    let border = index.checked_shr(inner).unwrap_or(0).count_ones();
303    (inner, border)
304}
305
306fn chain_inner(seed: Hash, path: &[Hash], index: u64) -> Hash {
307    let mut acc = seed;
308    for (i, sibling) in path.iter().enumerate() {
309        acc = if (index >> i) & 1 == 0 {
310            node_hash(&acc, sibling)
311        } else {
312            node_hash(sibling, &acc)
313        };
314    }
315    acc
316}
317
318/// As [`chain_inner`], but folding only where the path turns right.
319fn chain_inner_right(seed: Hash, path: &[Hash], index: u64) -> Hash {
320    let mut acc = seed;
321    for (i, sibling) in path.iter().enumerate() {
322        if (index >> i) & 1 == 1 {
323            acc = node_hash(sibling, &acc);
324        }
325    }
326    acc
327}
328
329fn chain_border_right(seed: Hash, path: &[Hash]) -> Hash {
330    path.iter()
331        .fold(seed, |acc, sibling| node_hash(sibling, &acc))
332}
333
334/// Verify that `old_root` at size `m` is a prefix of `new_root` at size `n`.
335///
336/// This is the reconstruction of RFC 6962 section 2.1.2: the proof is split
337/// into an inner and a border part, each folded in turn, yielding both roots
338/// from one path. Getting it wrong is not visible in ordinary use -- proofs
339/// would simply always fail, or worse, always pass -- so the round-trip
340/// tests exercise every `(m, n)` pair rather than a sample.
341///
342/// The sizes are `u64` on every target, for the reason
343/// [`verify_inclusion`]'s are.
344///
345/// # Example
346///
347/// ```
348/// use publet_algorithms::log::{Hash, consistency_proof, leaf_hash, root, verify_consistency};
349///
350/// # let leaves: Vec<Hash> = ["a", "b", "c"].iter().map(|e| leaf_hash(e.as_bytes())).collect();
351/// let old = root(&leaves[..2]);
352/// let proof = consistency_proof(&leaves, 2);
353/// assert!(verify_consistency(2, 3, &old, &root(&leaves), &proof));
354///
355/// // A log that rewrote its history is not consistent with what was seen before.
356/// let rewritten: Vec<Hash> = ["a", "B", "c"].iter().map(|e| leaf_hash(e.as_bytes())).collect();
357/// assert!(!verify_consistency(2, 3, &old, &root(&rewritten), &consistency_proof(&rewritten, 2)));
358/// ```
359#[must_use]
360pub fn verify_consistency(
361    m: u64,
362    n: u64,
363    old_root: &Hash,
364    new_root: &Hash,
365    proof: &[Hash],
366) -> bool {
367    if m > n {
368        return false;
369    }
370    if m == n {
371        return proof.is_empty() && old_root == new_root;
372    }
373    if m == 0 {
374        // Every tree contains the empty prefix.
375        return proof.is_empty();
376    }
377    if proof.is_empty() {
378        return false;
379    }
380
381    let (mut inner, border) = decompose(m - 1, n);
382    let shift = m.trailing_zeros();
383    inner -= shift;
384
385    // When `m` is an exact power of two the old root is the seed and is not
386    // carried in the proof; otherwise the proof supplies it.
387    let (seed, start) = if m == 1u64 << shift {
388        (*old_root, 0usize)
389    } else {
390        match proof.first() {
391            Some(h) => (*h, 1usize),
392            None => return false,
393        }
394    };
395
396    let expected = start + inner as usize + border as usize;
397    if proof.len() != expected {
398        return false;
399    }
400    let Some(rest) = proof.get(start..) else {
401        return false;
402    };
403    let Some(inner_part) = rest.get(..inner as usize) else {
404        return false;
405    };
406    let Some(border_part) = rest.get(inner as usize..) else {
407        return false;
408    };
409
410    let mask = (m - 1) >> shift;
411    let recomputed_old = chain_border_right(chain_inner_right(seed, inner_part, mask), border_part);
412    let recomputed_new = chain_border_right(chain_inner(seed, inner_part, mask), border_part);
413
414    recomputed_old == *old_root && recomputed_new == *new_root
415}
416
417/// Checkpoint origins for a client catching up to `head`.
418///
419/// Exponentially spaced, so a client far behind is covered in O(log n)
420/// fetches rather than one per entry.
421///
422/// # Example
423///
424/// ```
425/// use publet_algorithms::log::checkpoints;
426///
427/// // Behind a head at 100: entries 1, 2, 4, 8, ... back from it.
428/// assert_eq!(checkpoints(100), [36, 68, 84, 92, 96, 98, 99]);
429/// ```
430#[must_use]
431pub fn checkpoints(head: u64) -> Vec<u64> {
432    let mut out = Vec::new();
433    let mut step = 1u64;
434    while step <= head {
435        out.push(head - step);
436        step = step.saturating_mul(2);
437    }
438    out.sort_unstable();
439    out.dedup();
440    out
441}
442
443/// How many fetches a client at `current` needs to reach `head`.
444///
445/// With checkpoints at every power of two behind the head, a client greedily
446/// takes the largest jump that does not overshoot. The distance is therefore
447/// covered in one fetch per set bit -- `count_ones`, which is bounded by
448/// `log2(distance) + 1` and never exceeds 64.
449///
450/// # Example
451///
452/// ```
453/// use publet_algorithms::log::fetches_required;
454///
455/// // 0 to 300 is a distance with four set bits, so four fetches.
456/// assert_eq!(fetches_required(0, 300), 4);
457/// assert_eq!(fetches_required(300, 300), 0);
458/// ```
459#[must_use]
460pub fn fetches_required(current: u64, head: u64) -> u32 {
461    if current >= head {
462        return 0;
463    }
464    (head - current).count_ones()
465}