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
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
44const LEAF_PREFIX: u8 = 0x00;
46const NODE_PREFIX: u8 = 0x01;
47
48const 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
76const IDENTITY_LEAF_LABEL: &[u8] = b"HIDE/1.0 identity leaf";
80const EPOCH_LEAF_LABEL: &[u8] = b"HIDE/1.0 epoch leaf";
81
82pub 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
95pub 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;
107const 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
125fn 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 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 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
176pub 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
192fn root_of(leaves: &[Hash]) -> Hash {
194 match leaves.len() {
195 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
206fn largest_power_of_two_below(n: u64) -> u64 {
212 debug_assert!(n > 1);
213 1 << (n - 1).ilog2()
214}
215
216#[derive(Debug, Clone, PartialEq, Eq)]
218pub struct InclusionProof {
219 pub index: u64,
220 pub size: u64,
221 pub path: Vec<Hash>,
222}
223
224#[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#[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 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 pub fn root(&self) -> Hash {
260 root_of(&self.leaves)
261 }
262
263 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 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 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
332fn 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
351pub 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 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
401pub 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 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 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 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
478pub 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}