miden_crypto/merkle/smt/full/proof.rs
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
use super::{MerklePath, RpoDigest, SmtLeaf, SmtProofError, Word, SMT_DEPTH};
use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
use alloc::string::ToString;
/// A proof which can be used to assert membership (or non-membership) of key-value pairs in a
/// [`super::Smt`].
///
/// The proof consists of a Merkle path and leaf which describes the node located at the base of the
/// path.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SmtProof {
path: MerklePath,
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 is not [`SMT_DEPTH`].
pub fn new(path: MerklePath, leaf: SmtLeaf) -> Result<Self, SmtProofError> {
let depth: usize = SMT_DEPTH.into();
if path.len() != depth {
return Err(SmtProofError::InvalidPathLength(path.len()));
}
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(super) fn new_unchecked(path: MerklePath, leaf: SmtLeaf) -> Self {
Self { path, leaf }
}
// PROOF VERIFIER
// --------------------------------------------------------------------------------------------
/// Returns true if a [`super::Smt`] with the specified root contains the provided
/// key-value pair.
///
/// Note: this method cannot be used to assert non-membership. That is, if false is returned,
/// it does not mean that the provided key-value pair is not in the tree.
pub fn verify_membership(&self, key: &RpoDigest, value: &Word, root: &RpoDigest) -> bool {
let maybe_value_in_leaf = self.leaf.get_value(key);
match maybe_value_in_leaf {
Some(value_in_leaf) => {
// The value must match for the proof to be valid
if value_in_leaf != *value {
return false;
}
// make sure the Merkle path resolves to the correct root
self.compute_root() == *root
}
// If the key maps to a different leaf, the proof cannot verify membership of `value`
None => false,
}
}
// 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_membership()` check.
pub fn get(&self, key: &RpoDigest) -> Option<Word> {
self.leaf.get_value(key)
}
/// Computes the root of a [`super::Smt`] to which this proof resolves.
pub fn compute_root(&self) -> RpoDigest {
self.path
.compute_root(self.leaf.index().value(), self.leaf.hash())
.expect("failed to compute Merkle path root")
}
/// Returns the proof's Merkle path.
pub fn path(&self) -> &MerklePath {
&self.path
}
/// Returns the leaf associated with the proof.
pub fn leaf(&self) -> &SmtLeaf {
&self.leaf
}
/// Consume the proof and returns its parts.
pub fn into_parts(self) -> (MerklePath, 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 = MerklePath::read_from(source)?;
let leaf = SmtLeaf::read_from(source)?;
Self::new(path, leaf).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
}
}