1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
use alloc::string::ToString;
use super::{SMT_DEPTH, SmtLeaf, SmtProofError, SparseMerklePath, Word};
use crate::{
merkle::InnerNodeInfo,
utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
};
/// A proof which can be used to assert presence (or absence) of key-value pairs
/// in a [`super::Smt`] (Sparse Merkle Tree).
///
/// The proof consists of a sparse Merkle path and a leaf, which describes the node located at
/// the base of the path.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SmtProof {
/// The sparse Merkle path from the leaf to the root.
path: SparseMerklePath,
/// The leaf node containing one or more key-value pairs.
leaf: SmtLeaf,
}
impl SmtProof {
// CONSTRUCTOR
// --------------------------------------------------------------------------------------------
/// Returns a new instance of [`SmtProof`] instantiated from the specified path and leaf.
///
/// # Errors
/// Returns an error if the path length does not match the expected [`SMT_DEPTH`],
/// which would make the proof invalid.
pub fn new(path: SparseMerklePath, leaf: SmtLeaf) -> Result<Self, SmtProofError> {
let depth = path.depth();
if depth != SMT_DEPTH {
return Err(SmtProofError::InvalidMerklePathLength(depth as usize));
}
Ok(Self { path, leaf })
}
/// Returns a new instance of [`SmtProof`] instantiated from the specified path and leaf.
///
/// The length of the path is not checked. Reserved for internal use.
pub(in crate::merkle::smt) fn new_unchecked(path: SparseMerklePath, leaf: SmtLeaf) -> Self {
Self { path, leaf }
}
// PROOF VERIFIER
// --------------------------------------------------------------------------------------------
/// Verifies that a [`super::Smt`] with the specified root contains the provided key-value pair.
///
/// # Errors
/// - [`SmtProofError::InvalidKeyForProof`] if the key maps to a different leaf index than this
/// proof's leaf.
/// - [`SmtProofError::ConflictingRoots`] if the computed root doesn't match the expected root.
/// - [`SmtProofError::ValueMismatch`] if the value doesn't match the value in the leaf.
pub fn verify_presence(
&self,
key: &Word,
value: &Word,
root: &Word,
) -> Result<(), SmtProofError> {
let value_in_leaf = self.leaf.get_value(key).ok_or(SmtProofError::InvalidKeyForProof)?;
// Check root before value so that ValueMismatch implies the proof is valid
let computed_root = self.compute_root();
if computed_root != *root {
return Err(SmtProofError::ConflictingRoots {
expected_root: *root,
actual_root: computed_root,
});
}
if value_in_leaf != *value {
return Err(SmtProofError::ValueMismatch { expected: *value, actual: value_in_leaf });
}
Ok(())
}
/// Verifies that a [`super::Smt`] with the specified root does not contain any value
/// for the provided key (i.e., the key is unset).
///
/// This is equivalent to calling `verify_presence(key, &EMPTY_WORD, root)`, but makes
/// the intent clearer.
///
/// # Errors
/// - [`SmtProofError::InvalidKeyForProof`] if the key maps to a different leaf index than this
/// proof's leaf.
/// - [`SmtProofError::ConflictingRoots`] if the computed root doesn't match the expected root.
/// - [`SmtProofError::ValueMismatch`] if the key has a value in the tree (i.e., is not empty).
pub fn verify_unset(&self, key: &Word, root: &Word) -> Result<(), SmtProofError> {
self.verify_presence(key, &super::EMPTY_WORD, root)
}
/// Verifies that a specific key-value pair is not in the tree.
///
/// This succeeds if the key exists with a different value, or if the key is unset.
///
/// # Errors
/// - [`SmtProofError::InvalidKeyForProof`] if the key maps to a different leaf index than this
/// proof's leaf.
/// - [`SmtProofError::ConflictingRoots`] if the computed root doesn't match the expected root.
/// - [`SmtProofError::ValuePresent`] if the key-value pair exists in the tree.
pub fn verify_absence(
&self,
key: &Word,
value: &Word,
root: &Word,
) -> Result<(), SmtProofError> {
match self.verify_presence(key, value, root) {
// The key-value pair exists - absence verification fails
Ok(()) => Err(SmtProofError::ValuePresent { key: *key, value: *value }),
// Value is different - the pair is absent, success
Err(SmtProofError::ValueMismatch { .. }) => Ok(()),
// Other errors propagate as-is
Err(e) => Err(e),
}
}
// PUBLIC ACCESSORS
// --------------------------------------------------------------------------------------------
/// Returns the value associated with the specific key according to this proof, or None if
/// this proof does not contain a value for the specified key.
///
/// A key-value pair generated by using this method should pass the `verify_presence()` check.
pub fn get(&self, key: &Word) -> Option<Word> {
self.leaf.get_value(key)
}
/// Computes the root of a [`super::Smt`] to which this proof resolves.
pub fn compute_root(&self) -> Word {
self.path
.compute_root(self.leaf.index().position(), self.leaf.hash())
.expect("failed to compute Merkle path root")
}
/// Returns the proof's sparse Merkle path.
pub fn path(&self) -> &SparseMerklePath {
&self.path
}
/// Returns the leaf associated with the proof.
pub fn leaf(&self) -> &SmtLeaf {
&self.leaf
}
/// Returns an iterator over every inner node of this proof's merkle path.
pub fn authenticated_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
self.path
.authenticated_nodes(self.leaf.index().position(), self.leaf.hash())
.expect("leaf index is u64 and should be less than 2^SMT_DEPTH")
}
/// Consume the proof and returns its parts.
pub fn into_parts(self) -> (SparseMerklePath, SmtLeaf) {
(self.path, self.leaf)
}
}
impl Serializable for SmtProof {
fn write_into<W: ByteWriter>(&self, target: &mut W) {
self.path.write_into(target);
self.leaf.write_into(target);
}
}
impl Deserializable for SmtProof {
fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
let path = SparseMerklePath::read_from(source)?;
let leaf = SmtLeaf::read_from(source)?;
Self::new(path, leaf).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
}
}