use anyhow::Result;
use std::marker::PhantomData;
use typenum::marker_traits::Unsigned;
use typenum::U2;
use crate::hash::{Algorithm, Hashable};
use crate::merkle::get_merkle_proof_lemma_len;
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Proof<T: Eq + Clone + AsRef<[u8]>, BaseTreeArity: Unsigned = U2> {
pub sub_tree_proof: Option<Box<Proof<T, BaseTreeArity>>>,
top_layer_nodes: usize, sub_tree_layer_nodes: usize, lemma: Vec<T>,
path: Vec<usize>, _u: PhantomData<BaseTreeArity>, }
impl<T: Eq + Clone + AsRef<[u8]>, BaseTreeArity: Unsigned> Proof<T, BaseTreeArity> {
pub fn new<TopLayerArity: Unsigned, SubTreeArity: Unsigned>(
sub_tree_proof: Option<Box<Proof<T, BaseTreeArity>>>,
lemma: Vec<T>,
path: Vec<usize>,
) -> Result<Proof<T, BaseTreeArity>> {
if TopLayerArity::to_usize() == 0 && SubTreeArity::to_usize() == 0 {
ensure!(lemma.len() > 2, "Invalid lemma length (short)");
ensure!(
lemma.len()
== get_merkle_proof_lemma_len(path.len() + 1, BaseTreeArity::to_usize()),
"Invalid lemma length"
);
}
Ok(Proof {
sub_tree_proof,
top_layer_nodes: TopLayerArity::to_usize(),
sub_tree_layer_nodes: SubTreeArity::to_usize(),
lemma,
path,
_u: PhantomData,
})
}
pub fn item(&self) -> T {
self.lemma
.first()
.expect("[item] requested element is empty")
.clone()
}
pub fn sub_tree_root(&self) -> T {
assert!(self.sub_tree_layer_nodes > 0 && self.sub_tree_proof.is_some());
self.sub_tree_proof.as_ref().unwrap().root()
}
pub fn root(&self) -> T {
self.lemma
.last()
.expect("[root] requested element is empty")
.clone()
}
fn validate_sub_tree_proof<A: Algorithm<T>>(&self, arity: usize) -> Result<bool> {
let valid = self
.sub_tree_proof
.as_ref()
.expect("[validate_sub_tree_proof] couldn't get sub_tree_proof value")
.validate::<A>()?;
if !valid {
return Ok(valid);
}
let mut a = A::default();
a.reset();
let node_count = arity;
let h = {
let mut nodes: Vec<T> = Vec::with_capacity(node_count);
let mut cur_index = 0;
for j in 0..node_count {
if j == self.path()[0] {
nodes.push(self.sub_tree_root().clone());
} else {
nodes.push(self.lemma()[cur_index].clone());
cur_index += 1;
}
}
if cur_index != node_count - 1 {
return Ok(false);
}
a.multi_node(&nodes, 0)
};
Ok(h == self.root())
}
pub fn validate<A: Algorithm<T>>(&self) -> Result<bool> {
if self.top_layer_nodes > 0 {
ensure!(
self.sub_tree_proof.is_some(),
"Sub tree proof must be present for validation"
);
return self.validate_sub_tree_proof::<A>(self.top_layer_nodes);
}
if self.sub_tree_layer_nodes > 0 {
ensure!(
self.sub_tree_proof.is_some(),
"Sub tree proof must be present for validation"
);
return self.validate_sub_tree_proof::<A>(self.sub_tree_layer_nodes);
}
ensure!(
self.sub_tree_layer_nodes == 0,
"Base layer proof must have 0 as sub-tree layer node count"
);
ensure!(
self.top_layer_nodes == 0,
"Base layer proof must have 0 as top layer node count"
);
ensure!(self.sub_tree_proof.is_none(), "Sub tree proof must be None");
let size = self.lemma.len();
if size < 2 {
return Ok(false);
}
let branches = BaseTreeArity::to_usize();
let mut a = A::default();
let mut h = self.item();
let mut path_index = 1;
for i in (1..size - 1).step_by(branches - 1) {
a.reset();
h = {
let mut nodes: Vec<T> = Vec::with_capacity(branches);
let mut cur_index = 0;
for j in 0..branches {
if j == self.path[path_index - 1] {
nodes.push(h.clone());
} else {
nodes.push(self.lemma[i + cur_index].clone());
cur_index += 1;
}
}
if cur_index != branches - 1 {
return Ok(false);
}
path_index += 1;
a.multi_node(&nodes, i - 1)
};
}
Ok(h == self.root())
}
pub fn validate_with_data<A: Algorithm<T>>(&self, leaf_data: &dyn Hashable<A>) -> Result<bool> {
let mut a = A::default();
leaf_data.hash(&mut a);
let item = a.hash();
a.reset();
let leaf_hash = a.leaf(item);
if leaf_hash == self.item() {
self.validate::<A>()
} else {
Ok(false)
}
}
pub fn path(&self) -> &Vec<usize> {
&self.path
}
pub fn lemma(&self) -> &Vec<T> {
&self.lemma
}
pub fn lemma_mut(&mut self) -> &mut Vec<T> {
&mut self.lemma
}
pub fn top_layer_nodes(&self) -> usize {
self.top_layer_nodes
}
pub fn sub_layer_nodes(&self) -> usize {
self.sub_tree_layer_nodes
}
}
#[cfg(test)]
mod tests {
use crate::hash::{Algorithm, Hashable};
use crate::merkle::Element;
use crate::merkle::MerkleTree;
use crate::proof::Proof;
use crate::store::VecStore;
use crate::test_legacy::{get_vec_tree_from_slice, Item, Sha256Hasher, XOR128};
use typenum::{Unsigned, U0, U1, U2, U3, U4, U5, U8};
fn modify_proof<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>(
proof: &mut Proof<E, BaseTreeArity>,
) {
use rand::prelude::*;
if TopTreeArity::to_usize() > 0 {
assert!(proof.sub_tree_proof.is_some());
assert!(proof
.sub_tree_proof
.as_ref()
.unwrap() .sub_tree_proof
.is_some());
} else if SubTreeArity::to_usize() > 0 {
assert!(proof.sub_tree_proof.is_some());
}
let mut hasher_alg = A::default();
let mut tmp = vec![0u8; E::byte_len()];
if TopTreeArity::to_usize() > 0 || SubTreeArity::to_usize() > 0 {
let i = random::<usize>() % proof.sub_tree_proof.as_ref().unwrap().lemma().len();
let j = random::<usize>();
j.hash(&mut hasher_alg);
proof.sub_tree_proof.as_ref().unwrap().lemma()[i].copy_to_slice(&mut tmp);
tmp.hash(&mut hasher_alg);
proof.sub_tree_proof.as_mut().unwrap().lemma_mut()[i] = hasher_alg.hash();
} else {
let i = random::<usize>() % proof.lemma.len();
let k = random::<usize>();
k.hash(&mut hasher_alg);
proof.lemma[i].copy_to_slice(&mut tmp);
tmp.hash(&mut hasher_alg);
proof.lemma[i] = hasher_alg.hash();
}
}
#[test]
fn test_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 32768;
let tree = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
for i in 0..tree.leafs() {
let mut p = tree
.gen_proof(i)
.expect("[test_proofs] failed to generate Merkle proof");
assert!(p.validate::<A>().expect("[test_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, SubTreeArity, TopTreeArity>(&mut p);
assert!(!p.validate::<A>().expect("[test_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U2, U0, U0>();
run_test::<Item, Sha256Hasher, U2, U0, U0>();
}
#[test]
fn test_compound_quad_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 16384;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3])
.expect("[test_compound_quad_broken_proofs] Failed to build compound tree");
for i in 0..tree.leafs() {
let mut p = tree
.gen_proof(i)
.expect("[test_compound_quad_broken_proofs] failed to generate Merkle proof");
assert!(p
.validate::<A>()
.expect("[test_compound_quad_broken_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, SubTreeArity, TopTreeArity>(&mut p);
assert!(!p
.validate::<A>()
.expect("[test_compound_quad_broken_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U4, U3, U0>();
run_test::<Item, Sha256Hasher, U4, U3, U0>();
}
#[test]
fn test_compound_single_octree_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 32768;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1]).expect(
"[test_compound_single_octree_broken_proofs] Failed to build compound tree",
);
for i in 0..tree.leafs() {
let mut p = tree.gen_proof(i).expect(
"[test_compound_single_octree_broken_proofs] failed to generate Merkle proof",
);
assert!(p
.validate::<A>()
.expect("[test_compound_single_octree_broken_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, SubTreeArity, TopTreeArity>(&mut p);
assert!(!p
.validate::<A>()
.expect("[test_compound_single_octree_broken_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U8, U1, U0>();
run_test::<Item, Sha256Hasher, U8, U1, U0>();
}
#[test]
#[ignore]
fn test_compound_octree_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 32768;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt4 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3, mt4])
.expect("[test_compound_octree_broken_proofs] Failed to build compound tree");
for i in 0..tree.leafs() {
let mut p = tree
.gen_proof(i)
.expect("[test_compound_octree_broken_proofs] failed to generate Merkle proof");
assert!(p
.validate::<A>()
.expect("[test_compound_octree_broken_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, SubTreeArity, TopTreeArity>(&mut p);
assert!(!p
.validate::<A>()
.expect("[test_compound_octree_broken_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U8, U4, U0>();
run_test::<Item, Sha256Hasher, U8, U4, U0>();
}
#[test]
fn test_compound_compound_quad_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 16384;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt1: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3])
.expect("[test_compound_compound_quad_broken_proofs] failed to build compound merkle tree");
let mt4 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt5 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt6 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt2: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt4, mt5, mt6])
.expect("[test_compound_compound_quad_broken_proofs] failed to build compound merkle tree");
let mt7 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt8 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt9 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt3: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt7, mt8, mt9])
.expect("[test_compound_compound_quad_broken_proofs] failed to build compound merkle tree");
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity, TopTreeArity> =
MerkleTree::from_sub_trees(vec![cmt1, cmt2, cmt3])
.expect("[test_compound_compound_quad_broken_proofs] Failed to build compound-compound tree");
for i in 0..tree.leafs() {
let mut p = tree.gen_proof(i).expect("failed to generate Merkle proof");
assert!(p
.validate::<A>()
.expect("[test_compound_compound_quad_broken_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, SubTreeArity, TopTreeArity>(&mut p);
assert!(!p
.validate::<A>()
.expect("[test_compound_compound_quad_broken_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U4, U3, U3>();
run_test::<Item, Sha256Hasher, U4, U3, U3>();
}
#[test]
#[ignore]
fn test_compound_compound_single_quad_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 16384;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt1: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3])
.expect("[test_compound_compound_single_quad_broken_proofs] failed to build compound merkle tree");
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity, TopTreeArity> =
MerkleTree::from_sub_trees(vec![cmt1])
.expect("[test_compound_compound_single_quad_broken_proofs] Failed to build compound-compound tree");
for i in 0..tree.leafs() {
let mut p = tree.gen_proof(i).expect("[test_compound_compound_single_quad_broken_proofs] failed to generate Merkle proof");
assert!(p.validate::<A>().expect(
"[test_compound_compound_single_quad_broken_proofs] failed to validate"
));
modify_proof::<E, A, BaseTreeArity, TopTreeArity, SubTreeArity>(&mut p);
assert!(!p.validate::<A>().expect(
"[test_compound_compound_single_quad_broken_proofs] failed to validate"
));
}
}
run_test::<Item, XOR128, U4, U3, U1>();
run_test::<Item, Sha256Hasher, U4, U3, U1>();
}
#[test]
#[ignore]
fn test_compound_compound_octree_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 32768;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt4 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt1: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3, mt4]).expect(
"[test_compound_compound_octree_broken_proofs] Failed to build compound tree",
);
let mt5 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt6 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt7 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt8 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt2: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt5, mt6, mt7, mt8]).expect(
"[test_compound_compound_octree_broken_proofs] Failed to build compound tree",
);
let mt9 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt10 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt11 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt12 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt3: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt9, mt10, mt11, mt12]).expect(
"[test_compound_compound_octree_broken_proofs] Failed to build compound tree",
);
let mt13 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt14 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt15 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt16 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt4: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt13, mt14, mt15, mt16]).expect(
"[test_compound_compound_octree_broken_proofs] Failed to build compound tree",
);
let mt17 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt18 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt19 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt20 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt5: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt17, mt18, mt19, mt20]).expect(
"[test_compound_compound_octree_broken_proofs] Failed to build compound tree",
);
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity, TopTreeArity> =
MerkleTree::from_sub_trees(vec![cmt1, cmt2, cmt3, cmt4, cmt5])
.expect("[test_compound_compound_octree_broken_proofs] Failed to build compound-compound tree");
for i in 0..tree.leafs() {
let mut p = tree.gen_proof(i).expect(
"[test_compound_compound_octree_broken_proofs] failed to generate Merkle proof",
);
assert!(p
.validate::<A>()
.expect("[test_compound_compound_octree_broken_proofs] failed to validate"));
modify_proof::<E, A, BaseTreeArity, TopTreeArity, SubTreeArity>(&mut p);
assert!(!p
.validate::<A>()
.expect("[test_compound_compound_octree_broken_proofs] failed to validate"));
}
}
run_test::<Item, XOR128, U8, U4, U5>();
run_test::<Item, Sha256Hasher, U8, U4, U5>();
}
#[test]
#[ignore]
fn test_compound_compound_single_octree_broken_proofs() {
fn run_test<
E: Element,
A: Algorithm<E>,
BaseTreeArity: Unsigned,
SubTreeArity: Unsigned,
TopTreeArity: Unsigned,
>() {
let leafs = 32768;
let mt1 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt2 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt3 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let mt4 = get_vec_tree_from_slice::<E, A, BaseTreeArity>(leafs);
let cmt1: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity> =
MerkleTree::from_trees(vec![mt1, mt2, mt3, mt4])
.expect("[test_compound_compound_single_octree_broken_proofs] Failed to build compound tree");
let tree: MerkleTree<E, A, VecStore<E>, BaseTreeArity, SubTreeArity, TopTreeArity> =
MerkleTree::from_sub_trees(vec![cmt1]).expect("[test_compound_compound_single_octree_broken_proofs] Failed to build ccompound tree");
for i in 0..tree.leafs() {
let mut p = tree.gen_proof(i).expect("[test_compound_compound_single_octree_broken_proofs] failed to generate Merkle proof");
assert!(p.validate::<A>().expect(
"[test_compound_compound_single_octree_broken_proofs] failed to validate"
));
modify_proof::<E, A, BaseTreeArity, TopTreeArity, SubTreeArity>(&mut p);
assert!(!p.validate::<A>().expect(
"[test_compound_compound_single_octree_broken_proofs] failed to validate"
));
}
}
run_test::<Item, XOR128, U8, U4, U1>();
run_test::<Item, Sha256Hasher, U8, U4, U1>();
}
}