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}