r1cs_to_qap.tcc

Go to the documentation of this file.

/** @file
 *****************************************************************************
 
 Implementation of interfaces for a R1CS-to-QAP reduction.
 
 See r1cs_to_qap.hpp .
 
 *****************************************************************************
 * @author     This file is part of libsnark, developed by SCIPR Lab
 *             and contributors (see AUTHORS).
 * @copyright  MIT license (see LICENSE file)
 *****************************************************************************/
 
#ifndef R1CS_TO_QAP_TCC_
#define R1CS_TO_QAP_TCC_
 
#include <libff/common/profiling.hpp>
#include <libff/common/utils.hpp>
#include <libfqfft/evaluation_domain/get_evaluation_domain.hpp>
 
namespace libsnark
{
 
/**
 * Instance map for the R1CS-to-QAP reduction.
 *
 * Namely, given a R1CS constraint system cs, construct a QAP instance for
 * which: A := (A_0(z),A_1(z),...,A_m(z)) B := (B_0(z),B_1(z),...,B_m(z)) C :=
 * (C_0(z),C_1(z),...,C_m(z)) where m = number of variables of the QAP and each
 * A_i,B_i,C_i is expressed in the Lagrange basis.
 */
template<typename FieldT>
qap_instance<FieldT> r1cs_to_qap_instance_map(
    const r1cs_constraint_system<FieldT> &cs, bool force_pow_2_domain)
{
    libff::enter_block("Call to r1cs_to_qap_instance_map");
 
    const size_t min_n = cs.num_constraints() + cs.num_inputs() + 1;
    const size_t n = force_pow_2_domain ? 1 << libff::log2(min_n) : min_n;
    std::shared_ptr<libfqfft::evaluation_domain<FieldT>> domain =
        libfqfft::get_evaluation_domain<FieldT>(n);
 
    std::vector<std::map<size_t, FieldT>> A_in_Lagrange_basis(
        cs.num_variables() + 1);
    std::vector<std::map<size_t, FieldT>> B_in_Lagrange_basis(
        cs.num_variables() + 1);
    std::vector<std::map<size_t, FieldT>> C_in_Lagrange_basis(
        cs.num_variables() + 1);
 
    libff::enter_block("Compute polynomials A, B, C in Lagrange basis");
    /**
     * add and process the constraints
     *     input_i * 0 = 0
     * to ensure soundness of input consistency
     */
    for (size_t i = 0; i <= cs.num_inputs(); ++i) {
        A_in_Lagrange_basis[i][cs.num_constraints() + i] = FieldT::one();
    }
    /* process all other constraints */
    for (size_t i = 0; i < cs.num_constraints(); ++i) {
        for (size_t j = 0; j < cs.constraints[i].a.terms.size(); ++j) {
            A_in_Lagrange_basis[cs.constraints[i].a.terms[j].index][i] +=
                cs.constraints[i].a.terms[j].coeff;
        }
 
        for (size_t j = 0; j < cs.constraints[i].b.terms.size(); ++j) {
            B_in_Lagrange_basis[cs.constraints[i].b.terms[j].index][i] +=
                cs.constraints[i].b.terms[j].coeff;
        }
 
        for (size_t j = 0; j < cs.constraints[i].c.terms.size(); ++j) {
            C_in_Lagrange_basis[cs.constraints[i].c.terms[j].index][i] +=
                cs.constraints[i].c.terms[j].coeff;
        }
    }
    libff::leave_block("Compute polynomials A, B, C in Lagrange basis");
 
    libff::leave_block("Call to r1cs_to_qap_instance_map");
 
    return qap_instance<FieldT>(
        domain,
        cs.num_variables(),
        domain->m,
        cs.num_inputs(),
        std::move(A_in_Lagrange_basis),
        std::move(B_in_Lagrange_basis),
        std::move(C_in_Lagrange_basis));
}
 
/**
 * Instance map for the R1CS-to-QAP reduction followed by evaluation of the
 * resulting QAP instance.
 *
 * Namely, given a R1CS constraint system cs and a field element t, construct
 * a QAP instance (evaluated at t) for which:
 *   At := (A_0(t),A_1(t),...,A_m(t))
 *   Bt := (B_0(t),B_1(t),...,B_m(t))
 *   Ct := (C_0(t),C_1(t),...,C_m(t))
 *   Ht := (1,t,t^2,...,t^n)
 *   Zt := Z(t) = "vanishing polynomial of a certain set S, evaluated at t"
 * where
 *   m = number of variables of the QAP
 *   n = degree of the QAP
 */
template<typename FieldT>
qap_instance_evaluation<FieldT> r1cs_to_qap_instance_map_with_evaluation(
    const r1cs_constraint_system<FieldT> &cs,
    const FieldT &t,
    bool force_pow_2_domain)
{
    libff::enter_block("Call to r1cs_to_qap_instance_map_with_evaluation");
 
    const size_t min_n = cs.num_constraints() + cs.num_inputs() + 1;
    const size_t n = force_pow_2_domain ? 1 << libff::log2(min_n) : min_n;
    std::shared_ptr<libfqfft::evaluation_domain<FieldT>> domain =
        libfqfft::get_evaluation_domain<FieldT>(n);
 
    std::vector<FieldT> At, Bt, Ct, Ht;
 
    At.resize(cs.num_variables() + 1, FieldT::zero());
    Bt.resize(cs.num_variables() + 1, FieldT::zero());
    Ct.resize(cs.num_variables() + 1, FieldT::zero());
    Ht.reserve(domain->m + 1);
 
    const FieldT Zt = domain->compute_vanishing_polynomial(t);
 
    libff::enter_block("Compute evaluations of A, B, C, H at t");
    const std::vector<FieldT> u = domain->evaluate_all_lagrange_polynomials(t);
    /**
     * add and process the constraints
     *     input_i * 0 = 0
     * to ensure soundness of input consistency
     */
    for (size_t i = 0; i <= cs.num_inputs(); ++i) {
        At[i] = u[cs.num_constraints() + i];
    }
    /* process all other constraints */
    for (size_t i = 0; i < cs.num_constraints(); ++i) {
        for (size_t j = 0; j < cs.constraints[i].a.terms.size(); ++j) {
            At[cs.constraints[i].a.terms[j].index] +=
                u[i] * cs.constraints[i].a.terms[j].coeff;
        }
 
        for (size_t j = 0; j < cs.constraints[i].b.terms.size(); ++j) {
            Bt[cs.constraints[i].b.terms[j].index] +=
                u[i] * cs.constraints[i].b.terms[j].coeff;
        }
 
        for (size_t j = 0; j < cs.constraints[i].c.terms.size(); ++j) {
            Ct[cs.constraints[i].c.terms[j].index] +=
                u[i] * cs.constraints[i].c.terms[j].coeff;
        }
    }
 
    FieldT ti = FieldT::one();
    for (size_t i = 0; i < domain->m + 1; ++i) {
        Ht.emplace_back(ti);
        ti *= t;
    }
    libff::leave_block("Compute evaluations of A, B, C, H at t");
 
    libff::leave_block("Call to r1cs_to_qap_instance_map_with_evaluation");
 
    return qap_instance_evaluation<FieldT>(
        domain,
        cs.num_variables(),
        domain->m,
        cs.num_inputs(),
        t,
        std::move(At),
        std::move(Bt),
        std::move(Ct),
        std::move(Ht),
        Zt);
}
 
/**
 * Witness map for the R1CS-to-QAP reduction.
 *
 * The witness map takes zero knowledge into account when d1,d2,d3 are random.
 *
 * More precisely, compute the coefficients
 *     h_0,h_1,...,h_n
 * of the polynomial
 *     H(z) := (A(z)*B(z)-C(z))/Z(z)
 * where
 *   A(z) := A_0(z) + \sum_{k=1}^{m} w_k A_k(z) + d1 * Z(z)
 *   B(z) := B_0(z) + \sum_{k=1}^{m} w_k B_k(z) + d2 * Z(z)
 *   C(z) := C_0(z) + \sum_{k=1}^{m} w_k C_k(z) + d3 * Z(z)
 *   Z(z) := "vanishing polynomial of set S"
 * and
 *   m = number of variables of the QAP
 *   n = degree of the QAP
 *
 *
 * This is done as follows, where T is the coset gS of S, for g the
 * multiplicative generator of the field, (i.e. T={g*s | s \in S}):
 *  (1) compute evaluations of A,B,C on S = {sigma_1,...,sigma_n}
 *  (2) compute coefficients of A,B,C (iFFT)
 *  (3) compute evaluations of A,B,C on T (cosetFFT)
 *  (4) compute evaluation of H on T (in terms of evaluations of A, B, C)
 *  (5) compute coefficients of H (icosetFFT)
 *  (6) patch H to account for d1,d2,d3 (i.e., add coefficients of the
 * polynomial (A d2 + B d1 - d3) + d1*d2*Z )
 *
 * The code below is not as simple as the above high-level description due to
 * some reshuffling to save space.
 */
template<typename FieldT>
qap_witness<FieldT> r1cs_to_qap_witness_map(
    const r1cs_constraint_system<FieldT> &cs,
    const r1cs_primary_input<FieldT> &primary_input,
    const r1cs_auxiliary_input<FieldT> &auxiliary_input,
    const FieldT &d1,
    const FieldT &d2,
    const FieldT &d3,
    bool force_pow_2_domain)
{
    libff::enter_block("Call to r1cs_to_qap_witness_map");
 
    /* sanity check */
    assert(cs.is_satisfied(primary_input, auxiliary_input));
 
    const size_t min_n = cs.num_constraints() + cs.num_inputs() + 1;
    const size_t n = force_pow_2_domain ? 1 << libff::log2(min_n) : min_n;
    std::shared_ptr<libfqfft::evaluation_domain<FieldT>> domain =
        libfqfft::get_evaluation_domain<FieldT>(n);
 
    r1cs_variable_assignment<FieldT> full_variable_assignment = primary_input;
    full_variable_assignment.insert(
        full_variable_assignment.end(),
        auxiliary_input.begin(),
        auxiliary_input.end());
 
    libff::enter_block("Compute evaluation of polynomials A, B on set S");
    std::vector<FieldT> aA(domain->m, FieldT::zero()),
        aB(domain->m, FieldT::zero());
 
    /* account for the additional constraints input_i * 0 = 0 */
    for (size_t i = 0; i <= cs.num_inputs(); ++i) {
        aA[i + cs.num_constraints()] =
            (i > 0 ? full_variable_assignment[i - 1] : FieldT::one());
    }
    /* account for all other constraints */
    for (size_t i = 0; i < cs.num_constraints(); ++i) {
        aA[i] += cs.constraints[i].a.evaluate(full_variable_assignment);
        aB[i] += cs.constraints[i].b.evaluate(full_variable_assignment);
    }
    libff::leave_block("Compute evaluation of polynomials A, B on set S");
 
    libff::enter_block("Compute coefficients of polynomial A");
    domain->iFFT(aA);
    libff::leave_block("Compute coefficients of polynomial A");
 
    libff::enter_block("Compute coefficients of polynomial B");
    domain->iFFT(aB);
    libff::leave_block("Compute coefficients of polynomial B");
 
    libff::enter_block("Compute ZK-patch");
    std::vector<FieldT> coefficients_for_H(domain->m + 1, FieldT::zero());
#ifdef MULTICORE
#pragma omp parallel for
#endif
    /* add coefficients of the polynomial (d2*A + d1*B - d3) + d1*d2*Z */
    for (size_t i = 0; i < domain->m; ++i) {
        coefficients_for_H[i] = d2 * aA[i] + d1 * aB[i];
    }
    coefficients_for_H[0] -= d3;
    domain->add_poly_Z(d1 * d2, coefficients_for_H);
    libff::leave_block("Compute ZK-patch");
 
    libff::enter_block("Compute evaluation of polynomial A on set T");
    domain->cosetFFT(aA, FieldT::multiplicative_generator);
    libff::leave_block("Compute evaluation of polynomial A on set T");
 
    libff::enter_block("Compute evaluation of polynomial B on set T");
    domain->cosetFFT(aB, FieldT::multiplicative_generator);
    libff::leave_block("Compute evaluation of polynomial B on set T");
 
    libff::enter_block("Compute evaluation of polynomial H on set T");
    // can overwrite aA because it is not used later
    std::vector<FieldT> &H_tmp = aA;
#ifdef MULTICORE
#pragma omp parallel for
#endif
    for (size_t i = 0; i < domain->m; ++i) {
        H_tmp[i] = aA[i] * aB[i];
    }
    // destroy aB
    std::vector<FieldT>().swap(aB);
 
    libff::enter_block("Compute evaluation of polynomial C on set S");
    std::vector<FieldT> aC(domain->m, FieldT::zero());
    for (size_t i = 0; i < cs.num_constraints(); ++i) {
        aC[i] += cs.constraints[i].c.evaluate(full_variable_assignment);
    }
    libff::leave_block("Compute evaluation of polynomial C on set S");
 
    libff::enter_block("Compute coefficients of polynomial C");
    domain->iFFT(aC);
    libff::leave_block("Compute coefficients of polynomial C");
 
    libff::enter_block("Compute evaluation of polynomial C on set T");
    domain->cosetFFT(aC, FieldT::multiplicative_generator);
    libff::leave_block("Compute evaluation of polynomial C on set T");
 
#ifdef MULTICORE
#pragma omp parallel for
#endif
    for (size_t i = 0; i < domain->m; ++i) {
        H_tmp[i] = (H_tmp[i] - aC[i]);
    }
 
    libff::enter_block("Divide by Z on set T");
    domain->divide_by_Z_on_coset(H_tmp);
    libff::leave_block("Divide by Z on set T");
 
    libff::leave_block("Compute evaluation of polynomial H on set T");
 
    libff::enter_block("Compute coefficients of polynomial H");
    domain->icosetFFT(H_tmp, FieldT::multiplicative_generator);
    libff::leave_block("Compute coefficients of polynomial H");
 
    libff::enter_block("Compute sum of H and ZK-patch");
#ifdef MULTICORE
#pragma omp parallel for
#endif
    for (size_t i = 0; i < domain->m; ++i) {
        coefficients_for_H[i] += H_tmp[i];
    }
    libff::leave_block("Compute sum of H and ZK-patch");
 
    libff::leave_block("Call to r1cs_to_qap_witness_map");
 
    return qap_witness<FieldT>(
        cs.num_variables(),
        domain->m,
        cs.num_inputs(),
        d1,
        d2,
        d3,
        full_variable_assignment,
        std::move(coefficients_for_H));
}
 
} // namespace libsnark
 
#endif // R1CS_TO_QAP_TCC_