Skip to main content

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}