publet_algorithms/membership.rs
1//! Sorted membership tree with inclusion and absence proofs.
2//!
3//! A generation's members are hashed in sorted order, which is what makes
4//! absence provable: if a claimed member is missing, the two adjacent
5//! members that would bracket it are shown instead, and their adjacency in
6//! a sorted tree is itself proof that nothing lies between them.
7//!
8//! This is why two structures are needed rather than one. Sorting is what
9//! yields absence proofs, and it is also what makes consistency proofs
10//! unavailable, since inserting a member reorders interior nodes. The
11//! append-only [`crate::log`] covers the other half.
12
13use crate::log::{Hash, leaf_hash, root as tree_root};
14
15/// A generation's membership, held in sorted order.
16#[derive(Debug, Clone, Default, PartialEq, Eq)]
17pub struct Membership {
18 members: Vec<String>,
19}
20
21/// Evidence that a member is present or absent.
22#[derive(Debug, Clone, PartialEq, Eq)]
23#[non_exhaustive]
24pub enum Proof {
25 /// The member is present at `index`, with this audit path.
26 ///
27 /// Positions and sizes are `u64` on every target: a proof comes from
28 /// someone else, whose set may be larger than this machine's `usize`.
29 Present {
30 /// Position in sorted order.
31 index: u64,
32 /// Total members.
33 size: u64,
34 /// Audit path from the leaf upward.
35 path: Vec<Hash>,
36 },
37 /// The member is absent, bracketed by these neighbours.
38 ///
39 /// `before` and `after` are the adjacent present members. Either is
40 /// `None` when the queried value sorts outside the range entirely.
41 Absent {
42 /// The greatest present member less than the queried one.
43 before: Option<(u64, String, Vec<Hash>)>,
44 /// The least present member greater than the queried one.
45 after: Option<(u64, String, Vec<Hash>)>,
46 /// Total members.
47 size: u64,
48 },
49}
50
51impl Membership {
52 /// Build from an unsorted collection, sorting and deduplicating.
53 ///
54 /// # Example
55 ///
56 /// ```
57 /// use publet_algorithms::membership::Membership;
58 ///
59 /// // Order and duplicates in the input do not matter.
60 /// let one = Membership::new(["plum", "apple", "apple"].map(String::from));
61 /// let other = Membership::new(["apple", "plum"].map(String::from));
62 /// assert_eq!(one.root(), other.root());
63 /// ```
64 #[must_use]
65 pub fn new(members: impl IntoIterator<Item = String>) -> Self {
66 let mut members: Vec<String> = members.into_iter().collect();
67 members.sort();
68 members.dedup();
69 Self { members }
70 }
71
72 /// The members, in sorted order.
73 ///
74 /// # Example
75 ///
76 /// ```
77 /// use publet_algorithms::membership::Membership;
78 ///
79 /// # let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
80 /// assert_eq!(members.members(), ["apple", "cherry", "plum"]);
81 /// ```
82 #[must_use]
83 pub fn members(&self) -> &[String] {
84 &self.members
85 }
86
87 /// How many members there are.
88 ///
89 /// # Example
90 ///
91 /// ```
92 /// use publet_algorithms::membership::Membership;
93 ///
94 /// # let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
95 /// assert_eq!(members.len(), 3);
96 /// ```
97 #[must_use]
98 pub fn len(&self) -> usize {
99 self.members.len()
100 }
101
102 /// Whether there are no members.
103 ///
104 /// # Example
105 ///
106 /// ```
107 /// use publet_algorithms::membership::Membership;
108 ///
109 /// assert!(Membership::new(Vec::<String>::new()).is_empty());
110 /// ```
111 #[must_use]
112 pub fn is_empty(&self) -> bool {
113 self.members.is_empty()
114 }
115
116 fn leaves(&self) -> Vec<Hash> {
117 self.members
118 .iter()
119 .map(|m| leaf_hash(m.as_bytes()))
120 .collect()
121 }
122
123 /// The membership root for this generation.
124 ///
125 /// # Example
126 ///
127 /// ```
128 /// use publet_algorithms::membership::Membership;
129 ///
130 /// # let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
131 /// let more = Membership::new(["apple", "cherry", "plum", "quince"].map(String::from));
132 /// assert_ne!(members.root(), more.root());
133 /// ```
134 #[must_use]
135 pub fn root(&self) -> Hash {
136 tree_root(&self.leaves())
137 }
138
139 /// Prove that `member` is present or absent.
140 ///
141 /// # Example
142 ///
143 /// ```
144 /// use publet_algorithms::membership::{Membership, Proof, verify};
145 ///
146 /// # let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
147 /// let root = members.root();
148 ///
149 /// let present = members.prove("cherry");
150 /// assert!(matches!(present, Proof::Present { .. }));
151 /// assert!(verify("cherry", &present, &root));
152 ///
153 /// // "banana" is absent: "apple" and "cherry" are adjacent, so nothing lies between.
154 /// let absent = members.prove("banana");
155 /// assert!(matches!(absent, Proof::Absent { .. }));
156 /// assert!(verify("banana", &absent, &root));
157 /// ```
158 #[must_use]
159 pub fn prove(&self, member: &str) -> Proof {
160 let leaves = self.leaves();
161 match self.members.binary_search(&member.to_owned()) {
162 Ok(index) => Proof::Present {
163 index: index as u64,
164 size: self.members.len() as u64,
165 path: crate::log::inclusion_proof(&leaves, index),
166 },
167 Err(insertion) => {
168 let before = insertion.checked_sub(1).and_then(|i| {
169 self.members
170 .get(i)
171 .map(|m| (i as u64, m.clone(), crate::log::inclusion_proof(&leaves, i)))
172 });
173 let after = self.members.get(insertion).map(|m| {
174 (
175 insertion as u64,
176 m.clone(),
177 crate::log::inclusion_proof(&leaves, insertion),
178 )
179 });
180 Proof::Absent {
181 before,
182 after,
183 size: self.members.len() as u64,
184 }
185 }
186 }
187 }
188}
189
190/// Check a proof against a root.
191///
192/// An absence proof holds when both bracketing members verify, they are
193/// adjacent by index, and the queried value sorts strictly between them.
194/// Omitting the adjacency check would let a prover skip over the very
195/// member whose absence is being claimed.
196///
197/// # Example
198///
199/// ```
200/// use publet_algorithms::membership::{Membership, verify};
201///
202/// # let members = Membership::new(["apple", "cherry", "plum"].map(String::from));
203/// let root = members.root();
204/// let proof = members.prove("banana");
205/// assert!(verify("banana", &proof, &root));
206/// // A proof of absence for "banana" proves nothing about "cherry".
207/// assert!(!verify("cherry", &proof, &root));
208/// ```
209#[must_use]
210pub fn verify(member: &str, proof: &Proof, expected_root: &Hash) -> bool {
211 match proof {
212 Proof::Present { index, size, path } => crate::log::verify_inclusion(
213 &leaf_hash(member.as_bytes()),
214 *index,
215 *size,
216 path,
217 expected_root,
218 ),
219 Proof::Absent {
220 before,
221 after,
222 size,
223 } => {
224 if *size == 0 {
225 return before.is_none()
226 && after.is_none()
227 && *expected_root == crate::log::empty_root();
228 }
229 let check = |entry: &Option<(u64, String, Vec<Hash>)>| -> bool {
230 entry.as_ref().is_none_or(|(index, value, path)| {
231 crate::log::verify_inclusion(
232 &leaf_hash(value.as_bytes()),
233 *index,
234 *size,
235 path,
236 expected_root,
237 )
238 })
239 };
240 if !check(before) || !check(after) {
241 return false;
242 }
243 match (before, after) {
244 (Some((i, lower, _)), Some((j, upper, _))) => {
245 *j == i + 1 && lower.as_str() < member && member < upper.as_str()
246 }
247 // The queried value sorts before every member.
248 (None, Some((j, upper, _))) => *j == 0 && member < upper.as_str(),
249 // It sorts after every member.
250 (Some((i, lower, _)), None) => *i + 1 == *size && lower.as_str() < member,
251 (None, None) => false,
252 }
253 }
254 }
255}
256
257/// Members present in `next` but not `previous`, and the reverse.
258///
259/// Returned in sorted order so a generation record built from this is
260/// deterministic.
261///
262/// # Example
263///
264/// ```
265/// use publet_algorithms::membership::{Membership, diff};
266///
267/// let before = Membership::new(["apple", "cherry"].map(String::from));
268/// let after = Membership::new(["cherry", "plum"].map(String::from));
269/// let (added, removed) = diff(&before, &after);
270/// assert_eq!(added, ["plum"]);
271/// assert_eq!(removed, ["apple"]);
272/// ```
273#[must_use]
274pub fn diff(previous: &Membership, next: &Membership) -> (Vec<String>, Vec<String>) {
275 let added = next
276 .members
277 .iter()
278 .filter(|m| previous.members.binary_search(m).is_err())
279 .cloned()
280 .collect();
281 let removed = previous
282 .members
283 .iter()
284 .filter(|m| next.members.binary_search(m).is_err())
285 .cloned()
286 .collect();
287 (added, removed)
288}