p3_security/budget/
shape.rs

1//! Inputs to the round budget: protocol parameters, instance shape, and AIR shape.
2//!
3//! These mirror the security-relevant subset of a protocol's runtime configuration rather than
4//! wrapping it. The runtime types live in the protocol's own crate, which this one must not depend
5//! on, so the caller — the only site with visibility into both sides — assembles these explicitly.
6
7/// Protocol parameters that enter the round budget.
8///
9/// Every field must be bound into the protocol's Fiat-Shamir transcript, so a proof cannot be
10/// graded under parameters it was not produced with.
11#[derive(Copy, Clone, Debug, PartialEq, Eq)]
12pub struct ProtocolParams {
13    /// Log2 of the LDE blowup factor; the FRI rate is `2^-log_blowup`.
14    pub log_blowup: u32,
15    /// Log2 of the FRI folding arity.
16    pub log_folding_arity: u32,
17    /// Number of FRI query repetitions.
18    pub num_queries: u32,
19    /// Grinding bits before query index sampling.
20    pub query_pow_bits: u32,
21    /// Grinding bits before the DEEP-composition challenge is sampled. Read only when
22    /// [`AirShape::num_deep_terms`] is `Some`.
23    pub deep_pow_bits: u32,
24    /// Grinding bits before each FRI folding challenge.
25    pub folding_pow_bits: u32,
26    /// Grinding bits before the lookup / permutation argument's challenges are sampled.
27    ///
28    /// The lookup round's error grows linearly in trace length, so this is the only grinding site
29    /// whose absence degrades with instance size.
30    pub lookup_pow_bits: u32,
31}
32
33/// Shape of the proof instance being graded.
34#[derive(Copy, Clone, Debug, PartialEq, Eq)]
35pub struct InstanceShape {
36    /// Log2 of the largest AIR trace height in the proof.
37    ///
38    /// A lifted (multi-AIR) statement commits every matrix at the maximum height and tests a
39    /// single FRI instance against it, with shorter AIRs opened at powers of the same
40    /// out-of-domain point; every degree-dependent error therefore scales with this height, not
41    /// with each AIR's own. A single-AIR statement uses its own trace height directly.
42    pub log_max_height: u32,
43    /// Log2 of the challenge field size, in fixed point.
44    pub field_bits: u64,
45    /// Collision resistance of the commitment hash, in whole bits.
46    pub collision_resistance: u32,
47}
48
49impl InstanceShape {
50    /// The ceiling any reported level is capped at: no argument compiled with this transcript can
51    /// exceed the smaller of the challenge-field size and the commitment hash's collision
52    /// resistance.
53    pub const fn cap(&self) -> u64 {
54        let collision = crate::fixed::from_bits(self.collision_resistance);
55        if collision < self.field_bits {
56            collision
57        } else {
58            self.field_bits
59        }
60    }
61}
62
63/// Shape of a LogUp-style lookup argument, aggregated over every AIR in the proof.
64#[derive(Copy, Clone, Debug, PartialEq, Eq)]
65pub struct LookupShape {
66    /// Total lookup fractions emitted per row, summed over all AIRs.
67    ///
68    /// Bounds the number of distinct bus messages an adversary can place in an unbalanced
69    /// multiset at `fractions_per_row · 2^log_max_height`.
70    pub fractions_per_row: u32,
71    /// Maximum message width, i.e. the highest power of the second lookup challenge a denominator
72    /// can reach.
73    pub max_message_width: u32,
74}
75
76/// Shape of the AIRs being proved, aggregated over every AIR in the proof.
77#[derive(Copy, Clone, Debug, PartialEq, Eq)]
78pub struct AirShape {
79    /// Total constraints batched into the composition polynomial, plus one slot for each AIR
80    /// beyond the first when a second challenge batches multiple AIRs together (`0` slots for a
81    /// single-AIR statement, which needs no cross-AIR batching challenge).
82    pub num_composed_constraints: u32,
83    /// Maximum constraint degree over all AIRs.
84    pub max_constraint_degree: u32,
85    /// Maximum number of out-of-domain points referenced per committed column — one per distinct
86    /// point the AIR's rotations induce: `2` for an AIR that opens `local` and `next`, `1` for an
87    /// AIR whose constraints all read a single row, and higher for a wider rotation set.
88    ///
89    /// Read by the out-of-domain round, independent of [`Self::num_deep_terms`].
90    pub max_combo: u32,
91    /// Total committed columns opened by a DEEP-quotient batching argument, plus one slot per
92    /// out-of-domain point, or `None` when the protocol performs no α/β column-batching reduction
93    /// over its committed openings. The budget's out-of-domain round is charged regardless of this
94    /// field; `None` only waives the separate DEEP-composition round.
95    pub num_deep_terms: Option<u32>,
96    /// Lookup argument shape. A zero `fractions_per_row` means the protocol has no lookup
97    /// argument, and the round contributes no constraint on security.
98    pub lookup: LookupShape,
99}
p3_security/budget/shape.rs

p3_security/budget/
shape.rs
