use crate::log::{Hash, leaf_hash, root as tree_root};
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Membership {
members: Vec<String>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum Proof {
Present {
index: u64,
size: u64,
path: Vec<Hash>,
},
Absent {
before: Option<(u64, String, Vec<Hash>)>,
after: Option<(u64, String, Vec<Hash>)>,
size: u64,
},
}
impl Membership {
#[must_use]
pub fn new(members: impl IntoIterator<Item = String>) -> Self {
let mut members: Vec<String> = members.into_iter().collect();
members.sort();
members.dedup();
Self { members }
}
#[must_use]
pub fn members(&self) -> &[String] {
&self.members
}
#[must_use]
pub fn len(&self) -> usize {
self.members.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.members.is_empty()
}
fn leaves(&self) -> Vec<Hash> {
self.members
.iter()
.map(|m| leaf_hash(m.as_bytes()))
.collect()
}
#[must_use]
pub fn root(&self) -> Hash {
tree_root(&self.leaves())
}
#[must_use]
pub fn prove(&self, member: &str) -> Proof {
let leaves = self.leaves();
match self.members.binary_search(&member.to_owned()) {
Ok(index) => Proof::Present {
index: index as u64,
size: self.members.len() as u64,
path: crate::log::inclusion_proof(&leaves, index),
},
Err(insertion) => {
let before = insertion.checked_sub(1).and_then(|i| {
self.members
.get(i)
.map(|m| (i as u64, m.clone(), crate::log::inclusion_proof(&leaves, i)))
});
let after = self.members.get(insertion).map(|m| {
(
insertion as u64,
m.clone(),
crate::log::inclusion_proof(&leaves, insertion),
)
});
Proof::Absent {
before,
after,
size: self.members.len() as u64,
}
}
}
}
}
#[must_use]
pub fn verify(member: &str, proof: &Proof, expected_root: &Hash) -> bool {
match proof {
Proof::Present { index, size, path } => crate::log::verify_inclusion(
&leaf_hash(member.as_bytes()),
*index,
*size,
path,
expected_root,
),
Proof::Absent {
before,
after,
size,
} => {
if *size == 0 {
return before.is_none()
&& after.is_none()
&& *expected_root == crate::log::empty_root();
}
let check = |entry: &Option<(u64, String, Vec<Hash>)>| -> bool {
entry.as_ref().is_none_or(|(index, value, path)| {
crate::log::verify_inclusion(
&leaf_hash(value.as_bytes()),
*index,
*size,
path,
expected_root,
)
})
};
if !check(before) || !check(after) {
return false;
}
match (before, after) {
(Some((i, lower, _)), Some((j, upper, _))) => {
*j == i + 1 && lower.as_str() < member && member < upper.as_str()
}
(None, Some((j, upper, _))) => *j == 0 && member < upper.as_str(),
(Some((i, lower, _)), None) => *i + 1 == *size && lower.as_str() < member,
(None, None) => false,
}
}
}
}
#[must_use]
pub fn diff(previous: &Membership, next: &Membership) -> (Vec<String>, Vec<String>) {
let added = next
.members
.iter()
.filter(|m| previous.members.binary_search(m).is_err())
.cloned()
.collect();
let removed = previous
.members
.iter()
.filter(|m| next.members.binary_search(m).is_err())
.cloned()
.collect();
(added, removed)
}