1use 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
37const LEAF_PREFIX: u8 = 0x00;
39const NODE_PREFIX: u8 = 0x01;
40
41const 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
69const IDENTITY_LEAF_LABEL: &[u8] = b"HIDE/1.0 identity leaf";
73const EPOCH_LEAF_LABEL: &[u8] = b"HIDE/1.0 epoch leaf";
74
75pub 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
88pub 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;
100const 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
118fn 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 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 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
169pub 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
185fn root_of(leaves: &[Hash]) -> Hash {
187 match leaves.len() {
188 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
199fn largest_power_of_two_below(n: u64) -> u64 {
205 debug_assert!(n > 1);
206 1 << (n - 1).ilog2()
207}
208
209#[derive(Debug, Clone, PartialEq, Eq)]
211pub struct InclusionProof {
212 pub index: u64,
213 pub size: u64,
214 pub path: Vec<Hash>,
215}
216
217#[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#[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 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 pub fn root(&self) -> Hash {
253 root_of(&self.leaves)
254 }
255
256 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 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 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
325fn 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
344pub 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 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
394pub 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 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 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 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
471pub 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}