Skip to main content

hns_urkel_proof/
lib.rs

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    /// Decode with upstream HSD/Urkel compatibility, including its behavior of
80    /// ignoring trailing bytes. Use `decode_strict` at trust boundaries.
81    pub fn decode_hsd(raw: &[u8]) -> Result<Self, UrkelError> {
82        Self::decode_inner(raw).map(|(proof, _)| proof)
83    }
84
85    /// Decode one canonical proof and reject ignored trailing or non-minimal
86    /// prefix/bitmap encodings.
87    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}