-
Notifications
You must be signed in to change notification settings - Fork 55
/
constraint_eval.rs
156 lines (145 loc) · 6.26 KB
/
constraint_eval.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
use std::collections::BTreeMap;
use itertools::{zip_eq, Itertools};
use num_traits::Zero;
use super::component::{Input, WideFibAir, WideFibComponent, ALPHA_ID, Z_ID};
use super::trace_gen::write_trace_row;
use crate::core::air::accumulation::DomainEvaluationAccumulator;
use crate::core::air::{
AirProver, AirTraceVerifier, AirTraceWriter, Component, ComponentProver, ComponentTrace,
ComponentTraceWriter,
};
use crate::core::backend::CpuBackend;
use crate::core::channel::{Blake2sChannel, Channel};
use crate::core::constraints::{coset_vanishing, point_vanishing};
use crate::core::fields::m31::BaseField;
use crate::core::fields::qm31::SecureField;
use crate::core::fields::FieldExpOps;
use crate::core::poly::circle::{CanonicCoset, CircleEvaluation, SecureCirclePoly};
use crate::core::poly::BitReversedOrder;
use crate::core::utils::{bit_reverse, shifted_secure_combination};
use crate::core::{ColumnVec, InteractionElements};
use crate::examples::wide_fibonacci::component::LOG_N_COLUMNS;
// TODO(AlonH): Rename file to `cpu.rs`.
impl AirTraceVerifier for WideFibAir {
fn interaction_elements(&self, channel: &mut Blake2sChannel) -> InteractionElements {
let ids = self.component.interaction_element_ids();
let elements = channel.draw_felts(ids.len());
InteractionElements::new(BTreeMap::from_iter(zip_eq(ids, elements)))
}
}
impl AirTraceWriter<CpuBackend> for WideFibAir {
fn interact(
&self,
trace: &ColumnVec<CircleEvaluation<CpuBackend, BaseField, BitReversedOrder>>,
elements: &InteractionElements,
) -> Vec<CircleEvaluation<CpuBackend, BaseField, BitReversedOrder>> {
self.component
.write_interaction_trace(&trace.iter().collect(), elements)
}
fn to_air_prover(&self) -> &impl AirProver<CpuBackend> {
self
}
}
impl AirProver<CpuBackend> for WideFibAir {
fn prover_components(&self) -> Vec<&dyn ComponentProver<CpuBackend>> {
vec![&self.component]
}
}
impl ComponentProver<CpuBackend> for WideFibComponent {
fn evaluate_constraint_quotients_on_domain(
&self,
trace: &ComponentTrace<'_, CpuBackend>,
evaluation_accumulator: &mut DomainEvaluationAccumulator<CpuBackend>,
interaction_elements: &InteractionElements,
) {
let max_constraint_degree = self.max_constraint_log_degree_bound();
let trace_eval_domain = CanonicCoset::new(max_constraint_degree).circle_domain();
let trace_evals = &trace.evals;
let zero_domain = CanonicCoset::new(self.log_column_size()).coset;
let mut denoms = vec![];
let mut lookup_denoms = vec![];
for point in trace_eval_domain.iter() {
denoms.push(coset_vanishing(zero_domain, point));
lookup_denoms.push(point_vanishing(zero_domain.at(0), point));
}
bit_reverse(&mut denoms);
let mut denom_inverses = vec![BaseField::zero(); 1 << (max_constraint_degree)];
BaseField::batch_inverse(&denoms, &mut denom_inverses);
bit_reverse(&mut lookup_denoms);
let mut lookup_denom_inverses = vec![BaseField::zero(); 1 << (max_constraint_degree)];
BaseField::batch_inverse(&lookup_denoms, &mut lookup_denom_inverses);
let mut numerators = vec![SecureField::zero(); 1 << (max_constraint_degree)];
let mut lookup_numerators = vec![SecureField::zero(); 1 << (max_constraint_degree)];
let [mut accum] =
evaluation_accumulator.columns([(max_constraint_degree, self.n_constraints())]);
let (alpha, z) = (interaction_elements[ALPHA_ID], interaction_elements[Z_ID]);
for i in 0..trace_eval_domain.size() {
// Step constraints.
for j in 0..self.n_columns() - 2 {
numerators[i] += accum.random_coeff_powers[self.n_columns() - 3 - j]
* (trace_evals[0][j][i].square() + trace_evals[0][j + 1][i].square()
- trace_evals[0][j + 2][i]);
}
// Lookup constraints.
let lookup_value =
SecureCirclePoly::<CpuBackend>::eval_from_partial_evals(std::array::from_fn(|j| {
trace_evals[1][j][i].into()
}));
lookup_numerators[i] = accum.random_coeff_powers[self.n_columns() - 2]
* ((lookup_value
* shifted_secure_combination(
&[
trace_evals[0][self.n_columns() - 2][i],
trace_evals[0][self.n_columns() - 1][i],
],
alpha,
z,
))
- shifted_secure_combination(
&[trace_evals[0][0][i], trace_evals[0][1][i]],
alpha,
z,
));
}
for (i, (num, denom_inverse)) in numerators.iter().zip(denom_inverses.iter()).enumerate() {
accum.accumulate(i, *num * *denom_inverse);
}
for (i, (num, denom_inverse)) in lookup_numerators
.iter()
.zip(lookup_denom_inverses.iter())
.enumerate()
{
accum.accumulate(i, *num * *denom_inverse);
}
}
}
/// Generates the trace for the wide Fibonacci example.
pub fn gen_trace(
wide_fib: &WideFibComponent,
private_input: Vec<Input>,
) -> ColumnVec<Vec<BaseField>> {
let n_instances = 1 << wide_fib.log_n_instances;
assert_eq!(
private_input.len(),
n_instances,
"The number of inputs must match the number of instances"
);
assert!(
wide_fib.log_fibonacci_size >= LOG_N_COLUMNS as u32,
"The fibonacci size must be at least equal to the length of a row"
);
let n_rows_per_instance = 1 << (wide_fib.log_fibonacci_size - wide_fib.log_n_columns() as u32);
let n_rows = n_instances * n_rows_per_instance;
let zero_vec = vec![BaseField::zero(); n_rows];
let mut dst = vec![zero_vec; wide_fib.n_columns()];
(0..n_rows_per_instance).fold(private_input, |input, row| {
(0..n_instances)
.map(|instance| {
let (a, b) =
write_trace_row(&mut dst, &input[instance], row * n_instances + instance);
Input { a, b }
})
.collect_vec()
});
dst
}