jmt/types/
proof.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Merkle proof types.
5
6pub(crate) mod definition;
7#[cfg(all(test, feature = "std"))]
8pub(crate) mod proptest_proof;
9
10use crate::{
11    proof::SparseMerkleNode::{Internal, Leaf},
12    SimpleHasher,
13};
14
15#[cfg(all(test, feature = "std"))]
16use proptest_derive::Arbitrary;
17
18pub use self::definition::{SparseMerkleProof, SparseMerkleRangeProof, UpdateMerkleProof};
19use crate::{KeyHash, ValueHash, SPARSE_MERKLE_PLACEHOLDER_HASH};
20use borsh::{BorshDeserialize, BorshSerialize};
21use serde::{Deserialize, Serialize};
22
23pub const LEAF_DOMAIN_SEPARATOR: &[u8] = b"JMT::LeafNode";
24pub const INTERNAL_DOMAIN_SEPARATOR: &[u8] = b"JMT::IntrnalNode";
25
26#[cfg_attr(all(test, feature = "std"), derive(Arbitrary))]
27#[derive(
28    Serialize, Deserialize, Clone, Copy, Eq, PartialEq, BorshSerialize, BorshDeserialize, Debug,
29)]
30/// A [`SparseMerkleNode`] is either a null node, an internal sparse node or a leaf node.
31/// This is useful in the delete case to know if we need to coalesce the leaves on deletion.
32/// The [`SparseMerkleNode`] needs to store either a [`SparseMerkleInternalNode`] or a [`SparseMerkleLeafNode`]
33/// to be able to safely assert that the node is either a leaf or an internal node. Indeed,
34/// if one stores the node/leaf hash directly into the structure, any malicious prover would
35/// be able to forge the node/leaf type, as this assertion wouldn't be checked.
36/// Providing a [`SparseMerkleInternalNode`] or a [`SparseMerkleLeafNode`] structure is sufficient to
37/// prove the node type as one would need to reverse the hash function to forge them.
38pub(crate) enum SparseMerkleNode {
39    // The default sparse node
40    Null,
41    // The internal sparse merkle tree node
42    Internal(SparseMerkleInternalNode),
43    // The leaf sparse merkle tree node
44    Leaf(SparseMerkleLeafNode),
45}
46
47impl SparseMerkleNode {
48    pub(crate) fn hash<H: SimpleHasher>(&self) -> [u8; 32] {
49        match self {
50            SparseMerkleNode::Null => SPARSE_MERKLE_PLACEHOLDER_HASH,
51            Internal(node) => node.hash::<H>(),
52            Leaf(node) => node.hash::<H>(),
53        }
54    }
55}
56
57#[derive(
58    Serialize, Deserialize, Clone, Copy, Eq, PartialEq, BorshSerialize, BorshDeserialize, Debug,
59)]
60#[cfg_attr(all(test, feature = "std"), derive(Arbitrary))]
61pub(crate) struct SparseMerkleInternalNode {
62    left_child: [u8; 32],
63    right_child: [u8; 32],
64}
65
66impl SparseMerkleInternalNode {
67    pub fn new(left_child: [u8; 32], right_child: [u8; 32]) -> Self {
68        Self {
69            left_child,
70            right_child,
71        }
72    }
73
74    pub fn hash<H: SimpleHasher>(&self) -> [u8; 32] {
75        let mut hasher = H::new();
76        // chop a vowel to fit in 16 bytes
77        hasher.update(INTERNAL_DOMAIN_SEPARATOR);
78        hasher.update(&self.left_child);
79        hasher.update(&self.right_child);
80        hasher.finalize()
81    }
82}
83
84#[derive(Eq, Copy, Serialize, Deserialize, borsh::BorshSerialize, borsh::BorshDeserialize)]
85pub struct SparseMerkleLeafNode {
86    key_hash: KeyHash,
87    value_hash: ValueHash,
88}
89
90// Manually implement Arbitrary to get the correct bounds. The derived Arbitrary impl adds a spurious
91// H: Debug bound even with the proptest(no_bound) annotation
92#[cfg(any(test))]
93impl proptest::arbitrary::Arbitrary for SparseMerkleLeafNode {
94    type Parameters = ();
95    type Strategy = proptest::strategy::BoxedStrategy<Self>;
96
97    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
98        use proptest::{arbitrary::any, strategy::Strategy};
99        (any::<KeyHash>(), any::<ValueHash>())
100            .prop_map(|(key_hash, value_hash)| Self {
101                key_hash,
102                value_hash,
103            })
104            .boxed()
105    }
106}
107
108// Manually implement Clone to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
109// TODO: Switch back to #[derive] once the perfect_derive feature lands
110impl Clone for SparseMerkleLeafNode {
111    fn clone(&self) -> Self {
112        Self {
113            key_hash: self.key_hash.clone(),
114            value_hash: self.value_hash.clone(),
115        }
116    }
117}
118
119// Manually implement Debug to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
120// TODO: Switch back to #[derive] once the perfect_derive feature lands
121impl core::fmt::Debug for SparseMerkleLeafNode {
122    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
123        f.debug_struct("SparseMerkleLeafNode")
124            .field("key_hash", &self.key_hash)
125            .field("value_hash", &self.value_hash)
126            .finish()
127    }
128}
129
130// Manually implement PartialEq to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
131// TODO: Switch back to #[derive] once the perfect_derive feature lands
132impl PartialEq for SparseMerkleLeafNode {
133    fn eq(&self, other: &Self) -> bool {
134        self.key_hash == other.key_hash && self.value_hash == other.value_hash
135    }
136}
137
138impl SparseMerkleLeafNode {
139    pub(crate) fn new(key_hash: KeyHash, value_hash: ValueHash) -> Self {
140        SparseMerkleLeafNode {
141            key_hash,
142            value_hash,
143        }
144    }
145
146    pub(crate) fn key_hash(&self) -> KeyHash {
147        self.key_hash
148    }
149
150    pub(crate) fn hash<H: SimpleHasher>(&self) -> [u8; 32] {
151        let mut hasher = H::new();
152        hasher.update(LEAF_DOMAIN_SEPARATOR);
153        hasher.update(&self.key_hash.0);
154        hasher.update(&self.value_hash.0);
155        hasher.finalize()
156    }
157}
jmt/types/proof.rs

jmt/types/
proof.rs
