1use sha2::{Digest, Sha256};
29use thiserror::Error;
30
31const LEAF_PREFIX: u8 = 0x00;
33const NODE_PREFIX: u8 = 0x01;
34
35const MAX_PROOF_LEN: usize = 64;
38
39pub type Hash = [u8; 32];
40
41#[derive(Debug, Error, PartialEq, Eq)]
42pub enum LogError {
43 #[error("the log is empty")]
44 Empty,
45 #[error("entry {index} is not in a log of size {size}")]
46 OutOfRange { index: u64, size: u64 },
47 #[error("a log of size {old} cannot be a prefix of one of size {new}")]
48 NotAPrefix { old: u64, new: u64 },
49 #[error("the proof does not verify")]
50 BadProof,
51 #[error("a proof of {0} hashes exceeds the limit")]
52 ProofTooLong(usize),
53 #[error("the encoding is malformed")]
54 Malformed,
55}
56
57pub fn leaf_hash(data: &[u8]) -> Hash {
59 let mut hasher = Sha256::new();
60 hasher.update([LEAF_PREFIX]);
61 hasher.update(data);
62 hasher.finalize().into()
63}
64
65fn node_hash(left: &Hash, right: &Hash) -> Hash {
66 let mut hasher = Sha256::new();
67 hasher.update([NODE_PREFIX]);
68 hasher.update(left);
69 hasher.update(right);
70 hasher.finalize().into()
71}
72
73fn root_of(leaves: &[Hash]) -> Hash {
75 match leaves.len() {
76 0 => Sha256::digest(b"").into(),
79 1 => leaves[0],
80 n => {
81 let split = largest_power_of_two_below(n as u64) as usize;
82 node_hash(&root_of(&leaves[..split]), &root_of(&leaves[split..]))
83 }
84 }
85}
86
87fn largest_power_of_two_below(n: u64) -> u64 {
93 debug_assert!(n > 1);
94 1 << (n - 1).ilog2()
95}
96
97#[derive(Debug, Clone, PartialEq, Eq)]
99pub struct InclusionProof {
100 pub index: u64,
101 pub size: u64,
102 pub path: Vec<Hash>,
103}
104
105#[derive(Debug, Clone, PartialEq, Eq)]
107pub struct ConsistencyProof {
108 pub old_size: u64,
109 pub new_size: u64,
110 pub path: Vec<Hash>,
111}
112
113#[derive(Debug, Default, Clone)]
115pub struct TransparencyLog {
116 leaves: Vec<Hash>,
117}
118
119impl TransparencyLog {
120 pub fn new() -> Self {
121 Self::default()
122 }
123
124 pub fn append(&mut self, data: &[u8]) -> u64 {
126 let index = self.leaves.len() as u64;
127 self.leaves.push(leaf_hash(data));
128 index
129 }
130
131 pub fn len(&self) -> u64 {
132 self.leaves.len() as u64
133 }
134
135 pub fn is_empty(&self) -> bool {
136 self.leaves.is_empty()
137 }
138
139 pub fn root(&self) -> Hash {
141 root_of(&self.leaves)
142 }
143
144 pub fn root_at(&self, size: u64) -> Result<Hash, LogError> {
147 if size > self.len() {
148 return Err(LogError::OutOfRange {
149 index: size,
150 size: self.len(),
151 });
152 }
153 Ok(root_of(&self.leaves[..size as usize]))
154 }
155
156 pub fn prove_inclusion(&self, index: u64, size: u64) -> Result<InclusionProof, LogError> {
158 if size > self.len() || index >= size {
159 return Err(LogError::OutOfRange { index, size });
160 }
161 let mut path = Vec::new();
162 collect_inclusion(&self.leaves[..size as usize], index as usize, &mut path);
163 Ok(InclusionProof { index, size, path })
164 }
165
166 pub fn prove_consistency(
168 &self,
169 old_size: u64,
170 new_size: u64,
171 ) -> Result<ConsistencyProof, LogError> {
172 if new_size > self.len() {
173 return Err(LogError::OutOfRange {
174 index: new_size,
175 size: self.len(),
176 });
177 }
178 if old_size > new_size || old_size == 0 {
179 return Err(LogError::NotAPrefix {
180 old: old_size,
181 new: new_size,
182 });
183 }
184 let mut path = Vec::new();
185 collect_consistency(
186 &self.leaves[..new_size as usize],
187 old_size as usize,
188 true,
189 &mut path,
190 );
191 Ok(ConsistencyProof {
192 old_size,
193 new_size,
194 path,
195 })
196 }
197}
198
199fn collect_inclusion(leaves: &[Hash], index: usize, path: &mut Vec<Hash>) {
200 if leaves.len() <= 1 {
201 return;
202 }
203 let split = largest_power_of_two_below(leaves.len() as u64) as usize;
204 if index < split {
205 collect_inclusion(&leaves[..split], index, path);
206 path.push(root_of(&leaves[split..]));
207 } else {
208 collect_inclusion(&leaves[split..], index - split, path);
209 path.push(root_of(&leaves[..split]));
210 }
211}
212
213fn collect_consistency(leaves: &[Hash], old: usize, complete: bool, path: &mut Vec<Hash>) {
216 if old == leaves.len() {
217 if !complete {
218 path.push(root_of(leaves));
219 }
220 return;
221 }
222 let split = largest_power_of_two_below(leaves.len() as u64) as usize;
223 if old <= split {
224 collect_consistency(&leaves[..split], old, complete, path);
225 path.push(root_of(&leaves[split..]));
226 } else {
227 collect_consistency(&leaves[split..], old - split, false, path);
228 path.push(root_of(&leaves[..split]));
229 }
230}
231
232pub fn verify_inclusion(proof: &InclusionProof, leaf: &Hash, root: &Hash) -> Result<(), LogError> {
235 if proof.path.len() > MAX_PROOF_LEN {
236 return Err(LogError::ProofTooLong(proof.path.len()));
237 }
238 if proof.index >= proof.size {
239 return Err(LogError::OutOfRange {
240 index: proof.index,
241 size: proof.size,
242 });
243 }
244
245 let mut turns = Vec::new();
249 let mut index = proof.index;
250 let mut size = proof.size;
251 while size > 1 {
252 let split = largest_power_of_two_below(size);
253 if index < split {
254 turns.push(true);
255 size = split;
256 } else {
257 turns.push(false);
258 index -= split;
259 size -= split;
260 }
261 }
262
263 if turns.len() != proof.path.len() {
264 return Err(LogError::BadProof);
265 }
266
267 let mut hash = *leaf;
268 for (sibling, went_left) in proof.path.iter().zip(turns.iter().rev()) {
269 hash = if *went_left {
270 node_hash(&hash, sibling)
271 } else {
272 node_hash(sibling, &hash)
273 };
274 }
275
276 if hash != *root {
277 return Err(LogError::BadProof);
278 }
279 Ok(())
280}
281
282pub fn verify_consistency(
285 proof: &ConsistencyProof,
286 old_root: &Hash,
287 new_root: &Hash,
288) -> Result<(), LogError> {
289 if proof.path.len() > MAX_PROOF_LEN {
290 return Err(LogError::ProofTooLong(proof.path.len()));
291 }
292 if proof.old_size == 0 || proof.old_size > proof.new_size {
293 return Err(LogError::NotAPrefix {
294 old: proof.old_size,
295 new: proof.new_size,
296 });
297 }
298
299 if proof.old_size == proof.new_size {
301 return if proof.path.is_empty() && old_root == new_root {
302 Ok(())
303 } else {
304 Err(LogError::BadProof)
305 };
306 }
307
308 let mut turns = Vec::new();
312 let mut old_size = proof.old_size;
313 let mut new_size = proof.new_size;
314 let mut complete = true;
315 while old_size != new_size {
316 let split = largest_power_of_two_below(new_size);
317 if old_size <= split {
318 turns.push(true);
319 new_size = split;
320 } else {
321 turns.push(false);
322 old_size -= split;
323 new_size -= split;
324 complete = false;
325 }
326 }
327
328 let expected = turns.len() + usize::from(!complete);
331 if proof.path.len() != expected {
332 return Err(LogError::BadProof);
333 }
334
335 let mut path = proof.path.iter();
336 let seed = if complete {
337 *old_root
338 } else {
339 *path.next().ok_or(LogError::BadProof)?
340 };
341 let mut old_hash = seed;
342 let mut new_hash = seed;
343
344 for (sibling, went_left) in path.zip(turns.iter().rev()) {
345 if *went_left {
346 new_hash = node_hash(&new_hash, sibling);
347 } else {
348 old_hash = node_hash(sibling, &old_hash);
349 new_hash = node_hash(sibling, &new_hash);
350 }
351 }
352
353 if old_hash != *old_root || new_hash != *new_root {
354 return Err(LogError::BadProof);
355 }
356 Ok(())
357}
358
359pub fn encode_checkpoint(size: u64, root: &Hash) -> Vec<u8> {
362 let mut out = Vec::with_capacity(40);
363 out.extend_from_slice(&size.to_be_bytes());
364 out.extend_from_slice(root);
365 out
366}
367
368pub fn decode_checkpoint(bytes: &[u8]) -> Result<(u64, Hash), LogError> {
369 if bytes.len() != 40 {
370 return Err(LogError::Malformed);
371 }
372 let size = u64::from_be_bytes(bytes[..8].try_into().map_err(|_| LogError::Malformed)?);
373 let root: Hash = bytes[8..].try_into().map_err(|_| LogError::Malformed)?;
374 Ok((size, root))
375}