jmt/tree/
ics23_impl.rs

1use alloc::vec;
2use alloc::vec::Vec;
3use anyhow::Result;
4
5use crate::{
6    proof::{SparseMerkleProof, INTERNAL_DOMAIN_SEPARATOR, LEAF_DOMAIN_SEPARATOR},
7    storage::HasPreimage,
8    storage::TreeReader,
9    tree::ExclusionProof,
10    JellyfishMerkleTree, KeyHash, OwnedValue, SimpleHasher, Version,
11    SPARSE_MERKLE_PLACEHOLDER_HASH,
12};
13
14fn sparse_merkle_proof_to_ics23_existence_proof<H: SimpleHasher>(
15    key: Vec<u8>,
16    value: Vec<u8>,
17    proof: &SparseMerkleProof<H>,
18) -> ics23::ExistenceProof {
19    let key_hash: KeyHash = KeyHash::with::<H>(key.as_slice());
20    let mut path = Vec::new();
21    let mut skip = 256 - proof.siblings().len();
22    let mut sibling_idx = 0;
23
24    for byte_idx in (0..32).rev() {
25        // The JMT proofs iterate over the bits in MSB order
26        for bit_idx in 0..8 {
27            if skip > 0 {
28                skip -= 1;
29                continue;
30            } else {
31                let bit = (key_hash.0[byte_idx] >> bit_idx) & 0x1;
32                // ICS23 InnerOp computes
33                //    hash( prefix || current || suffix )
34                // so we want to construct (prefix, suffix) so that this is
35                // the correct hash-of-internal-node
36                let (prefix, suffix) = if bit == 1 {
37                    // We want hash( domsep || sibling || current )
38                    // so prefix = domsep || sibling
39                    //    suffix = (empty)
40                    let mut prefix = Vec::with_capacity(16 + 32);
41                    prefix.extend_from_slice(INTERNAL_DOMAIN_SEPARATOR);
42                    prefix.extend_from_slice(&proof.siblings()[sibling_idx].hash::<H>());
43                    (prefix, Vec::new())
44                } else {
45                    // We want hash( domsep || current || sibling )
46                    // so prefix = domsep
47                    //    suffix = sibling
48                    let prefix = INTERNAL_DOMAIN_SEPARATOR.to_vec();
49                    let suffix = proof.siblings()[sibling_idx].hash::<H>().to_vec();
50                    (prefix, suffix)
51                };
52                path.push(ics23::InnerOp {
53                    hash: ics23::HashOp::Sha256.into(),
54                    prefix,
55                    suffix,
56                });
57                sibling_idx += 1;
58            }
59        }
60    }
61
62    ics23::ExistenceProof {
63        key,
64        value,
65        path,
66        leaf: Some(ics23::LeafOp {
67            hash: ics23::HashOp::Sha256.into(),
68            prehash_key: ics23::HashOp::Sha256.into(),
69            prehash_value: ics23::HashOp::Sha256.into(),
70            length: ics23::LengthOp::NoPrefix.into(),
71            prefix: LEAF_DOMAIN_SEPARATOR.to_vec(),
72        }),
73    }
74}
75
76impl<'a, R, H> JellyfishMerkleTree<'a, R, H>
77where
78    R: 'a + TreeReader + HasPreimage,
79    H: SimpleHasher,
80{
81    fn exclusion_proof_to_ics23_nonexistence_proof(
82        &self,
83        key: Vec<u8>,
84        version: Version,
85        proof: &ExclusionProof<H>,
86    ) -> Result<ics23::NonExistenceProof> {
87        match proof {
88            ExclusionProof::Leftmost {
89                leftmost_right_proof,
90            } => {
91                let key_hash = leftmost_right_proof
92                    .leaf()
93                    .expect("must have leaf")
94                    .key_hash();
95                let key_left_proof = self
96                    .reader
97                    .preimage(key_hash)?
98                    .ok_or(anyhow::anyhow!("missing preimage for key hash"))?;
99
100                let value = self
101                    .get(key_hash, version)?
102                    .ok_or(anyhow::anyhow!("missing value for key hash"))?;
103
104                let leftmost_right_proof = sparse_merkle_proof_to_ics23_existence_proof(
105                    key_left_proof.clone(),
106                    value.clone(),
107                    leftmost_right_proof,
108                );
109
110                Ok(ics23::NonExistenceProof {
111                    key,
112                    right: Some(leftmost_right_proof),
113                    left: None,
114                })
115            }
116            ExclusionProof::Middle {
117                leftmost_right_proof,
118                rightmost_left_proof,
119            } => {
120                let leftmost_key_hash = leftmost_right_proof
121                    .leaf()
122                    .expect("must have leaf")
123                    .key_hash();
124                let value_leftmost = self
125                    .get(leftmost_key_hash, version)?
126                    .ok_or(anyhow::anyhow!("missing value for key hash"))?;
127                let key_leftmost = self
128                    .reader
129                    .preimage(leftmost_key_hash)?
130                    .ok_or(anyhow::anyhow!("missing preimage for key hash"))?;
131                let leftmost_right_proof = sparse_merkle_proof_to_ics23_existence_proof(
132                    key_leftmost.clone(),
133                    value_leftmost.clone(),
134                    leftmost_right_proof,
135                );
136
137                let rightmost_key_hash = rightmost_left_proof
138                    .leaf()
139                    .expect("must have leaf")
140                    .key_hash();
141                let value_rightmost = self
142                    .get(rightmost_key_hash, version)?
143                    .ok_or(anyhow::anyhow!("missing value for key hash"))?;
144                let key_rightmost = self
145                    .reader
146                    .preimage(rightmost_key_hash)?
147                    .ok_or(anyhow::anyhow!("missing preimage for key hash"))?;
148                let rightmost_left_proof = sparse_merkle_proof_to_ics23_existence_proof(
149                    key_rightmost.clone(),
150                    value_rightmost.clone(),
151                    rightmost_left_proof,
152                );
153
154                Ok(ics23::NonExistenceProof {
155                    key,
156                    right: Some(leftmost_right_proof),
157                    left: Some(rightmost_left_proof),
158                })
159            }
160            ExclusionProof::Rightmost {
161                rightmost_left_proof,
162            } => {
163                let rightmost_key_hash = rightmost_left_proof
164                    .leaf()
165                    .expect("must have leaf")
166                    .key_hash();
167                let value_rightmost = self
168                    .get(rightmost_key_hash, version)?
169                    .ok_or(anyhow::anyhow!("missing value for key hash"))?;
170                let key_rightmost = self
171                    .reader
172                    .preimage(rightmost_key_hash)?
173                    .ok_or(anyhow::anyhow!("missing preimage for key hash"))?;
174                let rightmost_left_proof = sparse_merkle_proof_to_ics23_existence_proof(
175                    key_rightmost.clone(),
176                    value_rightmost.clone(),
177                    rightmost_left_proof,
178                );
179
180                Ok(ics23::NonExistenceProof {
181                    key,
182                    right: None,
183                    left: Some(rightmost_left_proof),
184                })
185            }
186        }
187    }
188
189    /// Returns the value corresponding to the specified key (if there is a value associated with it)
190    /// along with an [ics23::CommitmentProof] proving either the presence of the value at that key,
191    /// or the absence of any value at that key, depending on which is the case.
192    pub fn get_with_ics23_proof(
193        &self,
194        key: Vec<u8>,
195        version: Version,
196    ) -> Result<(Option<OwnedValue>, ics23::CommitmentProof)> {
197        let key_hash: KeyHash = KeyHash::with::<H>(key.as_slice());
198        let proof_or_exclusion = self.get_with_exclusion_proof(key_hash, version)?;
199
200        match proof_or_exclusion {
201            Ok((value, proof)) => {
202                let ics23_exist =
203                    sparse_merkle_proof_to_ics23_existence_proof(key, value.clone(), &proof);
204
205                Ok((
206                    Some(value),
207                    ics23::CommitmentProof {
208                        proof: Some(ics23::commitment_proof::Proof::Exist(ics23_exist)),
209                    },
210                ))
211            }
212            Err(exclusion_proof) => {
213                let ics23_nonexist = self.exclusion_proof_to_ics23_nonexistence_proof(
214                    key,
215                    version,
216                    &exclusion_proof,
217                )?;
218
219                Ok((
220                    None,
221                    ics23::CommitmentProof {
222                        proof: Some(ics23::commitment_proof::Proof::Nonexist(ics23_nonexist)),
223                    },
224                ))
225            }
226        }
227    }
228}
229
230pub fn ics23_spec() -> ics23::ProofSpec {
231    ics23::ProofSpec {
232        leaf_spec: Some(ics23::LeafOp {
233            hash: ics23::HashOp::Sha256.into(),
234            prehash_key: ics23::HashOp::Sha256.into(),
235            prehash_value: ics23::HashOp::Sha256.into(),
236            length: ics23::LengthOp::NoPrefix.into(),
237            prefix: LEAF_DOMAIN_SEPARATOR.to_vec(),
238        }),
239        inner_spec: Some(ics23::InnerSpec {
240            hash: ics23::HashOp::Sha256.into(),
241            child_order: vec![0, 1],
242            min_prefix_length: INTERNAL_DOMAIN_SEPARATOR.len() as i32,
243            max_prefix_length: INTERNAL_DOMAIN_SEPARATOR.len() as i32,
244            child_size: 32,
245            empty_child: SPARSE_MERKLE_PLACEHOLDER_HASH.to_vec(),
246        }),
247        min_depth: 0,
248        max_depth: 64,
249        prehash_key_before_comparison: true,
250    }
251}
252
253#[cfg(test)]
254mod tests {
255    use alloc::format;
256    use ics23::{commitment_proof::Proof, HostFunctionsManager, NonExistenceProof};
257    use proptest::prelude::*;
258    use proptest::strategy::Strategy;
259    use sha2::Sha256;
260
261    use super::*;
262    use crate::{mock::MockTreeStore, KeyHash, TransparentHasher, SPARSE_MERKLE_PLACEHOLDER_HASH};
263
264    proptest! {
265         #![proptest_config(ProptestConfig {
266             cases: 1000, .. ProptestConfig::default()
267         })]
268
269        #[test]
270        /// Assert that the Ics23 bonding path calculations are correct.
271        /// To achieve this, the uses a strategy that consists in:
272        /// 1. generating a sorted vector of key preimages
273        /// 2. instantiating a JMT over a `TransparentHasher`
274        ///
275        /// The last point allow us to easily test that for a given key
276        /// that is *in* the JMT, we can generate two non-existent keys
277        /// that are "neighbor" to `k`: (k-1, k+1).
278        ///
279        /// To recap, we generate a vector of sorted key <k_1, ... k_n>;
280        /// then, we iterate over each existing key `k_i` and compute a
281        ///     tuple of neighbors (`k_i - 1`, `k_i + 1`) which are *not*
282        ///     in the tree.
283        /// Equipped with those nonexisting neighbors, we check for exclusion
284        /// in the tree, and specifically assert that the generated proof contains:
285        /// 1. the initial key we requested (i.e. `k_i + 1` or `k_i - 1`)
286        /// 2. the correct left neighbor (i.e. `k_{i-1}`, or `k_{i+1}`, or none`)
287        /// 2. the correct right neighbor (i.e. `k_{i-1}`, or `k_{i+1}`, or none`)
288        /// across configurations e.g. bounding path for a leftmost or rightmost subtree.
289        /// More context available in #104.
290         fn test_ics23_bounding_path_simple(key_seeds in key_strategy()) {
291             let mut preimages: Vec<String> = key_seeds.into_iter().filter(|k| *k!=0).map(|k| format!("{k:032x}")).collect();
292             preimages.sort();
293             preimages.dedup();
294
295           assert!(preimages.len() > 0);
296
297           let store = MockTreeStore::default();
298           let tree = JellyfishMerkleTree::<_, TransparentHasher>::new(&store);
299
300           // Our key preimages and key hashes are identical, but we still need to populate
301           // the mock store so that ics23 internal queries can resolve.
302           for preimage in preimages.iter() {
303             store.put_key_preimage(KeyHash::with::<TransparentHasher>(preimage.clone()), preimage.clone().as_bytes().to_vec().as_ref());
304           }
305
306           let (_, write_batch) = tree.put_value_set(
307               preimages.iter().enumerate().map(|(i,k)| (KeyHash::with::<TransparentHasher>(k.as_bytes()), Some(i.to_be_bytes().to_vec()))),
308               1
309           ).unwrap();
310
311           store.write_tree_update_batch(write_batch).expect("can write to mock storage");
312
313           let len_preimages = preimages.len();
314
315           for (idx, existing_key) in preimages.iter().enumerate() {
316            // For each existing key, we generate two alternative keys that are not
317            // in the tree. One that is one bit "ahead" and one that is one bit after.
318            // e.g.  0x5 -> 0x4 and 0x6
319            let (smaller_key, bigger_key) = generate_adjacent_keys(existing_key);
320
321            let (v, proof) = tree.get_with_ics23_proof(smaller_key.as_bytes().to_vec(), 1).expect("can query tree");
322            assert!(v.is_none(), "the key should not exist!");
323            let proof = proof.proof.expect("a proof is present");
324            if let Proof::Nonexist(NonExistenceProof { key, left, right }) = proof {
325              // Basic check that we are getting back the key that we queried.
326              assert_eq!(key, smaller_key.as_bytes().to_vec());
327
328             // The expected predecessor to the nonexistent key `k_i - 1` is `k_{i-1}`, unless `i=0`.
329             let expected_left_neighbor = if idx == 0 { None } else { preimages.get(idx-1) };
330             // The expected successor to the nonexistent key `k_i - 1` is `k_{i+1}`.
331             let expected_right_neighbor = Some(existing_key);
332
333             let reported_left_neighbor = left.clone().map(|existence_proof| String::from_utf8_lossy(&existence_proof.key).into_owned());
334             let reported_right_neighbor = right.clone().map(|existence_proof| String::from_utf8_lossy(&existence_proof.key).into_owned());
335
336             assert_eq!(expected_left_neighbor.cloned(), reported_left_neighbor);
337             assert_eq!(expected_right_neighbor.cloned(), reported_right_neighbor);
338           } else {
339                unreachable!("we have assessed that the value is `None`")
340            }
341
342            let (v, proof) = tree.get_with_ics23_proof(bigger_key.as_bytes().to_vec(), 1).expect("can query tree");
343            assert!(v.is_none(), "the key should not exist!");
344            let proof = proof.proof.expect("a proof is present");
345            if let Proof::Nonexist(NonExistenceProof { key, left, right }) = proof {
346                    // Basic check that we are getting back the key that we queried.
347                    assert_eq!(key, bigger_key.as_bytes().to_vec());
348                    let reported_left_neighbor = left.clone().map(|existence_proof| String::from_utf8_lossy(&existence_proof.key).into_owned());
349                    let reported_right_neighbor = right.clone().map(|existence_proof| String::from_utf8_lossy(&existence_proof.key).into_owned());
350
351                    // The expected predecessor to the nonexistent key `k_i + 1` is `k_{i}`.
352                    let expected_left_neighbor = Some(existing_key);
353                    // The expected successor to the nonexistent key `k_i + 1` is `k_{i+1}`.
354                    let expected_right_neighbor = if idx == len_preimages - 1 { None }  else { preimages.get(idx+1) };
355
356                   assert_eq!(expected_left_neighbor.cloned(), reported_left_neighbor);
357                   assert_eq!(expected_right_neighbor.cloned(), reported_right_neighbor);
358             } else {
359                 unreachable!("we have assessed that the value is `None`")
360             }
361         }
362     }
363
364     #[test]
365    fn test_jmt_ics23_nonexistence(keys: Vec<Vec<u8>>) {
366     test_jmt_ics23_nonexistence_with_keys(keys.into_iter().filter(|k| k.len() != 0));
367     }
368     }
369
370    fn key_strategy() -> impl Strategy<Value = Vec<u128>> {
371        proptest::collection::btree_set(u64::MAX as u128..=u128::MAX, 200)
372            .prop_map(|set| set.into_iter().collect())
373    }
374    fn generate_adjacent_keys(hex: &String) -> (String, String) {
375        let value = u128::from_str_radix(hex.as_str(), 16).expect("valid hexstring");
376        let prev = value - 1;
377        let next = value + 1;
378        let p = format!("{prev:032x}");
379        let n = format!("{next:032x}");
380        (p, n)
381    }
382
383    fn test_jmt_ics23_nonexistence_with_keys(keys: impl Iterator<Item = Vec<u8>>) {
384        let db = MockTreeStore::default();
385        let tree = JellyfishMerkleTree::<_, Sha256>::new(&db);
386
387        let mut kvs = Vec::new();
388
389        // Ensure that the tree contains at least one key-value pair
390        kvs.push((KeyHash::with::<Sha256>(b"key"), Some(b"value1".to_vec())));
391        db.put_key_preimage(KeyHash::with::<Sha256>(b"key"), &b"key".to_vec());
392
393        for key_preimage in keys {
394            // Since we hardcode the check for key, ensure that it's not inserted randomly by proptest
395            if key_preimage == b"notexist" {
396                continue;
397            }
398            let key_hash = KeyHash::with::<Sha256>(key_preimage.as_slice());
399            let value = vec![0u8; 32];
400            kvs.push((key_hash, Some(value)));
401            db.put_key_preimage(key_hash, &key_preimage.to_vec());
402        }
403
404        let (new_root_hash, batch) = tree.put_value_set(kvs, 0).unwrap();
405        db.write_tree_update_batch(batch).unwrap();
406
407        let (value_retrieved, commitment_proof) =
408            tree.get_with_ics23_proof(b"notexist".to_vec(), 0).unwrap();
409
410        let key_hash = KeyHash::with::<Sha256>(b"notexist".as_slice());
411        let proof_or_exclusion = tree.get_with_exclusion_proof(key_hash, 0).unwrap();
412
413        use crate::tree::ExclusionProof::{Leftmost, Middle, Rightmost};
414        match proof_or_exclusion {
415            Ok(_) => panic!("expected nonexistence proof"),
416            Err(exclusion_proof) => match exclusion_proof {
417                Leftmost {
418                    leftmost_right_proof,
419                } => {
420                    if leftmost_right_proof.root_hash() != new_root_hash {
421                        panic!(
422                            "root hash mismatch. siblings: {:?}, smph: {:?}",
423                            leftmost_right_proof.siblings(),
424                            SPARSE_MERKLE_PLACEHOLDER_HASH
425                        );
426                    }
427
428                    assert!(ics23::verify_non_membership::<HostFunctionsManager>(
429                        &commitment_proof,
430                        &ics23_spec(),
431                        &new_root_hash.0.to_vec(),
432                        b"notexist"
433                    ));
434
435                    assert_eq!(value_retrieved, None)
436                }
437                Rightmost {
438                    rightmost_left_proof,
439                } => {
440                    if rightmost_left_proof.root_hash() != new_root_hash {
441                        panic!(
442                            "root hash mismatch. siblings: {:?}, smph: {:?}",
443                            rightmost_left_proof.siblings(),
444                            SPARSE_MERKLE_PLACEHOLDER_HASH
445                        );
446                    }
447
448                    assert!(ics23::verify_non_membership::<HostFunctionsManager>(
449                        &commitment_proof,
450                        &ics23_spec(),
451                        &new_root_hash.0.to_vec(),
452                        b"notexist"
453                    ));
454
455                    assert_eq!(value_retrieved, None)
456                }
457                Middle {
458                    leftmost_right_proof,
459                    rightmost_left_proof,
460                } => {
461                    if leftmost_right_proof.root_hash() != new_root_hash {
462                        let good_proof = tree
463                            .get_with_proof(leftmost_right_proof.leaf().unwrap().key_hash(), 0)
464                            .unwrap();
465                        panic!(
466                            "root hash mismatch. bad proof: {:?}, good proof: {:?}",
467                            leftmost_right_proof, good_proof
468                        );
469                    }
470                    if rightmost_left_proof.root_hash() != new_root_hash {
471                        panic!(
472                            "root hash mismatch. siblings: {:?}",
473                            rightmost_left_proof.siblings()
474                        );
475                    }
476
477                    assert!(ics23::verify_non_membership::<HostFunctionsManager>(
478                        &commitment_proof,
479                        &ics23_spec(),
480                        &new_root_hash.0.to_vec(),
481                        b"notexist"
482                    ));
483
484                    assert_eq!(value_retrieved, None)
485                }
486            },
487        }
488
489        assert!(!ics23::verify_non_membership::<HostFunctionsManager>(
490            &commitment_proof,
491            &ics23_spec(),
492            &new_root_hash.0.to_vec(),
493            b"key",
494        ));
495    }
496
497    #[test]
498    #[should_panic]
499    fn test_jmt_ics23_nonexistence_single_empty_key() {
500        test_jmt_ics23_nonexistence_with_keys(vec![vec![]].into_iter());
501    }
502
503    #[test]
504    fn test_jmt_ics23_existence() {
505        let db = MockTreeStore::default();
506        let tree = JellyfishMerkleTree::<_, Sha256>::new(&db);
507
508        let key = b"key";
509        let key_hash = KeyHash::with::<Sha256>(&key);
510
511        // For testing, insert multiple values into the tree
512        let mut kvs = Vec::new();
513        kvs.push((key_hash, Some(b"value".to_vec())));
514        // make sure we have some sibling nodes, through carefully constructed k/v entries that will have overlapping paths
515        for i in 1..4 {
516            let mut overlap_key = KeyHash([0; 32]);
517            overlap_key.0[0..i].copy_from_slice(&key_hash.0[0..i]);
518            kvs.push((overlap_key, Some(b"bogus value".to_vec())));
519        }
520
521        let (new_root_hash, batch) = tree.put_value_set(kvs, 0).unwrap();
522        db.write_tree_update_batch(batch).unwrap();
523
524        let (value_retrieved, commitment_proof) =
525            tree.get_with_ics23_proof(b"key".to_vec(), 0).unwrap();
526
527        assert!(ics23::verify_membership::<HostFunctionsManager>(
528            &commitment_proof,
529            &ics23_spec(),
530            &new_root_hash.0.to_vec(),
531            b"key",
532            b"value",
533        ));
534
535        assert_eq!(value_retrieved.unwrap(), b"value");
536    }
537
538    #[test]
539    fn test_jmt_ics23_existence_random_keys() {
540        let db = MockTreeStore::default();
541        let tree = JellyfishMerkleTree::<_, Sha256>::new(&db);
542
543        const MAX_VERSION: u64 = 1 << 14;
544
545        for version in 0..=MAX_VERSION {
546            let key = format!("key{}", version).into_bytes();
547            let value = format!("value{}", version).into_bytes();
548            let (_root, batch) = tree
549                .put_value_set(vec![(KeyHash::with::<Sha256>(key), Some(value))], version)
550                .unwrap();
551            db.write_tree_update_batch(batch).unwrap();
552        }
553
554        let value_maxversion = format!("value{}", MAX_VERSION).into_bytes();
555
556        let (value_retrieved, commitment_proof) = tree
557            .get_with_ics23_proof(format!("key{}", MAX_VERSION).into_bytes(), MAX_VERSION)
558            .unwrap();
559
560        let root_hash = tree.get_root_hash(MAX_VERSION).unwrap().0.to_vec();
561
562        assert!(ics23::verify_membership::<HostFunctionsManager>(
563            &commitment_proof,
564            &ics23_spec(),
565            &root_hash,
566            format!("key{}", MAX_VERSION).as_bytes(),
567            format!("value{}", MAX_VERSION).as_bytes(),
568        ));
569
570        assert_eq!(value_retrieved.unwrap(), value_maxversion);
571    }
572
573    #[test]
574    /// Write four keys into the JMT, and query an ICS23 proof for a nonexistent
575    /// key. This reproduces a bug that was fixed in release `0.8.0`
576    fn test_jmt_ics23_nonexistence_simple() {
577        use crate::Sha256Jmt;
578        let db = MockTreeStore::default();
579        let tree = Sha256Jmt::new(&db);
580
581        const MAX_VERSION: u64 = 3;
582
583        for version in 0..=MAX_VERSION {
584            let key_str = format!("key-{}", version);
585            let key = key_str.clone().into_bytes();
586            let value_str = format!("value-{}", version);
587            let value = value_str.clone().into_bytes();
588            let keys = vec![key.clone()];
589            let values = vec![value];
590            let value_set = keys
591                .into_iter()
592                .zip(values.into_iter())
593                .map(|(k, v)| (KeyHash::with::<Sha256>(&k), Some(v)))
594                .collect::<Vec<_>>();
595            let key_hash = KeyHash::with::<Sha256>(&key);
596
597            db.put_key_preimage(key_hash, &key);
598            let (_root, batch) = tree.put_value_set(value_set, version).unwrap();
599            db.write_tree_update_batch(batch)
600                .expect("can insert node batch");
601        }
602        let (_value_retrieved, _commitment_proof) = tree
603            .get_with_ics23_proof(format!("does_not_exist").into_bytes(), MAX_VERSION)
604            .unwrap();
605    }
606
607    #[test]
608    /// Write four keys into the JMT, and query an ICS23 proof for a nonexistent
609    /// key. This reproduces a bug that was fixed in release `0.8.0`
610    fn test_jmt_ics23_nonexistence_simple_large() {
611        use crate::Sha256Jmt;
612        let db = MockTreeStore::default();
613        let tree = Sha256Jmt::new(&db);
614
615        const MAX_VERSION: u64 = 100;
616
617        for version in 0..=MAX_VERSION {
618            let key_str = format!("key-{}", version);
619            let key = key_str.clone().into_bytes();
620            let value_str = format!("value-{}", version);
621            let value = value_str.clone().into_bytes();
622            let keys = vec![key.clone()];
623            let values = vec![value];
624            let value_set = keys
625                .into_iter()
626                .zip(values.into_iter())
627                .map(|(k, v)| (KeyHash::with::<Sha256>(&k), Some(v)))
628                .collect::<Vec<_>>();
629            let key_hash = KeyHash::with::<Sha256>(&key);
630
631            db.put_key_preimage(key_hash, &key);
632            let (_root, batch) = tree.put_value_set(value_set, version).unwrap();
633            db.write_tree_update_batch(batch)
634                .expect("can insert node batch");
635        }
636
637        for version in 0..=MAX_VERSION {
638            let (_value_retrieved, _commitment_proof) = tree
639                .get_with_ics23_proof(format!("does_not_exist").into_bytes(), version)
640                .unwrap();
641        }
642    }
643
644    #[test]
645    /// Write four keys into the JMT, and query an ICS23 proof for a nonexistent
646    /// key. This reproduces a bug that was fixed in release `0.8.0`. This test uses
647    /// the `TransparentJmt` type, which uses a mock hash function that does not hash.
648    fn test_jmt_ics23_nonexistence_simple_transparent() {
649        let db = MockTreeStore::default();
650        let tree = JellyfishMerkleTree::<_, TransparentHasher>::new(&db);
651
652        const MAX_VERSION: u64 = 4;
653
654        let mock_keys_str = vec![
655            prefix_pad("a0"),
656            prefix_pad("b1"),
657            prefix_pad("c2"),
658            prefix_pad("d3"),
659            prefix_pad("e4"),
660        ];
661
662        for version in 0..=MAX_VERSION {
663            let key = mock_keys_str[version as usize].clone();
664            let key_hash = KeyHash::with::<TransparentHasher>(&key);
665            let value_str = format!("value-{}", version);
666            let value = value_str.clone().into_bytes();
667            let keys = vec![key.clone()];
668            let values = vec![value];
669            let value_set = keys
670                .into_iter()
671                .zip(values.into_iter())
672                .map(|(k, v)| (KeyHash::with::<TransparentHasher>(&k), Some(v)))
673                .collect::<Vec<_>>();
674            db.put_key_preimage(key_hash, &key.to_vec());
675            let (_root, batch) = tree.put_value_set(value_set, version).unwrap();
676            db.write_tree_update_batch(batch)
677                .expect("can insert node batch");
678        }
679
680        let nonexisting_key = prefix_pad("c3");
681        let (_value_retrieved, _commitment_proof) = tree
682            .get_with_ics23_proof(nonexisting_key.to_vec(), MAX_VERSION)
683            .unwrap();
684    }
685
686    /// Takes an hexadecimal prefix string (e.g "deadbeef") and returns a padded byte string
687    /// that encodes to the padded hexadecimal string (e.g. "deadbeef0....0")
688    /// This is useful to create keys with specific hexadecimal representations.
689    fn prefix_pad(hex_str: &str) -> [u8; 32] {
690        if hex_str.len() > 64 {
691            panic!("hexadecimal string is longer than 32 bytes when decoded");
692        }
693
694        let mut bytes = Vec::with_capacity(hex_str.len() / 2);
695        for i in (0..hex_str.len()).step_by(2) {
696            let byte_str = &hex_str[i..i + 2];
697            let byte = u8::from_str_radix(byte_str, 16).expect("Invalid hex character");
698            bytes.push(byte);
699        }
700
701        let mut padded_bytes = [0u8; 32];
702        padded_bytes[..bytes.len()].copy_from_slice(&bytes);
703
704        padded_bytes
705    }
706}
jmt/tree/ics23_impl.rs

jmt/tree/
ics23_impl.rs
