jmt_pq/tree/
ics23_impl.rs

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

jmt_pq/tree/
ics23_impl.rs
