#![cfg_attr(not(feature = "std"), no_std)]
#![warn(missing_docs)]
use frame_support::{RuntimeDebug, debug};
use sp_runtime::traits::{self, Saturating, One};
use sp_std::fmt;
#[cfg(not(feature = "std"))]
use sp_std::prelude::Vec;
pub trait LeafDataProvider {
type LeafData: FullLeaf + codec::Decode;
fn leaf_data() -> Self::LeafData;
}
impl LeafDataProvider for () {
type LeafData = ();
fn leaf_data() -> Self::LeafData {
()
}
}
impl<T: frame_system::Config> LeafDataProvider for frame_system::Module<T> {
type LeafData = (
<T as frame_system::Config>::BlockNumber,
<T as frame_system::Config>::Hash
);
fn leaf_data() -> Self::LeafData {
(
Self::block_number().saturating_sub(One::one()),
Self::parent_hash()
)
}
}
pub trait OnNewRoot<Hash> {
fn on_new_root(root: &Hash);
}
impl<Hash> OnNewRoot<Hash> for () {
fn on_new_root(_root: &Hash) {}
}
pub trait FullLeaf: Clone + PartialEq + fmt::Debug {
fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F, compact: bool) -> R;
}
impl<T: codec::Encode + codec::Decode + Clone + PartialEq + fmt::Debug> FullLeaf for T {
fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F, _compact: bool) -> R {
codec::Encode::using_encoded(self, f)
}
}
#[derive(RuntimeDebug, Clone, PartialEq)]
pub enum DataOrHash<H: traits::Hash, L> {
Data(L),
Hash(H::Output),
}
impl<H: traits::Hash, L> From<L> for DataOrHash<H, L> {
fn from(l: L) -> Self {
Self::Data(l)
}
}
mod encoding {
use super::*;
#[derive(codec::Encode, codec::Decode)]
enum Either<A, B> {
Left(A),
Right(B),
}
impl<H: traits::Hash, L: FullLeaf> codec::Encode for DataOrHash<H, L> {
fn encode_to<T: codec::Output + ?Sized>(&self, dest: &mut T) {
match self {
Self::Data(l) => l.using_encoded(
|data| Either::<&[u8], &H::Output>::Left(data).encode_to(dest), false
),
Self::Hash(h) => Either::<&[u8], &H::Output>::Right(h).encode_to(dest),
}
}
}
impl<H: traits::Hash, L: FullLeaf + codec::Decode> codec::Decode for DataOrHash<H, L> {
fn decode<I: codec::Input>(value: &mut I) -> Result<Self, codec::Error> {
let decoded: Either<Vec<u8>, H::Output> = Either::decode(value)?;
Ok(match decoded {
Either::Left(l) => DataOrHash::Data(L::decode(&mut &*l)?),
Either::Right(r) => DataOrHash::Hash(r),
})
}
}
}
impl<H: traits::Hash, L: FullLeaf> DataOrHash<H, L> {
pub fn hash(&self) -> H::Output {
match *self {
Self::Data(ref leaf) => leaf.using_encoded(<H as traits::Hash>::hash, true),
Self::Hash(ref hash) => hash.clone(),
}
}
}
#[derive(RuntimeDebug, Clone, PartialEq)]
pub struct Compact<H, T> {
pub tuple: T,
_hash: sp_std::marker::PhantomData<H>,
}
impl<H, T> sp_std::ops::Deref for Compact<H, T> {
type Target = T;
fn deref(&self) -> &Self::Target {
&self.tuple
}
}
impl<H, T> Compact<H, T> {
pub fn new(tuple: T) -> Self {
Self { tuple, _hash: Default::default() }
}
}
impl<H, T: codec::Decode> codec::Decode for Compact<H, T> {
fn decode<I: codec::Input>(value: &mut I) -> Result<Self, codec::Error> {
T::decode(value).map(Compact::new)
}
}
macro_rules! impl_leaf_data_for_tuple {
( $( $name:ident : $id:tt ),+ ) => {
impl<H, $( $name ),+> FullLeaf for Compact<H, ( $( DataOrHash<H, $name>, )+ )> where
H: traits::Hash,
$( $name: FullLeaf ),+
{
fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F, compact: bool) -> R {
if compact {
codec::Encode::using_encoded(&(
$( DataOrHash::<H, $name>::Hash(self.tuple.$id.hash()), )+
), f)
} else {
codec::Encode::using_encoded(&self.tuple, f)
}
}
}
impl<H, $( $name ),+> LeafDataProvider for Compact<H, ( $( $name, )+ )> where
H: traits::Hash,
$( $name: LeafDataProvider ),+
{
type LeafData = Compact<
H,
( $( DataOrHash<H, $name::LeafData>, )+ ),
>;
fn leaf_data() -> Self::LeafData {
let tuple = (
$( DataOrHash::Data($name::leaf_data()), )+
);
Compact::new(tuple)
}
}
impl<$( $name ),+> LeafDataProvider for ( $( $name, )+ ) where
( $( $name::LeafData, )+ ): FullLeaf,
$( $name: LeafDataProvider ),+
{
type LeafData = ( $( $name::LeafData, )+ );
fn leaf_data() -> Self::LeafData {
(
$( $name::leaf_data(), )+
)
}
}
}
}
#[cfg(test)]
impl<H, A, B> Compact<H, (DataOrHash<H, A>, DataOrHash<H, B>)> where
H: traits::Hash,
A: FullLeaf,
B: FullLeaf,
{
pub fn hash(&self) -> H::Output {
self.using_encoded(<H as traits::Hash>::hash, true)
}
}
impl_leaf_data_for_tuple!(A:0);
impl_leaf_data_for_tuple!(A:0, B:1);
impl_leaf_data_for_tuple!(A:0, B:1, C:2);
impl_leaf_data_for_tuple!(A:0, B:1, C:2, D:3);
impl_leaf_data_for_tuple!(A:0, B:1, C:2, D:3, E:4);
#[derive(codec::Encode, codec::Decode, RuntimeDebug, Clone, PartialEq, Eq)]
pub struct Proof<Hash> {
pub leaf_index: u64,
pub leaf_count: u64,
pub items: Vec<Hash>,
}
#[derive(RuntimeDebug, codec::Encode, codec::Decode, PartialEq, Eq)]
pub enum Error {
Push,
GetRoot,
Commit,
GenerateProof,
Verify,
LeafNotFound,
}
impl Error {
#![allow(unused_variables)]
pub fn log_error(self, e: impl fmt::Debug) -> Self {
debug::native::error!("[{:?}] MMR error: {:?}", self, e);
self
}
pub fn log_debug(self, e: impl fmt::Debug) -> Self {
debug::native::debug!("[{:?}] MMR error: {:?}", self, e);
self
}
}
#[cfg_attr(feature = "std", derive(serde::Serialize, serde::Deserialize))]
#[derive(RuntimeDebug, Clone, PartialEq)]
pub struct OpaqueLeaf(
#[cfg_attr(feature = "std", serde(with = "sp_core::bytes"))]
pub Vec<u8>
);
impl OpaqueLeaf {
pub fn from_leaf<T: FullLeaf>(leaf: &T) -> Self {
let encoded_leaf = leaf.using_encoded(|d| d.to_vec(), true);
OpaqueLeaf::from_encoded_leaf(encoded_leaf)
}
pub fn from_encoded_leaf(encoded_leaf: Vec<u8>) -> Self {
OpaqueLeaf(encoded_leaf)
}
}
impl FullLeaf for OpaqueLeaf {
fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F, _compact: bool) -> R {
f(&self.0)
}
}
sp_api::decl_runtime_apis! {
pub trait MmrApi<Leaf: codec::Codec, Hash: codec::Codec> {
fn generate_proof(leaf_index: u64) -> Result<(Leaf, Proof<Hash>), Error>;
fn verify_proof(leaf: Leaf, proof: Proof<Hash>) -> Result<(), Error>;
fn verify_proof_stateless(root: Hash, leaf: Vec<u8>, proof: Proof<Hash>)
-> Result<(), Error>;
}
}
#[cfg(test)]
mod tests {
use super::*;
use codec::Decode;
use sp_core::H256;
use sp_runtime::traits::Keccak256;
pub(crate) fn hex(s: &str) -> H256 {
s.parse().unwrap()
}
type Test = DataOrHash<Keccak256, String>;
type TestCompact = Compact<Keccak256, (Test, Test)>;
type TestProof = Proof<<Keccak256 as traits::Hash>::Output>;
#[test]
fn should_encode_decode_proof() {
let proof: TestProof = Proof {
leaf_index: 5,
leaf_count: 10,
items: vec![
hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),
hex("d3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),
hex("e3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"),
],
};
let encoded = codec::Encode::encode(&proof);
let decoded = TestProof::decode(&mut &*encoded);
assert_eq!(decoded, Ok(proof));
}
#[test]
fn should_encode_decode_correctly_if_no_compact() {
let cases = vec![
Test::Data("Hello World!".into()),
Test::Hash(hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd")),
Test::Data("".into()),
Test::Data("3e48d6bcd417fb22e044747242451e2c0f3e602d1bcad2767c34808621956417".into()),
];
let encoded = cases
.iter()
.map(codec::Encode::encode)
.collect::<Vec<_>>();
let decoded = encoded
.iter()
.map(|x| Test::decode(&mut &**x))
.collect::<Vec<_>>();
assert_eq!(decoded, cases.into_iter().map(Result::<_, codec::Error>::Ok).collect::<Vec<_>>());
assert_eq!(&encoded[0], &hex_literal::hex!("00343048656c6c6f20576f726c6421"));
assert_eq!(
encoded[1].as_slice(),
hex_literal::hex!(
"01c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"
).as_ref()
);
}
#[test]
fn should_return_the_hash_correctly() {
let a = Test::Data("Hello World!".into());
let b = Test::Hash(hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"));
let a = a.hash();
let b = b.hash();
assert_eq!(a, hex("a9c321be8c24ba4dc2bd73f5300bde67dc57228ab8b68b607bb4c39c5374fac9"));
assert_eq!(b, hex("c3e7ba6b511162fead58f2c8b5764ce869ed1118011ac37392522ed16720bbcd"));
}
#[test]
fn compact_should_work() {
let a = Test::Data("Hello World!".into());
let b = Test::Data("".into());
let c: TestCompact = Compact::new((a.clone(), b.clone()));
let d: TestCompact = Compact::new((
Test::Hash(a.hash()),
Test::Hash(b.hash()),
));
assert_eq!(c.hash(), d.hash());
}
#[test]
fn compact_should_encode_decode_correctly() {
let a = Test::Data("Hello World!".into());
let b = Test::Data("".into());
let c: TestCompact = Compact::new((a.clone(), b.clone()));
let d: TestCompact = Compact::new((
Test::Hash(a.hash()),
Test::Hash(b.hash()),
));
let cases = vec![c, d.clone()];
let encoded_compact = cases
.iter()
.map(|c| c.using_encoded(|x| x.to_vec(), true))
.collect::<Vec<_>>();
let encoded = cases
.iter()
.map(|c| c.using_encoded(|x| x.to_vec(), false))
.collect::<Vec<_>>();
let decoded_compact = encoded_compact
.iter()
.map(|x| TestCompact::decode(&mut &**x))
.collect::<Vec<_>>();
let decoded = encoded
.iter()
.map(|x| TestCompact::decode(&mut &**x))
.collect::<Vec<_>>();
assert_eq!(decoded, cases.into_iter().map(Result::<_, codec::Error>::Ok).collect::<Vec<_>>());
assert_eq!(decoded_compact, vec![Ok(d.clone()), Ok(d.clone())]);
}
#[test]
fn opaque_leaves_should_be_scale_compatible_with_concrete_ones() {
let a = Test::Data("Hello World!".into());
let b = Test::Data("".into());
let c: TestCompact = Compact::new((a.clone(), b.clone()));
let d: TestCompact = Compact::new((
Test::Hash(a.hash()),
Test::Hash(b.hash()),
));
let cases = vec![c, d.clone()];
let encoded_compact = cases
.iter()
.map(|c| c.using_encoded(|x| x.to_vec(), true))
.map(OpaqueLeaf::from_encoded_leaf)
.collect::<Vec<_>>();
let opaque = cases
.iter()
.map(OpaqueLeaf::from_leaf)
.collect::<Vec<_>>();
assert_eq!(
encoded_compact,
opaque,
);
}
}