p3_security/
bus.rs

1//! Soundness terms for a binary-native multiset bus.
2//!
3//! Challenges are uniform field elements sampled after the tuple columns are committed.
4//!
5//! The four numerators are `max(1, s) * N`, `5 * R`, `L * (T - 1)`, and `h`.
6//! They charge tuple collisions, sumcheck rounds, tree batching, and child collapse.
7//! Here `R` counts radix-four rounds while `L`, `T`, and `h` describe the product trees.
8//!
9//! Commitment binding and terminal-claim authentication are composed by the caller.
10
11use alloc::vec::Vec;
12
13use crate::{ErrorBits, SecurityTerm};
14
15/// Label for the union of every binary-bus algebraic error event.
16pub const BINARY_BUS_LABEL: &str = "binary-bus";
17
18/// Label for collisions in tuple compression and the product offset.
19pub const BUS_FINGERPRINT_LABEL: &str = "bus-tuple-fingerprint";
20
21/// Label for degree-five product-reduction sumchecks.
22pub const PRODUCT_GKR_SUMCHECK_LABEL: &str = "bus-product-gkr-sumcheck";
23
24/// Label for random linear combinations of product trees.
25pub const PRODUCT_GKR_BATCHING_LABEL: &str = "bus-product-gkr-tree-batching";
26
27/// Label for random coordinates that collapse child claims.
28pub const PRODUCT_GKR_COLLAPSE_LABEL: &str = "bus-product-gkr-child-collapse";
29
30/// Caller-supplied security counts for one product-GKR schedule.
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub struct ProductGkrSecurityProfile {
33    /// Variables in each logical product tree.
34    log_height: usize,
35    /// Product trees reduced under one batching challenge per layer.
36    tree_count: usize,
37    /// Degree-five sumcheck rounds across every reduction layer.
38    sumcheck_rounds: usize,
39    /// Root-to-leaf reduction layers.
40    layer_count: usize,
41    /// Random coordinates used to collapse child claims.
42    collapse_challenges: usize,
43}
44
45impl ProductGkrSecurityProfile {
46    /// Checks representability and the relations encoded directly by these fields.
47    ///
48    /// The remaining counts are trusted inputs to the numeric model.
49    /// Protocol code should derive them from its executed schedule.
50    /// The binary bus does so through `BusPlan::security_term` in `p3-bus`.
51    #[must_use]
52    pub const fn new(
53        log_height: usize,
54        tree_count: usize,
55        sumcheck_rounds: usize,
56        layer_count: usize,
57        collapse_challenges: usize,
58    ) -> Option<Self> {
59        if log_height >= usize::BITS as usize
60            || tree_count == 0
61            || tree_count > usize::MAX / 4
62            || collapse_challenges != log_height
63            || (log_height == 0) != (layer_count == 0)
64        {
65            return None;
66        }
67        Some(Self {
68            log_height,
69            tree_count,
70            sumcheck_rounds,
71            layer_count,
72            collapse_challenges,
73        })
74    }
75}
76
77/// Validated dimensions of one binary-native bus argument.
78#[derive(Clone, Copy, Debug, PartialEq, Eq)]
79pub struct BusSecurityModel {
80    /// Lower bound on the base-two logarithm of the challenge-field order.
81    field_bits: usize,
82    /// Variables in the multilinear tuple compressor.
83    tuple_variables: usize,
84    /// Declared factor positions on the push and pull sides.
85    non_padding_leaf_counts: [usize; 2],
86    /// Counts derived from the concrete product schedule.
87    product: ProductGkrSecurityProfile,
88}
89
90impl BusSecurityModel {
91    /// Checks representability and compatibility with the supplied product profile.
92    ///
93    /// Each declared factor count must fit in the logical product tree.
94    /// An absent bus or an unrepresentable product shape returns no model.
95    /// Other counts are trusted inputs to the numeric model.
96    /// The binary bus derives checked counts through `BusPlan::security_term` in `p3-bus`.
97    #[must_use]
98    pub const fn new(
99        field_bits: usize,
100        tuple_variables: usize,
101        non_padding_leaf_counts: [usize; 2],
102        product: ProductGkrSecurityProfile,
103    ) -> Option<Self> {
104        // The implementation addresses a logical tree with one machine word.
105        if field_bits == 0 || tuple_variables >= usize::BITS as usize {
106            return None;
107        }
108
109        // Every non-padding factor must lie inside the authenticated tree domain.
110        let capacity = 1usize << product.log_height;
111        if non_padding_leaf_counts[0] > capacity
112            || non_padding_leaf_counts[1] > capacity
113            || (non_padding_leaf_counts[0] == 0 && non_padding_leaf_counts[1] == 0)
114        {
115            return None;
116        }
117
118        Some(Self {
119            field_bits,
120            tuple_variables,
121            non_padding_leaf_counts,
122            product,
123        })
124    }
125
126    /// Return each algebraic error source for diagnostic reporting.
127    ///
128    /// The result excludes commitment binding and authentication of terminal leaf claims.
129    /// These components must not be passed separately as protocol extras.
130    #[must_use]
131    pub fn components(&self) -> Vec<SecurityTerm> {
132        // A product difference has total degree at most max(1, s) * N.
133        // Here s is the tuple dimension and N is the larger multiset capacity in use.
134        let factors = self.non_padding_leaf_counts[0].max(self.non_padding_leaf_counts[1]);
135        let fingerprint_numerator = self.tuple_variables.max(1) as u128 * factors as u128;
136        let mut terms = alloc::vec![SecurityTerm::new(
137            BUS_FINGERPRINT_LABEL,
138            error_from_numerator(self.field_bits, fingerprint_numerator),
139        )];
140
141        // The protocol adapter supplies counts from the concrete product schedule.
142        push_nonzero_term(
143            &mut terms,
144            PRODUCT_GKR_SUMCHECK_LABEL,
145            self.field_bits,
146            5 * self.product.sumcheck_rounds as u128,
147        );
148        push_nonzero_term(
149            &mut terms,
150            PRODUCT_GKR_BATCHING_LABEL,
151            self.field_bits,
152            self.product.layer_count as u128 * self.product.tree_count.saturating_sub(1) as u128,
153        );
154        push_nonzero_term(
155            &mut terms,
156            PRODUCT_GKR_COLLAPSE_LABEL,
157            self.field_bits,
158            self.product.collapse_challenges as u128,
159        );
160
161        terms
162    }
163
164    /// Return the union bound that composes as one protocol extra.
165    #[must_use]
166    pub fn combined_term(&self) -> SecurityTerm {
167        let components = self.components();
168        let errors = components
169            .iter()
170            .map(|component| component.bits)
171            .collect::<Vec<_>>();
172        SecurityTerm::new(BINARY_BUS_LABEL, ErrorBits::sum(&errors))
173    }
174}
175
176/// Append one union-bound term when its event can occur.
177fn push_nonzero_term(
178    terms: &mut Vec<SecurityTerm>,
179    label: &'static str,
180    field_bits: usize,
181    numerator: u128,
182) {
183    // A degree-zero check has no Schwartz--Zippel failure event.
184    if numerator != 0 {
185        terms.push(SecurityTerm::new(
186            label,
187            error_from_numerator(field_bits, numerator),
188        ));
189    }
190}
191
192/// Convert an exact numerator over the challenge-field order into bits.
193fn error_from_numerator(field_bits: usize, numerator: u128) -> ErrorBits {
194    // Round upward before taking the logarithm.
195    // This keeps the reported error at least as large up to f64 rounding.
196    let mut rounded = numerator as f64;
197    if (rounded as u128) < numerator {
198        rounded = rounded.next_up();
199    }
200    ErrorBits::from_log2((field_bits as f64 - libm::log2(rounded)).max(0.0))
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206    use crate::fri::FriRegime;
207    use crate::grinding::GrindingSites;
208    use crate::shape::{InstanceShape, StarkAirParams};
209    use crate::stark::proven_security_report;
210
211    fn profile(
212        log_height: usize,
213        tree_count: usize,
214        sumcheck_rounds: usize,
215        layer_count: usize,
216    ) -> ProductGkrSecurityProfile {
217        ProductGkrSecurityProfile::new(
218            log_height,
219            tree_count,
220            sumcheck_rounds,
221            layer_count,
222            log_height,
223        )
224        .unwrap()
225    }
226
227    fn bits(terms: &[SecurityTerm], label: &str) -> Option<f64> {
228        // Labels are unique because each random experiment is reported once.
229        terms
230            .iter()
231            .find(|term| term.label == label)
232            .map(|term| term.bits.bits())
233    }
234
235    #[test]
236    fn exact_terms_follow_a_twenty_variable_bus() {
237        // Fixture state:
238        //
239        //     tuple fingerprint  4 * 2^20 roots
240        //     radix-four rounds  0 + 2 + ... + 18 = 90
241        //     tree batching      10 layers * (2 - 1) roots
242        //     child collapse     20 coordinates
243        let model = BusSecurityModel::new(128, 4, [1 << 20, 1 << 18], profile(20, 2, 90, 10))
244            .expect("the dimensions fit the product tree");
245        let terms = model.components();
246
247        assert_eq!(
248            bits(&terms, BUS_FINGERPRINT_LABEL),
249            Some(128.0 - libm::log2((4u64 << 20) as f64))
250        );
251        assert_eq!(
252            bits(&terms, PRODUCT_GKR_SUMCHECK_LABEL),
253            Some(128.0 - libm::log2(450.0))
254        );
255        assert_eq!(
256            bits(&terms, PRODUCT_GKR_BATCHING_LABEL),
257            Some(128.0 - libm::log2(10.0))
258        );
259        assert_eq!(
260            bits(&terms, PRODUCT_GKR_COLLAPSE_LABEL),
261            Some(128.0 - libm::log2(20.0))
262        );
263    }
264
265    #[test]
266    fn zero_height_omits_every_product_reduction_term() {
267        // A one-leaf tree compares its roots directly.
268        // Only tuple compression can hide an unequal multiset.
269        let terms = BusSecurityModel::new(128, 0, [1, 1], profile(0, 2, 0, 0))
270            .expect("one factor fits a zero-height tree")
271            .components();
272
273        assert_eq!(terms.len(), 1);
274        assert_eq!(terms[0].label, BUS_FINGERPRINT_LABEL);
275        assert_eq!(terms[0].bits.bits(), 128.0);
276    }
277
278    #[test]
279    fn odd_height_charges_the_leading_binary_collapse() {
280        // A height-three tree starts with one binary level.
281        // Its remaining radix-four layer runs one degree-five round.
282        let terms = BusSecurityModel::new(128, 1, [8, 8], profile(3, 2, 1, 2))
283            .expect("eight factors fit a height-three tree")
284            .components();
285
286        assert_eq!(
287            bits(&terms, PRODUCT_GKR_SUMCHECK_LABEL),
288            Some(128.0 - libm::log2(5.0))
289        );
290        assert_eq!(bits(&terms, PRODUCT_GKR_BATCHING_LABEL), Some(127.0));
291        assert_eq!(
292            bits(&terms, PRODUCT_GKR_COLLAPSE_LABEL),
293            Some(128.0 - libm::log2(3.0))
294        );
295    }
296
297    #[test]
298    fn malformed_or_oversized_shapes_have_no_model() {
299        // Mutation matrix:
300        //
301        //     zero field width       no challenge entropy
302        //     zero trees             no product statement
303        //     oversized tree count   child-message length can overflow
304        //     oversized height       logical capacity cannot be shifted
305        //     two leaves at height 0 factor lies outside the tree
306        //     no factors             no bus statement
307        assert!(BusSecurityModel::new(0, 1, [1, 1], profile(0, 2, 0, 0)).is_none());
308        assert!(ProductGkrSecurityProfile::new(0, 0, 0, 0, 0).is_none());
309        assert!(ProductGkrSecurityProfile::new(0, usize::MAX, 0, 0, 0).is_none());
310        assert!(
311            BusSecurityModel::new(128, usize::BITS as usize, [1, 1], profile(0, 2, 0, 0),)
312                .is_none()
313        );
314        assert!(ProductGkrSecurityProfile::new(usize::BITS as usize, 2, 0, 0, 0).is_none());
315        assert!(BusSecurityModel::new(128, 1, [2, 1], profile(0, 2, 0, 0)).is_none());
316        assert!(BusSecurityModel::new(128, 1, [0, 0], profile(0, 2, 0, 0)).is_none());
317        assert!(ProductGkrSecurityProfile::new(1, 2, 0, 0, 0).is_none());
318    }
319
320    #[test]
321    fn a_192_bit_field_adds_sixty_four_bits_to_every_term() {
322        // Both models have identical algebraic numerators.
323        // Only the challenge-field denominator differs.
324        let narrow = BusSecurityModel::new(128, 4, [1 << 20, 1 << 18], profile(20, 2, 90, 10))
325            .expect("the 128-bit model is valid")
326            .components();
327        let wide = BusSecurityModel::new(192, 4, [1 << 20, 1 << 18], profile(20, 2, 90, 10))
328            .expect("the 192-bit model is valid")
329            .components();
330
331        assert_eq!(narrow.len(), wide.len());
332        for (narrow_term, wide_term) in narrow.iter().zip(wide) {
333            assert_eq!(narrow_term.label, wide_term.label);
334            assert!((wide_term.bits.bits() - narrow_term.bits.bits() - 64.0).abs() < 1e-12);
335        }
336    }
337
338    #[test]
339    fn combined_term_sums_all_component_probabilities() {
340        // Height three has four nonzero error sources with numerators 8, 5, 2, and 3.
341        let model = BusSecurityModel::new(128, 1, [8, 8], profile(3, 2, 1, 2)).unwrap();
342        let components = model.components();
343        let expected = ErrorBits::sum(
344            &components
345                .iter()
346                .map(|component| component.bits)
347                .collect::<Vec<_>>(),
348        );
349        assert_eq!(model.combined_term().bits, expected);
350        assert_eq!(model.combined_term().label, BINARY_BUS_LABEL);
351    }
352
353    #[test]
354    fn combined_term_composes_as_one_protocol_extra() {
355        // Use a small field so the bus union bound is visible in the final report.
356        let regime = FriRegime {
357            log_blowup: 1,
358            num_queries: 100,
359            log_final_poly_len: 0,
360            max_log_arity: 3,
361            commit_pow_bits: 0,
362            query_pow_bits: 16,
363        };
364        let air = StarkAirParams {
365            num_constraints: 1,
366            max_constraint_degree: 2,
367            num_quotient_chunks: 1,
368            max_combo: 2,
369        };
370        let shape = InstanceShape {
371            log_trace_length: 20,
372            modulus_bits: 64,
373            collision_resistance: 128,
374            num_batched_functions: 1,
375        };
376        let model =
377            BusSecurityModel::new(64, 4, [1 << 20, 1 << 18], profile(20, 2, 90, 10)).unwrap();
378        let term = model.combined_term();
379
380        // The report contains one composed event rather than four independent minima.
381        let report = proven_security_report(&regime, &air, &shape, &[term], &GrindingSites::NONE);
382        assert!(
383            report
384                .udr
385                .terms()
386                .iter()
387                .any(|candidate| candidate.label == BINARY_BUS_LABEL)
388        );
389        assert!(!report.udr.terms().iter().any(|candidate| {
390            [
391                BUS_FINGERPRINT_LABEL,
392                PRODUCT_GKR_SUMCHECK_LABEL,
393                PRODUCT_GKR_BATCHING_LABEL,
394                PRODUCT_GKR_COLLAPSE_LABEL,
395            ]
396            .contains(&candidate.label)
397        }));
398    }
399
400    #[test]
401    fn large_numerator_rounding_branch_is_exercised() {
402        // The fingerprint numerator exceeds the exact integer range of f64.
403        let model = BusSecurityModel::new(128, 3, [(1usize << 62) + 1, 1], profile(63, 2, 961, 32))
404            .unwrap();
405        assert!(model.components()[0].bits.bits().is_finite());
406    }
407}
p3_security/bus.rs

p3_security/
bus.rs
