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

jmt_pq/types/
proof.rs
