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 out-of-domain evaluation point is sampled.
22    ///
23    /// This round's error is the DEEP-ALI identity's degree over the field size, fixed by the AIR
24    /// and the trace height. Every other round here has a second lever — the query count, the
25    /// folding arity, the width of what is batched — so this is the only one whose bits nothing
26    /// but grinding can buy back.
27    pub ood_pow_bits: u32,
28    /// Grinding bits before the DEEP-composition challenge is sampled. Read only when
29    /// [`AirShape::num_deep_terms`] is `Some`.
30    pub deep_pow_bits: u32,
31    /// Grinding bits before each FRI folding challenge.
32    pub folding_pow_bits: u32,
33    /// Grinding bits before the lookup / permutation argument's challenges are sampled.
34    ///
35    /// The lookup round's error grows linearly in trace length, so its absence degrades with
36    /// instance size.
37    pub lookup_pow_bits: u32,
38}
39
40/// Shape of the proof instance being graded.
41#[derive(Copy, Clone, Debug, PartialEq, Eq)]
42pub struct InstanceShape {
43    /// Log2 of the largest AIR trace height in the proof.
44    ///
45    /// A lifted (multi-AIR) statement commits every matrix at the maximum height and tests a
46    /// single FRI instance against it, with shorter AIRs opened at powers of the same
47    /// out-of-domain point; every degree-dependent error therefore scales with this height, not
48    /// with each AIR's own. A single-AIR statement uses its own trace height directly.
49    pub log_max_height: u32,
50    /// Log2 of the challenge field size, in fixed point.
51    /// Must be in `1..=fixed::from_bits(u32::MAX)`; values outside the supported
52    /// whole-bit range are malformed and report zero security.
53    pub field_bits: u64,
54    /// Collision resistance of the commitment hash, in whole bits.
55    pub collision_resistance: u32,
56}
57
58impl InstanceShape {
59    /// The ceiling any reported level is capped at: no argument compiled with this transcript can
60    /// exceed the smaller of the challenge-field size and the commitment hash's collision
61    /// resistance.
62    pub const fn cap(&self) -> u64 {
63        if self.field_bits == 0 || self.field_bits > crate::fixed::from_bits(u32::MAX) {
64            return 0;
65        }
66        let collision = crate::fixed::from_bits(self.collision_resistance);
67        if collision < self.field_bits {
68            collision
69        } else {
70            self.field_bits
71        }
72    }
73}
74
75/// Shape of a LogUp-style lookup argument, aggregated over every AIR in the proof.
76#[derive(Copy, Clone, Debug, PartialEq, Eq)]
77pub struct LookupShape {
78    /// Total lookup fractions emitted per row, summed over all AIRs.
79    ///
80    /// Bounds the number of distinct bus messages an adversary can place in an unbalanced
81    /// multiset at `fractions_per_row · 2^log_max_height`.
82    pub fractions_per_row: u32,
83    /// Maximum message width, i.e. the highest power of the second lookup challenge a denominator
84    /// can reach.
85    pub max_message_width: u32,
86}
87
88/// Shape of the AIRs being proved, aggregated over every AIR in the proof.
89#[derive(Copy, Clone, Debug, PartialEq, Eq)]
90pub struct AirShape {
91    /// Total constraints batched into the composition polynomial, plus one slot for each AIR
92    /// beyond the first when a second challenge batches multiple AIRs together (`0` slots for a
93    /// single-AIR statement, which needs no cross-AIR batching challenge).
94    pub num_composed_constraints: u32,
95    /// Maximum constraint degree over all AIRs.
96    pub max_constraint_degree: u32,
97    /// Exact committed quotient chunk count, including ZK degree padding and doubling.
98    pub num_quotient_chunks: u32,
99    /// Maximum number of out-of-domain points referenced per committed column — one per distinct
100    /// point the AIR's rotations induce: `2` for an AIR that opens `local` and `next`, `1` for an
101    /// AIR whose constraints all read a single row, and higher for a wider rotation set.
102    ///
103    /// Read by the out-of-domain round, independent of [`Self::num_deep_terms`].
104    pub max_combo: u32,
105    /// Total committed columns opened by a DEEP-quotient batching argument, plus one slot per
106    /// out-of-domain point, or `None` when the protocol performs no α/β column-batching reduction
107    /// over its committed openings. The budget's out-of-domain round is charged regardless of this
108    /// field; `None` only waives the separate DEEP-composition round.
109    pub num_deep_terms: Option<u32>,
110    /// Lookup argument shape, or `None` when the protocol has no lookup round.
111    /// A present shape with zero fractions is invalid and reports zero security.
112    pub lookup: Option<LookupShape>,
113}
p3_security/budget/shape.rs

p3_security/budget/
shape.rs
