p3_binary_pcs/whir/
budget.rs

1//! A production ceiling on proof size and verifier work, checked before a proof is produced.
2
3use crate::whir::error::BudgetError;
4use crate::whir::shape::ProofShape;
5
6/// A ceiling a deployment refuses to prove above.
7///
8/// A schedule is graded against it before any witness is touched.
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub struct BinaryWhirBudget {
11    /// Most codeword positions a verifier will open.
12    pub max_stir_queries: usize,
13
14    /// Most bytes a serialized proof may occupy.
15    pub max_proof_bytes: usize,
16
17    /// Hardest grinding a prover will accept.
18    pub max_grinding_bits: usize,
19}
20
21impl BinaryWhirBudget {
22    /// The ceiling a deployment of this scheme is expected to hold to.
23    ///
24    /// Two hundred openings keep a verifier inside a few milliseconds of hashing.
25    ///
26    /// A quarter of a megabyte is the size at which a proof stops fitting comfortably on a wire.
27    ///
28    /// Twenty-four grinding bits cost a prover well under a second.
29    pub const PRODUCTION: Self = Self {
30        max_stir_queries: 200,
31        max_proof_bytes: 256 * 1024,
32        max_grinding_bits: 24,
33    };
34
35    /// Grade a schedule against the ceiling, before anything is committed.
36    ///
37    /// # Errors
38    ///
39    /// Returns an error naming the first figure the schedule exceeds.
40    pub const fn check_shape(
41        &self,
42        shape: &ProofShape,
43        base_element_bytes: usize,
44        extension_element_bytes: usize,
45        digest_bytes: usize,
46    ) -> Result<(), BudgetError> {
47        if shape.stir_queries > self.max_stir_queries {
48            return Err(BudgetError::Queries {
49                actual: shape.stir_queries,
50                budget: self.max_stir_queries,
51            });
52        }
53        if shape.grinding_bits > self.max_grinding_bits {
54            return Err(BudgetError::Grinding {
55                actual: shape.grinding_bits,
56                budget: self.max_grinding_bits,
57            });
58        }
59        let bytes = shape.max_bytes(base_element_bytes, extension_element_bytes, digest_bytes);
60        if bytes > self.max_proof_bytes {
61            return Err(BudgetError::Bytes {
62                actual: bytes,
63                budget: self.max_proof_bytes,
64            });
65        }
66        Ok(())
67    }
68
69    /// Grade a proof that was produced, against the same ceiling.
70    ///
71    /// # Errors
72    ///
73    /// Returns an error when the serialized proof is larger than the ceiling allows.
74    pub const fn check_bytes(&self, bytes: usize) -> Result<(), BudgetError> {
75        if bytes > self.max_proof_bytes {
76            return Err(BudgetError::Bytes {
77                actual: bytes,
78                budget: self.max_proof_bytes,
79            });
80        }
81        Ok(())
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::{BinaryWhirBudget, BudgetError, ProofShape};
88
89    const SHAPE: ProofShape = ProofShape {
90        stir_queries: 40,
91        opened_base_elements: 100,
92        opened_extension_elements: 200,
93        merkle_digests: 300,
94        sent_base_elements: 10,
95        sent_extension_elements: 50,
96        grinding_bits: 16,
97    };
98
99    #[test]
100    fn a_shape_inside_the_ceiling_is_accepted() {
101        BinaryWhirBudget::PRODUCTION
102            .check_shape(&SHAPE, 4, 16, 32)
103            .unwrap();
104    }
105
106    #[test]
107    fn each_axis_refuses_on_its_own() {
108        let queries = BinaryWhirBudget {
109            max_stir_queries: 39,
110            ..BinaryWhirBudget::PRODUCTION
111        };
112        assert_eq!(
113            queries.check_shape(&SHAPE, 4, 16, 32),
114            Err(BudgetError::Queries {
115                actual: 40,
116                budget: 39
117            })
118        );
119
120        let grinding = BinaryWhirBudget {
121            max_grinding_bits: 15,
122            ..BinaryWhirBudget::PRODUCTION
123        };
124        assert_eq!(
125            grinding.check_shape(&SHAPE, 4, 16, 32),
126            Err(BudgetError::Grinding {
127                actual: 16,
128                budget: 15
129            })
130        );
131
132        let bytes = BinaryWhirBudget {
133            max_proof_bytes: 14_039,
134            ..BinaryWhirBudget::PRODUCTION
135        };
136        assert_eq!(
137            bytes.check_shape(&SHAPE, 4, 16, 32),
138            Err(BudgetError::Bytes {
139                actual: 14_040,
140                budget: 14_039
141            })
142        );
143        assert_eq!(
144            bytes.check_bytes(14_040),
145            Err(BudgetError::Bytes {
146                actual: 14_040,
147                budget: 14_039
148            })
149        );
150        assert_eq!(bytes.check_bytes(14_039), Ok(()));
151    }
152}
p3_binary_pcs/whir/budget.rs

p3_binary_pcs/whir/
budget.rs
