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
31mod checkpoint;
32pub use checkpoint::{
33    CHECKPOINT_CONTEXT, Checkpoint, MAX_NOTE_BYTES, MAX_ORIGIN_BYTES, NoteSignature, SignedNote,
34    key_id,
35};
36
37/// RFC 6962 domain separators.
38const LEAF_PREFIX: u8 = 0x00;
39const NODE_PREFIX: u8 = 0x01;
40
41/// Refuse an absurd proof before allocating for it. A path longer than this
42/// implies a log with more entries than could ever be built.
43const MAX_PROOF_LEN: usize = 64;
44
45pub type Hash = [u8; 32];
46
47#[derive(Debug, Error, PartialEq, Eq)]
48pub enum LogError {
49    #[error("the log is empty")]
50    Empty,
51    #[error("entry {index} is not in a log of size {size}")]
52    OutOfRange { index: u64, size: u64 },
53    #[error("a log of size {old} cannot be a prefix of one of size {new}")]
54    NotAPrefix { old: u64, new: u64 },
55    #[error("the proof does not verify")]
56    BadProof,
57    #[error("a proof of {0} hashes exceeds the limit")]
58    ProofTooLong(usize),
59    #[error("the encoding is malformed")]
60    Malformed,
61    #[error("the checkpoint is not signed by the expected log key")]
62    Unsigned,
63    #[error("a signature from the expected log key does not verify")]
64    BadSignature,
65    #[error("the checkpoint names origin {found:?}, not the expected one")]
66    WrongOrigin { found: String },
67}
68
69/// Labels of the two leaf types this specification defines (§16.3). The
70/// leaves carry links, never encoded logs, so a legacy log and its 1.0
71/// re-encoding (same links, different bytes) are one leaf, not two (§15.9).
72const IDENTITY_LEAF_LABEL: &[u8] = b"HIDE/1.0 identity leaf";
73const EPOCH_LEAF_LABEL: &[u8] = b"HIDE/1.0 epoch leaf";
74
75/// The leaf that logs one state of an identity: which identity (its root
76/// link), which recovery key it binds (by device id), and which history (the
77/// head link and entry count).
78pub fn identity_leaf(root: &Hash, recovery_id: &Hash, head: &Hash, entries: u64) -> Vec<u8> {
79    let mut out = Vec::with_capacity(IDENTITY_LEAF_LABEL.len() + 104);
80    out.extend_from_slice(IDENTITY_LEAF_LABEL);
81    out.extend_from_slice(root);
82    out.extend_from_slice(recovery_id);
83    out.extend_from_slice(head);
84    out.extend_from_slice(&entries.to_be_bytes());
85    out
86}
87
88/// The leaf that logs one state of an identity's epoch chain.
89pub fn epoch_leaf(identity_root: &Hash, chain_head: &Hash, epochs: u64) -> Vec<u8> {
90    let mut out = Vec::with_capacity(EPOCH_LEAF_LABEL.len() + 72);
91    out.extend_from_slice(EPOCH_LEAF_LABEL);
92    out.extend_from_slice(identity_root);
93    out.extend_from_slice(chain_head);
94    out.extend_from_slice(&epochs.to_be_bytes());
95    out
96}
97
98const INCLUSION_TAG: u8 = 0x01;
99const CONSISTENCY_TAG: u8 = 0x02;
100/// tag(1) || u64 || u64 || count(1)
101const PROOF_HEADER: usize = 18;
102
103fn encode_proof(tag: u8, first: u64, second: u64, path: &[Hash]) -> Result<Vec<u8>, LogError> {
104    if path.len() > MAX_PROOF_LEN {
105        return Err(LogError::ProofTooLong(path.len()));
106    }
107    let mut out = Vec::with_capacity(PROOF_HEADER + 32 * path.len());
108    out.push(tag);
109    out.extend_from_slice(&first.to_be_bytes());
110    out.extend_from_slice(&second.to_be_bytes());
111    out.push(path.len() as u8);
112    for hash in path {
113        out.extend_from_slice(hash);
114    }
115    Ok(out)
116}
117
118/// Fixed layout, so every field has one encoding and no re-encode check is
119/// needed: the count is checked against the limit and the exact length before
120/// anything is copied.
121fn decode_proof(tag: u8, bytes: &[u8]) -> Result<(u64, u64, Vec<Hash>), LogError> {
122    if bytes.len() < PROOF_HEADER || bytes[0] != tag {
123        return Err(LogError::Malformed);
124    }
125    let first = u64::from_be_bytes(bytes[1..9].try_into().map_err(|_| LogError::Malformed)?);
126    let second = u64::from_be_bytes(bytes[9..17].try_into().map_err(|_| LogError::Malformed)?);
127    let count = usize::from(bytes[17]);
128    if count > MAX_PROOF_LEN {
129        return Err(LogError::ProofTooLong(count));
130    }
131    if bytes.len() != PROOF_HEADER + 32 * count {
132        return Err(LogError::Malformed);
133    }
134    let path = bytes[PROOF_HEADER..]
135        .chunks_exact(32)
136        .map(|chunk| chunk.try_into().map_err(|_| LogError::Malformed))
137        .collect::<Result<Vec<Hash>, _>>()?;
138    Ok((first, second, path))
139}
140
141impl InclusionProof {
142    /// `0x01 || u64be(index) || u64be(size) || u8(n) || n × hash` (§16.3).
143    pub fn encode(&self) -> Result<Vec<u8>, LogError> {
144        encode_proof(INCLUSION_TAG, self.index, self.size, &self.path)
145    }
146
147    pub fn decode(bytes: &[u8]) -> Result<Self, LogError> {
148        let (index, size, path) = decode_proof(INCLUSION_TAG, bytes)?;
149        Ok(Self { index, size, path })
150    }
151}
152
153impl ConsistencyProof {
154    /// `0x02 || u64be(old_size) || u64be(new_size) || u8(n) || n × hash` (§16.3).
155    pub fn encode(&self) -> Result<Vec<u8>, LogError> {
156        encode_proof(CONSISTENCY_TAG, self.old_size, self.new_size, &self.path)
157    }
158
159    pub fn decode(bytes: &[u8]) -> Result<Self, LogError> {
160        let (old_size, new_size, path) = decode_proof(CONSISTENCY_TAG, bytes)?;
161        Ok(Self {
162            old_size,
163            new_size,
164            path,
165        })
166    }
167}
168
169/// Hashes a leaf. The prefix is what stops a leaf being read as a node.
170pub fn leaf_hash(data: &[u8]) -> Hash {
171    let mut hasher = Sha256::new();
172    hasher.update([LEAF_PREFIX]);
173    hasher.update(data);
174    hasher.finalize().into()
175}
176
177fn node_hash(left: &Hash, right: &Hash) -> Hash {
178    let mut hasher = Sha256::new();
179    hasher.update([NODE_PREFIX]);
180    hasher.update(left);
181    hasher.update(right);
182    hasher.finalize().into()
183}
184
185/// The root of a subtree covering `leaves`, per RFC 6962 §2.1.
186fn root_of(leaves: &[Hash]) -> Hash {
187    match leaves.len() {
188        // The empty tree is the hash of nothing, so an empty log still has a
189        // well-defined root rather than a special case at every call site.
190        0 => Sha256::digest(b"").into(),
191        1 => leaves[0],
192        n => {
193            let split = largest_power_of_two_below(n as u64) as usize;
194            node_hash(&root_of(&leaves[..split]), &root_of(&leaves[split..]))
195        }
196    }
197}
198
199/// RFC 6962 splits at the largest power of two strictly less than `n`, which is
200/// what makes a tree's shape depend only on its size. Computed from the bit
201/// length rather than by shifting a probe upward: for `n > 2^63` the probe
202/// wraps to zero and a shift loop never terminates, and `n` comes from an
203/// untrusted proof.
204fn largest_power_of_two_below(n: u64) -> u64 {
205    debug_assert!(n > 1);
206    1 << (n - 1).ilog2()
207}
208
209/// Proof that one entry is in the log at a given size.
210#[derive(Debug, Clone, PartialEq, Eq)]
211pub struct InclusionProof {
212    pub index: u64,
213    pub size: u64,
214    pub path: Vec<Hash>,
215}
216
217/// Proof that a smaller log is a prefix of a larger one.
218#[derive(Debug, Clone, PartialEq, Eq)]
219pub struct ConsistencyProof {
220    pub old_size: u64,
221    pub new_size: u64,
222    pub path: Vec<Hash>,
223}
224
225/// The log itself. Holds leaf hashes only: the entries are the caller's.
226#[derive(Debug, Default, Clone)]
227pub struct TransparencyLog {
228    leaves: Vec<Hash>,
229}
230
231impl TransparencyLog {
232    pub fn new() -> Self {
233        Self::default()
234    }
235
236    /// Appends an entry, returning its index.
237    pub fn append(&mut self, data: &[u8]) -> u64 {
238        let index = self.leaves.len() as u64;
239        self.leaves.push(leaf_hash(data));
240        index
241    }
242
243    pub fn len(&self) -> u64 {
244        self.leaves.len() as u64
245    }
246
247    pub fn is_empty(&self) -> bool {
248        self.leaves.is_empty()
249    }
250
251    /// The root commitment for the whole log.
252    pub fn root(&self) -> Hash {
253        root_of(&self.leaves)
254    }
255
256    /// The root the log had when it held `size` entries. A log can always
257    /// re-derive its own past roots, which is what lets it answer an audit.
258    pub fn root_at(&self, size: u64) -> Result<Hash, LogError> {
259        if size > self.len() {
260            return Err(LogError::OutOfRange {
261                index: size,
262                size: self.len(),
263            });
264        }
265        Ok(root_of(&self.leaves[..size as usize]))
266    }
267
268    /// An audit path for `index` in the log as it stands at `size`.
269    pub fn prove_inclusion(&self, index: u64, size: u64) -> Result<InclusionProof, LogError> {
270        if size > self.len() || index >= size {
271            return Err(LogError::OutOfRange { index, size });
272        }
273        let mut path = Vec::new();
274        collect_inclusion(&self.leaves[..size as usize], index as usize, &mut path);
275        Ok(InclusionProof { index, size, path })
276    }
277
278    /// A proof that the log of `old_size` is a prefix of the log of `new_size`.
279    pub fn prove_consistency(
280        &self,
281        old_size: u64,
282        new_size: u64,
283    ) -> Result<ConsistencyProof, LogError> {
284        if new_size > self.len() {
285            return Err(LogError::OutOfRange {
286                index: new_size,
287                size: self.len(),
288            });
289        }
290        if old_size > new_size || old_size == 0 {
291            return Err(LogError::NotAPrefix {
292                old: old_size,
293                new: new_size,
294            });
295        }
296        let mut path = Vec::new();
297        collect_consistency(
298            &self.leaves[..new_size as usize],
299            old_size as usize,
300            true,
301            &mut path,
302        );
303        Ok(ConsistencyProof {
304            old_size,
305            new_size,
306            path,
307        })
308    }
309}
310
311fn collect_inclusion(leaves: &[Hash], index: usize, path: &mut Vec<Hash>) {
312    if leaves.len() <= 1 {
313        return;
314    }
315    let split = largest_power_of_two_below(leaves.len() as u64) as usize;
316    if index < split {
317        collect_inclusion(&leaves[..split], index, path);
318        path.push(root_of(&leaves[split..]));
319    } else {
320        collect_inclusion(&leaves[split..], index - split, path);
321        path.push(root_of(&leaves[..split]));
322    }
323}
324
325/// RFC 6962 §2.1.2. `complete` tracks whether the old tree is exactly the
326/// subtree being considered, which decides whether its root must be sent.
327fn collect_consistency(leaves: &[Hash], old: usize, complete: bool, path: &mut Vec<Hash>) {
328    if old == leaves.len() {
329        if !complete {
330            path.push(root_of(leaves));
331        }
332        return;
333    }
334    let split = largest_power_of_two_below(leaves.len() as u64) as usize;
335    if old <= split {
336        collect_consistency(&leaves[..split], old, complete, path);
337        path.push(root_of(&leaves[split..]));
338    } else {
339        collect_consistency(&leaves[split..], old - split, false, path);
340        path.push(root_of(&leaves[..split]));
341    }
342}
343
344/// Checks an audit path against a root. The verifier holds only the root, the
345/// entry, and the proof — never the log.
346pub fn verify_inclusion(proof: &InclusionProof, leaf: &Hash, root: &Hash) -> Result<(), LogError> {
347    if proof.path.len() > MAX_PROOF_LEN {
348        return Err(LogError::ProofTooLong(proof.path.len()));
349    }
350    if proof.index >= proof.size {
351        return Err(LogError::OutOfRange {
352            index: proof.index,
353            size: proof.size,
354        });
355    }
356
357    // Descend to the leaf first, recording which side each step took. The
358    // prover pushes siblings on the way back up, so the path is deepest-first
359    // and must be consumed in that order.
360    let mut turns = Vec::new();
361    let mut index = proof.index;
362    let mut size = proof.size;
363    while size > 1 {
364        let split = largest_power_of_two_below(size);
365        if index < split {
366            turns.push(true);
367            size = split;
368        } else {
369            turns.push(false);
370            index -= split;
371            size -= split;
372        }
373    }
374
375    if turns.len() != proof.path.len() {
376        return Err(LogError::BadProof);
377    }
378
379    let mut hash = *leaf;
380    for (sibling, went_left) in proof.path.iter().zip(turns.iter().rev()) {
381        hash = if *went_left {
382            node_hash(&hash, sibling)
383        } else {
384            node_hash(sibling, &hash)
385        };
386    }
387
388    if hash != *root {
389        return Err(LogError::BadProof);
390    }
391    Ok(())
392}
393
394/// Checks that `old_root` really is the root the log had before it grew to
395/// `new_root`. This is the check that catches a rewritten history.
396pub fn verify_consistency(
397    proof: &ConsistencyProof,
398    old_root: &Hash,
399    new_root: &Hash,
400) -> Result<(), LogError> {
401    if proof.path.len() > MAX_PROOF_LEN {
402        return Err(LogError::ProofTooLong(proof.path.len()));
403    }
404    if proof.old_size == 0 || proof.old_size > proof.new_size {
405        return Err(LogError::NotAPrefix {
406            old: proof.old_size,
407            new: proof.new_size,
408        });
409    }
410
411    // Nothing grew, so the roots must simply match and no path is needed.
412    if proof.old_size == proof.new_size {
413        return if proof.path.is_empty() && old_root == new_root {
414            Ok(())
415        } else {
416            Err(LogError::BadProof)
417        };
418    }
419
420    // Record the descent, mirroring how the prover recurses, so the two walks
421    // agree on which sibling belongs at which level. `complete` says whether
422    // the old log is exactly this subtree, in which case its root is not sent.
423    let mut turns = Vec::new();
424    let mut old_size = proof.old_size;
425    let mut new_size = proof.new_size;
426    let mut complete = true;
427    while old_size != new_size {
428        let split = largest_power_of_two_below(new_size);
429        if old_size <= split {
430            turns.push(true);
431            new_size = split;
432        } else {
433            turns.push(false);
434            old_size -= split;
435            new_size -= split;
436            complete = false;
437        }
438    }
439
440    // The prover pushes the subtree root here only when the old log is not a
441    // complete subtree of the new one.
442    let expected = turns.len() + usize::from(!complete);
443    if proof.path.len() != expected {
444        return Err(LogError::BadProof);
445    }
446
447    let mut path = proof.path.iter();
448    let seed = if complete {
449        *old_root
450    } else {
451        *path.next().ok_or(LogError::BadProof)?
452    };
453    let mut old_hash = seed;
454    let mut new_hash = seed;
455
456    for (sibling, went_left) in path.zip(turns.iter().rev()) {
457        if *went_left {
458            new_hash = node_hash(&new_hash, sibling);
459        } else {
460            old_hash = node_hash(sibling, &old_hash);
461            new_hash = node_hash(sibling, &new_hash);
462        }
463    }
464
465    if old_hash != *old_root || new_hash != *new_root {
466        return Err(LogError::BadProof);
467    }
468    Ok(())
469}
470
471/// Encodes a root for publication: size and hash together, because a hash with
472/// no size is not a commitment to anything checkable.
473pub fn encode_checkpoint(size: u64, root: &Hash) -> Vec<u8> {
474    let mut out = Vec::with_capacity(40);
475    out.extend_from_slice(&size.to_be_bytes());
476    out.extend_from_slice(root);
477    out
478}
479
480pub fn decode_checkpoint(bytes: &[u8]) -> Result<(u64, Hash), LogError> {
481    if bytes.len() != 40 {
482        return Err(LogError::Malformed);
483    }
484    let size = u64::from_be_bytes(bytes[..8].try_into().map_err(|_| LogError::Malformed)?);
485    let root: Hash = bytes[8..].try_into().map_err(|_| LogError::Malformed)?;
486    Ok((size, root))
487}