1use sha2::{Digest, Sha256};
9
10use deed::{Error, Result};
11
12#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Entry {
15 pub id: String,
17 pub digest: String,
19 pub unix_time: u64,
21}
22
23impl Entry {
24 #[must_use]
26 pub fn material(&self) -> Vec<u8> {
27 format!("{}\t{}\t{}", self.id, self.digest, self.unix_time).into_bytes()
28 }
29
30 #[must_use]
32 pub fn line(&self) -> String {
33 format!("{}\t{}\t{}\n", self.id, self.digest, self.unix_time)
34 }
35
36 pub fn parse(line: &str) -> Result<Self> {
42 let mut parts = line.trim_end_matches('\n').split('\t');
43 let (Some(id), Some(digest), Some(time), None) =
44 (parts.next(), parts.next(), parts.next(), parts.next())
45 else {
46 return Err(Error::Io(format!("log: not an entry: {line:?}")));
47 };
48 let unix_time = time
49 .parse()
50 .map_err(|_| Error::Io(format!("log: not a time: {time:?}")))?;
51 Ok(Self {
52 id: id.to_string(),
53 digest: digest.to_string(),
54 unix_time,
55 })
56 }
57}
58
59#[must_use]
61pub fn leaf_hash(material: &[u8]) -> [u8; 32] {
62 let mut hasher = Sha256::new();
63 hasher.update([0x00]);
64 hasher.update(material);
65 hasher.finalize().into()
66}
67
68#[must_use]
70pub fn node_hash(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
71 let mut hasher = Sha256::new();
72 hasher.update([0x01]);
73 hasher.update(left);
74 hasher.update(right);
75 hasher.finalize().into()
76}
77
78#[must_use]
82pub fn root(leaves: &[[u8; 32]]) -> [u8; 32] {
83 match leaves {
84 [] => Sha256::digest([]).into(),
85 [one] => *one,
86 _ => {
87 let split = split_point(leaves.len());
88 node_hash(&root(&leaves[..split]), &root(&leaves[split..]))
89 }
90 }
91}
92
93fn split_point(width: usize) -> usize {
96 let mut split = 1usize;
97 while split * 2 < width {
98 split *= 2;
99 }
100 split
101}
102
103#[derive(Debug, Clone, PartialEq, Eq)]
105pub struct Head {
106 pub size: usize,
108 pub root: String,
110}
111
112impl Head {
113 #[must_use]
115 pub fn over(leaves: &[[u8; 32]]) -> Self {
116 Self {
117 size: leaves.len(),
118 root: hex(&root(leaves)),
119 }
120 }
121
122 #[must_use]
124 pub fn material(&self) -> Vec<u8> {
125 format!("deedar-log-v1\t{}\t{}", self.size, self.root).into_bytes()
126 }
127}
128
129#[must_use]
132pub fn inclusion_proof(leaves: &[[u8; 32]], index: usize) -> Option<Vec<[u8; 32]>> {
133 if index >= leaves.len() {
134 return None;
135 }
136 if leaves.len() == 1 {
137 return Some(Vec::new());
138 }
139 let split = split_point(leaves.len());
140 Some(if index < split {
141 let mut path = inclusion_proof(&leaves[..split], index)?;
142 path.push(root(&leaves[split..]));
143 path
144 } else {
145 let mut path = inclusion_proof(&leaves[split..], index - split)?;
146 path.push(root(&leaves[..split]));
147 path
148 })
149}
150
151#[must_use]
153pub fn verify_inclusion(
154 leaf: &[u8; 32],
155 index: usize,
156 size: usize,
157 path: &[[u8; 32]],
158 root_hex: &str,
159) -> bool {
160 if index >= size {
161 return false;
162 }
163 let mut hash = *leaf;
164 let (mut at, mut last) = (index, size - 1);
165 let mut steps = path.iter();
166 while last > 0 {
167 let Some(step) = steps.next() else {
168 return false;
169 };
170 if at % 2 == 1 || at == last {
173 hash = node_hash(step, &hash);
174 while at != 0 && at % 2 == 0 {
175 at /= 2;
176 last /= 2;
177 }
178 } else {
179 hash = node_hash(&hash, step);
180 }
181 at /= 2;
182 last /= 2;
183 }
184 steps.next().is_none() && hex(&hash) == root_hex
185}
186
187#[must_use]
192pub fn consistency_proof(leaves: &[[u8; 32]], old: usize) -> Option<Vec<[u8; 32]>> {
193 if old == 0 || old > leaves.len() {
194 return None;
195 }
196 Some(subproof(leaves, old, true))
197}
198
199fn subproof(leaves: &[[u8; 32]], old: usize, known: bool) -> Vec<[u8; 32]> {
203 if old == leaves.len() {
204 return if known {
205 Vec::new()
206 } else {
207 vec![root(leaves)]
208 };
209 }
210 let split = split_point(leaves.len());
211 if old <= split {
212 let mut path = subproof(&leaves[..split], old, known);
213 path.push(root(&leaves[split..]));
214 path
215 } else {
216 let mut path = subproof(&leaves[split..], old - split, false);
217 path.push(root(&leaves[..split]));
218 path
219 }
220}
221
222#[must_use]
225pub fn verify_consistency(
226 old: usize,
227 old_root: &str,
228 new: usize,
229 new_root: &str,
230 path: &[[u8; 32]],
231) -> bool {
232 if old == 0 || old > new {
233 return false;
234 }
235 if old == new {
236 return path.is_empty() && old_root == new_root;
239 }
240 let (seed, rest) = if old.is_power_of_two() {
243 let Some(seed) = from_hex(old_root) else {
244 return false;
245 };
246 (seed, path)
247 } else {
248 let Some((head, rest)) = path.split_first() else {
249 return false;
250 };
251 (*head, rest)
252 };
253
254 let (mut at, mut last) = (old - 1, new - 1);
255 while at % 2 == 1 {
256 at /= 2;
257 last /= 2;
258 }
259 let (mut from_old, mut from_new) = (seed, seed);
260 for step in rest {
261 if last == 0 {
262 return false;
263 }
264 if at % 2 == 1 || at == last {
265 from_old = node_hash(step, &from_old);
266 from_new = node_hash(step, &from_new);
267 while at != 0 && at % 2 == 0 {
268 at /= 2;
269 last /= 2;
270 }
271 } else {
272 from_new = node_hash(&from_new, step);
273 }
274 at /= 2;
275 last /= 2;
276 }
277 last == 0 && hex(&from_old) == old_root && hex(&from_new) == new_root
278}
279
280#[must_use]
283pub fn from_hex(text: &str) -> Option<[u8; 32]> {
284 if text.len() != 64 || !text.bytes().all(|b| matches!(b, b'0'..=b'9' | b'a'..=b'f')) {
287 return None;
288 }
289 let mut out = [0u8; 32];
290 for (slot, pair) in out.iter_mut().zip(text.as_bytes().chunks_exact(2)) {
291 let pair = std::str::from_utf8(pair).ok()?;
292 *slot = u8::from_str_radix(pair, 16).ok()?;
293 }
294 Some(out)
295}
296
297#[must_use]
299pub fn hex(bytes: &[u8]) -> String {
300 bytes.iter().map(|b| format!("{b:02x}")).collect()
301}
302
303#[cfg(test)]
304mod tests {
305 use super::*;
306
307 fn leaves(n: usize) -> Vec<[u8; 32]> {
308 (0..n)
309 .map(|i| leaf_hash(format!("deed-{i}").as_bytes()))
310 .collect()
311 }
312
313 #[test]
316 fn a_leaf_is_not_a_node() {
317 let left = leaf_hash(b"a");
318 let right = leaf_hash(b"b");
319 let parent = node_hash(&left, &right);
320 let mut joined = Vec::new();
321 joined.extend_from_slice(&left);
322 joined.extend_from_slice(&right);
323 assert_ne!(parent, leaf_hash(&joined));
324 }
325
326 #[test]
329 fn every_leaf_proves_in() {
330 for size in 1..=33usize {
331 let set = leaves(size);
332 let head = Head::over(&set);
333 assert_eq!(head.size, size);
334 for index in 0..size {
335 let path = inclusion_proof(&set, index).expect("a path");
336 assert!(
337 verify_inclusion(&set[index], index, size, &path, &head.root),
338 "size {size} index {index}"
339 );
340 }
341 }
342 }
343
344 #[test]
347 fn a_proof_does_not_travel() {
348 let set = leaves(8);
349 let head = Head::over(&set);
350 let path = inclusion_proof(&set, 3).expect("a path");
351 assert!(verify_inclusion(&set[3], 3, 8, &path, &head.root));
352 assert!(!verify_inclusion(&set[4], 3, 8, &path, &head.root));
354 assert!(!verify_inclusion(&set[3], 4, 8, &path, &head.root));
356 assert!(!verify_inclusion(&set[3], 3, 8, &path, &"0".repeat(64)));
358 assert!(!verify_inclusion(&set[3], 3, 8, &path[..2], &head.root));
360 }
361
362 #[test]
364 fn every_prefix_proves_it_is_one() {
365 for new in 1..=33usize {
366 let all = leaves(new);
367 let later = Head::over(&all);
368 for old in 1..=new {
369 let earlier = Head::over(&all[..old]);
370 let path = consistency_proof(&all, old).expect("a proof");
371 assert!(
372 verify_consistency(old, &earlier.root, new, &later.root, &path),
373 "size {old} is not proving a prefix of {new}"
374 );
375 }
376 }
377 }
378
379 #[test]
381 fn a_rewritten_log_cannot_extend_the_head_it_replaced() {
382 let honest = leaves(8);
383 let published = Head::over(&honest);
384
385 let mut rewritten: Vec<[u8; 32]> = honest.clone();
388 rewritten.remove(2);
389 rewritten.push(leaf_hash(b"deed-8"));
390 rewritten.push(leaf_hash(b"deed-9"));
391 let now = Head::over(&rewritten);
392
393 let path = inclusion_proof(&rewritten, 0).expect("a path");
396 assert!(verify_inclusion(
397 &rewritten[0],
398 0,
399 now.size,
400 &path,
401 &now.root
402 ));
403
404 let offered = consistency_proof(&rewritten, published.size).expect("a proof");
407 assert!(
408 !verify_consistency(
409 published.size,
410 &published.root,
411 now.size,
412 &now.root,
413 &offered
414 ),
415 "a rewritten log passed as an extension"
416 );
417 }
418
419 #[test]
422 fn a_consistency_proof_does_not_travel() {
423 let all = leaves(12);
424 let later = Head::over(&all);
425 let earlier = Head::over(&all[..5]);
426 let path = consistency_proof(&all, 5).expect("a proof");
427 assert!(verify_consistency(5, &earlier.root, 12, &later.root, &path));
428
429 let other = Head::over(&all[..6]);
431 assert!(!verify_consistency(6, &other.root, 12, &later.root, &path));
432 assert!(!verify_consistency(
434 5,
435 &"0".repeat(64),
436 12,
437 &later.root,
438 &path
439 ));
440 assert!(!verify_consistency(
442 5,
443 &earlier.root,
444 12,
445 &later.root,
446 &path[..1]
447 ));
448 let mut padded = path.clone();
449 padded.push([0u8; 32]);
450 assert!(!verify_consistency(
451 5,
452 &earlier.root,
453 12,
454 &later.root,
455 &padded
456 ));
457 assert!(!verify_consistency(
459 12,
460 &later.root,
461 5,
462 &earlier.root,
463 &path
464 ));
465 assert!(consistency_proof(&all, 0).is_none());
467 assert!(consistency_proof(&all, 13).is_none());
468 }
469
470 #[test]
473 fn removing_an_entry_moves_the_root() {
474 let set = leaves(6);
475 let full = Head::over(&set);
476 let mut short = set.clone();
477 short.remove(2);
478 let missing = Head::over(&short);
479 assert_ne!(full.root, missing.root);
480 assert_ne!(full.size, missing.size);
481 let path = inclusion_proof(&set, 2).expect("a path");
483 assert!(!verify_inclusion(
484 &set[2],
485 2,
486 short.len(),
487 &path,
488 &missing.root
489 ));
490 }
491
492 #[test]
495 fn an_entry_round_trips_and_a_bad_line_is_refused() {
496 let entry = Entry {
497 id: "deed-file-note".into(),
498 digest: "sha256:abc".into(),
499 unix_time: 1_757_000_000,
500 };
501 let back = Entry::parse(&entry.line()).expect("parses");
502 assert_eq!(back, entry);
503 assert!(Entry::parse("two\tfields\n").is_err());
504 assert!(Entry::parse("a\tb\tnot-a-time\n").is_err());
505 assert!(Entry::parse("a\tb\t1\tc\n").is_err());
506 }
507
508 #[test]
511 fn an_empty_log_still_has_a_head() {
512 let head = Head::over(&[]);
513 assert_eq!(head.size, 0);
514 assert_eq!(head.root.len(), 64);
515 assert!(inclusion_proof(&[], 0).is_none());
516 }
517}