Skip to main content

deedar/
log.rs

1//! An append-only Merkle log over the deeds a store has issued, hashed as
2//! RFC 9162 (doi:10.17487/RFC9162): leaf `SHA-256(0x00 || entry)`, node
3//! `SHA-256(0x01 || left || right)`. Inclusion proofs catch a dropped deed;
4//! consistency proofs catch a rewritten log. Signatures alone bind neither.
5//! Gossip lives outside this file. Two consistent logs shown to two readers
6//! both verify here.
7
8use sha2::{Digest, Sha256};
9
10use deed::{Error, Result};
11
12/// One entry: the deed's content address and the instant it was logged.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Entry {
15    /// The deed's accession.
16    pub id: String,
17    /// `sha256:` of the canonical deed bytes.
18    pub digest: String,
19    /// Seconds since the epoch, as the evidence records them.
20    pub unix_time: u64,
21}
22
23impl Entry {
24    /// The bytes a leaf hashes over: tab-separated, fixed order.
25    #[must_use]
26    pub fn material(&self) -> Vec<u8> {
27        format!("{}\t{}\t{}", self.id, self.digest, self.unix_time).into_bytes()
28    }
29
30    /// The line this entry is stored as.
31    #[must_use]
32    pub fn line(&self) -> String {
33        format!("{}\t{}\t{}\n", self.id, self.digest, self.unix_time)
34    }
35
36    /// Parse one stored line.
37    ///
38    /// # Errors
39    ///
40    /// Fails when the line is not three tab-separated fields with a numeric time.
41    pub fn parse(line: &str) -> Result<Self> {
42        let mut parts = line.trim_end_matches('\n').split('\t');
43        let (Some(id), Some(digest), Some(time), None) =
44            (parts.next(), parts.next(), parts.next(), parts.next())
45        else {
46            return Err(Error::Io(format!("log: not an entry: {line:?}")));
47        };
48        let unix_time = time
49            .parse()
50            .map_err(|_| Error::Io(format!("log: not a time: {time:?}")))?;
51        Ok(Self {
52            id: id.to_string(),
53            digest: digest.to_string(),
54            unix_time,
55        })
56    }
57}
58
59/// Leaf hash, `SHA-256(0x00 || entry)`.
60#[must_use]
61pub fn leaf_hash(material: &[u8]) -> [u8; 32] {
62    let mut hasher = Sha256::new();
63    hasher.update([0x00]);
64    hasher.update(material);
65    hasher.finalize().into()
66}
67
68/// Interior hash, `SHA-256(0x01 || left || right)`.
69#[must_use]
70pub fn node_hash(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
71    let mut hasher = Sha256::new();
72    hasher.update([0x01]);
73    hasher.update(left);
74    hasher.update(right);
75    hasher.finalize().into()
76}
77
78/// The Merkle root over `leaves`, RFC 9162 section 2.1: the tree splits at
79/// the largest power of two below the width, which is the shape the proofs
80/// below are sound over.
81#[must_use]
82pub fn root(leaves: &[[u8; 32]]) -> [u8; 32] {
83    match leaves {
84        [] => Sha256::digest([]).into(),
85        [one] => *one,
86        _ => {
87            let split = split_point(leaves.len());
88            node_hash(&root(&leaves[..split]), &root(&leaves[split..]))
89        }
90    }
91}
92
93/// The largest power of two strictly below `width`, which is where a tree of
94/// that width divides.
95fn split_point(width: usize) -> usize {
96    let mut split = 1usize;
97    while split * 2 < width {
98        split *= 2;
99    }
100    split
101}
102
103/// What a store publishes: how many entries it has, and the root over them.
104#[derive(Debug, Clone, PartialEq, Eq)]
105pub struct Head {
106    /// Number of entries the root covers.
107    pub size: usize,
108    /// Merkle root, hex.
109    pub root: String,
110}
111
112impl Head {
113    /// The head over a set of leaves.
114    #[must_use]
115    pub fn over(leaves: &[[u8; 32]]) -> Self {
116        Self {
117            size: leaves.len(),
118            root: hex(&root(leaves)),
119        }
120    }
121
122    /// The bytes a signature covers.
123    #[must_use]
124    pub fn material(&self) -> Vec<u8> {
125        format!("deedar-log-v1\t{}\t{}", self.size, self.root).into_bytes()
126    }
127}
128
129/// The audit path for the leaf at `index`, RFC 9162 section 2.1.3: sibling
130/// subtree roots, innermost first.
131#[must_use]
132pub fn inclusion_proof(leaves: &[[u8; 32]], index: usize) -> Option<Vec<[u8; 32]>> {
133    if index >= leaves.len() {
134        return None;
135    }
136    if leaves.len() == 1 {
137        return Some(Vec::new());
138    }
139    let split = split_point(leaves.len());
140    Some(if index < split {
141        let mut path = inclusion_proof(&leaves[..split], index)?;
142        path.push(root(&leaves[split..]));
143        path
144    } else {
145        let mut path = inclusion_proof(&leaves[split..], index - split)?;
146        path.push(root(&leaves[..split]));
147        path
148    })
149}
150
151/// Whether `leaf` sits at `index` of a tree of `size` leaves with that root.
152#[must_use]
153pub fn verify_inclusion(
154    leaf: &[u8; 32],
155    index: usize,
156    size: usize,
157    path: &[[u8; 32]],
158    root_hex: &str,
159) -> bool {
160    if index >= size {
161        return false;
162    }
163    let mut hash = *leaf;
164    let (mut at, mut last) = (index, size - 1);
165    let mut steps = path.iter();
166    while last > 0 {
167        let Some(step) = steps.next() else {
168            return false;
169        };
170        // A right-hand node, or the last node at this level, joins from the
171        // left; anything else joins from the right.
172        if at % 2 == 1 || at == last {
173            hash = node_hash(step, &hash);
174            while at != 0 && at % 2 == 0 {
175                at /= 2;
176                last /= 2;
177            }
178        } else {
179            hash = node_hash(&hash, step);
180        }
181        at /= 2;
182        last /= 2;
183    }
184    steps.next().is_none() && hex(&hash) == root_hex
185}
186
187/// The consistency proof that a tree of `old` leaves is a prefix of these,
188/// RFC 9162 section 2.1.4. The nodes recompute both roots; a rewritten log
189/// cannot produce a set that yields both. `None` when `old` is zero or wider
190/// than the tree.
191#[must_use]
192pub fn consistency_proof(leaves: &[[u8; 32]], old: usize) -> Option<Vec<[u8; 32]>> {
193    if old == 0 || old > leaves.len() {
194        return None;
195    }
196    Some(subproof(leaves, old, true))
197}
198
199/// The RFC's SUBPROOF. `known` is whether the reader already holds the root of
200/// the subtree being described, which is true exactly when it is the old tree
201/// itself and so never needs sending.
202fn subproof(leaves: &[[u8; 32]], old: usize, known: bool) -> Vec<[u8; 32]> {
203    if old == leaves.len() {
204        return if known {
205            Vec::new()
206        } else {
207            vec![root(leaves)]
208        };
209    }
210    let split = split_point(leaves.len());
211    if old <= split {
212        let mut path = subproof(&leaves[..split], old, known);
213        path.push(root(&leaves[split..]));
214        path
215    } else {
216        let mut path = subproof(&leaves[split..], old - split, false);
217        path.push(root(&leaves[..split]));
218        path
219    }
220}
221
222/// Whether the tree of `old` leaves with `old_root` is a prefix of the tree of
223/// `new` leaves with `new_root`; both roots are recomputed from `nodes`.
224#[must_use]
225pub fn verify_consistency(
226    old: usize,
227    old_root: &str,
228    new: usize,
229    new_root: &str,
230    path: &[[u8; 32]],
231) -> bool {
232    if old == 0 || old > new {
233        return false;
234    }
235    if old == new {
236        // Nothing was added, so there is nothing to send and the two heads
237        // have to be the same head.
238        return path.is_empty() && old_root == new_root;
239    }
240    // When the old tree is a whole subtree its root was never sent, because
241    // the reader is the one holding it.
242    let (seed, rest) = if old.is_power_of_two() {
243        let Some(seed) = from_hex(old_root) else {
244            return false;
245        };
246        (seed, path)
247    } else {
248        let Some((head, rest)) = path.split_first() else {
249            return false;
250        };
251        (*head, rest)
252    };
253
254    let (mut at, mut last) = (old - 1, new - 1);
255    while at % 2 == 1 {
256        at /= 2;
257        last /= 2;
258    }
259    let (mut from_old, mut from_new) = (seed, seed);
260    for step in rest {
261        if last == 0 {
262            return false;
263        }
264        if at % 2 == 1 || at == last {
265            from_old = node_hash(step, &from_old);
266            from_new = node_hash(step, &from_new);
267            while at != 0 && at % 2 == 0 {
268                at /= 2;
269                last /= 2;
270            }
271        } else {
272            from_new = node_hash(&from_new, step);
273        }
274        at /= 2;
275        last /= 2;
276    }
277    last == 0 && hex(&from_old) == old_root && hex(&from_new) == new_root
278}
279
280/// A 32 byte hash from the lower-case hex [`hex`] writes. Any other text
281/// yields nothing.
282#[must_use]
283pub fn from_hex(text: &str) -> Option<[u8; 32]> {
284    // `from_str_radix` alone also reads `+b` as `0b` and `B` as `b`, so a
285    // proof with a changed byte would still check.
286    if text.len() != 64 || !text.bytes().all(|b| matches!(b, b'0'..=b'9' | b'a'..=b'f')) {
287        return None;
288    }
289    let mut out = [0u8; 32];
290    for (slot, pair) in out.iter_mut().zip(text.as_bytes().chunks_exact(2)) {
291        let pair = std::str::from_utf8(pair).ok()?;
292        *slot = u8::from_str_radix(pair, 16).ok()?;
293    }
294    Some(out)
295}
296
297/// Hex, lower case, fixed width.
298#[must_use]
299pub fn hex(bytes: &[u8]) -> String {
300    bytes.iter().map(|b| format!("{b:02x}")).collect()
301}
302
303#[cfg(test)]
304mod tests {
305    use super::*;
306
307    fn leaves(n: usize) -> Vec<[u8; 32]> {
308        (0..n)
309            .map(|i| leaf_hash(format!("deed-{i}").as_bytes()))
310            .collect()
311    }
312
313    /// A leaf and a node hash differently over the same bytes, which is what
314    /// stops a leaf being presented as an interior node.
315    #[test]
316    fn a_leaf_is_not_a_node() {
317        let left = leaf_hash(b"a");
318        let right = leaf_hash(b"b");
319        let parent = node_hash(&left, &right);
320        let mut joined = Vec::new();
321        joined.extend_from_slice(&left);
322        joined.extend_from_slice(&right);
323        assert_ne!(parent, leaf_hash(&joined));
324    }
325
326    /// Every leaf proves in, at every tree size, including the odd ones where
327    /// a node is carried up a level with no sibling.
328    #[test]
329    fn every_leaf_proves_in() {
330        for size in 1..=33usize {
331            let set = leaves(size);
332            let head = Head::over(&set);
333            assert_eq!(head.size, size);
334            for index in 0..size {
335                let path = inclusion_proof(&set, index).expect("a path");
336                assert!(
337                    verify_inclusion(&set[index], index, size, &path, &head.root),
338                    "size {size} index {index}"
339                );
340            }
341        }
342    }
343
344    /// The proof is for one leaf at one place. A verifier that accepted it for
345    /// another would be checking nothing.
346    #[test]
347    fn a_proof_does_not_travel() {
348        let set = leaves(8);
349        let head = Head::over(&set);
350        let path = inclusion_proof(&set, 3).expect("a path");
351        assert!(verify_inclusion(&set[3], 3, 8, &path, &head.root));
352        // Same path, different leaf.
353        assert!(!verify_inclusion(&set[4], 3, 8, &path, &head.root));
354        // Same leaf, different place.
355        assert!(!verify_inclusion(&set[3], 4, 8, &path, &head.root));
356        // Same everything, a root the store did not publish.
357        assert!(!verify_inclusion(&set[3], 3, 8, &path, &"0".repeat(64)));
358        // A truncated path leaves the hash short of the root.
359        assert!(!verify_inclusion(&set[3], 3, 8, &path[..2], &head.root));
360    }
361
362    /// Every prefix of every tree up to the bound proves it is a prefix.
363    #[test]
364    fn every_prefix_proves_it_is_one() {
365        for new in 1..=33usize {
366            let all = leaves(new);
367            let later = Head::over(&all);
368            for old in 1..=new {
369                let earlier = Head::over(&all[..old]);
370                let path = consistency_proof(&all, old).expect("a proof");
371                assert!(
372                    verify_consistency(old, &earlier.root, new, &later.root, &path),
373                    "size {old} is not proving a prefix of {new}"
374                );
375            }
376        }
377    }
378
379    /// A log rewritten wholesale passes inclusion and fails consistency.
380    #[test]
381    fn a_rewritten_log_cannot_extend_the_head_it_replaced() {
382        let honest = leaves(8);
383        let published = Head::over(&honest);
384
385        // The store drops what it published at index 2 and appends two more,
386        // so the tree is the same width it would honestly have been.
387        let mut rewritten: Vec<[u8; 32]> = honest.clone();
388        rewritten.remove(2);
389        rewritten.push(leaf_hash(b"deed-8"));
390        rewritten.push(leaf_hash(b"deed-9"));
391        let now = Head::over(&rewritten);
392
393        // Inclusion against the new head is fine for everything in it, which
394        // is exactly why inclusion alone does not answer this.
395        let path = inclusion_proof(&rewritten, 0).expect("a path");
396        assert!(verify_inclusion(
397            &rewritten[0],
398            0,
399            now.size,
400            &path,
401            &now.root
402        ));
403
404        // Consistency is not: no proof the store can offer makes the head it
405        // published an ancestor of the one it publishes now.
406        let offered = consistency_proof(&rewritten, published.size).expect("a proof");
407        assert!(
408            !verify_consistency(
409                published.size,
410                &published.root,
411                now.size,
412                &now.root,
413                &offered
414            ),
415            "a rewritten log passed as an extension"
416        );
417    }
418
419    /// A proof for one pair of heads does not check another, and a shortened
420    /// or padded one does not check at all.
421    #[test]
422    fn a_consistency_proof_does_not_travel() {
423        let all = leaves(12);
424        let later = Head::over(&all);
425        let earlier = Head::over(&all[..5]);
426        let path = consistency_proof(&all, 5).expect("a proof");
427        assert!(verify_consistency(5, &earlier.root, 12, &later.root, &path));
428
429        // A different old size.
430        let other = Head::over(&all[..6]);
431        assert!(!verify_consistency(6, &other.root, 12, &later.root, &path));
432        // A root nobody published.
433        assert!(!verify_consistency(
434            5,
435            &"0".repeat(64),
436            12,
437            &later.root,
438            &path
439        ));
440        // Truncated, and padded.
441        assert!(!verify_consistency(
442            5,
443            &earlier.root,
444            12,
445            &later.root,
446            &path[..1]
447        ));
448        let mut padded = path.clone();
449        padded.push([0u8; 32]);
450        assert!(!verify_consistency(
451            5,
452            &earlier.root,
453            12,
454            &later.root,
455            &padded
456        ));
457        // Backwards is not a prefix.
458        assert!(!verify_consistency(
459            12,
460            &later.root,
461            5,
462            &earlier.root,
463            &path
464        ));
465        // And an empty tree has no prefix to speak of.
466        assert!(consistency_proof(&all, 0).is_none());
467        assert!(consistency_proof(&all, 13).is_none());
468    }
469
470    /// Dropping a deed changes the root, which is the whole point: a store
471    /// that removes one cannot publish a head that still covers it.
472    #[test]
473    fn removing_an_entry_moves_the_root() {
474        let set = leaves(6);
475        let full = Head::over(&set);
476        let mut short = set.clone();
477        short.remove(2);
478        let missing = Head::over(&short);
479        assert_ne!(full.root, missing.root);
480        assert_ne!(full.size, missing.size);
481        // And the proof the store issued before the removal no longer checks.
482        let path = inclusion_proof(&set, 2).expect("a path");
483        assert!(!verify_inclusion(
484            &set[2],
485            2,
486            short.len(),
487            &path,
488            &missing.root
489        ));
490    }
491
492    /// An entry round-trips through the line the log stores it as, and a line
493    /// that is not an entry is refused rather than skipped.
494    #[test]
495    fn an_entry_round_trips_and_a_bad_line_is_refused() {
496        let entry = Entry {
497            id: "deed-file-note".into(),
498            digest: "sha256:abc".into(),
499            unix_time: 1_757_000_000,
500        };
501        let back = Entry::parse(&entry.line()).expect("parses");
502        assert_eq!(back, entry);
503        assert!(Entry::parse("two\tfields\n").is_err());
504        assert!(Entry::parse("a\tb\tnot-a-time\n").is_err());
505        assert!(Entry::parse("a\tb\t1\tc\n").is_err());
506    }
507
508    /// The empty tree has a defined root rather than a panic, because a store
509    /// publishes a head before it holds anything.
510    #[test]
511    fn an_empty_log_still_has_a_head() {
512        let head = Head::over(&[]);
513        assert_eq!(head.size, 0);
514        assert_eq!(head.root.len(), 64);
515        assert!(inclusion_proof(&[], 0).is_none());
516    }
517}