oasis_core_runtime/storage/mkvs/sync/
proof.rs

1use std::{
2    cell::RefCell,
3    collections::BTreeMap,
4    ops::{Deref, DerefMut},
5    rc::Rc,
6};
7
8use anyhow::{anyhow, Result};
9use arbitrary::Arbitrary;
10
11use crate::{
12    common::crypto::hash::Hash,
13    storage::mkvs::{marshal::Marshal, tree::*},
14};
15
16/// Proof entry type for full nodes.
17const PROOF_ENTRY_FULL: u8 = 0x01;
18/// Proof entry type for subtree hashes.
19const PROOF_ENTRY_HASH: u8 = 0x02;
20
21// Min and max supported proof versions.
22const MIN_PROOF_VERSION: u16 = 0;
23const MAX_PROOF_VERSION: u16 = 1;
24
25/// A raw proof entry.
26#[derive(Clone, Debug, Default, PartialEq, Eq, cbor::Encode, cbor::Decode, Arbitrary)]
27#[cbor(transparent)]
28pub struct RawProofEntry(pub Vec<u8>);
29
30impl AsRef<[u8]> for RawProofEntry {
31    fn as_ref(&self) -> &[u8] {
32        &self.0
33    }
34}
35
36impl Deref for RawProofEntry {
37    type Target = Vec<u8>;
38
39    fn deref(&self) -> &Self::Target {
40        &self.0
41    }
42}
43
44impl DerefMut for RawProofEntry {
45    fn deref_mut(&mut self) -> &mut Self::Target {
46        &mut self.0
47    }
48}
49
50impl From<RawProofEntry> for Vec<u8> {
51    fn from(val: RawProofEntry) -> Self {
52        val.0
53    }
54}
55
56impl From<Vec<u8>> for RawProofEntry {
57    fn from(v: Vec<u8>) -> RawProofEntry {
58        RawProofEntry(v)
59    }
60}
61
62/// A Merkle proof for a subtree.
63#[derive(Clone, Debug, Default, PartialEq, Eq, cbor::Encode, cbor::Decode)]
64pub struct Proof {
65    // The proof version.
66    //
67    // We don't use `Versioned` since we want version 0 proofs to be
68    // backwards compatible with the old structure which was not versioned.
69    //
70    // Version 0:
71    // Initial format.
72    //
73    // Version 1 change:
74    // Leaf nodes are included separately, as children. In version 0 the leaf node was
75    // serialized within the internal node.  The rationale behind this change is to eliminate
76    // the need to serialize all leaf nodes on the path when proving the existence of a
77    // specific value.
78    #[cbor(optional)]
79    pub v: u16,
80    /// The root hash this proof is for. This should only be used as a quick
81    /// sanity check and proof verification MUST use an independently obtained
82    /// root hash as the prover can provide any root.
83    pub untrusted_root: Hash,
84    /// Proof entries in pre-order traversal.
85    pub entries: Vec<Option<RawProofEntry>>,
86}
87
88struct ProofNode {
89    serialized: Vec<u8>,
90    children: Vec<Hash>,
91}
92
93/// A Merkle proof builder.
94pub struct ProofBuilder {
95    proof_version: u16,
96    root: Hash,
97    included: BTreeMap<Hash, ProofNode>,
98}
99
100impl ProofBuilder {
101    /// Create a new proof builder for the given root hash.
102    pub fn new(root: Hash) -> Self {
103        Self::new_with_version(root, MAX_PROOF_VERSION).unwrap()
104    }
105
106    /// Create a new proof builder for the given root hash and proof version.
107    pub fn new_with_version(root: Hash, proof_version: u16) -> Result<Self> {
108        if !(MIN_PROOF_VERSION..=MAX_PROOF_VERSION).contains(&proof_version) {
109            return Err(anyhow!(
110                "proof builder: unsupported proof version: {}",
111                proof_version
112            ));
113        }
114
115        Ok(Self {
116            proof_version,
117            root,
118            included: BTreeMap::new(),
119        })
120    }
121
122    /// Add a node to the set of included nodes.
123    ///
124    /// # Panics
125    ///
126    /// Panics if the node is not clean.
127    pub fn include(&mut self, node: &NodeBox) {
128        if !node.is_clean() {
129            panic!("proof builder: node is not clean");
130        }
131
132        // If node is already included, skip.
133        let nh = node.get_hash();
134        if self.included.contains_key(&nh) {
135            return;
136        }
137        let mut pn = ProofNode {
138            serialized: node
139                .compact_marshal_binary(self.proof_version)
140                .expect("marshaling node in proof"),
141            children: vec![],
142        };
143
144        // For internal nodes, also include children.
145        if let NodeBox::Internal(nd) = node {
146            fn get_child_hash(nd: &Rc<RefCell<NodePointer>>) -> Hash {
147                nd.borrow()
148                    .node
149                    .as_ref()
150                    .map(|n| n.borrow().get_hash())
151                    .unwrap_or_else(Hash::empty_hash)
152            }
153
154            if self.proof_version == 1 {
155                // In proof version 1, leaf nodes are included separately as children.
156                pn.children.push(get_child_hash(&nd.leaf_node));
157            }
158            pn.children.push(get_child_hash(&nd.left));
159            pn.children.push(get_child_hash(&nd.right));
160        }
161
162        self.included.insert(nh, pn);
163    }
164
165    /// Build the (unverified) proof.
166    pub fn build(&self) -> Proof {
167        let mut proof = Proof {
168            v: self.proof_version,
169            untrusted_root: self.root,
170            entries: vec![],
171        };
172        self._build(&mut proof, &self.root);
173
174        proof
175    }
176
177    fn _build(&self, p: &mut Proof, h: &Hash) {
178        if h.is_empty() {
179            // Append nil for empty nodes.
180            p.entries.push(None);
181            return;
182        }
183
184        match self.included.get(h) {
185            None => {
186                // Node is not included in this proof, just add hash of subtree.
187                let mut data = Vec::with_capacity(h.as_ref().len() + 1);
188                data.push(PROOF_ENTRY_HASH);
189                data.extend_from_slice(h.as_ref());
190
191                p.entries.push(Some(RawProofEntry(data)));
192            }
193            Some(pn) => {
194                // Pre-order traversal, add visited node.
195                let mut data = Vec::with_capacity(pn.serialized.len() + 1);
196                data.push(PROOF_ENTRY_FULL);
197                data.extend_from_slice(&pn.serialized);
198
199                p.entries.push(Some(RawProofEntry(data)));
200
201                // Recurse into children.
202                for ch in pn.children.iter() {
203                    self._build(p, ch);
204                }
205            }
206        }
207    }
208}
209
210/// A proof verifier enables verifying proofs returned by the ReadSyncer API.
211pub struct ProofVerifier;
212
213impl ProofVerifier {
214    /// Verify a proof and generate an in-memory subtree representing the
215    /// nodes which are included in the proof.
216    pub fn verify_proof(&self, root: Hash, proof: &Proof) -> Result<NodePtrRef> {
217        // Check proof version.
218        if !(MIN_PROOF_VERSION..=MAX_PROOF_VERSION).contains(&proof.v) {
219            return Err(anyhow!("verifier: unsupported proof version: {}", proof.v));
220        }
221
222        // Sanity check that the proof is for the correct root (as otherwise it
223        // makes no sense to verify the proof).
224        if proof.untrusted_root != root {
225            return Err(anyhow!(
226                "verifier: got proof for unexpected root (expected: {:?} got {:?})",
227                root,
228                proof.untrusted_root,
229            ));
230        }
231        if proof.entries.is_empty() {
232            return Err(anyhow!("verifier: empty proof"));
233        }
234
235        let (idx, root_node) = Self::_verify_proof(proof, 0)?;
236        // Make sure that all of the entries in the proof have been used. The returned index should
237        // point to just beyond the last element.
238        if idx != proof.entries.len() {
239            return Err(anyhow!("verifier: unused entries in proof"));
240        }
241        let root_hash = root_node.borrow().hash;
242        if root_hash != root {
243            return Err(anyhow!(
244                "verifier: bad root (expected: {:?} got {:?})",
245                root,
246                root_hash,
247            ));
248        }
249
250        Ok(root_node)
251    }
252
253    fn _verify_proof(proof: &Proof, idx: usize) -> Result<(usize, NodePtrRef)> {
254        if idx >= proof.entries.len() {
255            return Err(anyhow!("verifier: malformed proof"));
256        }
257        let entry = match &proof.entries[idx] {
258            Some(entry) => entry.as_ref(),
259            None => return Ok((idx + 1, NodePointer::null_ptr())),
260        };
261        if entry.is_empty() {
262            return Err(anyhow!("verifier: malformed proof"));
263        }
264
265        match entry[0] {
266            PROOF_ENTRY_FULL => {
267                // Full node.
268                let mut node = NodeBox::default();
269                node.unmarshal_binary(&entry[1..])?;
270
271                // For internal nodes, also decode children.
272                let mut pos = idx + 1;
273                if let NodeBox::Internal(ref mut nd) = node {
274                    match proof.v {
275                        0 => {
276                            // In proof version 0, leaf nodes are included within the internal node.
277                        }
278                        1 => {
279                            // In proof version 1, leaf nodes are included separately as children.
280                            (pos, nd.leaf_node) = Self::_verify_proof(proof, pos)?;
281                        }
282                        _ => {
283                            // Should not happen, checked in verify_proof.
284                            panic!("unsupported proof version: {:?}", proof.v)
285                        }
286                    }
287
288                    // Left.
289                    (pos, nd.left) = Self::_verify_proof(proof, pos)?;
290                    // Right.
291                    (pos, nd.right) = Self::_verify_proof(proof, pos)?;
292
293                    // Recompute hash as hashes were not recomputed for compact encoding.
294                    nd.update_hash();
295                }
296
297                Ok((pos, NodePointer::from_node(node)))
298            }
299            PROOF_ENTRY_HASH => {
300                // Hash of a node.
301                let entry = &entry[1..];
302                if entry.len() != Hash::len() {
303                    return Err(anyhow!("verifier: malformed hash entry"));
304                }
305
306                Ok((idx + 1, NodePointer::hash_ptr(entry.into())))
307            }
308            entry_type => Err(anyhow!(
309                "verifier: unexpected entry in proof ({:?})",
310                entry_type
311            )),
312        }
313    }
314}
315
316#[cfg(test)]
317mod test {
318    use base64::prelude::*;
319    use rustc_hex::ToHex;
320
321    use crate::storage::mkvs::{cache::Cache, sync::NoopReadSyncer};
322
323    use super::*;
324
325    #[test]
326    fn test_proof() {
327        // Test vectors generated by Go.
328
329        // V0 proof.
330        let test_vector_proof = BASE64_STANDARD.decode(
331            "omdlbnRyaWVzhUoBASQAa2V5IDACRgEBAQAAAlghAsFltYRhD4dAwHOdOmEigY1r02pJH6InhiibKlh9neYlWCECpsJnkjOnIgc4+\
332yfvpsqCcIYHh5eld1hNMWTT7arAfHFYIQLhNTLWRbks1RBf52ulnlOTO+7D5EZNMYFzTx8U46sCnm51bnRydXN0ZWRfcm9vdFggWeZ8L9wIuOEN0Iu2\
333uO/mFPzJZey4liX5fxf4fwcQRhM=",
334        ).unwrap();
335
336        let test_vector_root_hash =
337            "59e67c2fdc08b8e10dd08bb6b8efe614fcc965ecb89625f97f17f87f07104613";
338
339        // Proof should decode.
340        let proof: Proof =
341            cbor::from_slice(&test_vector_proof).expect("V0 proof should deserialize");
342        assert_eq!(proof.v, 0, "proof version should be 0");
343        let root_hash = Hash::from(test_vector_root_hash);
344
345        // Proof should round-trip.
346        assert_eq!(
347            test_vector_proof,
348            cbor::to_vec(proof.clone()),
349            "proof should round-trip"
350        );
351
352        // Proof should verify.
353        let pv = ProofVerifier;
354        pv.verify_proof(root_hash, &proof)
355            .expect("verify proof should not fail with a valid proof");
356
357        // Invalid proofs should not verify.
358
359        // Empty proof.
360        let empty_proof = Proof::default();
361        let result = pv.verify_proof(root_hash, &empty_proof);
362        assert!(
363            result.is_err(),
364            "verify proof should fail with an empty proof"
365        );
366
367        // Different root.
368        let bogus_hash = Hash::digest_bytes(b"i am a bogus hash");
369        let result = pv.verify_proof(bogus_hash, &proof);
370        assert!(
371            result.is_err(),
372            "verify proof should fail with a proof for a different root"
373        );
374
375        // Different hash element.
376        let mut corrupted = proof.clone();
377        corrupted.entries[4].as_mut().unwrap()[10] = 0x00;
378        let result = pv.verify_proof(root_hash, &corrupted);
379        assert!(
380            result.is_err(),
381            "verify proof should fail with invalid proof"
382        );
383
384        // Corrupted full node.
385        let mut corrupted = proof.clone();
386        corrupted.entries[0].as_mut().unwrap().truncate(3);
387        let result = pv.verify_proof(root_hash, &corrupted);
388        assert!(
389            result.is_err(),
390            "verify proof should fail with invalid proof"
391        );
392
393        // Corrupted hash.
394        let mut corrupted = proof.clone();
395        corrupted.entries[2].as_mut().unwrap().truncate(3);
396        let result = pv.verify_proof(root_hash, &corrupted);
397        assert!(
398            result.is_err(),
399            "verify proof should fail with invalid proof"
400        );
401
402        // Corrupted proof element type.
403        let mut corrupted = proof.clone();
404        corrupted.entries[3].as_mut().unwrap()[0] = 0xaa;
405        let result = pv.verify_proof(root_hash, &corrupted);
406        assert!(
407            result.is_err(),
408            "verify proof should fail with invalid proof"
409        );
410
411        // Missing elements.
412        let mut corrupted = proof.clone();
413        corrupted.entries.truncate(3);
414        let result = pv.verify_proof(root_hash, &corrupted);
415        assert!(
416            result.is_err(),
417            "verify proof should fail with invalid proof"
418        );
419
420        // V1 proof.
421        let test_vector_proof = BASE64_STANDARD.decode(
422            "o2F2AWdlbnRyaWVzh0oBASQAa2V5IDAC9kYBAQEAAAL2WCECwWW1hGEPh0DAc506YSKBjWvTakkfoieGKJsqWH2d5iVYIQKmwmeSM6ciBzj7J+\
423            +myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCBZ5nwv3Ai44Q3Qi7a47+\
424            YU/Mll7LiWJfl/F/h/BxBGEw=="
425        ).unwrap();
426
427        // Proof should decode.
428        let proof: Proof =
429            cbor::from_slice(&test_vector_proof).expect("V1 proof should deserialize");
430        assert_eq!(proof.v, 1, "proof version should be 1");
431        let root_hash = Hash::from(test_vector_root_hash);
432
433        // Proof should round-trip.
434        assert_eq!(
435            test_vector_proof,
436            cbor::to_vec(proof.clone()),
437            "proof should round-trip"
438        );
439
440        // Proof should verify.
441        let pv = ProofVerifier;
442        pv.verify_proof(root_hash, &proof)
443            .expect("verify proof should not fail with a valid proof");
444    }
445
446    #[test]
447    fn test_proof_builder_v1() {
448        // NOTE: Ensure this test matches TestProofV1 in go/storage/mkvs/syncer_test.go.
449
450        // Prepare test tree.
451        let mut tree = Tree::builder()
452            .with_root(Root {
453                hash: Hash::empty_hash(),
454                ..Default::default()
455            })
456            .build(Box::new(NoopReadSyncer));
457        for i in 0..11 {
458            let k = format!("key {}", i).into_bytes();
459            let v = format!("value {}", i).into_bytes();
460            tree.insert(&k, &v).expect("insert");
461        }
462        let roothash = tree.commit(Default::default(), 1).expect("commit");
463
464        let mut pb = ProofBuilder::new(roothash);
465
466        // Ensure proof matches Go side.
467        let proof = pb.build();
468        assert_eq!(
469            BASE64_STANDARD.encode(cbor::to_vec(proof)),
470            "o2F2AWdlbnRyaWVzgVghAqlAud7XYhorEEl8hG9G3Hd4OXl5VR1xvuLAepMZ5qpFbnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ=="
471        );
472
473        // Include root node.
474        let root_ptr = tree.cache.borrow().get_pending_root();
475        let root_node = root_ptr.borrow().get_node();
476        pb.include(&*root_node.borrow());
477        // Ensure proof matches Go side.
478        let proof = pb.build();
479        assert_eq!(
480            BASE64_STANDARD.encode(cbor::to_vec(proof)),
481		    "o2F2AWdlbnRyaWVzhEoBASQAa2V5IDAC9lghAhQ6RgqFtADx+B6VKE0CVRrfDHmwgZwU3ewsj4gswWv+WCEC4TUy1kW5LNUQX+drpZ5Tkzvuw+RGTTGBc08fFOOrAp5udW50cnVzdGVkX3Jvb3RYIKlAud7XYhorEEl8hG9G3Hd4OXl5VR1xvuLAepMZ5qpF",
482        );
483
484        // Include root.left node.
485        let root_left = noderef_as!(root_node, Internal).left.borrow().get_node();
486        pb.include(&*root_left.borrow());
487        // Ensure proof matches Go side.
488        let proof = pb.build();
489        assert_eq!(
490            BASE64_STANDARD.encode(cbor::to_vec(proof)),
491            "o2F2AWdlbnRyaWVzh0oBASQAa2V5IDAC9kYBAQEAAAL2WCEC+OrSSPCCo9/QXQt7IsunAp+eUqMndKBCu0NcGHx4HrhYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
492        );
493
494        // Include root.left.left node.
495        let root_left2 = noderef_as!(root_left, Internal).left.borrow().get_node();
496        pb.include(&*root_left2.borrow());
497
498        // Include root.left.left.left node.
499        let root_left3: Rc<RefCell<NodeBox>> =
500            noderef_as!(root_left2, Internal).left.borrow().get_node();
501        pb.include(&*root_left3.borrow());
502
503        // Include root.left.left.left.right node.
504        let root_left3_right = noderef_as!(root_left3, Internal).right.borrow().get_node();
505        pb.include(&*root_left3_right.borrow());
506
507        // Include root.left.left.left.right.left leaf node.
508        let bottom = noderef_as!(root_left3_right, Internal)
509            .left
510            .borrow()
511            .get_node();
512        pb.include(&*bottom.borrow());
513        // Ensure proof matches Go side.
514        let proof = pb.build();
515        assert_eq!(
516            BASE64_STANDARD.encode(cbor::to_vec(proof)),
517		    "o2F2AWdlbnRyaWVzkEoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZGAQEBAAAC9lghAlF8/rp9QOAd1qSchhUxDtVkpmnze6sjz5IfFhdOuaypRgEBAQCAAlghAldMzQwgHh/Ecm+rF+i31AnOgFYBipBAlcx5Tf5l4yW+VgEABgBrZXkgMTAIAAAAdmFsdWUgMTD2WCECDnYjQhsAp5fD+gf0W5YYFY6CnGURrEETtJvJp+ijH4xYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
518        );
519    }
520
521    #[test]
522    fn test_proof_extra_nodes() {
523        // V0 proof.
524        let test_vector_proof = BASE64_STANDARD.decode(
525                "omdlbnRyaWVzhUoBASQAa2V5IDACRgEBAQAAAlghAsFltYRhD4dAwHOdOmEigY1r02pJH6InhiibKlh9neYlWCECpsJnkjOnIgc4+\
526    yfvpsqCcIYHh5eld1hNMWTT7arAfHFYIQLhNTLWRbks1RBf52ulnlOTO+7D5EZNMYFzTx8U46sCnm51bnRydXN0ZWRfcm9vdFggWeZ8L9wIuOEN0Iu2\
527    uO/mFPzJZey4liX5fxf4fwcQRhM=",
528            ).unwrap();
529        let test_vector_root_hash =
530            "59e67c2fdc08b8e10dd08bb6b8efe614fcc965ecb89625f97f17f87f07104613";
531
532        // Proof should decode.
533        let mut proof: Proof =
534            cbor::from_slice(&test_vector_proof).expect("proof should deserialize");
535        let root_hash = Hash::from(test_vector_root_hash);
536
537        // Proof should verify.
538        let pv = ProofVerifier;
539        pv.verify_proof(root_hash, &proof)
540            .expect("verify proof should not fail with a valid proof");
541
542        // Duplicate some nodes and add them to the end.
543        proof.entries.push(proof.entries[0].clone());
544
545        pv.verify_proof(root_hash, &proof)
546            .expect_err("proof with extra data should fail to validate");
547
548        // V1 proof.
549        let test_vector_proof = BASE64_STANDARD.decode(
550                "o2F2AWdlbnRyaWVzh0oBASQAa2V5IDAC9kYBAQEAAAL2WCECwWW1hGEPh0DAc506YSKBjWvTakkfoieGKJsqWH2d5iVYIQKmwmeSM6ciBzj7J+\
551                +myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCBZ5nwv3Ai44Q3Qi7a47+\
552                YU/Mll7LiWJfl/F/h/BxBGEw=="
553            ).unwrap();
554
555        // Proof should decode.
556        let mut proof: Proof =
557            cbor::from_slice(&test_vector_proof).expect("V1 proof should deserialize");
558        assert_eq!(proof.v, 1, "proof version should be 1");
559        let root_hash = Hash::from(test_vector_root_hash);
560
561        // Proof should verify.
562        let pv = ProofVerifier;
563        pv.verify_proof(root_hash, &proof)
564            .expect("verify proof should not fail with a valid proof");
565
566        // Duplicate some nodes and add them to the end.
567        proof.entries.push(proof.entries[0].clone());
568        pv.verify_proof(root_hash, &proof)
569            .expect_err("verify proof should fail with an invalid proof");
570    }
571
572    #[test]
573    fn test_proof_builder_v0() {
574        // NOTE: Ensure this test matches TestProofV0 in go/storage/mkvs/syncer_test.go.
575
576        // Prepare test tree.
577        let mut tree = Tree::builder()
578            .with_root(Root {
579                hash: Hash::empty_hash(),
580                ..Default::default()
581            })
582            .build(Box::new(NoopReadSyncer));
583        for i in 0..10 {
584            let k = format!("key {}", i).into_bytes();
585            let v = format!("value {}", i).into_bytes();
586            tree.insert(&k, &v).expect("insert");
587        }
588        let roothash = tree.commit(Default::default(), 1).expect("commit");
589
590        // Ensure tree matches Go side.
591        assert_eq!(
592            roothash.0.to_hex::<String>(),
593            "59e67c2fdc08b8e10dd08bb6b8efe614fcc965ecb89625f97f17f87f07104613",
594        );
595
596        // Ensure proof matches Go side.
597        let mut pb = ProofBuilder::new_with_version(roothash, 0).expect("new proof builder v0");
598        let root_only_proof = pb.build();
599        assert_eq!(
600            BASE64_STANDARD.encode(cbor::to_vec(root_only_proof)),
601            "omdlbnRyaWVzgVghAlnmfC/cCLjhDdCLtrjv5hT8yWXsuJYl+X8X+H8HEEYTbnVudHJ1c3RlZF9yb290WCBZ5nwv3Ai44Q3Qi7a47+YU/Mll7LiWJfl/F/h/BxBGEw==",
602        );
603
604        // Include root node.
605        let root_ptr = tree.cache.borrow().get_pending_root();
606        let root_node = root_ptr.borrow().get_node();
607        pb.include(&*root_node.borrow());
608        // Include root.left node.
609        pb.include(
610            &*noderef_as!(root_node, Internal)
611                .left
612                .borrow()
613                .get_node()
614                .borrow(),
615        );
616        // Ensure proofs matches Go side.
617        let test_proof = pb.build();
618        assert_eq!(
619            BASE64_STANDARD.encode(cbor::to_vec(test_proof)),
620            "omdlbnRyaWVzhUoBASQAa2V5IDACRgEBAQAAAlghAsFltYRhD4dAwHOdOmEigY1r02pJH6InhiibKlh9neYlWCECpsJnkjOnIgc4+yfvpsqCcIYHh5eld1hNMWTT7arAfHFYIQLhNTLWRbks1RBf52ulnlOTO+7D5EZNMYFzTx8U46sCnm51bnRydXN0ZWRfcm9vdFggWeZ8L9wIuOEN0Iu2uO/mFPzJZey4liX5fxf4fwcQRhM=",
621        );
622    }
623
624    #[test]
625    fn test_tree_proofs() {
626        // NOTE: Ensure this test matches TestTreeProofs in go/storage/mkvs/syncer_test.go.
627
628        // Prepare test tree.
629        let mut tree = Tree::builder()
630            .with_root(Root {
631                hash: Hash::empty_hash(),
632                ..Default::default()
633            })
634            .build(Box::new(NoopReadSyncer));
635        let mut keys = vec![];
636        for i in 0..11 {
637            let k = format!("key {}", i).into_bytes();
638            let v = format!("value {}", i).into_bytes();
639            tree.insert(&k, &v).expect("insert");
640            keys.push(k);
641        }
642        let roothash = tree.commit(Default::default(), 1).expect("commit");
643        // Ensure tree matches Go side.
644        assert_eq!(
645            roothash.0.to_hex::<String>(),
646            "a940b9ded7621a2b10497c846f46dc7778397979551d71bee2c07a9319e6aa45",
647        );
648
649        for tc in vec![
650            // Note: Tree::get_proof doesn't support version 0 proofs.
651            // We test only version 1 proofs here.
652            (
653                // Proof v.
654                1,
655                vec![
656                    // 0.
657                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZGAQEBAAAC9lQBAAUAa2V5IDAHAAAAdmFsdWUgMFghAlO8PtYkGTEg304b/z/cv4oH6+BRaJ88layf7VgIl3xTWCECDnYjQhsAp5fD+gf0W5YYFY6CnGURrEETtJvJp+ijH4xYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
658                    // 1.
659                    "o2F2AWdlbnRyaWVzkEoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZGAQEBAAAC9lghAlF8/rp9QOAd1qSchhUxDtVkpmnze6sjz5IfFhdOuaypRgEBAQCAAlQBAAUAa2V5IDEHAAAAdmFsdWUgMVghAm2EG0dH85+yEl5rdT67+D59/gbjHB9qDtnCcv0kkuje9lghAg52I0IbAKeXw/oH9FuWGBWOgpxlEaxBE7Sbyafoox+MWCECpsJnkjOnIgc4+yfvpsqCcIYHh5eld1hNMWTT7arAfHFYIQLhNTLWRbks1RBf52ulnlOTO+7D5EZNMYFzTx8U46sCnm51bnRydXN0ZWRfcm9vdFggqUC53tdiGisQSXyEb0bcd3g5eXlVHXG+4sB6kxnmqkU=",
660                    // 2.
661                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZYIQLnu/nMm00WQo9ZxRbRFM/hVtoTov4Phs3vIQ/6jS/29kYBAQEAgAL2VAEABQBrZXkgMgcAAAB2YWx1ZSAyWCECJtIdvBvSs2Vh4Z1ghY3zvHvK8JsoBmt3+dBpRCNdA/xYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
662                    // 3.
663                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZYIQLnu/nMm00WQo9ZxRbRFM/hVtoTov4Phs3vIQ/6jS/29kYBAQEAgAL2WCECoYj1TutUHeB1K0anT1hRts8AKOw8AfEtn963XMVxV1xUAQAFAGtleSAzBwAAAHZhbHVlIDNYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
664                    // 4.
665                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2WCEC+OrSSPCCo9/QXQt7IsunAp+eUqMndKBCu0NcGHx4HrhGAQEBAIAC9kYBAQEAAAL2VAEABQBrZXkgNAcAAAB2YWx1ZSA0WCEC7uES0HThvwiREsS6OKGDOodNGn7WGC3BTBJSLBIsJf1YIQK31gqPbwp33M7yKb2VSo7eB8p4jZZmYGnJ7njeFBGHtVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
666                    // 5.
667                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2WCEC+OrSSPCCo9/QXQt7IsunAp+eUqMndKBCu0NcGHx4HrhGAQEBAIAC9kYBAQEAAAL2WCECxgplEp2jBopznMqoBJZ1ezCE7IO2Bb5CqLypC+IiEhpUAQAFAGtleSA1BwAAAHZhbHVlIDVYIQK31gqPbwp33M7yKb2VSo7eB8p4jZZmYGnJ7njeFBGHtVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
668                    // 6.
669                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2WCEC+OrSSPCCo9/QXQt7IsunAp+eUqMndKBCu0NcGHx4HrhGAQEBAIAC9lghAivLwJbWkwZ8nROaPHGxpfthiG8vqyPbvzhkEEX793dIRgEBAQCAAvZUAQAFAGtleSA2BwAAAHZhbHVlIDZYIQK96CvAaM4vOReqLe+AoO6KajYFZiUsAyvSi8rEgClU7FghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
670                    // 7.
671                    "o2F2AWdlbnRyaWVzjUoBASQAa2V5IDAC9kYBAQEAAAL2WCEC+OrSSPCCo9/QXQt7IsunAp+eUqMndKBCu0NcGHx4HrhGAQEBAIAC9lghAivLwJbWkwZ8nROaPHGxpfthiG8vqyPbvzhkEEX793dIRgEBAQCAAvZYIQICPF9slSfLMzCKpIGUKFWpXWq5dxfVdfe6wfGW6xjer1QBAAUAa2V5IDcHAAAAdmFsdWUgN1ghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
672                    // 8.
673                    "o2F2AWdlbnRyaWVzh0oBASQAa2V5IDAC9lghAhQ6RgqFtADx+B6VKE0CVRrfDHmwgZwU3ewsj4gswWv+RgEBAwCAAvZUAQAFAGtleSA4BwAAAHZhbHVlIDhYIQINczJ806eMr+T/iGsJmo8/JQFXZtjy1/k+as0V9FdfVG51bnRydXN0ZWRfcm9vdFggqUC53tdiGisQSXyEb0bcd3g5eXlVHXG+4sB6kxnmqkU=",
674                    // 9.
675                    "o2F2AWdlbnRyaWVzh0oBASQAa2V5IDAC9lghAhQ6RgqFtADx+B6VKE0CVRrfDHmwgZwU3ewsj4gswWv+RgEBAwCAAvZYIQIwwW7eyXCi2yXyFCzFD9U+Ssy1gwSwiskBQfk+9KCUA1QBAAUAa2V5IDkHAAAAdmFsdWUgOW51bnRydXN0ZWRfcm9vdFggqUC53tdiGisQSXyEb0bcd3g5eXlVHXG+4sB6kxnmqkU=",
676                    // 10.
677                    "o2F2AWdlbnRyaWVzkEoBASQAa2V5IDAC9kYBAQEAAAL2RgEBAQAAAvZGAQEBAAAC9lghAlF8/rp9QOAd1qSchhUxDtVkpmnze6sjz5IfFhdOuaypRgEBAQCAAlghAldMzQwgHh/Ecm+rF+i31AnOgFYBipBAlcx5Tf5l4yW+VgEABgBrZXkgMTAIAAAAdmFsdWUgMTD2WCECDnYjQhsAp5fD+gf0W5YYFY6CnGURrEETtJvJp+ijH4xYIQKmwmeSM6ciBzj7J++myoJwhgeHl6V3WE0xZNPtqsB8cVghAuE1MtZFuSzVEF/na6WeU5M77sPkRk0xgXNPHxTjqwKebnVudHJ1c3RlZF9yb290WCCpQLne12IaKxBJfIRvRtx3eDl5eVUdcb7iwHqTGeaqRQ==",
678                ],
679            ),
680            ]{
681                // Ensure tree proofs match Go side.
682                for (i, k) in tc.1.iter().enumerate() {
683                    let proof = tree.get_proof(&keys[i]).expect("get proof works").expect("proof exists");
684                    assert_eq!(
685                        BASE64_STANDARD.encode(cbor::to_vec(proof.clone())),
686                        *k,
687                        "expected proof for keys[{}]",
688                        i
689                    );
690                    // Proof should verify.
691                    let pv = ProofVerifier;
692                    pv.verify_proof(roothash, &proof)
693                        .expect("verify proof should not fail with a valid proof");
694                }
695            };
696    }
697}
oasis_core_runtime/storage/mkvs/sync/proof.rs

oasis_core_runtime/storage/mkvs/sync/
proof.rs
