lib_q_lattice_zkp/
lib.rs

1//! Module-lattice commitments, QROM Fiat–Shamir sigma protocols, and BLNS-style batching hooks.
2//!
3//! Wire **v0** (`lattice_zkp_wire_v0`) freezes profiles, encodings, and KAT fixtures. Security
4//! targets the same \(R_q = \mathbb{Z}_q\[X\]/(X^{256}+1)\) field as ML-DSA via [`lib_q_ring`].
5#![forbid(unsafe_code)]
6#![allow(missing_docs)]
7#![cfg_attr(not(test), deny(clippy::unwrap_used, clippy::expect_used))]
8#![cfg_attr(feature = "no_std", no_std)]
9
10#[cfg(feature = "hardened")]
11pub mod hardened;
12
13#[cfg(feature = "alloc")]
14extern crate alloc;
15
16pub mod blind;
17pub mod budget;
18pub mod challenge;
19pub mod commitment;
20pub mod error;
21pub mod params;
22pub mod profile;
23pub mod serialize;
24pub mod sigma;
25pub mod token;
26pub mod util;
27pub mod wire;
28
29pub use blind::{
30    BLIND_ISSUER_FS_LABEL,
31    BlindIssuance,
32    BlindIssuerKeypair,
33    BlindRequest,
34    BlindResponse,
35    BlindSignature,
36    BlindUserState,
37    ISSUER_PARAMS_DIGEST_DOMAIN,
38    IssuerCommitmentParams,
39    UnblindedBlindSignature,
40    UnblindedIssuance,
41    add_module_vec,
42    aggregate_opening,
43    blind_message_digest,
44    blinded_commitment,
45    blinded_commitment_digest,
46    issuance_blind_message_extra,
47    issuance_transcript_ctx,
48};
49pub use budget::{
50    AmortisationBudget,
51    measured_opening_wire_body_bytes,
52};
53pub use challenge::MlDsaCompatibleChallenge;
54pub use commitment::{
55    AjtaiCommitment,
56    AjtaiCommitmentKey,
57    AjtaiOpening,
58    commit,
59};
60pub use error::{
61    ProofError,
62    VerifyError,
63};
64pub use params::AjtaiParameters;
65pub use profile::{
66    LATTICE_ZKP_WIRE_VERSION_V0,
67    LatticeZkpProfileV0,
68    PROFILE_ID_PVTN_MEMBERSHIP_V0,
69    PROFILE_ID_SELECTIVE_DISCLOSURE_V0,
70    PROFILE_ID_TOKEN_SPEND_V0,
71    RQ_COEFF_PACK_BITS,
72    WIRE_BUDGET_PRESENTATION_BYTES,
73    WIRE_BUDGET_PRESENTATION_HARD_CAP_BYTES,
74    WIRE_BUDGET_PVTN_MEMBERSHIP_BYTES,
75};
76pub use wire::{
77    BlindIssuanceWireV0,
78    MAX_WIRE_BYTES_AMORTISED_V0,
79    MAX_WIRE_BYTES_BLIND_ISSUANCE_V0,
80    MAX_WIRE_BYTES_DUAL_RING_V0,
81    MAX_WIRE_BYTES_LINEAR_V0,
82    MAX_WIRE_BYTES_NULLIFIER_V0,
83    MAX_WIRE_BYTES_OPENING_V0,
84    MAX_WIRE_BYTES_PVTN_V0,
85    MAX_WIRE_BYTES_SPENDING_V0,
86    ProofKindV0,
87    WIRE_ENVELOPE_HEADER_LEN,
88    decode_amortised_proof_v0,
89    decode_blind_issuance_v0,
90    decode_dual_ring_opening_proof_v0,
91    decode_linear_relation_proof_v0,
92    decode_nullifier_opening_proof_v0,
93    decode_opening_proof_v0,
94    decode_private_membership_proof_v0,
95    decode_spending_proof_v0,
96    decode_witness_nullifier_opening_proof_v0,
97    encode_amortised_proof_v0,
98    encode_blind_issuance_v0,
99    encode_dual_ring_opening_proof_v0,
100    encode_linear_relation_proof_v0,
101    encode_nullifier_opening_proof_v0,
102    encode_opening_proof_v0,
103    encode_private_membership_proof_v0,
104    encode_spending_proof_v0,
105    encode_witness_nullifier_opening_proof_v0,
106    wire_byte_len,
107};
108#[cfg(feature = "wasm")]
109mod wasm;
110
111pub use sigma::hierarchical::{
112    PVTN_PATH_INDEX_COMMIT_DOMAIN,
113    merkle_direction_at,
114    path_index_commitment,
115    recover_clearance_level,
116    recover_path_index,
117    verify_merkle_path_from_index,
118};
119pub use sigma::opening::{
120    QROM_FS_W_DIGEST_DOMAIN,
121    fs_w_digest,
122};
123pub use sigma::{
124    AmortisedProof,
125    BatchPresentationState,
126    CrtPackedNormProof,
127    DualRingOpeningProof,
128    HierarchicalAuthProof,
129    LinearRelationProof,
130    MerklePath,
131    NullifierOpeningProof,
132    OpeningProof,
133    PVTN_CLEARANCE_MARGIN_NORM_BETA,
134    PrivateMembershipProof,
135    WitnessNullifierOpeningProof,
136    aggregate_proofs,
137    amortise,
138    encode_pvtn_leaf,
139    hierarchical,
140    hierarchical_opening_ctx,
141    leaf_clearance_level,
142    leaf_hash,
143    linear,
144    node_hash,
145    norm,
146    opening,
147    opening_ctx_with_nullifier,
148    opening_ctx_with_witness_nullifier,
149    private_membership_opening_ctx,
150    prove_dual_ring_opening,
151    prove_inf_norm,
152    prove_level_membership,
153    prove_linear,
154    prove_nullifier_opening,
155    prove_opening,
156    prove_private_membership,
157    prove_witness_nullifier_opening,
158    registry_nullifier,
159    uniqueness,
160    uniqueness_amortisation_label,
161    verify_aggregate,
162    verify_dual_ring_opening,
163    verify_hierarchical_membership,
164    verify_inf_norm,
165    verify_inf_norm_proof,
166    verify_level_membership,
167    verify_linear,
168    verify_merkle_path,
169    verify_nullifier_opening,
170    verify_opening,
171    verify_private_membership,
172    verify_witness_nullifier_opening,
173    witness_nullifier,
174    witness_uniqueness_amortisation_label,
175    witness_wire,
176};
177pub use token::{
178    AnonymousToken,
179    SpendingProof,
180    TOKEN_EPOCH_LEN,
181    TOKEN_ORIGIN_LEN,
182    TOKEN_SERIAL_LEN,
183    opening_from_token_fields,
184};
185pub use zeroize::Zeroizing;
186
187#[cfg(test)]
188mod tests {
189    use lib_q_random::new_deterministic_rng;
190    use lib_q_ring::{
191        ModuleVec,
192        Poly,
193        sample_in_ball,
194    };
195
196    use super::*;
197
198    #[inline]
199    fn test_seed32(tag: u64) -> [u8; 32] {
200        let mut seed = [0u8; 32];
201        seed[0..8].copy_from_slice(&tag.to_le_bytes());
202        seed
203    }
204
205    #[inline]
206    fn test_prove_attempts() -> usize {
207        #[cfg(feature = "hardened")]
208        {
209            crate::hardened::TEST_FIXED_PROVE_ATTEMPTS
210        }
211        #[cfg(not(feature = "hardened"))]
212        {
213            512
214        }
215    }
216
217    #[test]
218    fn commitment_homomorphic_r_and_m() {
219        let params = AjtaiParameters::new(2, 1);
220        let key = AjtaiCommitmentKey {
221            seed: [9u8; 32],
222            params,
223        };
224        let mut m1 = alloc::vec![Poly::zero(), Poly::zero()];
225        m1[0].coeffs[0] = 3;
226        let mut m2 = alloc::vec![Poly::zero(), Poly::zero()];
227        m2[0].coeffs[0] = 5;
228        let mut r1 = alloc::vec![Poly::zero()];
229        r1[0].coeffs[0] = 11;
230        let mut r2 = alloc::vec![Poly::zero()];
231        r2[0].coeffs[0] = 13;
232        let o1 = AjtaiOpening {
233            message: ModuleVec(m1.clone()),
234            randomness: ModuleVec(r1.clone()),
235        };
236        let o2 = AjtaiOpening {
237            message: ModuleVec(m2.clone()),
238            randomness: ModuleVec(r2.clone()),
239        };
240        let c1 = commit(&key, &o1);
241        let c2 = commit(&key, &o2);
242        let mut r_sum = r1.clone();
243        r_sum[0].add_assign(&r2[0]);
244        let mut ms = m1.clone();
245        for (a, b) in ms.iter_mut().zip(m2.iter()) {
246            a.add_assign(b);
247        }
248        let o_sum = AjtaiOpening {
249            message: ModuleVec(ms),
250            randomness: ModuleVec(r_sum),
251        };
252        let c_sum = commit(&key, &o_sum);
253        let mut expect = c1.value.0.clone();
254        for (e, b) in expect.iter_mut().zip(c2.value.0.iter()) {
255            e.add_assign(b);
256        }
257        assert_eq!(c_sum.value.0.len(), expect.len());
258        for (a, b) in c_sum.value.0.iter().zip(expect.iter()) {
259            assert_eq!(a.coeffs, b.coeffs);
260        }
261    }
262
263    #[test]
264    fn commitment_is_deterministic() {
265        let params = AjtaiParameters::new(2, 1);
266        let key = AjtaiCommitmentKey {
267            seed: [11u8; 32],
268            params,
269        };
270        let opening = AjtaiOpening {
271            message: ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]),
272            randomness: ModuleVec(alloc::vec![Poly::zero()]),
273        };
274        let c1 = commit(&key, &opening);
275        let c2 = commit(&key, &opening);
276        assert_eq!(c1, c2);
277    }
278
279    #[test]
280    fn opening_proof_roundtrip() {
281        let params = AjtaiParameters::new(2, 1);
282        let key = AjtaiCommitmentKey {
283            seed: [3u8; 32],
284            params,
285        };
286        let message = alloc::vec![Poly::zero(), Poly::zero()];
287        let randomness = alloc::vec![Poly::zero()];
288        let opening = AjtaiOpening {
289            message: ModuleVec(message),
290            randomness: ModuleVec(randomness),
291        };
292        let com = commit(&key, &opening);
293        let mut rng = new_deterministic_rng(test_seed32(0xC0FFEE));
294        let proof = prove_opening(
295            &mut rng,
296            &key,
297            &opening,
298            &com,
299            b"ctx-opening",
300            39,
301            20_000_000,
302            test_prove_attempts(),
303        )
304        .expect("prove");
305        verify_opening(&key, &com, &proof, b"ctx-opening", 39, 20_000_000).expect("verify");
306    }
307
308    #[test]
309    fn opening_proof_completeness_100_iterations() {
310        let params = AjtaiParameters::new(2, 1);
311        let key = AjtaiCommitmentKey {
312            seed: [5u8; 32],
313            params,
314        };
315        let opening = AjtaiOpening {
316            message: ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]),
317            randomness: ModuleVec(alloc::vec![Poly::zero()]),
318        };
319        let com = commit(&key, &opening);
320        for i in 0..100u64 {
321            let mut rng = new_deterministic_rng(test_seed32(
322                0xC0FFEE_u64 ^ (i.wrapping_mul(0x9E3779B97F4A7C15)),
323            ));
324            let proof = prove_opening(
325                &mut rng,
326                &key,
327                &opening,
328                &com,
329                b"ctx-open-complete",
330                39,
331                20_000_000,
332                test_prove_attempts(),
333            )
334            .expect("prove");
335            verify_opening(&key, &com, &proof, b"ctx-open-complete", 39, 20_000_000)
336                .expect("verify");
337        }
338    }
339
340    #[test]
341    fn opening_proof_tamper_fails_verification() {
342        let params = AjtaiParameters::new(2, 1);
343        let key = AjtaiCommitmentKey {
344            seed: [13u8; 32],
345            params,
346        };
347        let opening = AjtaiOpening {
348            message: ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]),
349            randomness: ModuleVec(alloc::vec![Poly::zero()]),
350        };
351        let com = commit(&key, &opening);
352        let mut rng = new_deterministic_rng(test_seed32(0xBAD5EED));
353        let mut proof = prove_opening(
354            &mut rng,
355            &key,
356            &opening,
357            &com,
358            b"ctx-open-tamper",
359            39,
360            20_000_000,
361            test_prove_attempts(),
362        )
363        .expect("prove");
364        proof.z.0[0].coeffs[0] ^= 1;
365        let res = verify_opening(&key, &com, &proof, b"ctx-open-tamper", 39, 20_000_000);
366        assert!(res.is_err());
367    }
368
369    #[test]
370    fn challenge_kat_matches_ring() {
371        let seed = [7u8; 32];
372        let c1 = MlDsaCompatibleChallenge::derive(&seed, 39);
373        let c2 = sample_in_ball(&seed, 39);
374        assert_eq!(c1.poly.coeffs, c2.coeffs);
375    }
376
377    #[test]
378    fn batch_transcript_smaller_than_per_attribute_hash_duplication() {
379        let mut st = BatchPresentationState::new(b"batch");
380        for i in 0u8..10 {
381            st.absorb_attribute(&[i], &[0u8; 48]);
382        }
383        let smart = st.buf.len();
384        // Naive model: each attribute carries two independent 64-byte hashes on the wire.
385        let naive = 10 * (64 + 64);
386        assert!(smart < naive);
387    }
388
389    #[test]
390    fn batch_transcript_growth_is_sublinear_against_naive_model() {
391        let mut hundred = BatchPresentationState::new(b"batch");
392        for i in 0u8..100 {
393            hundred.absorb_attribute(&[i], &[0u8; 48]);
394        }
395        let hundred_len = hundred.buf.len();
396
397        // Naive model: each attribute ships two independent 64-byte hashes.
398        let naive_hundred = 100 * (64 + 64);
399        assert!(hundred_len < naive_hundred);
400    }
401
402    #[test]
403    fn amortised_proof_verifies_with_single_batch_challenge() {
404        let params = AjtaiParameters::new(2, 1);
405        let key = AjtaiCommitmentKey {
406            seed: [21u8; 32],
407            params,
408        };
409
410        let mut m1 = alloc::vec![Poly::zero(), Poly::zero()];
411        m1[0].coeffs[0] = 2;
412        let mut r1 = alloc::vec![Poly::zero()];
413        r1[0].coeffs[0] = 9;
414        let o1 = AjtaiOpening {
415            message: ModuleVec(m1),
416            randomness: ModuleVec(r1),
417        };
418
419        let mut m2 = alloc::vec![Poly::zero(), Poly::zero()];
420        m2[1].coeffs[0] = 3;
421        let mut r2 = alloc::vec![Poly::zero()];
422        r2[0].coeffs[0] = 7;
423        let o2 = AjtaiOpening {
424            message: ModuleVec(m2),
425            randomness: ModuleVec(r2),
426        };
427
428        let c1 = commit(&key, &o1);
429        let c2 = commit(&key, &o2);
430        let commitments = alloc::vec![c1, c2];
431        let openings = alloc::vec![o1, o2];
432
433        let mut rng = new_deterministic_rng(test_seed32(0xA5515EED));
434        let proof = amortise(
435            &mut rng,
436            &key,
437            &openings,
438            &commitments,
439            b"batch-ctx",
440            39,
441            100_000_000,
442        )
443        .expect("amortise");
444        verify_aggregate(&key, &commitments, &proof, 39, 100_000_000).expect("verify aggregate");
445    }
446
447    #[test]
448    fn amortised_proof_tamper_fails_verification() {
449        let params = AjtaiParameters::new(2, 1);
450        let key = AjtaiCommitmentKey {
451            seed: [22u8; 32],
452            params,
453        };
454        let o = AjtaiOpening {
455            message: ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]),
456            randomness: ModuleVec(alloc::vec![Poly::zero()]),
457        };
458        let c = commit(&key, &o);
459        let commitments = alloc::vec![c];
460        let openings = alloc::vec![o];
461
462        let mut rng = new_deterministic_rng(test_seed32(0xBADB_A7C1));
463        let mut proof = amortise(
464            &mut rng,
465            &key,
466            &openings,
467            &commitments,
468            b"batch-ctx",
469            39,
470            100_000_000,
471        )
472        .expect("amortise");
473        proof.r_scalars[0] ^= 1;
474        let res = verify_aggregate(&key, &commitments, &proof, 39, 100_000_000);
475        assert!(res.is_err());
476    }
477
478    #[test]
479    fn packed_norm_proof_accepts_and_rejects_expected_bounds() {
480        let mut p = Poly::zero();
481        p.coeffs[0] = 7;
482        let slots = alloc::vec![alloc::vec![p.clone()], alloc::vec![Poly::zero()]];
483        let proof = prove_inf_norm(&slots, 8);
484        assert!(verify_inf_norm(&slots[0], 8));
485        assert!(verify_inf_norm_proof(&proof, 8));
486        assert!(!verify_inf_norm_proof(&proof, 6));
487    }
488
489    #[test]
490    fn budget_estimator_matches_expected_values_and_saturates() {
491        let pilot = AmortisationBudget::mldsa65_pilot();
492        assert_eq!(pilot.bytes_per_attribute, 6_304);
493        assert_eq!(pilot.overhead_bytes, 128);
494        assert_eq!(pilot.estimate_presentation_bytes(10), 63_168);
495
496        let saturated = AmortisationBudget::new(usize::MAX, usize::MAX - 1);
497        assert_eq!(saturated.estimate_presentation_bytes(2), usize::MAX);
498    }
499
500    #[test]
501    fn module_vec_serialization_roundtrip_and_error_paths() {
502        let mut p0 = Poly::zero();
503        p0.coeffs[0] = 123;
504        p0.coeffs[10] = -45;
505        let mut p1 = Poly::zero();
506        p1.coeffs[0] = 7;
507        p1.coeffs[255] = -7;
508        let polys = alloc::vec![p0, p1];
509
510        let encoded = serialize::write_module_vec(&polys);
511        let decoded = serialize::read_module_vec(&encoded).expect("decode");
512        assert_eq!(decoded.len(), polys.len());
513        assert_eq!(decoded[0].coeffs, polys[0].coeffs);
514        assert_eq!(decoded[1].coeffs, polys[1].coeffs);
515
516        assert_eq!(
517            serialize::read_module_vec(&[1, 2, 3]),
518            Err(VerifyError::InvalidFormat)
519        );
520        assert_eq!(
521            serialize::read_module_vec(&[2, 0, 0, 0]),
522            Err(VerifyError::InvalidFormat)
523        );
524        assert_eq!(
525            serialize::read_module_vec(&encoded[..encoded.len() - 1]),
526            Err(VerifyError::InvalidFormat)
527        );
528    }
529
530    #[test]
531    fn util_vector_ops_cover_success_and_errors() {
532        let mut a = Poly::zero();
533        a.coeffs[0] = 3;
534        let mut b = Poly::zero();
535        b.coeffs[0] = 5;
536
537        let sum = util::module_add(&[a.clone()], &[b.clone()]).expect("sum");
538        assert_eq!(sum.len(), 1);
539        assert_eq!(sum[0].coeffs[0], 8);
540
541        let diff = util::module_sub(&sum, &[b.clone()]).expect("diff");
542        assert_eq!(diff[0].coeffs[0], a.coeffs[0]);
543
544        assert_eq!(
545            util::module_add(&[a.clone()], &[]),
546            Err(VerifyError::InvalidFormat)
547        );
548        assert_eq!(
549            util::module_sub(&[a.clone()], &[]),
550            Err(VerifyError::InvalidFormat)
551        );
552
553        let prod = util::module_ring_mul_challenge(&Poly::zero(), &[a.clone(), b.clone()]);
554        assert_eq!(prod.len(), 2);
555        assert_eq!(prod[0].coeffs, Poly::zero().coeffs);
556        assert_eq!(prod[1].coeffs, Poly::zero().coeffs);
557
558        assert_eq!(util::module_infinity_norm(&[]), 0);
559        assert_eq!(util::module_infinity_norm(&[a.clone(), b.clone()]), 5);
560        assert!(bool::from(util::module_norm_within_bound(&[a.clone()], 5)));
561        assert!(!bool::from(util::module_norm_within_bound(&[b.clone()], 4)));
562
563        assert!(bool::from(util::polys_ct_eq(
564            &[a.clone(), b.clone()],
565            &[a.clone(), b.clone()]
566        )));
567        assert!(!bool::from(util::polys_ct_eq(&[a.clone()], &[b.clone()])));
568        assert!(!bool::from(util::polys_ct_eq(&[a], &[b, Poly::zero()])));
569    }
570
571    #[test]
572    fn linear_relation_proof_roundtrip_and_rejects_tamper() {
573        let params = AjtaiParameters::new(2, 1);
574        let key = AjtaiCommitmentKey {
575            seed: [31u8; 32],
576            params,
577        };
578
579        let mut m = alloc::vec![Poly::zero(), Poly::zero()];
580        m[0].coeffs[0] = 4;
581        let mut r = alloc::vec![Poly::zero()];
582        r[0].coeffs[0] = 6;
583        let opening = AjtaiOpening {
584            message: ModuleVec(m),
585            randomness: ModuleVec(r),
586        };
587        let com = commit(&key, &opening);
588
589        let mut witness = opening.randomness.0.clone();
590        witness.extend(opening.message.0.clone());
591        let l =
592            lib_q_ring::ModuleMatrix::expand_from_seed(&[0x42u8; 32], 1, key.params.witness_len());
593        let t = l.mul_vec(&ModuleVec(witness));
594
595        let mut rng = new_deterministic_rng(test_seed32(0x1EE7_CAFE));
596        let proof = prove_linear(
597            &mut rng,
598            &key,
599            &opening,
600            &com,
601            &l,
602            &t,
603            b"linear-ctx",
604            39,
605            40_000_000,
606            512,
607        )
608        .expect("prove_linear");
609
610        verify_linear(&key, &com, &proof, &l, &t, b"linear-ctx", 39, 40_000_000)
611            .expect("verify_linear");
612
613        let mut tampered = proof.clone();
614        tampered.u.0[0].coeffs[0] ^= 1;
615        let res = verify_linear(&key, &com, &tampered, &l, &t, b"linear-ctx", 39, 40_000_000);
616        assert_eq!(res, Err(VerifyError::Rejected));
617    }
618
619    #[test]
620    fn linear_relation_parameter_checks_and_rejection_limit() {
621        let params = AjtaiParameters::new(2, 1);
622        let key = AjtaiCommitmentKey {
623            seed: [44u8; 32],
624            params,
625        };
626        let opening = AjtaiOpening {
627            message: ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]),
628            randomness: ModuleVec(alloc::vec![Poly::zero()]),
629        };
630        let com = commit(&key, &opening);
631        let l =
632            lib_q_ring::ModuleMatrix::expand_from_seed(&[0x33u8; 32], 1, key.params.witness_len());
633
634        let bad_t = ModuleVec(alloc::vec![Poly::zero(), Poly::zero()]);
635        let mut rng = new_deterministic_rng(test_seed32(0xA11C_0001));
636        assert_eq!(
637            prove_linear(
638                &mut rng,
639                &key,
640                &opening,
641                &com,
642                &l,
643                &bad_t,
644                b"linear-bad-params",
645                39,
646                10_000_000,
647                16,
648            ),
649            Err(ProofError::InvalidParameters)
650        );
651
652        let mut m = alloc::vec![Poly::zero(), Poly::zero()];
653        m[0].coeffs[0] = 1;
654        let opening_non_zero = AjtaiOpening {
655            message: ModuleVec(m),
656            randomness: ModuleVec(alloc::vec![Poly::zero()]),
657        };
658        let mut witness = opening_non_zero.randomness.0.clone();
659        witness.extend(opening_non_zero.message.0.clone());
660        let t = l.mul_vec(&ModuleVec(witness));
661        let com_non_zero = commit(&key, &opening_non_zero);
662        let mut rng = new_deterministic_rng(test_seed32(0xA11C_0002));
663        let res = prove_linear(
664            &mut rng,
665            &key,
666            &opening_non_zero,
667            &com_non_zero,
668            &l,
669            &t,
670            b"linear-reject-limit",
671            39,
672            0,
673            1,
674        );
675        assert_eq!(res, Err(ProofError::RejectionLimit));
676    }
677}
lib_q_lattice_zkp/lib.rs

lib_q_lattice_zkp/
lib.rs
