use crate::{
nibble::LeftNibbleSlice,
nibble_ops::NIBBLE_LENGTH,
node::{Node, NodeHandle, Value},
rstd::{convert::TryInto, iter::Peekable, marker::PhantomData, result::Result, vec, vec::Vec},
CError, ChildReference, NodeCodec, TrieHash, TrieLayout,
};
use hash_db::Hasher;
#[derive(PartialEq, Eq)]
#[cfg_attr(feature = "std", derive(Debug))]
pub enum Error<HO, CE> {
DuplicateKey(Vec<u8>),
ExtraneousNode,
ExtraneousValue(Vec<u8>),
ExtraneousHashReference(HO),
InvalidChildReference(Vec<u8>),
ValueMismatch(Vec<u8>),
IncompleteProof,
RootMismatch(HO),
DecodeError(CE),
}
#[cfg(feature = "std")]
impl<HO: std::fmt::Debug, CE: std::error::Error> std::fmt::Display for Error<HO, CE> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
match self {
Error::DuplicateKey(key) =>
write!(f, "Duplicate key in input statement: key={:?}", key),
Error::ExtraneousNode => write!(f, "Extraneous node found in proof"),
Error::ExtraneousValue(key) =>
write!(f, "Extraneous value found in proof should have been omitted: key={:?}", key),
Error::ExtraneousHashReference(hash) => write!(
f,
"Extraneous hash reference found in proof should have been omitted: hash={:?}",
hash
),
Error::InvalidChildReference(data) =>
write!(f, "Invalid child reference exceeds hash length: {:?}", data),
Error::ValueMismatch(key) =>
write!(f, "Expected value was not found in the trie: key={:?}", key),
Error::IncompleteProof => write!(f, "Proof is incomplete -- expected more nodes"),
Error::RootMismatch(hash) => write!(f, "Computed incorrect root {:?} from proof", hash),
Error::DecodeError(err) => write!(f, "Unable to decode proof node: {}", err),
}
}
}
#[cfg(feature = "std")]
impl<HO: std::fmt::Debug, CE: std::error::Error + 'static> std::error::Error for Error<HO, CE> {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Error::DecodeError(err) => Some(err),
_ => None,
}
}
}
struct StackEntry<'a, L: TrieLayout> {
prefix: LeftNibbleSlice<'a>,
node: Node<'a>,
is_inline: bool,
value: Option<Value<'a>>,
child_index: usize,
children: Vec<Option<ChildReference<TrieHash<L>>>>,
next_value_hash: Option<TrieHash<L>>,
_marker: PhantomData<L>,
}
impl<'a, L: TrieLayout> StackEntry<'a, L> {
fn new(
node_data: &'a [u8],
prefix: LeftNibbleSlice<'a>,
is_inline: bool,
) -> Result<Self, Error<TrieHash<L>, CError<L>>> {
let node = L::Codec::decode(&node_data[..]).map_err(Error::DecodeError)?;
let children_len = match &node {
Node::Empty | Node::Leaf(..) => 0,
Node::Extension(..) => 1,
Node::Branch(..) | Node::NibbledBranch(..) => NIBBLE_LENGTH,
};
let value = match &node {
Node::Empty | Node::Extension(_, _) => None,
Node::Leaf(_, value) => Some(value.clone()),
Node::Branch(_, value) | Node::NibbledBranch(_, _, value) => value.clone(),
};
Ok(StackEntry {
node,
is_inline,
prefix,
value,
child_index: 0,
children: vec![None; children_len],
next_value_hash: None,
_marker: PhantomData::default(),
})
}
fn value(&self) -> Option<Value> {
if let Some(hash) = self.next_value_hash.as_ref() {
Some(Value::Node(hash.as_ref()))
} else {
self.value.clone()
}
}
fn encode_node(mut self) -> Result<Vec<u8>, Error<TrieHash<L>, CError<L>>> {
self.complete_children()?;
Ok(match self.node {
Node::Empty => L::Codec::empty_node().to_vec(),
Node::Leaf(partial, _) => {
let value = self.value().expect(
"value is assigned to Some in StackEntry::new; \
value is only ever reassigned in the ValueMatch::MatchesLeaf match \
clause, which assigns only to Some",
);
L::Codec::leaf_node(partial.right_iter(), partial.len(), value)
},
Node::Extension(partial, _) => {
let child =
self.children[0].expect("the child must be completed since child_index is 1");
L::Codec::extension_node(partial.right_iter(), partial.len(), child)
},
Node::Branch(_, _) => L::Codec::branch_node(self.children.iter(), self.value()),
Node::NibbledBranch(partial, _, _) => L::Codec::branch_node_nibbled(
partial.right_iter(),
partial.len(),
self.children.iter(),
self.value(),
),
})
}
fn advance_child_index<I>(
&mut self,
child_prefix: LeftNibbleSlice<'a>,
proof_iter: &mut I,
) -> Result<Self, Error<TrieHash<L>, CError<L>>>
where
I: Iterator<Item = &'a [u8]>,
{
match self.node {
Node::Extension(_, child) => {
assert_eq!(self.child_index, 0);
Self::make_child_entry(proof_iter, child, child_prefix)
},
Node::Branch(children, _) | Node::NibbledBranch(_, children, _) => {
assert!(child_prefix.len() > 0);
let child_index = child_prefix
.at(child_prefix.len() - 1)
.expect("it's less than prefix.len(); qed") as usize;
while self.child_index < child_index {
if let Some(child) = children[self.child_index] {
let child_ref = child.try_into().map_err(Error::InvalidChildReference)?;
self.children[self.child_index] = Some(child_ref);
}
self.child_index += 1;
}
let child = children[self.child_index].expect("guaranteed by advance_item");
Self::make_child_entry(proof_iter, child, child_prefix)
},
_ => panic!("cannot have children"),
}
}
fn complete_children(&mut self) -> Result<(), Error<TrieHash<L>, CError<L>>> {
match self.node {
Node::Extension(_, child) if self.child_index == 0 => {
let child_ref = child.try_into().map_err(Error::InvalidChildReference)?;
self.children[self.child_index] = Some(child_ref);
self.child_index += 1;
},
Node::Branch(children, _) | Node::NibbledBranch(_, children, _) => {
while self.child_index < NIBBLE_LENGTH {
if let Some(child) = children[self.child_index] {
let child_ref = child.try_into().map_err(Error::InvalidChildReference)?;
self.children[self.child_index] = Some(child_ref);
}
self.child_index += 1;
}
},
_ => {},
}
Ok(())
}
fn make_child_entry<I>(
proof_iter: &mut I,
child: NodeHandle<'a>,
prefix: LeftNibbleSlice<'a>,
) -> Result<Self, Error<TrieHash<L>, CError<L>>>
where
I: Iterator<Item = &'a [u8]>,
{
match child {
NodeHandle::Inline(data) =>
if data.is_empty() {
let node_data = proof_iter.next().ok_or(Error::IncompleteProof)?;
StackEntry::new(node_data, prefix, false)
} else {
StackEntry::new(data, prefix, true)
},
NodeHandle::Hash(data) => {
let mut hash = TrieHash::<L>::default();
if data.len() != hash.as_ref().len() {
return Err(Error::InvalidChildReference(data.to_vec()))
}
hash.as_mut().copy_from_slice(data);
Err(Error::ExtraneousHashReference(hash))
},
}
}
fn set_value(&mut self, value: &'a [u8]) {
self.value = if L::MAX_INLINE_VALUE.map(|max| value.len() < max as usize).unwrap_or(true) {
Some(Value::Inline(value))
} else {
let hash = L::Hash::hash(value);
self.next_value_hash = Some(hash);
None
};
}
fn advance_item<I>(
&mut self,
items_iter: &mut Peekable<I>,
) -> Result<Step<'a>, Error<TrieHash<L>, CError<L>>>
where
I: Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
{
let step = loop {
if let Some((key_bytes, value)) = items_iter.peek().cloned() {
let key = LeftNibbleSlice::new(key_bytes);
if key.starts_with(&self.prefix) {
match match_key_to_node(&key, self.prefix.len(), &self.node) {
ValueMatch::MatchesLeaf =>
if let Some(value) = value {
self.set_value(value);
} else {
return Err(Error::ValueMismatch(key_bytes.to_vec()))
},
ValueMatch::MatchesBranch =>
if let Some(value) = value {
self.set_value(value);
} else {
self.value = None;
},
ValueMatch::NotFound =>
if value.is_some() {
return Err(Error::ValueMismatch(key_bytes.to_vec()))
},
ValueMatch::NotOmitted =>
return Err(Error::ExtraneousValue(key_bytes.to_vec())),
ValueMatch::IsChild(child_prefix) => break Step::Descend(child_prefix),
}
items_iter.next();
continue
}
}
break Step::UnwindStack
};
Ok(step)
}
}
enum ValueMatch<'a> {
MatchesLeaf,
MatchesBranch,
NotFound,
NotOmitted,
IsChild(LeftNibbleSlice<'a>),
}
fn match_key_to_node<'a>(
key: &LeftNibbleSlice<'a>,
prefix_len: usize,
node: &Node,
) -> ValueMatch<'a> {
match node {
Node::Empty => ValueMatch::NotFound,
Node::Leaf(partial, value) => {
if key.contains(partial, prefix_len) && key.len() == prefix_len + partial.len() {
match value {
Value::Node(..) => ValueMatch::NotOmitted,
Value::Inline(value) =>
if value.is_empty() {
ValueMatch::MatchesLeaf
} else {
ValueMatch::NotOmitted
},
}
} else {
ValueMatch::NotFound
}
},
Node::Extension(partial, _) =>
if key.contains(partial, prefix_len) {
ValueMatch::IsChild(key.truncate(prefix_len + partial.len()))
} else {
ValueMatch::NotFound
},
Node::Branch(children, value) =>
match_key_to_branch_node(key, prefix_len, children, value.as_ref()),
Node::NibbledBranch(partial, children, value) =>
if key.contains(partial, prefix_len) {
match_key_to_branch_node(key, prefix_len + partial.len(), children, value.as_ref())
} else {
ValueMatch::NotFound
},
}
}
fn match_key_to_branch_node<'a>(
key: &LeftNibbleSlice<'a>,
prefix_plus_partial_len: usize,
children: &[Option<NodeHandle>; NIBBLE_LENGTH],
value: Option<&Value>,
) -> ValueMatch<'a> {
if key.len() == prefix_plus_partial_len {
if value.is_none() {
ValueMatch::MatchesBranch
} else {
ValueMatch::NotOmitted
}
} else {
let index =
key.at(prefix_plus_partial_len).expect("it's less than prefix.len(); qed") as usize;
if children[index].is_some() {
ValueMatch::IsChild(key.truncate(prefix_plus_partial_len + 1))
} else {
ValueMatch::NotFound
}
}
}
enum Step<'a> {
Descend(LeftNibbleSlice<'a>),
UnwindStack,
}
pub fn verify_proof<'a, L, I, K, V>(
root: &<L::Hash as Hasher>::Out,
proof: &[Vec<u8>],
items: I,
) -> Result<(), Error<TrieHash<L>, CError<L>>>
where
L: TrieLayout,
I: IntoIterator<Item = &'a (K, Option<V>)>,
K: 'a + AsRef<[u8]>,
V: 'a + AsRef<[u8]>,
{
let mut items = items
.into_iter()
.map(|(k, v)| (k.as_ref(), v.as_ref().map(|v| v.as_ref())))
.collect::<Vec<_>>();
items.sort();
if items.is_empty() {
return if proof.is_empty() { Ok(()) } else { Err(Error::ExtraneousNode) }
}
for i in 1..items.len() {
if items[i].0 == items[i - 1].0 {
return Err(Error::DuplicateKey(items[i].0.to_vec()))
}
}
let mut proof_iter = proof.iter().map(|i| i.as_slice());
let mut items_iter = items.into_iter().peekable();
let mut stack: Vec<StackEntry<L>> = Vec::new();
let root_node = match proof_iter.next() {
Some(node) => node,
None => return Err(Error::IncompleteProof),
};
let mut last_entry = StackEntry::<L>::new(root_node, LeftNibbleSlice::new(&[]), false)?;
loop {
match last_entry.advance_item(&mut items_iter)? {
Step::Descend(child_prefix) => {
let next_entry = last_entry.advance_child_index(child_prefix, &mut proof_iter)?;
stack.push(last_entry);
last_entry = next_entry;
},
Step::UnwindStack => {
let is_inline = last_entry.is_inline;
let node_data = last_entry.encode_node()?;
let child_ref = if is_inline {
if node_data.len() > L::Hash::LENGTH {
return Err(Error::InvalidChildReference(node_data))
}
let mut hash = <TrieHash<L>>::default();
hash.as_mut()[..node_data.len()].copy_from_slice(node_data.as_ref());
ChildReference::Inline(hash, node_data.len())
} else {
let hash = L::Hash::hash(&node_data);
ChildReference::Hash(hash)
};
if let Some(entry) = stack.pop() {
last_entry = entry;
last_entry.children[last_entry.child_index] = Some(child_ref);
last_entry.child_index += 1;
} else {
if proof_iter.next().is_some() {
return Err(Error::ExtraneousNode)
}
let computed_root = match child_ref {
ChildReference::Hash(hash) => hash,
ChildReference::Inline(_, _) =>
panic!("the bottom item on the stack has is_inline = false; qed"),
};
if computed_root != *root {
return Err(Error::RootMismatch(computed_root))
}
break
}
},
}
}
Ok(())
}