1#![doc = "Bounded parsing and verification for HSD's Urkel proof wire format."]
2
3use blake2::Blake2bVar;
4use blake2::digest::{Update, VariableOutput};
5use hns_primitives::{NameHash, TreeRoot};
6use thiserror::Error;
7
8pub const URKEL_BITS: usize = 256;
9pub const EMPTY_ROOT: TreeRoot = TreeRoot::new([0; 32]);
10pub const MAX_HSD_PROOF_SIZE: usize = 82_469;
11
12const TYPE_DEADEND: u16 = 0;
13const TYPE_SHORT: u16 = 1;
14const TYPE_COLLISION: u16 = 2;
15const TYPE_EXISTS: u16 = 3;
16
17#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
18pub enum ProofKind {
19 Inclusion,
20 NonInclusion,
21}
22
23#[derive(Clone, Debug, Eq, PartialEq)]
24pub struct UrkelProof {
25 pub name_hash: NameHash,
26 pub kind: ProofKind,
27 pub raw: Vec<u8>,
28}
29
30impl UrkelProof {
31 pub fn verify_hsd(&self, root: TreeRoot) -> Result<Option<Vec<u8>>, UrkelError> {
32 let proof = HsdUrkelProof::decode_hsd(&self.raw)?;
33 if proof.kind() != self.kind {
34 return Err(UrkelError::KindMismatch);
35 }
36 proof.verify(root, self.name_hash)
37 }
38
39 pub fn verify_strict(&self, root: TreeRoot) -> Result<Option<Vec<u8>>, UrkelError> {
40 let proof = HsdUrkelProof::decode_strict(&self.raw)?;
41 if proof.kind() != self.kind {
42 return Err(UrkelError::KindMismatch);
43 }
44 proof.verify(root, self.name_hash)
45 }
46}
47
48#[derive(Clone, Debug, Eq, PartialEq)]
49pub struct HsdUrkelProof {
50 depth: u16,
51 nodes: Vec<ProofNode>,
52 terminal: ProofTerminal,
53}
54
55#[derive(Clone, Debug, Eq, PartialEq)]
56struct ProofNode {
57 prefix: BitPrefix,
58 sibling: [u8; 32],
59}
60
61#[derive(Clone, Debug, Eq, PartialEq)]
62enum ProofTerminal {
63 DeadEnd,
64 Short {
65 prefix: BitPrefix,
66 left: [u8; 32],
67 right: [u8; 32],
68 },
69 Collision {
70 key: NameHash,
71 value_hash: [u8; 32],
72 },
73 Exists {
74 value: Vec<u8>,
75 },
76}
77
78impl HsdUrkelProof {
79 pub fn decode_hsd(raw: &[u8]) -> Result<Self, UrkelError> {
82 Self::decode_inner(raw).map(|(proof, _)| proof)
83 }
84
85 pub fn decode_strict(raw: &[u8]) -> Result<Self, UrkelError> {
88 let (proof, consumed) = Self::decode_inner(raw)?;
89 if consumed != raw.len() {
90 return Err(UrkelError::TrailingBytes(raw.len() - consumed));
91 }
92 if proof.encode()? != raw {
93 return Err(UrkelError::NonCanonical);
94 }
95 Ok(proof)
96 }
97
98 fn decode_inner(raw: &[u8]) -> Result<(Self, usize), UrkelError> {
99 if raw.len() > MAX_HSD_PROOF_SIZE {
100 return Err(UrkelError::TooLarge(raw.len()));
101 }
102 let mut reader = ProofReader::new(raw);
103 let field = reader.read_u16()?;
104 let proof_type = field >> 14;
105 let depth = field & 0x3fff;
106 if usize::from(depth) > URKEL_BITS {
107 return Err(UrkelError::Depth(depth));
108 }
109 let count = usize::from(reader.read_u16()?);
110 if count > URKEL_BITS {
111 return Err(UrkelError::NodeCount(count));
112 }
113 let prefix_field = reader.read_vec(count.div_ceil(8))?;
114 let mut nodes = Vec::with_capacity(count);
115 for index in 0..count {
116 let prefix = if packed_bit(&prefix_field, index) == 1 {
117 let prefix = reader.read_prefix()?;
118 if prefix.bit_len() == 0 {
119 return Err(UrkelError::EmptyExplicitPrefix);
120 }
121 prefix
122 } else {
123 BitPrefix::default()
124 };
125 nodes.push(ProofNode {
126 prefix,
127 sibling: reader.read_hash()?,
128 });
129 }
130 let terminal = match proof_type {
131 TYPE_DEADEND => ProofTerminal::DeadEnd,
132 TYPE_SHORT => {
133 let prefix = reader.read_prefix()?;
134 if prefix.bit_len() == 0 {
135 return Err(UrkelError::EmptyShortPrefix);
136 }
137 ProofTerminal::Short {
138 prefix,
139 left: reader.read_hash()?,
140 right: reader.read_hash()?,
141 }
142 }
143 TYPE_COLLISION => ProofTerminal::Collision {
144 key: NameHash::new(reader.read_hash()?),
145 value_hash: reader.read_hash()?,
146 },
147 TYPE_EXISTS => {
148 let size = usize::from(reader.read_u16()?);
149 ProofTerminal::Exists {
150 value: reader.read_vec(size)?,
151 }
152 }
153 _ => unreachable!("two-bit proof type"),
154 };
155 let proof = Self {
156 depth,
157 nodes,
158 terminal,
159 };
160 proof.validate()?;
161 Ok((proof, reader.position()))
162 }
163
164 pub fn encode(&self) -> Result<Vec<u8>, UrkelError> {
165 self.validate()?;
166 let proof_type = match self.terminal {
167 ProofTerminal::DeadEnd => TYPE_DEADEND,
168 ProofTerminal::Short { .. } => TYPE_SHORT,
169 ProofTerminal::Collision { .. } => TYPE_COLLISION,
170 ProofTerminal::Exists { .. } => TYPE_EXISTS,
171 };
172 let mut raw = Vec::new();
173 raw.extend_from_slice(&((proof_type << 14) | self.depth).to_le_bytes());
174 raw.extend_from_slice(&(self.nodes.len() as u16).to_le_bytes());
175 let bitmap_offset = raw.len();
176 raw.resize(bitmap_offset + self.nodes.len().div_ceil(8), 0);
177 for (index, node) in self.nodes.iter().enumerate() {
178 if node.prefix.bit_len() != 0 {
179 set_packed_bit(&mut raw[bitmap_offset..], index, 1);
180 node.prefix.write_hsd(&mut raw);
181 }
182 raw.extend_from_slice(&node.sibling);
183 }
184 match &self.terminal {
185 ProofTerminal::DeadEnd => {}
186 ProofTerminal::Short {
187 prefix,
188 left,
189 right,
190 } => {
191 prefix.write_hsd(&mut raw);
192 raw.extend_from_slice(left);
193 raw.extend_from_slice(right);
194 }
195 ProofTerminal::Collision { key, value_hash } => {
196 raw.extend_from_slice(key.as_bytes());
197 raw.extend_from_slice(value_hash);
198 }
199 ProofTerminal::Exists { value } => {
200 raw.extend_from_slice(&(value.len() as u16).to_le_bytes());
201 raw.extend_from_slice(value);
202 }
203 }
204 if raw.len() > MAX_HSD_PROOF_SIZE {
205 return Err(UrkelError::TooLarge(raw.len()));
206 }
207 Ok(raw)
208 }
209
210 pub fn kind(&self) -> ProofKind {
211 match self.terminal {
212 ProofTerminal::Exists { .. } => ProofKind::Inclusion,
213 _ => ProofKind::NonInclusion,
214 }
215 }
216
217 pub const fn depth(&self) -> u16 {
218 self.depth
219 }
220
221 pub fn node_count(&self) -> usize {
222 self.nodes.len()
223 }
224
225 pub fn verify(
226 &self,
227 expected_root: TreeRoot,
228 key: NameHash,
229 ) -> Result<Option<Vec<u8>>, UrkelError> {
230 self.validate()?;
231 let key_bytes = key.as_bytes();
232 let (mut hash, value) = match &self.terminal {
233 ProofTerminal::DeadEnd => ([0; 32], None),
234 ProofTerminal::Short {
235 prefix,
236 left,
237 right,
238 } => {
239 if prefix.matches_key(key_bytes, usize::from(self.depth)) {
240 return Err(UrkelError::ShortFollowsKey);
241 }
242 (hash_internal(prefix, left, right), None)
243 }
244 ProofTerminal::Collision {
245 key: collision,
246 value_hash,
247 } => {
248 if *collision == key {
249 return Err(UrkelError::CollisionUsesKey);
250 }
251 (hash_leaf(collision.as_bytes(), value_hash), None)
252 }
253 ProofTerminal::Exists { value } => (
254 hash_leaf(key_bytes, &blake2b_256(value)),
255 Some(value.clone()),
256 ),
257 };
258
259 let mut depth = usize::from(self.depth);
260 for node in self.nodes.iter().rev() {
261 let prefix_bits = node.prefix.bit_len();
262 if depth < prefix_bits + 1 {
263 return Err(UrkelError::AncestorDepth);
264 }
265 depth -= 1;
266 hash = if key_bit(key_bytes, depth) == 1 {
267 hash_internal(&node.prefix, &node.sibling, &hash)
268 } else {
269 hash_internal(&node.prefix, &hash, &node.sibling)
270 };
271 depth -= prefix_bits;
272 if !node.prefix.matches_key(key_bytes, depth) {
273 return Err(UrkelError::AncestorPrefix);
274 }
275 }
276 if depth != 0 {
277 return Err(UrkelError::IncompletePath(depth));
278 }
279 let actual = TreeRoot::new(hash);
280 if actual != expected_root {
281 return Err(UrkelError::RootMismatch {
282 expected: expected_root,
283 actual,
284 });
285 }
286 Ok(value)
287 }
288
289 fn validate(&self) -> Result<(), UrkelError> {
290 if usize::from(self.depth) > URKEL_BITS {
291 return Err(UrkelError::Depth(self.depth));
292 }
293 if self.nodes.len() > URKEL_BITS {
294 return Err(UrkelError::NodeCount(self.nodes.len()));
295 }
296 for node in &self.nodes {
297 node.prefix.validate()?;
298 }
299 if let ProofTerminal::Short { prefix, .. } = &self.terminal {
300 prefix.validate()?;
301 if prefix.bit_len() == 0 {
302 return Err(UrkelError::EmptyShortPrefix);
303 }
304 }
305 if let ProofTerminal::Exists { value } = &self.terminal
306 && value.len() > usize::from(u16::MAX)
307 {
308 return Err(UrkelError::ValueTooLarge(value.len()));
309 }
310 Ok(())
311 }
312}
313
314#[derive(Clone, Debug, Default, Eq, PartialEq)]
315struct BitPrefix {
316 bit_len: u16,
317 bytes: Vec<u8>,
318}
319
320impl BitPrefix {
321 fn bit_len(&self) -> usize {
322 usize::from(self.bit_len)
323 }
324
325 fn bit(&self, index: usize) -> u8 {
326 packed_bit(&self.bytes, index)
327 }
328
329 fn matches_key(&self, key: &[u8; 32], depth: usize) -> bool {
330 depth
331 .checked_add(self.bit_len())
332 .is_some_and(|end| end <= URKEL_BITS)
333 && (0..self.bit_len()).all(|offset| self.bit(offset) == key_bit(key, depth + offset))
334 }
335
336 fn validate(&self) -> Result<(), UrkelError> {
337 let bit_len = self.bit_len();
338 if bit_len > URKEL_BITS {
339 return Err(UrkelError::PrefixLength(bit_len));
340 }
341 if self.bytes.len() != bit_len.div_ceil(8) {
342 return Err(UrkelError::PrefixSize);
343 }
344 if !bit_len.is_multiple_of(8) && !self.bytes.is_empty() {
345 let used = bit_len % 8;
346 let trailing_mask = (1_u8 << (8 - used)) - 1;
347 if self.bytes[self.bytes.len() - 1] & trailing_mask != 0 {
348 return Err(UrkelError::PrefixTrailingBits);
349 }
350 }
351 Ok(())
352 }
353
354 fn write_hsd(&self, output: &mut Vec<u8>) {
355 let bit_len = self.bit_len();
356 if bit_len >= 0x80 {
357 output.push(0x80 | ((bit_len >> 8) as u8));
358 }
359 output.push(bit_len as u8);
360 output.extend_from_slice(&self.bytes);
361 }
362}
363
364struct ProofReader<'a> {
365 raw: &'a [u8],
366 offset: usize,
367}
368
369impl<'a> ProofReader<'a> {
370 const fn new(raw: &'a [u8]) -> Self {
371 Self { raw, offset: 0 }
372 }
373
374 const fn position(&self) -> usize {
375 self.offset
376 }
377
378 fn read_u8(&mut self) -> Result<u8, UrkelError> {
379 let value = *self
380 .raw
381 .get(self.offset)
382 .ok_or(UrkelError::UnexpectedEnd(self.offset))?;
383 self.offset += 1;
384 Ok(value)
385 }
386
387 fn read_u16(&mut self) -> Result<u16, UrkelError> {
388 Ok(u16::from_le_bytes(
389 self.read_slice(2)?
390 .try_into()
391 .expect("two-byte proof field"),
392 ))
393 }
394
395 fn read_hash(&mut self) -> Result<[u8; 32], UrkelError> {
396 Ok(self.read_slice(32)?.try_into().expect("32-byte proof hash"))
397 }
398
399 fn read_vec(&mut self, size: usize) -> Result<Vec<u8>, UrkelError> {
400 Ok(self.read_slice(size)?.to_vec())
401 }
402
403 fn read_prefix(&mut self) -> Result<BitPrefix, UrkelError> {
404 let first = self.read_u8()?;
405 let bit_len = if first & 0x80 != 0 {
406 (usize::from(first & 0x7f) << 8) | usize::from(self.read_u8()?)
407 } else {
408 usize::from(first)
409 };
410 if bit_len > URKEL_BITS {
411 return Err(UrkelError::PrefixLength(bit_len));
412 }
413 let prefix = BitPrefix {
414 bit_len: bit_len as u16,
415 bytes: self.read_vec(bit_len.div_ceil(8))?,
416 };
417 prefix.validate()?;
418 Ok(prefix)
419 }
420
421 fn read_slice(&mut self, size: usize) -> Result<&'a [u8], UrkelError> {
422 let end = self
423 .offset
424 .checked_add(size)
425 .ok_or(UrkelError::OffsetOverflow)?;
426 let bytes = self
427 .raw
428 .get(self.offset..end)
429 .ok_or(UrkelError::UnexpectedEnd(self.offset))?;
430 self.offset = end;
431 Ok(bytes)
432 }
433}
434
435fn hash_leaf(key: &[u8; 32], value_hash: &[u8; 32]) -> [u8; 32] {
436 blake2b_256_many(&[&[0], key, value_hash])
437}
438
439fn hash_internal(prefix: &BitPrefix, left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
440 if prefix.bit_len() == 0 {
441 return blake2b_256_many(&[&[1], left, right]);
442 }
443 let size = (prefix.bit_len() as u16).to_le_bytes();
444 blake2b_256_many(&[&[2], &size, &prefix.bytes, left, right])
445}
446
447fn blake2b_256(input: &[u8]) -> [u8; 32] {
448 blake2b_256_many(&[input])
449}
450
451fn blake2b_256_many(parts: &[&[u8]]) -> [u8; 32] {
452 let mut hasher = Blake2bVar::new(32).expect("valid BLAKE2b output length");
453 for part in parts {
454 hasher.update(part);
455 }
456 let mut output = [0_u8; 32];
457 hasher
458 .finalize_variable(&mut output)
459 .expect("valid BLAKE2b output buffer");
460 output
461}
462
463fn key_bit(key: &[u8; 32], index: usize) -> u8 {
464 (key[index / 8] >> (7 - (index % 8))) & 1
465}
466
467fn packed_bit(bytes: &[u8], index: usize) -> u8 {
468 (bytes[index / 8] >> (7 - (index % 8))) & 1
469}
470
471fn set_packed_bit(bytes: &mut [u8], index: usize, bit: u8) {
472 bytes[index / 8] |= bit << (7 - (index % 8));
473}
474
475#[derive(Debug, Error, Eq, PartialEq)]
476pub enum UrkelError {
477 #[error("HSD proof uses {0} bytes, exceeding its configured bound")]
478 TooLarge(usize),
479 #[error("HSD proof depth {0} exceeds 256 bits")]
480 Depth(u16),
481 #[error("HSD proof node count {0} exceeds 256")]
482 NodeCount(usize),
483 #[error("HSD proof prefix uses {0} bits")]
484 PrefixLength(usize),
485 #[error("HSD proof prefix byte length is inconsistent")]
486 PrefixSize,
487 #[error("HSD proof prefix has nonzero unused bits")]
488 PrefixTrailingBits,
489 #[error("HSD proof encodes an empty explicit ancestor prefix")]
490 EmptyExplicitPrefix,
491 #[error("HSD short proof encodes an empty prefix")]
492 EmptyShortPrefix,
493 #[error("unexpected end of HSD proof at byte {0}")]
494 UnexpectedEnd(usize),
495 #[error("HSD proof offset overflow")]
496 OffsetOverflow,
497 #[error("{0} trailing HSD proof byte(s)")]
498 TrailingBytes(usize),
499 #[error("HSD proof is not canonically encoded")]
500 NonCanonical,
501 #[error("included proof value uses {0} bytes, exceeding 65535")]
502 ValueTooLarge(usize),
503 #[error("declared inclusion class differs from proof terminal")]
504 KindMismatch,
505 #[error("short proof prefix follows the requested key")]
506 ShortFollowsKey,
507 #[error("collision proof uses the requested key")]
508 CollisionUsesKey,
509 #[error("proof depth precedes a compressed ancestor")]
510 AncestorDepth,
511 #[error("compressed ancestor prefix differs from the requested key")]
512 AncestorPrefix,
513 #[error("proof path stops {0} bit(s) before the tree root")]
514 IncompletePath(usize),
515 #[error("Urkel proof root mismatch")]
516 RootMismatch {
517 expected: TreeRoot,
518 actual: TreeRoot,
519 },
520}
521
522#[cfg(test)]
523mod tests {
524 use super::*;
525
526 const ROOT: &str = "961d2caeea0311f64152665755a905fed00a3dd39bfa1b1217a5bbd356586f80";
527 const ALPHA_KEY: &str = "8f9ca3f331d0e099a724c861aabc1a5906f7b92f4c3b10618c791aab9d433045";
528 const ALPHA_PROOF: &str = "03c003000008ccd32448dd945f74c5df7b689096a8e9b2e7556196a2ed6567379328eb210e89fdfeee71539b6fc6020cb25173cd2ec986f83abab0a9d59411893e887875d83049a050258883441796a0c2263168cf9c1143b98e25b3a86157c7045444e20b040000010203";
529 const MISSING_KEY: &str = "23e587a06765c200c68c20a62f7b9c766a29dce0a572f59268e854f30118083d";
530 const COLLISION_PROOF: &str = "0280020000b47b6f4bca3a4caf5304170027f760a4cced32b9739a0e580ffbd50a7c18663be4221ce21fbf13e813163c53a4efaf779f15da26ee65a4367e33291a09906f173c2bb709c7f6df963eef15c9a9b024d059f99fec904116fd5bc05726945e2df2545db83fd403da1091070a319d15d0d29faf383af24c68172bd6a565d0d71f63";
531 const SHORT_KEY: &str = "e4c5923b20bd6ade4dfbc2afe74ec66d9c5aceefeb7a4905f9459b3400658037";
532 const SHORT_PROOF: &str = "024002000008ccd32448dd945f74c5df7b689096a8e9b2e7556196a2ed6567379328eb210ef789264e81a9fea73d4a4306c6e87c2815f4251c6ab57f5f6436e73a1897316d0400795975f88d7a3d9faf04acb0b541c65df9308de3e3580cbce81e4ef6b5d066d51ed52b6ddb9149df707e5058baff9e22bfcb812ff8e035a2b7580bc9cd287021";
533
534 fn root() -> TreeRoot {
535 TreeRoot::from_hex(ROOT).expect("root")
536 }
537
538 #[test]
539 fn exact_hsd_inclusion_and_empty_proofs_verify() {
540 let raw = hex::decode(ALPHA_PROOF).expect("hex");
541 let proof = HsdUrkelProof::decode_strict(&raw).expect("proof");
542 assert_eq!(proof.kind(), ProofKind::Inclusion);
543 assert_eq!(proof.depth(), 3);
544 assert_eq!(proof.node_count(), 3);
545 assert_eq!(
546 proof
547 .verify(root(), NameHash::from_hex(ALPHA_KEY).expect("key"))
548 .expect("valid"),
549 Some(vec![0, 1, 2, 3])
550 );
551 assert_eq!(proof.encode().expect("encoded"), raw);
552
553 let empty = HsdUrkelProof::decode_strict(&[0, 0, 0, 0]).expect("empty");
554 assert_eq!(
555 empty
556 .verify(EMPTY_ROOT, NameHash::new([0x55; 32]))
557 .expect("valid"),
558 None
559 );
560 }
561
562 #[test]
563 fn exact_hsd_short_and_collision_noninclusion_proofs_verify() {
564 for (key, raw) in [(SHORT_KEY, SHORT_PROOF), (MISSING_KEY, COLLISION_PROOF)] {
565 let raw = hex::decode(raw).expect("hex");
566 let proof = HsdUrkelProof::decode_strict(&raw).expect("proof");
567 assert_eq!(proof.kind(), ProofKind::NonInclusion);
568 assert_eq!(
569 proof
570 .verify(root(), NameHash::from_hex(key).expect("key"))
571 .expect("valid"),
572 None
573 );
574 assert_eq!(proof.encode().expect("encoded"), raw);
575 }
576 }
577
578 #[test]
579 fn upstream_trailing_compatibility_is_separate_from_strict_admission() {
580 let canonical = hex::decode(COLLISION_PROOF).expect("hex");
581 let mut trailing = canonical.clone();
582 trailing.push(0xff);
583 let compatible = HsdUrkelProof::decode_hsd(&trailing).expect("HSD accepts");
584 assert_eq!(compatible.encode().expect("canonical"), canonical);
585 assert_eq!(
586 HsdUrkelProof::decode_strict(&trailing),
587 Err(UrkelError::TrailingBytes(1))
588 );
589 }
590
591 #[test]
592 fn wrong_root_key_and_mutated_terminal_fail_closed() {
593 let raw = hex::decode(COLLISION_PROOF).expect("hex");
594 let proof = HsdUrkelProof::decode_strict(&raw).expect("proof");
595 assert!(
596 proof
597 .verify(
598 TreeRoot::new([0xa5; 32]),
599 NameHash::from_hex(MISSING_KEY).expect("key")
600 )
601 .is_err()
602 );
603 assert!(proof.verify(root(), NameHash::new([0xb5; 32])).is_err());
604 let mut mutated = raw;
605 *mutated.last_mut().expect("byte") ^= 1;
606 let proof = HsdUrkelProof::decode_strict(&mutated).expect("structurally valid");
607 assert!(
608 proof
609 .verify(root(), NameHash::from_hex(MISSING_KEY).expect("key"))
610 .is_err()
611 );
612 }
613}