barretenberg
Loading...
Searching...
No Matches
plookup_auxiliary_widget.hpp
1#pragma once
2
3#include "./transition_widget.hpp"
4
5namespace proof_system::plonk {
6namespace widget {
7
41template <class Field, class Getters, typename PolyContainer> class PlookupAuxiliaryKernel {
42 public:
43 static constexpr bool use_quotient_mid = false;
44 static constexpr size_t num_independent_relations = 4;
45 // We state the challenges required for linear/nonlinear terms computation
46 static constexpr uint8_t quotient_required_challenges = CHALLENGE_BIT_ALPHA;
47 // We state the challenges required for updating kate opening scalars
48 static constexpr uint8_t update_required_challenges = CHALLENGE_BIT_ALPHA;
49
50 private:
51 typedef containers::challenge_array<Field, num_independent_relations> challenge_array;
52
53 public:
54 inline static std::set<PolynomialIndex> const& get_required_polynomial_ids()
55 {
56 static const std::set<PolynomialIndex> required_polynomial_ids = {
57 PolynomialIndex::Q_1, PolynomialIndex::Q_2, PolynomialIndex::Q_3, PolynomialIndex::Q_4,
58 PolynomialIndex::Q_M, PolynomialIndex::Q_C, PolynomialIndex::Q_ARITHMETIC, PolynomialIndex::Q_AUX,
59 PolynomialIndex::W_1, PolynomialIndex::W_2, PolynomialIndex::W_3, PolynomialIndex::W_4
60 };
61 return required_polynomial_ids;
62 }
63
64 inline static void accumulate_contribution(PolyContainer& polynomials,
65 const challenge_array& challenges,
66 Field& quotient,
67 const size_t i = 0)
68 {
69 constexpr barretenberg::fr LIMB_SIZE(uint256_t(1) << 68);
70 constexpr barretenberg::fr SUBLIMB_SHIFT(uint256_t(1) << 14);
71
72 const Field& w_1 =
73 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::W_1>(polynomials, i);
74 const Field& w_2 =
75 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::W_2>(polynomials, i);
76 const Field& w_3 =
77 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::W_3>(polynomials, i);
78 const Field& w_4 =
79 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::W_4>(polynomials, i);
80 const Field& w_1_omega =
81 Getters::template get_value<EvaluationType::SHIFTED, PolynomialIndex::W_1>(polynomials, i);
82 const Field& w_2_omega =
83 Getters::template get_value<EvaluationType::SHIFTED, PolynomialIndex::W_2>(polynomials, i);
84 const Field& w_3_omega =
85 Getters::template get_value<EvaluationType::SHIFTED, PolynomialIndex::W_3>(polynomials, i);
86 const Field& w_4_omega =
87 Getters::template get_value<EvaluationType::SHIFTED, PolynomialIndex::W_4>(polynomials, i);
88
89 const Field& alpha_base = challenges.alpha_powers[0];
90 const Field& alpha = challenges.elements[ChallengeIndex::ALPHA];
91 const Field& eta = challenges.elements[ChallengeIndex::ETA];
92
93 const Field& q_aux =
94 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_AUX>(polynomials, i);
95 const Field& q_1 =
96 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_1>(polynomials, i);
97 const Field& q_2 =
98 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_2>(polynomials, i);
99 const Field& q_3 =
100 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_3>(polynomials, i);
101 const Field& q_4 =
102 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_4>(polynomials, i);
103 const Field& q_m =
104 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_M>(polynomials, i);
105 const Field& q_c =
106 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_C>(polynomials, i);
107 const Field& q_arith =
108 Getters::template get_value<EvaluationType::NON_SHIFTED, PolynomialIndex::Q_ARITHMETIC>(polynomials, i);
109
119 Field limb_subproduct = w_1 * w_2_omega + w_1_omega * w_2;
120 Field non_native_field_gate_2 = (w_1 * w_4 + w_2 * w_3 - w_3_omega);
121 non_native_field_gate_2 *= LIMB_SIZE;
122 non_native_field_gate_2 -= w_4_omega;
123 non_native_field_gate_2 += limb_subproduct;
124 non_native_field_gate_2 *= q_4;
125
126 limb_subproduct *= LIMB_SIZE;
127 limb_subproduct += (w_1_omega * w_2_omega);
128 Field non_native_field_gate_1 = limb_subproduct;
129 non_native_field_gate_1 -= (w_3 + w_4);
130 non_native_field_gate_1 *= q_3;
131
132 Field non_native_field_gate_3 = limb_subproduct;
133 non_native_field_gate_3 += w_4;
134 non_native_field_gate_3 -= (w_3_omega + w_4_omega);
135 non_native_field_gate_3 *= q_m;
136
137 Field non_native_field_identity = non_native_field_gate_1 + non_native_field_gate_2 + non_native_field_gate_3;
138 non_native_field_identity *= q_2;
139
140 Field limb_accumulator_1 = w_2_omega;
141 limb_accumulator_1 *= SUBLIMB_SHIFT;
142 limb_accumulator_1 += w_1_omega;
143 limb_accumulator_1 *= SUBLIMB_SHIFT;
144 limb_accumulator_1 += w_3;
145 limb_accumulator_1 *= SUBLIMB_SHIFT;
146 limb_accumulator_1 += w_2;
147 limb_accumulator_1 *= SUBLIMB_SHIFT;
148 limb_accumulator_1 += w_1;
149 limb_accumulator_1 -= w_4;
150 limb_accumulator_1 *= q_4;
151
152 Field limb_accumulator_2 = w_3_omega;
153 limb_accumulator_2 *= SUBLIMB_SHIFT;
154 limb_accumulator_2 += w_2_omega;
155 limb_accumulator_2 *= SUBLIMB_SHIFT;
156 limb_accumulator_2 += w_1_omega;
157 limb_accumulator_2 *= SUBLIMB_SHIFT;
158 limb_accumulator_2 += w_4;
159 limb_accumulator_2 *= SUBLIMB_SHIFT;
160 limb_accumulator_2 += w_3;
161 limb_accumulator_2 -= w_4_omega;
162 limb_accumulator_2 *= q_m;
163
164 Field limb_accumulator_identity = limb_accumulator_1 + limb_accumulator_2;
165 limb_accumulator_identity *= q_3;
166
205 Field memory_record_check = w_3;
206 memory_record_check *= eta;
207 memory_record_check += w_2;
208 memory_record_check *= eta;
209 memory_record_check += w_1;
210 memory_record_check *= eta;
211 memory_record_check += q_c;
212 Field partial_record_check = memory_record_check; // used in RAM consistency check
213 memory_record_check = memory_record_check - w_4;
214
228 Field index_delta = w_1_omega - w_1;
229 Field record_delta = w_4_omega - w_4;
230
231 Field index_is_monotonically_increasing = index_delta.sqr() - index_delta;
232
233 Field adjacent_values_match_if_adjacent_indices_match = (Field(1) - index_delta) * record_delta;
234
235 Field ROM_consistency_check_identity = adjacent_values_match_if_adjacent_indices_match;
236 ROM_consistency_check_identity *= alpha;
237 ROM_consistency_check_identity += index_is_monotonically_increasing;
238 ROM_consistency_check_identity *= alpha;
239 ROM_consistency_check_identity += memory_record_check;
240
259 Field access_type = (w_4 - partial_record_check); // will be 0 or 1 for honest Prover
260 Field access_check = access_type.sqr() - access_type; // check value is 0 or 1
261
262 // TODO: oof nasty compute here. If we sorted in reverse order we could re-use `partial_record_check`
263 Field next_gate_access_type = w_3_omega;
264 next_gate_access_type *= eta;
265 next_gate_access_type += w_2_omega;
266 next_gate_access_type *= eta;
267 next_gate_access_type += w_1_omega;
268 next_gate_access_type *= eta;
269 next_gate_access_type = w_4_omega - next_gate_access_type;
270
271 Field value_delta = w_3_omega - w_3;
272 Field adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation =
273 (Field(1) - index_delta) * value_delta * (Field(1) - next_gate_access_type);
274
275 // We can't apply the RAM consistency check identity on the final entry in the sorted list (the wires in the
276 // next gate would make the identity fail).
277 // We need to validate that its 'access type' bool is correct. Can't do
278 // with an arithmetic gate because of the `eta` factors. We need to check that the *next* gate's access type is
279 // correct, to cover this edge case
280 Field next_gate_access_type_is_boolean = next_gate_access_type.sqr() - next_gate_access_type;
281
282 // Putting it all together...
283 Field RAM_consistency_check_identity =
284 adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation;
285 RAM_consistency_check_identity *= alpha;
286 RAM_consistency_check_identity += index_is_monotonically_increasing;
287 RAM_consistency_check_identity *= alpha;
288 RAM_consistency_check_identity += next_gate_access_type_is_boolean;
289 RAM_consistency_check_identity *= alpha;
290 RAM_consistency_check_identity += access_check;
291
303 Field timestamp_delta = w_2_omega - w_2;
304 Field RAM_timestamp_check_identity = (Field(1) - index_delta) * timestamp_delta - w_3;
305
310 Field memory_identity = ROM_consistency_check_identity * q_2;
311 memory_identity += RAM_timestamp_check_identity * q_4;
312 memory_identity += memory_record_check * q_m;
313 memory_identity *= q_1;
314 memory_identity += (RAM_consistency_check_identity * q_arith);
315
316 Field auxiliary_identity = memory_identity + non_native_field_identity + limb_accumulator_identity;
317 auxiliary_identity *= q_aux;
318 auxiliary_identity *= alpha_base;
319
320 quotient += (auxiliary_identity);
321 }
322};
323
324} // namespace widget
325
326template <typename Settings>
327using ProverPlookupAuxiliaryWidget =
328 widget::TransitionWidget<barretenberg::fr, Settings, widget::PlookupAuxiliaryKernel>;
329
330template <typename Field, typename Group, typename Transcript, typename Settings>
331using VerifierPlookupAuxiliaryWidget =
332 widget::GenericVerifierWidget<Field, Transcript, Settings, widget::PlookupAuxiliaryKernel>;
333
334} // namespace proof_system::plonk
numeric::uint256_t
Definition: uint256.hpp:25
proof_system::plonk::widget::PlookupAuxiliaryKernel
Plookup Auxiliary Widget.
Definition: plookup_auxiliary_widget.hpp:41
proof_system::plonk::widget::PlookupAuxiliaryKernel::accumulate_contribution
static void accumulate_contribution(PolyContainer &polynomials, const challenge_array &challenges, Field &quotient, const size_t i=0)
Definition: plookup_auxiliary_widget.hpp:64
proof_system::plonk
Definition: widget.bench.cpp:13
barretenberg::field::sqr
BBERG_INLINE constexpr field sqr() const noexcept
Definition: field_impl.hpp:61
proof_system::plonk::widget::containers::challenge_array
Definition: transition_widget.hpp:38
Generated by doxygen 1.9.6