winter_air/proof/mod.rs
1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6//! Contains STARK proof struct and associated components.
7
8use alloc::vec::Vec;
9
10use crypto::{Hasher, MerkleTree};
11use fri::FriProof;
12use math::FieldElement;
13use security::{ConjecturedSecurity, ProvenSecurity};
14use utils::{ByteReader, Deserializable, DeserializationError, Serializable, SliceReader};
15
16use crate::{options::BatchingMethod, ProofOptions, TraceInfo};
17
18mod context;
19pub use context::Context;
20
21mod commitments;
22pub use commitments::Commitments;
23
24mod queries;
25pub use queries::Queries;
26
27mod ood_frame;
28pub use ood_frame::{OodFrame, TraceOodFrame};
29
30mod security;
31
32mod table;
33pub use table::Table;
34
35#[cfg(test)]
36mod tests;
37
38// PROOF
39// ================================================================================================
40/// A proof generated by Winterfell prover.
41///
42/// A STARK proof contains information proving that a computation was executed correctly. A proof
43/// also contains basic metadata for the computation, but neither the definition of the computation
44/// itself, nor public inputs consumed by the computation are contained in a proof.
45///
46/// A proof can be serialized into a sequence of bytes using [to_bytes()](Proof::to_bytes) function,
47/// and deserialized from a sequence of bytes using [from_bytes()](Proof::from_bytes) function.
48///
49/// To estimate soundness of a proof (in bits), [security_level()](Proof::security_level) function
50/// can be used.
51#[derive(Debug, Clone, Eq, PartialEq)]
52pub struct Proof {
53 /// Basic metadata about the execution of the computation described by this proof.
54 pub context: Context,
55 /// Number of unique queries made by the verifier. This will be different from the
56 /// context.options.num_queries if the same position in the domain was queried more than once.
57 pub num_unique_queries: u8,
58 /// Commitments made by the prover during the commit phase of the protocol.
59 pub commitments: Commitments,
60 /// Decommitments of extended execution trace values (for all trace segments) at position
61 /// queried by the verifier.
62 pub trace_queries: Vec<Queries>,
63 /// Decommitments of constraint composition polynomial evaluations at positions queried by
64 /// the verifier.
65 pub constraint_queries: Queries,
66 /// Trace and constraint polynomial evaluations at an out-of-domain point.
67 pub ood_frame: OodFrame,
68 /// Low-degree proof for a DEEP composition polynomial.
69 pub fri_proof: FriProof,
70 /// Proof-of-work nonce for query seed grinding.
71 pub pow_nonce: u64,
72}
73
74impl Proof {
75 /// Returns STARK protocol parameters used to generate this proof.
76 pub fn options(&self) -> &ProofOptions {
77 self.context.options()
78 }
79
80 /// Returns trace info for the computation described by this proof.
81 pub fn trace_info(&self) -> &TraceInfo {
82 self.context.trace_info()
83 }
84
85 /// Returns the size of the LDE domain for the computation described by this proof.
86 pub fn lde_domain_size(&self) -> usize {
87 self.context.lde_domain_size()
88 }
89
90 // SECURITY LEVEL
91 // --------------------------------------------------------------------------------------------
92 /// Returns security level of this proof (in bits) using conjectured security.
93 ///
94 /// This is the conjecture on the security of the Toy problem (Conjecture 1)
95 /// in https://eprint.iacr.org/2021/582.
96 pub fn conjectured_security<H: Hasher>(&self) -> ConjecturedSecurity {
97 ConjecturedSecurity::compute(
98 self.context.options(),
99 self.context.num_modulus_bits(),
100 H::COLLISION_RESISTANCE,
101 )
102 }
103 /// Returns security level of this proof (in bits) using proven security.
104 ///
105 /// Usually, the number of queries needed for provable security is 2x - 3x higher than
106 /// the number of queries needed for conjectured security at the same security level.
107 pub fn proven_security<H: Hasher>(&self) -> ProvenSecurity {
108 // note that we need the count of the total number of constraints in the protocol as
109 // the soundness error, in the case of algebraic batching, depends on the this number.
110 let num_constraints = self.context.num_constraints();
111
112 // we need to count the number of code words appearing in the protocol as the soundness
113 // error, in the case of algebraic batching, depends on the this number.
114 // we use the blowup factor as an upper bound on the number of constraint composition
115 // polynomials.
116 let num_trace_polys = self.context.trace_info().width();
117 let num_constraint_composition_polys = self.options().blowup_factor();
118 let num_committed_polys = num_trace_polys + num_constraint_composition_polys;
119 ProvenSecurity::compute(
120 self.context.options(),
121 self.context.num_modulus_bits(),
122 self.trace_info().length(),
123 H::COLLISION_RESISTANCE,
124 num_constraints,
125 num_committed_polys,
126 )
127 }
128
129 // SERIALIZATION / DESERIALIZATION
130 // --------------------------------------------------------------------------------------------
131
132 /// Serializes this proof into a vector of bytes.
133 pub fn to_bytes(&self) -> Vec<u8> {
134 Serializable::to_bytes(self)
135 }
136
137 /// Returns a STARK proof read from the specified `source`.
138 ///
139 /// # Errors
140 /// Returns an error of a valid STARK proof could not be read from the specified `source`.
141 pub fn from_bytes(source: &[u8]) -> Result<Self, DeserializationError> {
142 Deserializable::read_from_bytes(source)
143 }
144
145 /// Creates a dummy `Proof` for use in tests.
146 pub fn new_dummy() -> Self {
147 use crypto::{hashers::Blake3_192 as DummyHasher, BatchMerkleProof};
148 use math::fields::f64::BaseElement as DummyField;
149
150 use crate::FieldExtension;
151
152 Self {
153 context: Context::new::<DummyField>(
154 TraceInfo::new(1, 8),
155 ProofOptions::new(
156 1,
157 2,
158 2,
159 FieldExtension::None,
160 8,
161 1,
162 BatchingMethod::Linear,
163 BatchingMethod::Linear,
164 ),
165 100,
166 ),
167 num_unique_queries: 1,
168 commitments: Commitments::default(),
169 trace_queries: vec![
170 Queries::new::<DummyHasher<DummyField>, DummyField, MerkleTree<_>>(
171 BatchMerkleProof::<DummyHasher<DummyField>> { nodes: Vec::new(), depth: 0 },
172 vec![vec![DummyField::ONE]],
173 ),
174 ],
175 constraint_queries: Queries::new::<DummyHasher<DummyField>, DummyField, MerkleTree<_>>(
176 BatchMerkleProof::<DummyHasher<DummyField>> { nodes: Vec::new(), depth: 0 },
177 vec![vec![DummyField::ONE]],
178 ),
179 ood_frame: OodFrame::default(),
180 fri_proof: FriProof::new_dummy(),
181 pow_nonce: 0,
182 }
183 }
184}
185
186// SERIALIZATION
187// ================================================================================================
188
189impl Serializable for Proof {
190 fn write_into<W: utils::ByteWriter>(&self, target: &mut W) {
191 self.context.write_into(target);
192 target.write_u8(self.num_unique_queries);
193 self.commitments.write_into(target);
194 target.write_many(&self.trace_queries);
195 self.constraint_queries.write_into(target);
196 self.ood_frame.write_into(target);
197 self.fri_proof.write_into(target);
198 self.pow_nonce.write_into(target);
199 }
200}
201
202impl Deserializable for Proof {
203 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
204 let context = Context::read_from(source)?;
205 let num_unique_queries = source.read_u8()?;
206 let commitments = Commitments::read_from(source)?;
207 let num_trace_segments = context.trace_info().num_segments();
208 let mut trace_queries = Vec::with_capacity(num_trace_segments);
209 for _ in 0..num_trace_segments {
210 trace_queries.push(Queries::read_from(source)?);
211 }
212
213 let proof = Proof {
214 context,
215 num_unique_queries,
216 commitments,
217 trace_queries,
218 constraint_queries: Queries::read_from(source)?,
219 ood_frame: OodFrame::read_from(source)?,
220 fri_proof: FriProof::read_from(source)?,
221 pow_nonce: source.read_u64()?,
222 };
223 Ok(proof)
224 }
225}