nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType > Class Template Reference

#include <r1cs_to_sap.hpp>

+ Collaboration diagram for nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType >:

Static Public Member Functions

static std::shared_ptr< math::evaluation_domain< FieldType > > get_domain (const r1cs_constraint_system< FieldType > &cs)
 
static sap_instance< FieldType > instance_map (const r1cs_constraint_system< FieldType > &cs)
 
static sap_instance_evaluation< FieldType > instance_map_with_evaluation (const r1cs_constraint_system< FieldType > &cs, const typename FieldType::value_type &t)
 
static sap_witness< FieldType > witness_map (const r1cs_constraint_system< FieldType > &cs, const r1cs_primary_input< FieldType > &primary_input, const r1cs_auxiliary_input< FieldType > &auxiliary_input, const typename FieldType::value_type &d1, const typename FieldType::value_type &d2)
 

Member Function Documentation

◆ get_domain()

template<typename FieldType >
static std::shared_ptr<math::evaluation_domain<FieldType> > nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType >::get_domain ( const r1cs_constraint_system< FieldType > &  cs)
inlinestatic

Helper function to find evaluation domain that will be used by the reduction for a given R1CS instance.

◆ instance_map()

template<typename FieldType >
static sap_instance<FieldType> nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType >::instance_map ( const r1cs_constraint_system< FieldType > &  cs)
inlinestatic

Instance map for the R1CS-to-SAP reduction.

process R1CS constraints, converting a constraint of the form \sum a_i x_i * \sum b_i x_i = \sum c_i x_i into two constraints (\sum (a_i + b_i) x_i)^2 = 4 \sum c_i x_i + x'_i (\sum (a_i - b_i) x_i)^2 = x'_i where x'_i is an extra variable (a separate one for each original constraint)

this adds 2 * cs.num_constraints() constraints (numbered 0 .. 2 * cs.num_constraints() - 1) and cs.num_constraints() extra variables (numbered cs.num_variables() + 1 .. cs.num_variables() + cs.num_constraints())

add and convert the extra constraints x_i * 1 = x_i to ensure that the polynomials 0 .. cs.num_inputs() are linearly independent from each other and the rest, which is required for security proofs (see [GM17, p. 29])

note that i = 0 is a special case, where this constraint is expressible as x_0^2 = x_0, whereas for every other i we introduce an extra variable x''_i and do (x_i + x_0)^2 = 4 x_i + x''_i (x_i - x_0)^2 = x''_i

this adds 2 * cs.num_inputs() + 1 extra constraints (numbered 2 * cs.num_constraints() .. 2 * cs.num_constraints() + 2 * cs.num_inputs()) and cs.num_inputs() extra variables (numbered cs.num_variables() + cs.num_constraints() + 1 .. cs.num_variables() + cs.num_constraints() + cs.num_inputs())

NB: extra variables start at (extra_var_offset2 + 1), because i starts at 1 below

◆ instance_map_with_evaluation()

template<typename FieldType >
static sap_instance_evaluation<FieldType> nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType >::instance_map_with_evaluation ( const r1cs_constraint_system< FieldType > &  cs,
const typename FieldType::value_type &  t 
)
inlinestatic

Instance map for the R1CS-to-SAP reduction followed by evaluation of the resulting QAP instance.

add and process all constraints as in instance_map

◆ witness_map()

template<typename FieldType >
static sap_witness<FieldType> nil::crypto3::zk::snark::reductions::r1cs_to_sap< FieldType >::witness_map ( const r1cs_constraint_system< FieldType > &  cs,
const r1cs_primary_input< FieldType > &  primary_input,
const r1cs_auxiliary_input< FieldType > &  auxiliary_input,
const typename FieldType::value_type &  d1,
const typename FieldType::value_type &  d2 
)
inlinestatic

Witness map for the R1CS-to-SAP reduction.

The witness map takes zero knowledge into account when d1, d2 are random.

More precisely, compute the coefficients h_0,h_1,...,h_n of the polynomial H(z) := (A(z)*A(z)-C(z))/Z(z) where A(z) := A_0(z) + \sum_{k=1}^{m} w_k A_k(z) + d1 * Z(z) C(z) := C_0(z) + \sum_{k=1}^{m} w_k C_k(z) + d2 * Z(z) Z(z) := "vanishing polynomial of set S" and m = number of variables of the SAP n = degree of the SAP

This is done as follows: (1) compute evaluations of A,C on S = {sigma_1,...,sigma_n} (2) compute coefficients of A,C (3) compute evaluations of A,C on T = "coset of S" (4) compute evaluation of H on T (5) compute coefficients of H (6) patch H to account for d1,d2 (i.e., add coefficients of the polynomial (2*d1*A - d2 + d1^2 * Z))

The code below is not as simple as the above high-level description due to some reshuffling to save space.

we need to generate values of all the extra variables that we added during the reduction

note: below, we pass full_variable_assignment into the .evaluate() method of the R1CS constraints. however, these extra variables shouldn't be a problem, because .evaluate() only accesses the variables that are actually used in the constraint.

this is variable (extra_var_offset + i), an extra variable we introduced that is not present in the input. its value is (a - b)^2

this is variable (extra_var_offset2 + i), an extra variable we introduced that is not present in the input. its value is (x_i - 1)^2


The documentation for this class was generated from the following file: