Skip to main content

qualia_core_db/net/peer/replication/
proof.rs

1//! Membership proofs over a checkpoint's committed ids (SVC-01.08 partial).
2//!
3//! Membership of listed ids is verified separately from range coverage and from
4//! set completeness (`membership_implies_completeness`). The proof object
5//! stores the checkpoint digest plus counts only: `count` is the committed-id
6//! slice length used to build the checkpoint (never a free-standing caller
7//! field) and `included` is the claimed member subset length. Merkle pages,
8//! omitted-range witnesses, and neighbor metadata remain open.
9
10use crate::crypto::network::transcript::Transcript;
11use crate::net::peer::replication::checkpoint::{build_checkpoint, Checkpoint, MAX_CHECKPOINT_OPS};
12use crate::net::qdnf::errors::QdnfError;
13use crate::net::qdnf::types::StrongDigest;
14
15pub const MAX_PROOF_IDS: usize = 16; // == MAX_CHECKPOINT_OPS
16
17const _: () = assert!(MAX_PROOF_IDS == MAX_CHECKPOINT_OPS);
18
19const MEMBERSHIP_DOMAIN: &[u8] = b"qdnf:sync:membership:v1-pq";
20
21#[repr(C)]
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub struct MembershipProof {
24    pub checkpoint_digest: StrongDigest,
25    /// Must equal `committed_ids.len()` used to build; caller cannot forge independently.
26    pub count: u16,
27    /// Number of claimed member ids in this proof (subset).
28    pub included: u16,
29}
30
31/// Membership of the listed ids does not imply the checkpoint range is complete.
32pub fn membership_implies_range_coverage() -> bool {
33    false
34}
35
36/// Proofs do not carry private neighboring operation metadata.
37pub fn private_neighbor_metadata_in_proof() -> bool {
38    false
39}
40
41/// Build a proof that `members` are a subset of `committed_ids` used to build `cp`.
42///
43/// [`QdnfError::Capacity`] if `members.len() > MAX_PROOF_IDS` or
44/// `committed_ids.len() > MAX_CHECKPOINT_OPS`.
45/// [`QdnfError::Conflict`] if any member id appears more than once.
46/// [`QdnfError::Malformed`] if any member is not in `committed_ids`, or if `cp`
47/// was not built from `committed_ids`.
48pub fn prove_membership(
49    cp: &Checkpoint,
50    committed_ids: &[StrongDigest],
51    members: &[StrongDigest],
52) -> Result<MembershipProof, QdnfError> {
53    if members.len() > MAX_PROOF_IDS || committed_ids.len() > MAX_CHECKPOINT_OPS {
54        return Err(QdnfError::Capacity);
55    }
56    if has_duplicate(members) {
57        return Err(QdnfError::Conflict);
58    }
59    let mut i = 0usize;
60    while i < members.len() {
61        if !contains_id(committed_ids, &members[i]) {
62            return Err(QdnfError::Malformed);
63        }
64        i += 1;
65    }
66    let rebuilt = build_checkpoint(cp.scope, committed_ids)?;
67    if rebuilt != *cp {
68        return Err(QdnfError::Malformed);
69    }
70    let count = committed_ids.len() as u16;
71    let included = members.len() as u16;
72    bind_membership_counts(&cp.digest, count, included)?;
73    Ok(MembershipProof {
74        checkpoint_digest: cp.digest,
75        count,
76        included,
77    })
78}
79
80/// Rebuild the expected proof from `members` and `committed_ids`.
81///
82/// [`QdnfError::Malformed`] on mismatch, including a forged `proof.count` that
83/// is not `committed_ids.len() as u16`. Capacity and duplicate outcomes follow
84/// [`prove_membership`].
85pub fn verify_membership(
86    cp: &Checkpoint,
87    committed_ids: &[StrongDigest],
88    members: &[StrongDigest],
89    proof: &MembershipProof,
90) -> Result<(), QdnfError> {
91    if proof.count != committed_ids.len() as u16 {
92        return Err(QdnfError::Malformed);
93    }
94    let expected = prove_membership(cp, committed_ids, members)?;
95    if expected != *proof {
96        return Err(QdnfError::Malformed);
97    }
98    Ok(())
99}
100
101fn contains_id(ids: &[StrongDigest], needle: &StrongDigest) -> bool {
102    let mut i = 0usize;
103    while i < ids.len() {
104        if ids[i] == *needle {
105            return true;
106        }
107        i += 1;
108    }
109    false
110}
111
112fn has_duplicate(ids: &[StrongDigest]) -> bool {
113    let mut i = 0usize;
114    while i < ids.len() {
115        let mut j = i + 1;
116        while j < ids.len() {
117            if ids[i] == ids[j] {
118                return true;
119            }
120            j += 1;
121        }
122        i += 1;
123    }
124    false
125}
126
127/// Domain-separated count binding. The public proof stores digest + counts only;
128/// extra Merkle pages stay open.
129fn bind_membership_counts(
130    checkpoint_digest: &StrongDigest,
131    count: u16,
132    included: u16,
133) -> Result<(), QdnfError> {
134    let mut t = Transcript::new();
135    t.append(b"v", MEMBERSHIP_DOMAIN)?;
136    t.append(b"cp", &checkpoint_digest.0)?;
137    t.append(b"count", &count.to_be_bytes())?;
138    t.append(b"included", &included.to_be_bytes())?;
139    let _ = t.digest();
140    Ok(())
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146    use crate::net::peer::replication::checkpoint::membership_implies_completeness;
147    use crate::net::peer::replication::operation::{operation_id, OperationDesc, MAX_PARENTS};
148
149    fn desc(seq: u32) -> OperationDesc {
150        OperationDesc {
151            author: StrongDigest([0x11; 48]),
152            epoch: 1,
153            sequence: seq,
154            scope: 7,
155            contract: StrongDigest([0x22; 48]),
156            purpose: StrongDigest([0x33; 48]),
157            payload_digest: StrongDigest([seq as u8; 48]),
158            parents: [StrongDigest::ZERO; MAX_PARENTS],
159            parent_count: 0,
160        }
161    }
162
163    fn oid(seq: u32) -> StrongDigest {
164        operation_id(&desc(seq))
165    }
166
167    #[test]
168    fn membership_does_not_imply_coverage_and_omits_neighbors() {
169        assert!(!membership_implies_range_coverage());
170        assert!(!private_neighbor_metadata_in_proof());
171        assert!(!membership_implies_completeness());
172    }
173
174    #[test]
175    fn prove_subset_of_three_id_checkpoint_and_verify() {
176        let committed = [oid(1), oid(2), oid(3)];
177        let cp = build_checkpoint(7, &committed).unwrap();
178        let members = [committed[0], committed[2]];
179        let proof = prove_membership(&cp, &committed, &members).unwrap();
180        assert_eq!(proof.checkpoint_digest, cp.digest);
181        assert_eq!(proof.count, 3);
182        assert_eq!(proof.included, 2);
183        verify_membership(&cp, &committed, &members, &proof).unwrap();
184    }
185
186    #[test]
187    fn member_not_in_committed_ids_is_malformed() {
188        let committed = [oid(1), oid(2), oid(3)];
189        let cp = build_checkpoint(7, &committed).unwrap();
190        let members = [oid(9)];
191        assert_eq!(
192            prove_membership(&cp, &committed, &members),
193            Err(QdnfError::Malformed)
194        );
195    }
196
197    #[test]
198    fn forged_proof_count_is_malformed_on_verify() {
199        let committed = [oid(1), oid(2), oid(3)];
200        let cp = build_checkpoint(7, &committed).unwrap();
201        let members = [committed[1]];
202        let mut proof = prove_membership(&cp, &committed, &members).unwrap();
203        proof.count = 99;
204        assert_eq!(
205            verify_membership(&cp, &committed, &members, &proof),
206            Err(QdnfError::Malformed)
207        );
208    }
209
210    #[test]
211    fn empty_members_on_empty_checkpoint_ok() {
212        let cp = build_checkpoint(7, &[]).unwrap();
213        let proof = prove_membership(&cp, &[], &[]).unwrap();
214        assert_eq!(proof.count, 0);
215        assert_eq!(proof.included, 0);
216        assert_eq!(proof.checkpoint_digest, cp.digest);
217        verify_membership(&cp, &[], &[], &proof).unwrap();
218    }
219
220    #[test]
221    fn duplicate_members_is_conflict() {
222        let committed = [oid(1), oid(2), oid(3)];
223        let cp = build_checkpoint(7, &committed).unwrap();
224        let members = [committed[0], committed[0]];
225        assert_eq!(
226            prove_membership(&cp, &committed, &members),
227            Err(QdnfError::Conflict)
228        );
229    }
230
231    #[test]
232    fn seventeenth_member_is_capacity() {
233        let committed = [oid(1), oid(2), oid(3)];
234        let cp = build_checkpoint(7, &committed).unwrap();
235        let mut members = [StrongDigest::ZERO; 17];
236        let mut i = 0u32;
237        while i < 17 {
238            members[i as usize] = oid(i + 1);
239            i += 1;
240        }
241        assert_eq!(
242            prove_membership(&cp, &committed, &members),
243            Err(QdnfError::Capacity)
244        );
245    }
246}