Skip to main content

hide_transparency/
lib.rs

1//! An append-only log whose history cannot be rewritten without detection.
2//!
3//! A signature proves who wrote something; it cannot prove that everyone was
4//! shown the *same* something. That is what this is for. The log publishes one
5//! 32-byte root per size, and answers two questions:
6//!
7//! - **Inclusion**: "is this entry in the log of size *n*?" — an audit path of
8//!   about log₂(n) hashes.
9//! - **Consistency**: "is the log of size *m* a prefix of the log of size *n*?"
10//!   — the proof that nothing already published was altered or removed.
11//!
12//! Consistency is the one that matters. Without it a server can show one
13//! history to a victim and another to everyone else; with it, doing so requires
14//! producing two roots for one size, which is permanent, transferable evidence
15//! of misbehaviour.
16//!
17//! The hashing follows RFC 6962: leaves are prefixed `0x00` and internal nodes
18//! `0x01`, so a leaf can never be reinterpreted as a node — the second-preimage
19//! attack that an unprefixed Merkle tree allows.
20//!
21//! # What a log cannot do by itself
22//!
23//! It cannot detect a *split view* on its own: two divergent logs are each
24//! internally consistent. Catching that needs witnesses — independent parties
25//! who gossip roots and refuse to sign two roots for one size. Nothing here
26//! implements witnessing, and a log without it is a promise, not a proof.
27
28use sha2::{Digest, Sha256};
29use thiserror::Error;
30
31/// RFC 6962 domain separators.
32const LEAF_PREFIX: u8 = 0x00;
33const NODE_PREFIX: u8 = 0x01;
34
35/// Refuse an absurd proof before allocating for it. A path longer than this
36/// implies a log with more entries than could ever be built.
37const MAX_PROOF_LEN: usize = 64;
38
39pub type Hash = [u8; 32];
40
41#[derive(Debug, Error, PartialEq, Eq)]
42pub enum LogError {
43    #[error("the log is empty")]
44    Empty,
45    #[error("entry {index} is not in a log of size {size}")]
46    OutOfRange { index: u64, size: u64 },
47    #[error("a log of size {old} cannot be a prefix of one of size {new}")]
48    NotAPrefix { old: u64, new: u64 },
49    #[error("the proof does not verify")]
50    BadProof,
51    #[error("a proof of {0} hashes exceeds the limit")]
52    ProofTooLong(usize),
53    #[error("the encoding is malformed")]
54    Malformed,
55}
56
57/// Hashes a leaf. The prefix is what stops a leaf being read as a node.
58pub fn leaf_hash(data: &[u8]) -> Hash {
59    let mut hasher = Sha256::new();
60    hasher.update([LEAF_PREFIX]);
61    hasher.update(data);
62    hasher.finalize().into()
63}
64
65fn node_hash(left: &Hash, right: &Hash) -> Hash {
66    let mut hasher = Sha256::new();
67    hasher.update([NODE_PREFIX]);
68    hasher.update(left);
69    hasher.update(right);
70    hasher.finalize().into()
71}
72
73/// The root of a subtree covering `leaves`, per RFC 6962 §2.1.
74fn root_of(leaves: &[Hash]) -> Hash {
75    match leaves.len() {
76        // The empty tree is the hash of nothing, so an empty log still has a
77        // well-defined root rather than a special case at every call site.
78        0 => Sha256::digest(b"").into(),
79        1 => leaves[0],
80        n => {
81            let split = largest_power_of_two_below(n);
82            node_hash(&root_of(&leaves[..split]), &root_of(&leaves[split..]))
83        }
84    }
85}
86
87/// RFC 6962 splits at the largest power of two strictly less than `n`, which is
88/// what makes a tree's shape depend only on its size.
89fn largest_power_of_two_below(n: usize) -> usize {
90    debug_assert!(n > 1);
91    let mut split = 1;
92    while split << 1 < n {
93        split <<= 1;
94    }
95    split
96}
97
98/// Proof that one entry is in the log at a given size.
99#[derive(Debug, Clone, PartialEq, Eq)]
100pub struct InclusionProof {
101    pub index: u64,
102    pub size: u64,
103    pub path: Vec<Hash>,
104}
105
106/// Proof that a smaller log is a prefix of a larger one.
107#[derive(Debug, Clone, PartialEq, Eq)]
108pub struct ConsistencyProof {
109    pub old_size: u64,
110    pub new_size: u64,
111    pub path: Vec<Hash>,
112}
113
114/// The log itself. Holds leaf hashes only: the entries are the caller's.
115#[derive(Debug, Default, Clone)]
116pub struct TransparencyLog {
117    leaves: Vec<Hash>,
118}
119
120impl TransparencyLog {
121    pub fn new() -> Self {
122        Self::default()
123    }
124
125    /// Appends an entry, returning its index.
126    pub fn append(&mut self, data: &[u8]) -> u64 {
127        let index = self.leaves.len() as u64;
128        self.leaves.push(leaf_hash(data));
129        index
130    }
131
132    pub fn len(&self) -> u64 {
133        self.leaves.len() as u64
134    }
135
136    pub fn is_empty(&self) -> bool {
137        self.leaves.is_empty()
138    }
139
140    /// The root commitment for the whole log.
141    pub fn root(&self) -> Hash {
142        root_of(&self.leaves)
143    }
144
145    /// The root the log had when it held `size` entries. A log can always
146    /// re-derive its own past roots, which is what lets it answer an audit.
147    pub fn root_at(&self, size: u64) -> Result<Hash, LogError> {
148        if size > self.len() {
149            return Err(LogError::OutOfRange {
150                index: size,
151                size: self.len(),
152            });
153        }
154        Ok(root_of(&self.leaves[..size as usize]))
155    }
156
157    /// An audit path for `index` in the log as it stands at `size`.
158    pub fn prove_inclusion(&self, index: u64, size: u64) -> Result<InclusionProof, LogError> {
159        if size > self.len() || index >= size {
160            return Err(LogError::OutOfRange { index, size });
161        }
162        let mut path = Vec::new();
163        collect_inclusion(&self.leaves[..size as usize], index as usize, &mut path);
164        Ok(InclusionProof { index, size, path })
165    }
166
167    /// A proof that the log of `old_size` is a prefix of the log of `new_size`.
168    pub fn prove_consistency(
169        &self,
170        old_size: u64,
171        new_size: u64,
172    ) -> Result<ConsistencyProof, LogError> {
173        if new_size > self.len() {
174            return Err(LogError::OutOfRange {
175                index: new_size,
176                size: self.len(),
177            });
178        }
179        if old_size > new_size || old_size == 0 {
180            return Err(LogError::NotAPrefix {
181                old: old_size,
182                new: new_size,
183            });
184        }
185        let mut path = Vec::new();
186        collect_consistency(
187            &self.leaves[..new_size as usize],
188            old_size as usize,
189            true,
190            &mut path,
191        );
192        Ok(ConsistencyProof {
193            old_size,
194            new_size,
195            path,
196        })
197    }
198}
199
200fn collect_inclusion(leaves: &[Hash], index: usize, path: &mut Vec<Hash>) {
201    if leaves.len() <= 1 {
202        return;
203    }
204    let split = largest_power_of_two_below(leaves.len());
205    if index < split {
206        collect_inclusion(&leaves[..split], index, path);
207        path.push(root_of(&leaves[split..]));
208    } else {
209        collect_inclusion(&leaves[split..], index - split, path);
210        path.push(root_of(&leaves[..split]));
211    }
212}
213
214/// RFC 6962 §2.1.2. `complete` tracks whether the old tree is exactly the
215/// subtree being considered, which decides whether its root must be sent.
216fn collect_consistency(leaves: &[Hash], old: usize, complete: bool, path: &mut Vec<Hash>) {
217    if old == leaves.len() {
218        if !complete {
219            path.push(root_of(leaves));
220        }
221        return;
222    }
223    let split = largest_power_of_two_below(leaves.len());
224    if old <= split {
225        collect_consistency(&leaves[..split], old, complete, path);
226        path.push(root_of(&leaves[split..]));
227    } else {
228        collect_consistency(&leaves[split..], old - split, false, path);
229        path.push(root_of(&leaves[..split]));
230    }
231}
232
233/// Checks an audit path against a root. The verifier holds only the root, the
234/// entry, and the proof — never the log.
235pub fn verify_inclusion(proof: &InclusionProof, leaf: &Hash, root: &Hash) -> Result<(), LogError> {
236    if proof.path.len() > MAX_PROOF_LEN {
237        return Err(LogError::ProofTooLong(proof.path.len()));
238    }
239    if proof.index >= proof.size {
240        return Err(LogError::OutOfRange {
241            index: proof.index,
242            size: proof.size,
243        });
244    }
245
246    // Descend to the leaf first, recording which side each step took. The
247    // prover pushes siblings on the way back up, so the path is deepest-first
248    // and must be consumed in that order.
249    let mut turns = Vec::new();
250    let mut index = proof.index;
251    let mut size = proof.size;
252    while size > 1 {
253        let split = largest_power_of_two_below(size as usize) as u64;
254        if index < split {
255            turns.push(true);
256            size = split;
257        } else {
258            turns.push(false);
259            index -= split;
260            size -= split;
261        }
262    }
263
264    if turns.len() != proof.path.len() {
265        return Err(LogError::BadProof);
266    }
267
268    let mut hash = *leaf;
269    for (sibling, went_left) in proof.path.iter().zip(turns.iter().rev()) {
270        hash = if *went_left {
271            node_hash(&hash, sibling)
272        } else {
273            node_hash(sibling, &hash)
274        };
275    }
276
277    if hash != *root {
278        return Err(LogError::BadProof);
279    }
280    Ok(())
281}
282
283/// Checks that `old_root` really is the root the log had before it grew to
284/// `new_root`. This is the check that catches a rewritten history.
285pub fn verify_consistency(
286    proof: &ConsistencyProof,
287    old_root: &Hash,
288    new_root: &Hash,
289) -> Result<(), LogError> {
290    if proof.path.len() > MAX_PROOF_LEN {
291        return Err(LogError::ProofTooLong(proof.path.len()));
292    }
293    if proof.old_size == 0 || proof.old_size > proof.new_size {
294        return Err(LogError::NotAPrefix {
295            old: proof.old_size,
296            new: proof.new_size,
297        });
298    }
299
300    // Nothing grew, so the roots must simply match and no path is needed.
301    if proof.old_size == proof.new_size {
302        return if proof.path.is_empty() && old_root == new_root {
303            Ok(())
304        } else {
305            Err(LogError::BadProof)
306        };
307    }
308
309    // Record the descent, mirroring how the prover recurses, so the two walks
310    // agree on which sibling belongs at which level. `complete` says whether
311    // the old log is exactly this subtree, in which case its root is not sent.
312    let mut turns = Vec::new();
313    let mut old_size = proof.old_size;
314    let mut new_size = proof.new_size;
315    let mut complete = true;
316    while old_size != new_size {
317        let split = largest_power_of_two_below(new_size as usize) as u64;
318        if old_size <= split {
319            turns.push(true);
320            new_size = split;
321        } else {
322            turns.push(false);
323            old_size -= split;
324            new_size -= split;
325            complete = false;
326        }
327    }
328
329    // The prover pushes the subtree root here only when the old log is not a
330    // complete subtree of the new one.
331    let expected = turns.len() + usize::from(!complete);
332    if proof.path.len() != expected {
333        return Err(LogError::BadProof);
334    }
335
336    let mut path = proof.path.iter();
337    let seed = if complete {
338        *old_root
339    } else {
340        *path.next().ok_or(LogError::BadProof)?
341    };
342    let mut old_hash = seed;
343    let mut new_hash = seed;
344
345    for (sibling, went_left) in path.zip(turns.iter().rev()) {
346        if *went_left {
347            new_hash = node_hash(&new_hash, sibling);
348        } else {
349            old_hash = node_hash(sibling, &old_hash);
350            new_hash = node_hash(sibling, &new_hash);
351        }
352    }
353
354    if old_hash != *old_root || new_hash != *new_root {
355        return Err(LogError::BadProof);
356    }
357    Ok(())
358}
359
360/// Encodes a root for publication: size and hash together, because a hash with
361/// no size is not a commitment to anything checkable.
362pub fn encode_checkpoint(size: u64, root: &Hash) -> Vec<u8> {
363    let mut out = Vec::with_capacity(40);
364    out.extend_from_slice(&size.to_be_bytes());
365    out.extend_from_slice(root);
366    out
367}
368
369pub fn decode_checkpoint(bytes: &[u8]) -> Result<(u64, Hash), LogError> {
370    if bytes.len() != 40 {
371        return Err(LogError::Malformed);
372    }
373    let size = u64::from_be_bytes(bytes[..8].try_into().map_err(|_| LogError::Malformed)?);
374    let root: Hash = bytes[8..].try_into().map_err(|_| LogError::Malformed)?;
375    Ok((size, root))
376}