qualia_core_db/net/peer/replication/
proof.rs1use 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; const _: () = 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 pub count: u16,
27 pub included: u16,
29}
30
31pub fn membership_implies_range_coverage() -> bool {
33 false
34}
35
36pub fn private_neighbor_metadata_in_proof() -> bool {
38 false
39}
40
41pub 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
80pub 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
127fn 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}