qualia_core_db/bundle/stream/proof/
builder.rs1use super::{empty_root, hash::parent, leaf_hash, ProofError, TreeSpec, MAX_SIBLINGS};
2use crate::net::qdnf::types::StrongDigest;
3
4#[derive(Clone, Copy, Debug, PartialEq, Eq)]
5pub struct OutboardNode {
6 pub start_leaf: u64,
7 pub leaf_count: u64,
8 pub digest: StrongDigest,
9}
10
11pub struct TreeBuilder {
15 spec: TreeSpec,
16 count: u64,
17 frontier: [StrongDigest; MAX_SIBLINGS + 1],
18 poisoned: bool,
19 finished: Option<StrongDigest>,
20}
21impl TreeBuilder {
22 pub fn new(spec: TreeSpec) -> Self {
23 Self {
24 spec,
25 count: 0,
26 frontier: [StrongDigest::ZERO; MAX_SIBLINGS + 1],
27 poisoned: false,
28 finished: None,
29 }
30 }
31 pub const fn appended(&self) -> u64 {
32 self.count
33 }
34 pub const fn is_poisoned(&self) -> bool {
35 self.poisoned
36 }
37 pub fn append(
38 &mut self,
39 bytes: &[u8],
40 mut observe: impl FnMut(OutboardNode) -> Result<(), ProofError>,
41 ) -> Result<(), ProofError> {
42 if self.poisoned {
43 return Err(ProofError::Poisoned);
44 }
45 if self.count == self.spec.leaf_count() {
46 return Err(ProofError::Complete);
47 }
48 let mut digest = leaf_hash(&self.spec, self.count, bytes)?;
49 let mut level = 0;
50 let mut width = 1u64;
51 self.poisoned = true;
52 observe(OutboardNode {
53 start_leaf: self.count,
54 leaf_count: width,
55 digest,
56 })
57 .map_err(|_| ProofError::Sink)?;
58 while self.count & width != 0 {
59 digest = parent(self.frontier[level], digest);
60 level += 1;
61 width <<= 1;
62 observe(OutboardNode {
63 start_leaf: self.count + 1 - width,
64 leaf_count: width,
65 digest,
66 })
67 .map_err(|_| ProofError::Sink)?;
68 }
69 self.frontier[level] = digest;
70 self.count += 1;
71 self.poisoned = false;
72 Ok(())
73 }
74 pub fn finish(
75 &mut self,
76 mut observe: impl FnMut(OutboardNode) -> Result<(), ProofError>,
77 ) -> Result<StrongDigest, ProofError> {
78 if self.poisoned {
79 return Err(ProofError::Poisoned);
80 }
81 if let Some(root) = self.finished {
82 return Ok(root);
83 }
84 if self.count != self.spec.leaf_count() {
85 return Err(ProofError::Incomplete);
86 }
87 if self.count == 0 {
88 let root = empty_root(&self.spec)?;
89 self.finished = Some(root);
90 return Ok(root);
91 }
92 self.poisoned = true;
93 let mut result = None;
94 let mut right_count = 0u64;
95 for level in 0..=MAX_SIBLINGS {
96 let width = 1u64 << level;
97 if self.count & width == 0 {
98 continue;
99 }
100 let digest = match result {
101 None => self.frontier[level],
102 Some(right) => parent(self.frontier[level], right),
103 };
104 if result.is_some() {
105 observe(OutboardNode {
106 start_leaf: self.count - right_count - width,
107 leaf_count: right_count + width,
108 digest,
109 })
110 .map_err(|_| ProofError::Sink)?;
111 }
112 result = Some(digest);
113 right_count += width;
114 }
115 let root = result.ok_or(ProofError::Incomplete)?;
116 self.finished = Some(root);
117 self.poisoned = false;
118 Ok(root)
119 }
120}