starky-tmp/src/lib.rs
src/lib.rsRaw
1/// The code of this file is an adaptation from the Starky example from the plonky2 repo.
2///
3use plonky2::field::extension::{Extendable, FieldExtension};
4use plonky2::field::packed::PackedField;
5use plonky2::field::polynomial::PolynomialValues;
6use plonky2::hash::hash_types::RichField;
7use std::marker::PhantomData;
8
9// Imports to define the constraints of our STARK.
10use starky::constraint_consumer::{ConstraintConsumer, RecursiveConstraintConsumer};
11use starky::evaluation_frame::{StarkEvaluationFrame, StarkFrame};
12use starky::stark::Stark;
13
14// Imports to define the recursive constraints of our STARK.
15use plonky2::iop::ext_target::ExtensionTarget;
16use plonky2::plonk::circuit_builder::CircuitBuilder;
17use starky::util::trace_rows_to_poly_values;
18
19// Imports to generate a STARK instance, compute the trace and prove it
20use plonky2::field::types::Field;
21use plonky2::plonk::config::GenericConfig;
22use plonky2::plonk::config::PoseidonGoldilocksConfig;
23use plonky2::util::timing::TimingTree;
24use starky::config::StarkConfig;
25use starky::prover::prove;
26use starky::verifier::verify_stark_proof;
27
28const D: usize = 2;
29const CONFIG: StarkConfig = StarkConfig::standard_fast_config();
30type C = PoseidonGoldilocksConfig;
31type F = <C as GenericConfig<D>>::F;
32type S = FibonacciStark<F, D>;
33
34#[derive(Copy, Clone)]
35pub struct FibonacciStark<F: RichField + Extendable<D>, const D: usize> {
36 num_rows: usize,
37 _phantom: PhantomData<F>,
38}
39// Define witness generation.
40impl<F: RichField + Extendable<D>, const D: usize> FibonacciStark<F, D> {
41 // The first public input is `x0`.
42 const PI_INDEX_X0: usize = 0;
43 // The second public input is `x1`.
44 const PI_INDEX_X1: usize = 1;
45 // The third public input is the second element of the last row,
46 // which should be equal to the `num_rows`-th Fibonacci number.
47 const PI_INDEX_RES: usize = 2;
48
49 pub(crate) fn new(num_rows: usize) -> Self {
50 Self {
51 num_rows,
52 _phantom: PhantomData,
53 }
54 }
55
56 /// Generate the trace using `x0, x1, 0` as initial state values.
57 fn generate_trace(&self, x0: F, x1: F) -> Vec<PolynomialValues<F>> {
58 let mut trace_rows = (0..self.num_rows)
59 .scan([x0, x1, F::ZERO], |acc, _| {
60 let tmp = *acc;
61 acc[0] = tmp[1];
62 acc[1] = tmp[0] + tmp[1];
63 acc[2] = tmp[2] + F::ONE;
64 Some(tmp)
65 })
66 .collect::<Vec<_>>();
67 // Transpose the row-wise trace for the prover.
68 trace_rows_to_poly_values(trace_rows)
69 }
70}
71
72// Define constraints.
73const COLUMNS: usize = 3;
74const PUBLIC_INPUTS: usize = 3;
75
76impl<F: RichField + Extendable<D>, const D: usize> Stark<F, D> for FibonacciStark<F, D> {
77 type EvaluationFrame<FE, P, const D2: usize>
78 = StarkFrame<P, P::Scalar, COLUMNS, PUBLIC_INPUTS>
79 where
80 FE: FieldExtension<D2, BaseField = F>,
81 P: PackedField<Scalar = FE>;
82
83 type EvaluationFrameTarget =
84 StarkFrame<ExtensionTarget<D>, ExtensionTarget<D>, COLUMNS, PUBLIC_INPUTS>;
85
86 // Define this STARK's constraints.
87 fn eval_packed_generic<FE, P, const D2: usize>(
88 &self,
89 vars: &Self::EvaluationFrame<FE, P, D2>,
90 yield_constr: &mut ConstraintConsumer<P>,
91 ) where
92 FE: FieldExtension<D2, BaseField = F>,
93 P: PackedField<Scalar = FE>,
94 {
95 let local_values = vars.get_local_values();
96 let next_values = vars.get_next_values();
97 let public_inputs = vars.get_public_inputs();
98
99 // Check public inputs.
100 yield_constr.constraint_first_row(local_values[0] - public_inputs[Self::PI_INDEX_X0]);
101 yield_constr.constraint_first_row(local_values[1] - public_inputs[Self::PI_INDEX_X1]);
102 yield_constr.constraint_last_row(local_values[1] - public_inputs[Self::PI_INDEX_RES]);
103
104 // Enforce the Fibonacci transition constraints.
105 // x0' <- x1
106 yield_constr.constraint_transition(next_values[0] - local_values[1]);
107 // x1' <- x0 + x1
108 yield_constr.constraint_transition(next_values[1] - local_values[0] - local_values[1]);
109 }
110
111 // Define the constraints to recursively verify this STARK.
112 fn eval_ext_circuit(
113 &self,
114 builder: &mut CircuitBuilder<F, D>,
115 vars: &Self::EvaluationFrameTarget,
116 yield_constr: &mut RecursiveConstraintConsumer<F, D>,
117 ) {
118 let local_values = vars.get_local_values();
119 let next_values = vars.get_next_values();
120 let public_inputs = vars.get_public_inputs();
121
122 // Check public inputs.
123 let pis_constraints = [
124 builder.sub_extension(local_values[0], public_inputs[Self::PI_INDEX_X0]),
125 builder.sub_extension(local_values[1], public_inputs[Self::PI_INDEX_X1]),
126 builder.sub_extension(local_values[1], public_inputs[Self::PI_INDEX_RES]),
127 ];
128
129 yield_constr.constraint_first_row(builder, pis_constraints[0]);
130 yield_constr.constraint_first_row(builder, pis_constraints[1]);
131 yield_constr.constraint_last_row(builder, pis_constraints[2]);
132
133 // Enforce the Fibonacci transition constraints.
134 // x0' <- x1
135 let first_col_constraint = builder.sub_extension(next_values[0], local_values[1]);
136 yield_constr.constraint_transition(builder, first_col_constraint);
137 // x1' <- x0 + x1
138 let second_col_constraint = {
139 let tmp = builder.sub_extension(next_values[1], local_values[0]);
140 builder.sub_extension(tmp, local_values[1])
141 };
142 yield_constr.constraint_transition(builder, second_col_constraint);
143 }
144
145 fn constraint_degree(&self) -> usize {
146 2
147 }
148}
149
150#[cfg(test)]
151mod tests {
152 use super::*;
153
154 fn fibonacci_native<F: Field>(n: usize, x0: F, x1: F) -> F {
155 (0..n).fold((x0, x1), |acc, _| (acc.1, acc.0 + acc.1)).1
156 }
157
158 // test that instantiates a new `FibonacciStark` instance, generates an associated STARK trace,
159 // and generates a proof for it.
160 #[test]
161 fn test_fibonacci_stark() {
162 let num_rows = 1 << 10;
163 let x0 = F::from_canonical_u32(2);
164 let x1 = F::from_canonical_u32(7);
165
166 let public_inputs = [x0, x1, fibonacci_native(num_rows - 1, x0, x1)];
167 let stark = FibonacciStark::<F, D>::new(num_rows);
168 let trace = stark.generate_trace(public_inputs[0], public_inputs[1]);
169
170 let proof = prove::<F, C, S, D>(
171 stark,
172 &CONFIG,
173 trace,
174 &public_inputs,
175 None,
176 &mut TimingTree::default(),
177 )
178 .expect("We should have a valid proof!");
179
180 verify_stark_proof(stark, proof, &CONFIG, None)
181 .expect("We should be able to verify this proof!")
182 }
183}