zinc_protocol/
shared_challenge.rs

1//! Shared-challenge sampling across constraint families.
2//!
3//! With multiple field families active (one Q[X] family over a sampled prime
4//! $q_0$, plus one F_q[X] family per declared prime $q_1, \ldots, q_n$),
5//! every protocol-level challenge is sampled **once** as an integer in
6//! $[0, q^*)$ — where $q^* := \min(q_0, q_1, \ldots, q_n)$ — and then
7//! projected into each family's field via the family's config. Because each
8//! shared integer is strictly less than every $q_i$, the per-family
9//! projection is a type cast: all families see the same integer value, just
10//! typed in different fields.
11//!
12//! The functions in this module are independent of the `MultiDegreeSumcheck`
13//! / `IdealCheck` / `CombinedPolyResolver` / etc. interfaces: they produce
14//! `Vec<F>` (one entry per family). The caller distributes the per-family
15//! lifts to the appropriate sub-protocol invocations.
16
17use crypto_primitives::BaseFieldConfig;
18use zinc_transcript::traits::{ConstTranscribable, Transcript};
19
20/// Compute the index of $q^* := \min$ in `prime_cfgs` (the family whose
21/// modulus is smallest).
22///
23/// `prime_cfgs[0]` is $q_0$ ($Q[X]$ family); `prime_cfgs[1..=n]` are $q_i$
24/// ($F_q[X]$ families).
25///
26/// # Panics
27/// Panics if `prime_cfgs` is empty.
28#[inline]
29pub fn compute_q_star_idx<C>(prime_cfgs: &[C]) -> usize
30where
31    C: BaseFieldConfig,
32{
33    prime_cfgs
34        .iter()
35        .enumerate()
36        .min_by_key(|(_, cfg)| cfg.modulus())
37        .map(|(i, _)| i)
38        .expect("prime_cfgs must be non-empty")
39}
40
41/// Sample one shared integer challenge in $[0, q^*)$ from the transcript and
42/// return it lifted into each per-family field.
43///
44/// The returned `Vec<C::Element>` has length `prime_cfgs.len()`; entry $i$
45/// is the same underlying integer typed in $F_{q_i}$ via that family's
46/// config. Since the integer is `< q^* <= q_i`, no per-family modular
47/// reduction occurs.
48///
49/// Internally this samples a wide [`C::Integer`] from the transcript and
50/// reduces mod $q^*$ once. The reduction bias is negligible whenever
51/// $q^* \ll \text{C::Integer}$ size (the typical case: a $\sim 2^{60}$-ish
52/// prime versus a $\sim 2^{192}$-wide `C::Integer`).
53#[inline]
54pub fn sample_shared_field_challenge<C>(
55    transcript: &mut impl Transcript,
56    q_star_cfg: &C,
57    prime_cfgs: &[C],
58) -> Vec<C::Element>
59where
60    C: BaseFieldConfig,
61    C::Integer: ConstTranscribable,
62{
63    let v = transcript.get_field_challenge(q_star_cfg);
64    let v_int = q_star_cfg.lift(&v);
65    prime_cfgs.iter().map(|cfg| cfg.project(&v_int)).collect()
66}
67
68/// Sample `n` shared integer challenges in $[0, q^*)$ and return the result
69/// as a per-family matrix: outer length `prime_cfgs.len()`, inner length
70/// `n`. Entry `[i][k]` is the $k$-th shared integer typed in
71/// $F_{q_i}$.
72#[inline]
73pub fn sample_shared_field_challenges<C>(
74    transcript: &mut impl Transcript,
75    n: usize,
76    q_star_cfg: &C,
77    prime_cfgs: &[C],
78) -> Vec<Vec<C::Element>>
79where
80    C: BaseFieldConfig,
81    C::Integer: ConstTranscribable,
82{
83    // Sample shared integers first (one transcript draw per challenge),
84    // then transpose into per-family vectors. This guarantees that each
85    // family sees challenges in the same order they were squeezed.
86    let shared: Vec<C::Integer> = (0..n)
87        .map(|_| {
88            let v = transcript.get_field_challenge(q_star_cfg);
89            q_star_cfg.lift(&v)
90        })
91        .collect();
92
93    prime_cfgs
94        .iter()
95        .map(|cfg| shared.iter().map(|v| cfg.project(v)).collect())
96        .collect()
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    use crypto_primitives::{
103        LiftElementWithConfig,
104        crypto_bigint_monty::MontyField,
105        crypto_bigint_uint::{U64, Uint},
106    };
107    use zinc_transcript::Blake3Transcript;
108
109    const FIELD_LIMBS: usize = U64::LIMBS * 3;
110    type Cfg = MontyField<FIELD_LIMBS>;
111    type FMod = Uint<FIELD_LIMBS>;
112
113    fn cfg_from_u64(prime: u64) -> Cfg {
114        Cfg::new(&FMod::from(prime)).expect("prime")
115    }
116
117    #[test]
118    fn compute_q_star_picks_minimum() {
119        // q_0 (random sampled prime) > q_1 > q_2: expect q_star == q_2.
120        let cfgs = vec![
121            cfg_from_u64(0xFFFF_FFFF_FFFF_FFC5),
122            cfg_from_u64(0xFFFF_FFFF_FFFF_FFAD),
123            cfg_from_u64(0xFFFF_FFFF_FFFF_F9C5),
124        ];
125        let idx = compute_q_star_idx(&cfgs);
126        assert_eq!(idx, 2);
127        let q_star = cfgs[idx].modulus();
128        let expected = FMod::from(0xFFFF_FFFF_FFFF_F9C5_u64);
129        assert_eq!(q_star, expected);
130    }
131
132    #[test]
133    fn shared_challenge_lifts_same_integer_to_each_family() {
134        let cfgs = vec![
135            cfg_from_u64(0xFFFF_FFFF_FFFF_FFC5),
136            cfg_from_u64(0xFFFF_FFFF_FFFF_FFAD),
137        ];
138        let q_star = &cfgs[compute_q_star_idx(&cfgs)];
139        let mut transcript = Blake3Transcript::new();
140
141        let per_family = sample_shared_field_challenge(&mut transcript, q_star, &cfgs);
142        assert_eq!(per_family.len(), cfgs.len());
143
144        // Every family must hold the same underlying *natural integer*
145        // (modular reduction is the identity because the shared integer is
146        // strictly less than every q_i). Compare via lifting to the integer
147        // form so the Montgomery encoding (which differs per cfg) doesn't
148        // get in the way.
149        let int_0: FMod = cfgs[0].lift(&per_family[0]);
150        for (i, fe) in per_family.iter().enumerate().skip(1) {
151            let int_i: FMod = cfgs[i].lift(fe);
152            assert_eq!(
153                int_i, int_0,
154                "family {i}: shared challenge differs from family 0",
155            );
156        }
157
158        // Sanity: the shared integer is < q_star.
159        assert!(
160            int_0 < q_star.modulus(),
161            "shared challenge must be < q_star"
162        );
163    }
164
165    #[test]
166    fn shared_challenges_batched_matches_repeated_singles() {
167        let cfgs = vec![
168            cfg_from_u64(0xFFFF_FFFF_FFFF_FFC5),
169            cfg_from_u64(0xFFFF_FFFF_FFFF_FFAD),
170        ];
171        let q_star = &cfgs[compute_q_star_idx(&cfgs)];
172        let n = 5;
173
174        // Batched sampling.
175        let mut t_batch = Blake3Transcript::new();
176        let batched = sample_shared_field_challenges(&mut t_batch, n, q_star, &cfgs);
177        assert_eq!(batched.len(), cfgs.len());
178        for family in &batched {
179            assert_eq!(family.len(), n);
180        }
181
182        // Same n single-element samples on a fresh transcript.
183        let mut t_single = Blake3Transcript::new();
184        let mut singles_per_family: Vec<Vec<_>> =
185            cfgs.iter().map(|_| Vec::with_capacity(n)).collect();
186        for _ in 0..n {
187            let per_family = sample_shared_field_challenge(&mut t_single, q_star, &cfgs);
188            for (i, fe) in per_family.into_iter().enumerate() {
189                singles_per_family[i].push(fe);
190            }
191        }
192
193        // Batched output must equal repeated singles, element-wise (compared
194        // via natural integer form).
195        for (i, (b, s)) in batched.iter().zip(&singles_per_family).enumerate() {
196            for (k, (bk, sk)) in b.iter().zip(s).enumerate() {
197                let bk_int: FMod = cfgs[i].lift(bk);
198                let sk_int: FMod = cfgs[i].lift(sk);
199                assert_eq!(
200                    bk_int, sk_int,
201                    "family {i}, idx {k}: batched != repeated singles",
202                );
203            }
204        }
205    }
206}
zinc_protocol/shared_challenge.rs

zinc_protocol/
shared_challenge.rs
