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