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);
82 node_hash(&root_of(&leaves[..split]), &root_of(&leaves[split..]))
83 }
84 }
85}
86
87fn largest_power_of_two_below(n: usize) -> usize {
90 debug_assert!(n > 1);
91 let mut split = 1;
92 while split << 1 < n {
93 split <<= 1;
94 }
95 split
96}
97
98#[derive(Debug, Clone, PartialEq, Eq)]
100pub struct InclusionProof {
101 pub index: u64,
102 pub size: u64,
103 pub path: Vec<Hash>,
104}
105
106#[derive(Debug, Clone, PartialEq, Eq)]
108pub struct ConsistencyProof {
109 pub old_size: u64,
110 pub new_size: u64,
111 pub path: Vec<Hash>,
112}
113
114#[derive(Debug, Default, Clone)]
116pub struct TransparencyLog {
117 leaves: Vec<Hash>,
118}
119
120impl TransparencyLog {
121 pub fn new() -> Self {
122 Self::default()
123 }
124
125 pub fn append(&mut self, data: &[u8]) -> u64 {
127 let index = self.leaves.len() as u64;
128 self.leaves.push(leaf_hash(data));
129 index
130 }
131
132 pub fn len(&self) -> u64 {
133 self.leaves.len() as u64
134 }
135
136 pub fn is_empty(&self) -> bool {
137 self.leaves.is_empty()
138 }
139
140 pub fn root(&self) -> Hash {
142 root_of(&self.leaves)
143 }
144
145 pub fn root_at(&self, size: u64) -> Result<Hash, LogError> {
148 if size > self.len() {
149 return Err(LogError::OutOfRange {
150 index: size,
151 size: self.len(),
152 });
153 }
154 Ok(root_of(&self.leaves[..size as usize]))
155 }
156
157 pub fn prove_inclusion(&self, index: u64, size: u64) -> Result<InclusionProof, LogError> {
159 if size > self.len() || index >= size {
160 return Err(LogError::OutOfRange { index, size });
161 }
162 let mut path = Vec::new();
163 collect_inclusion(&self.leaves[..size as usize], index as usize, &mut path);
164 Ok(InclusionProof { index, size, path })
165 }
166
167 pub fn prove_consistency(
169 &self,
170 old_size: u64,
171 new_size: u64,
172 ) -> Result<ConsistencyProof, LogError> {
173 if new_size > self.len() {
174 return Err(LogError::OutOfRange {
175 index: new_size,
176 size: self.len(),
177 });
178 }
179 if old_size > new_size || old_size == 0 {
180 return Err(LogError::NotAPrefix {
181 old: old_size,
182 new: new_size,
183 });
184 }
185 let mut path = Vec::new();
186 collect_consistency(
187 &self.leaves[..new_size as usize],
188 old_size as usize,
189 true,
190 &mut path,
191 );
192 Ok(ConsistencyProof {
193 old_size,
194 new_size,
195 path,
196 })
197 }
198}
199
200fn collect_inclusion(leaves: &[Hash], index: usize, path: &mut Vec<Hash>) {
201 if leaves.len() <= 1 {
202 return;
203 }
204 let split = largest_power_of_two_below(leaves.len());
205 if index < split {
206 collect_inclusion(&leaves[..split], index, path);
207 path.push(root_of(&leaves[split..]));
208 } else {
209 collect_inclusion(&leaves[split..], index - split, path);
210 path.push(root_of(&leaves[..split]));
211 }
212}
213
214fn collect_consistency(leaves: &[Hash], old: usize, complete: bool, path: &mut Vec<Hash>) {
217 if old == leaves.len() {
218 if !complete {
219 path.push(root_of(leaves));
220 }
221 return;
222 }
223 let split = largest_power_of_two_below(leaves.len());
224 if old <= split {
225 collect_consistency(&leaves[..split], old, complete, path);
226 path.push(root_of(&leaves[split..]));
227 } else {
228 collect_consistency(&leaves[split..], old - split, false, path);
229 path.push(root_of(&leaves[..split]));
230 }
231}
232
233pub fn verify_inclusion(proof: &InclusionProof, leaf: &Hash, root: &Hash) -> Result<(), LogError> {
236 if proof.path.len() > MAX_PROOF_LEN {
237 return Err(LogError::ProofTooLong(proof.path.len()));
238 }
239 if proof.index >= proof.size {
240 return Err(LogError::OutOfRange {
241 index: proof.index,
242 size: proof.size,
243 });
244 }
245
246 let mut turns = Vec::new();
250 let mut index = proof.index;
251 let mut size = proof.size;
252 while size > 1 {
253 let split = largest_power_of_two_below(size as usize) as u64;
254 if index < split {
255 turns.push(true);
256 size = split;
257 } else {
258 turns.push(false);
259 index -= split;
260 size -= split;
261 }
262 }
263
264 if turns.len() != proof.path.len() {
265 return Err(LogError::BadProof);
266 }
267
268 let mut hash = *leaf;
269 for (sibling, went_left) in proof.path.iter().zip(turns.iter().rev()) {
270 hash = if *went_left {
271 node_hash(&hash, sibling)
272 } else {
273 node_hash(sibling, &hash)
274 };
275 }
276
277 if hash != *root {
278 return Err(LogError::BadProof);
279 }
280 Ok(())
281}
282
283pub fn verify_consistency(
286 proof: &ConsistencyProof,
287 old_root: &Hash,
288 new_root: &Hash,
289) -> Result<(), LogError> {
290 if proof.path.len() > MAX_PROOF_LEN {
291 return Err(LogError::ProofTooLong(proof.path.len()));
292 }
293 if proof.old_size == 0 || proof.old_size > proof.new_size {
294 return Err(LogError::NotAPrefix {
295 old: proof.old_size,
296 new: proof.new_size,
297 });
298 }
299
300 if proof.old_size == proof.new_size {
302 return if proof.path.is_empty() && old_root == new_root {
303 Ok(())
304 } else {
305 Err(LogError::BadProof)
306 };
307 }
308
309 let mut turns = Vec::new();
313 let mut old_size = proof.old_size;
314 let mut new_size = proof.new_size;
315 let mut complete = true;
316 while old_size != new_size {
317 let split = largest_power_of_two_below(new_size as usize) as u64;
318 if old_size <= split {
319 turns.push(true);
320 new_size = split;
321 } else {
322 turns.push(false);
323 old_size -= split;
324 new_size -= split;
325 complete = false;
326 }
327 }
328
329 let expected = turns.len() + usize::from(!complete);
332 if proof.path.len() != expected {
333 return Err(LogError::BadProof);
334 }
335
336 let mut path = proof.path.iter();
337 let seed = if complete {
338 *old_root
339 } else {
340 *path.next().ok_or(LogError::BadProof)?
341 };
342 let mut old_hash = seed;
343 let mut new_hash = seed;
344
345 for (sibling, went_left) in path.zip(turns.iter().rev()) {
346 if *went_left {
347 new_hash = node_hash(&new_hash, sibling);
348 } else {
349 old_hash = node_hash(sibling, &old_hash);
350 new_hash = node_hash(sibling, &new_hash);
351 }
352 }
353
354 if old_hash != *old_root || new_hash != *new_root {
355 return Err(LogError::BadProof);
356 }
357 Ok(())
358}
359
360pub fn encode_checkpoint(size: u64, root: &Hash) -> Vec<u8> {
363 let mut out = Vec::with_capacity(40);
364 out.extend_from_slice(&size.to_be_bytes());
365 out.extend_from_slice(root);
366 out
367}
368
369pub fn decode_checkpoint(bytes: &[u8]) -> Result<(u64, Hash), LogError> {
370 if bytes.len() != 40 {
371 return Err(LogError::Malformed);
372 }
373 let size = u64::from_be_bytes(bytes[..8].try_into().map_err(|_| LogError::Malformed)?);
374 let root: Hash = bytes[8..].try_into().map_err(|_| LogError::Malformed)?;
375 Ok((size, root))
376}