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
// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.
//! This module provides a generic set of traits
//! for customizing nodes in the sparse Merkle tree.
//!
//! For examples on how to use these traits,
//! see the implementations of the [example](../example/index.html) module.
use crate::pad_secret::Secret;
use crate::{error::DecodingError, index::TreeIndex};
/// Trait for merging two child nodes to extract the parent node in the SMT.
pub trait Mergeable {
/// A function to merge two child nodes as the parent node in the SMT.
fn merge(lch: &Self, rch: &Self) -> Self;
}
/// Trait for generating a padding node in the SMT.
pub trait Paddable {
/// When the tree node of the input index doesn't exist,
/// we need to construct a padding node at that position.
fn padding(idx: &TreeIndex, secret: &Secret) -> Self;
}
/// Trait for getting the type name of tree nodes in the SMT.
pub trait TypeName {
/// A function returning the type name of tree nodes in the SMT for logging purpose.
fn get_name() -> String {
"Name".to_owned()
}
}
/// Trait for generating a random value.
pub trait Rand {
/// A function returning a random value of the corresponding type.
fn randomize(&mut self) {}
}
/// Trait for extracting a node with necessary information in Merkle proofs from a tree node.
pub trait ProofExtractable {
/// The type of a node with necessary information in Merkle proofs.
type ProofNode;
/// Extracting a proof node from a tree node.
fn get_proof_node(&self) -> Self::ProofNode;
}
/// Trait for prove and verify padding nodes at random sampling.
pub trait PaddingProvable {
/// The data type of the proof for a padding node.
type PaddingProof;
/// Generate the proof for padding node at given tree index.
fn prove_padding_node(&self, idx: &TreeIndex, secret: &Secret) -> Self::PaddingProof;
/// Verify the proof for a padding node at given tree index with associated node data in the Merkle proof.
///
/// Note that ```node``` is the node data in the Merkle proof,
/// ```proof``` is the proof of the padding node,
/// ```idx``` is the tree index.
fn verify_padding_node(
node: &<Self as ProofExtractable>::ProofNode,
proof: &Self::PaddingProof,
idx: &TreeIndex,
) -> bool
where
Self: ProofExtractable;
}
/// Trait for encoding.
pub trait Serializable {
/// Encode the input object.
fn serialize(&self) -> Vec<u8>
where
Self: std::marker::Sized;
/// Decode some of the input bytes starting from the ```begin``` position as a ```Self``` object,
/// possibly with some bytes at the end left.
///
/// Note that ```bytes``` is the input bytes to be decoded,
/// and ```begin``` is the beginning position of ```bytes```.
/// At the end of the execution,
/// ```begin``` should point to the first byte not decoded.
fn deserialize_as_a_unit(bytes: &[u8], begin: &mut usize) -> Result<Self, DecodingError>
where
Self: std::marker::Sized;
/// Decode the input bytes as a ```Self``` object, using up all bytes.
///
/// The default implementation of this method is to first call ```deserialize_as_a_unit``` with ```begin = 0```.
/// If any error message is returned, return the error message directly.
/// If ```begin != bytes.len()```, which means there are bytes not used for decoding,
/// return [DecodingError::TooManyEncodedBytes](../error/enum.DecodingError.html#variant.TooManyEncodedBytes).
/// Otherwise, return the object of decoding result.
fn deserialize(bytes: &[u8]) -> Result<Self, DecodingError>
where
Self: std::marker::Sized,
{
let mut begin = 0usize;
let res = Self::deserialize_as_a_unit(bytes, &mut begin);
if let Err(e) = res {
return Err(e);
}
// Check if all input bytes are used for decoding.
if begin != bytes.len() {
println!("{}, {}", begin, bytes.len());
return Err(DecodingError::TooManyEncodedBytes);
}
res
}
}
/// Trait for generating and verifying inclusion proofs.
pub trait InclusionProvable {
/// The data type of a node with necessary information in Merkle proofs.
type ProofNodeType;
/// The data type of the Merkle tree.
type TreeStruct;
/// Generate an inclusion proof for the input list of indexes.
fn generate_inclusion_proof(tree: &Self::TreeStruct, list: &[TreeIndex]) -> Option<Self>
where
Self: std::marker::Sized;
/// Verify the inclusion proof according to the leave nodes and the root.
fn verify_inclusion_proof(
&self,
leaves: &[Self::ProofNodeType],
root: &Self::ProofNodeType,
) -> bool;
}
/// Trait for random sampling and verifying sampling proofs.
pub trait RandomSampleable {
/// The data type of a node with necessary information in Merkle proofs.
type ProofNodeType;
/// The data type of the Merkle tree.
type TreeStruct;
/// Random sampling.
/// Returns the random sampling proof of the input index.
///
/// If the input index is a real leaf node in the Merkle tree, return the inclusion proof of the leaf node.
///
/// Otherwise, find the closest real leaf nodes left to and right to the input index respectively.
/// Return the inclusion proof of the closest nodes if exist,
/// together with proofs of necessary padding nodes showing that the leaf nodes are the closest.
fn random_sampling(tree: &Self::TreeStruct, idx: &TreeIndex, secret: &Secret) -> Self;
/// Verify the random sampling proof.
fn verify_random_sampling_proof(&self, root: &Self::ProofNodeType) -> bool;
}