use crate::core::hash::Hash;
use crate::core::pmmr;
use crate::ser;
use crate::ser::{PMMRIndexHashable, Readable, Reader, Writeable, Writer};
use util::ToHex;
#[derive(Clone, Debug, PartialEq)]
pub enum MerkleProofError {
RootMismatch,
}
#[derive(Serialize, Deserialize, Debug, Eq, PartialEq, Clone, PartialOrd, Ord)]
pub struct MerkleProof {
pub mmr_size: u64,
pub path: Vec<Hash>,
}
impl Writeable for MerkleProof {
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), ser::Error> {
writer.write_u64(self.mmr_size)?;
writer.write_u64(self.path.len() as u64)?;
self.path.write(writer)?;
Ok(())
}
}
impl Readable for MerkleProof {
fn read<R: Reader>(reader: &mut R) -> Result<MerkleProof, ser::Error> {
let mmr_size = reader.read_u64()?;
let path_len = reader.read_u64()?;
let mut path = Vec::with_capacity(path_len as usize);
for _ in 0..path_len {
let hash = Hash::read(reader)?;
path.push(hash);
}
Ok(MerkleProof { mmr_size, path })
}
}
impl Default for MerkleProof {
fn default() -> MerkleProof {
MerkleProof::empty()
}
}
impl MerkleProof {
pub fn empty() -> MerkleProof {
MerkleProof {
mmr_size: 0,
path: Vec::default(),
}
}
pub fn to_hex(&self) -> String {
let mut vec = Vec::new();
ser::serialize_default(&mut vec, &self).expect("serialization failed");
vec.to_hex()
}
pub fn from_hex(hex: &str) -> Result<MerkleProof, String> {
let bytes = util::from_hex(hex).unwrap();
let res = ser::deserialize_default(&mut &bytes[..])
.map_err(|_| "failed to deserialize a Merkle Proof".to_string())?;
Ok(res)
}
pub fn verify(
&self,
root: Hash,
element: &dyn PMMRIndexHashable,
node_pos: u64,
) -> Result<(), MerkleProofError> {
let mut proof = self.clone();
let peaks_pos = pmmr::peaks(self.mmr_size);
proof.verify_consume(root, element, node_pos, &peaks_pos)
}
fn verify_consume(
&mut self,
root: Hash,
element: &dyn PMMRIndexHashable,
node_pos0: u64,
peaks_pos0: &[u64],
) -> Result<(), MerkleProofError> {
let node_hash = if node_pos0 >= self.mmr_size {
element.hash_with_index(self.mmr_size)
} else {
element.hash_with_index(node_pos0)
};
if self.path.is_empty() {
if root == node_hash {
return Ok(());
} else {
return Err(MerkleProofError::RootMismatch);
}
}
let sibling = self.path.remove(0);
let (parent_pos0, sibling_pos0) = pmmr::family(node_pos0);
if let Ok(x) = peaks_pos0.binary_search(&(node_pos0)) {
let parent = if x == peaks_pos0.len() - 1 {
(sibling, node_hash)
} else {
(node_hash, sibling)
};
self.verify(root, &parent, parent_pos0)
} else if parent_pos0 >= self.mmr_size {
let parent = (sibling, node_hash);
self.verify(root, &parent, parent_pos0)
} else {
let parent = if pmmr::is_left_sibling(sibling_pos0) {
(sibling, node_hash)
} else {
(node_hash, sibling)
};
self.verify(root, &parent, parent_pos0)
}
}
}