38 #ifndef CRYPTO3_ZK_QAP_HPP
39 #define CRYPTO3_ZK_QAP_HPP
56 template<
typename FieldType>
59 template<
typename FieldType>
60 struct qap_instance_evaluation;
75 template<
typename FieldType>
77 using field_type = FieldType;
78 using field_value_type =
typename field_type::value_type;
85 std::shared_ptr<evaluation_domain<field_type>>
domain;
92 const std::size_t num_variables,
93 const std::size_t degree,
94 const std::size_t num_inputs,
95 const std::vector<std::map<std::size_t, field_value_type>> &A_in_Lagrange_basis,
96 const std::vector<std::map<std::size_t, field_value_type>> &B_in_Lagrange_basis,
97 const std::vector<std::map<std::size_t, field_value_type>> &C_in_Lagrange_basis) :
98 num_variables(num_variables),
99 degree(degree), num_inputs(num_inputs), domain(domain),
100 A_in_Lagrange_basis(A_in_Lagrange_basis), B_in_Lagrange_basis(B_in_Lagrange_basis),
101 C_in_Lagrange_basis(C_in_Lagrange_basis) {
105 const std::size_t num_variables,
106 const std::size_t degree,
107 const std::size_t num_inputs,
108 std::vector<std::map<std::size_t, field_value_type>> &&A_in_Lagrange_basis,
109 std::vector<std::map<std::size_t, field_value_type>> &&B_in_Lagrange_basis,
110 std::vector<std::map<std::size_t, field_value_type>> &&C_in_Lagrange_basis) :
111 num_variables(num_variables),
112 degree(degree), num_inputs(num_inputs), domain(domain),
113 A_in_Lagrange_basis(std::
move(A_in_Lagrange_basis)),
114 B_in_Lagrange_basis(std::
move(B_in_Lagrange_basis)),
115 C_in_Lagrange_basis(std::
move(C_in_Lagrange_basis)) {
124 const field_value_type t = algebra::random_element<field_type>();
126 std::vector<field_value_type> At(this->num_variables + 1, field_value_type::zero());
127 std::vector<field_value_type> Bt(this->num_variables + 1, field_value_type::zero());
128 std::vector<field_value_type> Ct(this->num_variables + 1, field_value_type::zero());
129 std::vector<field_value_type> Ht(this->degree + 1);
131 const field_value_type Zt = this->domain->compute_vanishing_polynomial(t);
133 const std::vector<field_value_type> u = this->domain->evaluate_all_lagrange_polynomials(t);
135 for (
size_t i = 0; i < this->num_variables + 1; ++i) {
136 for (
auto &el : A_in_Lagrange_basis[i]) {
137 At[i] += u[el.first] * el.second;
140 for (
auto &el : B_in_Lagrange_basis[i]) {
141 Bt[i] += u[el.first] * el.second;
144 for (
auto &el : C_in_Lagrange_basis[i]) {
145 Ct[i] += u[el.first] * el.second;
149 field_value_type ti = field_value_type::one();
150 for (
size_t i = 0; i < this->degree + 1; ++i) {
182 template<
typename FieldType>
184 using field_type = FieldType;
185 using field_value_type =
typename field_type::value_type;
192 std::shared_ptr<evaluation_domain<field_type>>
domain;
196 std::vector<field_value_type>
At, Bt, Ct, Ht;
201 const std::size_t num_variables,
202 const std::size_t degree,
203 const std::size_t num_inputs,
204 const field_value_type &t,
205 const std::vector<field_value_type> &At,
206 const std::vector<field_value_type> &Bt,
207 const std::vector<field_value_type> &Ct,
208 const std::vector<field_value_type> &Ht,
209 const field_value_type &Zt) :
210 num_variables(num_variables),
211 degree(degree), num_inputs(num_inputs), domain(domain), t(t), At(At), Bt(Bt), Ct(Ct), Ht(Ht),
216 const std::size_t num_variables,
217 const std::size_t degree,
218 const std::size_t num_inputs,
219 const field_value_type &t,
220 std::vector<field_value_type> &&At,
221 std::vector<field_value_type> &&Bt,
222 std::vector<field_value_type> &&Ct,
223 std::vector<field_value_type> &&Ht,
224 const field_value_type &Zt) :
225 num_variables(num_variables),
226 degree(degree), num_inputs(num_inputs), domain(domain), t(t), At(std::
move(At)),
227 Bt(std::
move(Bt)), Ct(std::
move(Ct)), Ht(std::
move(Ht)), Zt(Zt) {
241 if (this->degree != witness.
degree) {
257 if (this->At.size() != this->num_variables + 1 || this->Bt.size() != this->num_variables + 1 ||
258 this->Ct.size() != this->num_variables + 1) {
262 if (this->Ht.size() != this->degree + 1) {
266 if (this->Zt != this->domain->compute_vanishing_polynomial(this->t)) {
270 field_value_type ans_A = this->At[0] + witness.
d1 * this->Zt;
271 field_value_type ans_B = this->Bt[0] + witness.
d2 * this->Zt;
272 field_value_type ans_C = this->Ct[0] + witness.
d3 * this->Zt;
273 field_value_type ans_H = field_value_type::zero();
276 this->At.begin() + 1 + this->num_variables,
279 this->num_variables);
281 this->Bt.begin() + 1 + this->num_variables,
284 this->num_variables);
286 this->Ct.begin() + 1 + this->num_variables,
289 this->num_variables);
291 this->Ht.begin() + this->degree + 1,
296 if (ans_A * ans_B - ans_C != ans_H * this->Zt) {
309 template<
typename FieldType>
311 using field_type = FieldType;
312 using field_value_type =
typename field_type::value_type;
319 field_value_type
d1, d2, d3;
325 const std::size_t degree,
326 const std::size_t num_inputs,
327 const field_value_type &d1,
328 const field_value_type &d2,
329 const field_value_type &d3,
330 const std::vector<field_value_type> &coefficients_for_ABCs,
331 const std::vector<field_value_type> &coefficients_for_H) :
332 num_variables(num_variables),
333 degree(degree), num_inputs(num_inputs), d1(d1), d2(d2), d3(d3),
334 coefficients_for_ABCs(coefficients_for_ABCs), coefficients_for_H(coefficients_for_H) {
338 const std::size_t degree,
339 const std::size_t num_inputs,
340 const field_value_type &d1,
341 const field_value_type &d2,
342 const field_value_type &d3,
343 const std::vector<field_value_type> &coefficients_for_ABCs,
344 std::vector<field_value_type> &&coefficients_for_H) :
345 num_variables(num_variables),
346 degree(degree), num_inputs(num_inputs), d1(d1), d2(d2), d3(d3),
347 coefficients_for_ABCs(coefficients_for_ABCs),
348 coefficients_for_H(std::
move(coefficients_for_H)) {
Definition: evaluation_domain.hpp:41
std::size_t num_inputs
Definition: qap.hpp:83
qap_instance & operator=(qap_instance< field_type > &&other)=default
qap_instance & operator=(const qap_instance< field_type > &other)=default
std::vector< std::map< std::size_t, field_value_type > > A_in_Lagrange_basis
Definition: qap.hpp:87
bool is_satisfied(const qap_witness< field_type > &witness) const
Definition: qap.hpp:123
std::size_t num_variables
Definition: qap.hpp:81
std::vector< std::map< std::size_t, field_value_type > > C_in_Lagrange_basis
Definition: qap.hpp:89
std::shared_ptr< evaluation_domain< field_type > > domain
Definition: qap.hpp:85
qap_instance(const std::shared_ptr< evaluation_domain< field_type >> &domain, const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, std::vector< std::map< std::size_t, field_value_type >> &&A_in_Lagrange_basis, std::vector< std::map< std::size_t, field_value_type >> &&B_in_Lagrange_basis, std::vector< std::map< std::size_t, field_value_type >> &&C_in_Lagrange_basis)
Definition: qap.hpp:104
qap_instance(const qap_instance< field_type > &other)=default
qap_instance(qap_instance< field_type > &&other)=default
qap_instance(const std::shared_ptr< evaluation_domain< field_type >> &domain, const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, const std::vector< std::map< std::size_t, field_value_type >> &A_in_Lagrange_basis, const std::vector< std::map< std::size_t, field_value_type >> &B_in_Lagrange_basis, const std::vector< std::map< std::size_t, field_value_type >> &C_in_Lagrange_basis)
Definition: qap.hpp:91
std::vector< std::map< std::size_t, field_value_type > > B_in_Lagrange_basis
Definition: qap.hpp:88
std::size_t degree
Definition: qap.hpp:82
vector(T, U...) -> vector< std::enable_if_t<(std::is_same_v< T, U > &&...), T >, 1+sizeof...(U)>
deduction guide for uniform initialization
std::iterator_traits< InputBaseIterator >::value_type inner_product(InputBaseIterator a_begin, InputBaseIterator a_end, InputBaseIterator b_begin, InputBaseIterator b_end)
Definition: algebra/include/nil/crypto3/algebra/multiexp/inner_product.hpp:40
OutputIterator move(const SinglePassRange &rng, OutputIterator result)
Definition: move.hpp:45
Definition: make_evaluation_domain.hpp:40
field_value_type t
Definition: qap.hpp:194
qap_instance_evaluation & operator=(qap_instance_evaluation< field_type > &&other)=default
std::size_t degree
Definition: qap.hpp:189
std::size_t num_inputs
Definition: qap.hpp:190
std::vector< field_value_type > At
Definition: qap.hpp:196
field_value_type Zt
Definition: qap.hpp:198
qap_instance_evaluation(const std::shared_ptr< evaluation_domain< field_type >> &domain, const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, const field_value_type &t, std::vector< field_value_type > &&At, std::vector< field_value_type > &&Bt, std::vector< field_value_type > &&Ct, std::vector< field_value_type > &&Ht, const field_value_type &Zt)
Definition: qap.hpp:215
std::shared_ptr< evaluation_domain< field_type > > domain
Definition: qap.hpp:192
std::size_t num_variables
Definition: qap.hpp:188
qap_instance_evaluation(const std::shared_ptr< evaluation_domain< field_type >> &domain, const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, const field_value_type &t, const std::vector< field_value_type > &At, const std::vector< field_value_type > &Bt, const std::vector< field_value_type > &Ct, const std::vector< field_value_type > &Ht, const field_value_type &Zt)
Definition: qap.hpp:200
qap_instance_evaluation & operator=(const qap_instance_evaluation< field_type > &other)=default
qap_instance_evaluation(const qap_instance_evaluation< field_type > &other)=default
bool is_satisfied(const qap_witness< field_type > &witness) const
Definition: qap.hpp:235
qap_instance_evaluation(qap_instance_evaluation< field_type > &&other)=default
field_value_type d3
Definition: qap.hpp:319
std::size_t num_inputs
Definition: qap.hpp:317
qap_witness & operator=(qap_witness< field_type > &&other)=default
std::size_t num_variables
Definition: qap.hpp:315
qap_witness(const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, const field_value_type &d1, const field_value_type &d2, const field_value_type &d3, const std::vector< field_value_type > &coefficients_for_ABCs, std::vector< field_value_type > &&coefficients_for_H)
Definition: qap.hpp:337
qap_witness & operator=(const qap_witness< field_type > &other)=default
std::vector< field_value_type > coefficients_for_H
Definition: qap.hpp:322
std::vector< field_value_type > coefficients_for_ABCs
Definition: qap.hpp:321
qap_witness(const qap_witness< field_type > &other)=default
field_value_type d1
Definition: qap.hpp:319
qap_witness(const std::size_t num_variables, const std::size_t degree, const std::size_t num_inputs, const field_value_type &d1, const field_value_type &d2, const field_value_type &d3, const std::vector< field_value_type > &coefficients_for_ABCs, const std::vector< field_value_type > &coefficients_for_H)
Definition: qap.hpp:324
qap_witness(qap_witness< field_type > &&other)=default
field_value_type d2
Definition: qap.hpp:319
std::size_t degree
Definition: qap.hpp:316