zk/include/nil/crypto3/zk/snark/systems/ppzksnark/r1cs_gg_ppzksnark/verifier.hpp

Go to the documentation of this file.

//---------------------------------------------------------------------------//
// Copyright (c) 2018-2021 Mikhail Komarov <nemo@nil.foundation>
// Copyright (c) 2020-2021 Nikita Kaskov <nbering@nil.foundation>
//
// MIT License
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//---------------------------------------------------------------------------//
// @file Declaration of interfaces for a ppzkSNARK for BACS.
//
// This includes:
// - class for proving key
// - class for verification key
// - class for processed verification key
// - class for key pair (proving key & verification key)
// - class for proof
// - generator algorithm
// - prover algorithm
// - verifier algorithm (with strong or weak input consistency)
// - online verifier algorithm (with strong or weak input consistency)
//
// The implementation is a straightforward combination of:
// (1) a BACS-to-R1CS reduction, and
// (2) a ppzkSNARK for R1CS.
//
//
// Acronyms:
//
// - BACS = "Bilinear Arithmetic Circuit Satisfiability"
// - R1CS = "Rank-1 Constraint System"
// - ppzkSNARK = "PreProcessing Zero-Knowledge Succinct Non-interactive ARgument of Knowledge"
//---------------------------------------------------------------------------//
 
#ifndef CRYPTO3_ZK_R1CS_GG_PPZKSNARK_BASIC_VERIFIER_HPP
#define CRYPTO3_ZK_R1CS_GG_PPZKSNARK_BASIC_VERIFIER_HPP
 
#include <nil/crypto3/algebra/algorithms/pair.hpp>
 
#include <nil/crypto3/zk/snark/accumulation_vector.hpp>
#include <nil/crypto3/zk/snark/commitments/knowledge_commitment.hpp>
#include <nil/crypto3/zk/snark/relations/constraint_satisfaction_problems/r1cs.hpp>
#include <nil/crypto3/zk/snark/reductions/r1cs_to_qap.hpp>
#include <nil/crypto3/zk/snark/systems/ppzksnark/r1cs_gg_ppzksnark/detail/basic_policy.hpp>
 
namespace nil {
    namespace crypto3 {
        namespace zk {
            namespace snark {
 
                using namespace algebra;
 
                template<typename CurveType, ProvingMode Mode = ProvingMode::Basic>
                class r1cs_gg_ppzksnark_process_verification_key;
 
                template<typename CurveType, ProvingMode Mode = ProvingMode::Basic>
                class r1cs_gg_ppzksnark_verifier_weak_input_consistency;
 
                template<typename CurveType, ProvingMode Mode = ProvingMode::Basic>
                class r1cs_gg_ppzksnark_verifier_strong_input_consistency;
 
                template<typename CurveType>
                class r1cs_gg_ppzksnark_process_verification_key<CurveType, ProvingMode::Basic> {
                    typedef detail::r1cs_gg_ppzksnark_basic_policy<CurveType, ProvingMode::Basic> policy_type;
 
                public:
                    typedef typename policy_type::verification_key_type verification_key_type;
                    typedef typename policy_type::processed_verification_key_type processed_verification_key_type;
 
                    static inline processed_verification_key_type
                        process(const verification_key_type &verification_key) {
 
                        processed_verification_key_type processed_verification_key;
                        processed_verification_key.vk_alpha_g1_beta_g2 = verification_key.alpha_g1_beta_g2;
                        processed_verification_key.vk_gamma_g2_precomp =
                            precompute_g2<CurveType>(verification_key.gamma_g2);
                        processed_verification_key.vk_delta_g2_precomp =
                            precompute_g2<CurveType>(verification_key.delta_g2);
                        processed_verification_key.gamma_ABC_g1 = verification_key.gamma_ABC_g1;
 
                        return processed_verification_key;
                    }
                };
 
                template<typename CurveType>
                class r1cs_gg_ppzksnark_verifier_weak_input_consistency<CurveType, ProvingMode::Basic> {
                    typedef detail::r1cs_gg_ppzksnark_basic_policy<CurveType, ProvingMode::Basic> policy_type;
 
                    typedef typename CurveType::scalar_field_type scalar_field_type;
                    typedef typename CurveType::template g1_type<> g1_type;
                    typedef typename CurveType::gt_type gt_type;
                    typedef typename pairing::pairing_policy<CurveType>::g1_precomputed_type g1_precomputed_type;
                    typedef typename pairing::pairing_policy<CurveType>::g2_precomputed_type g2_precomputed_type;
 
                public:
                    typedef typename policy_type::primary_input_type primary_input_type;
                    typedef typename policy_type::verification_key_type verification_key_type;
                    typedef typename policy_type::processed_verification_key_type processed_verification_key_type;
                    typedef typename policy_type::proof_type proof_type;
 
                    static inline bool process(const verification_key_type &verification_key,
                                               const primary_input_type &primary_input,
                                               const proof_type &proof) {
                        return process(r1cs_gg_ppzksnark_process_verification_key<CurveType>::process(verification_key),
                                       primary_input, proof);
                    }
 
                    static inline bool process(const processed_verification_key_type &processed_verification_key,
                                               const primary_input_type &primary_input,
                                               const proof_type &proof) {
 
                        assert(processed_verification_key.gamma_ABC_g1.domain_size() >= primary_input.size());
 
                        const accumulation_vector<g1_type> accumulated_IC =
                            processed_verification_key.gamma_ABC_g1.accumulate_chunk(primary_input.begin(),
                                                                                     primary_input.end(), 0);
 
                        const typename g1_type::value_type &acc = accumulated_IC.first;
 
                        bool result = true;
 
                        if (!proof.is_well_formed()) {
                            result = false;
                        }
 
                        const g1_precomputed_type proof_g_A_precomp = precompute_g1<CurveType>(proof.g_A);
                        const g2_precomputed_type proof_g_B_precomp = precompute_g2<CurveType>(proof.g_B);
                        const g1_precomputed_type proof_g_C_precomp = precompute_g1<CurveType>(proof.g_C);
                        const g1_precomputed_type acc_precomp = precompute_g1<CurveType>(acc);
 
                        const typename gt_type::value_type QAP1 =
                            miller_loop<CurveType>(proof_g_A_precomp, proof_g_B_precomp);
                        const typename gt_type::value_type QAP2 = double_miller_loop<CurveType>(
                            acc_precomp, processed_verification_key.vk_gamma_g2_precomp, proof_g_C_precomp,
                            processed_verification_key.vk_delta_g2_precomp);
                        const typename gt_type::value_type QAP =
                            final_exponentiation<CurveType>(QAP1 * QAP2.unitary_inversed());
 
                        if (QAP != processed_verification_key.vk_alpha_g1_beta_g2) {
                            result = false;
                        }
 
                        return result;
                    }
                };
 
                template<typename CurveType>
                class r1cs_gg_ppzksnark_verifier_strong_input_consistency<CurveType, ProvingMode::Basic> {
                    typedef detail::r1cs_gg_ppzksnark_basic_policy<CurveType, ProvingMode::Basic> policy_type;
 
                public:
                    typedef typename policy_type::primary_input_type primary_input_type;
                    typedef typename policy_type::verification_key_type verification_key_type;
                    typedef typename policy_type::processed_verification_key_type processed_verification_key_type;
                    typedef typename policy_type::proof_type proof_type;
 
                    static inline bool process(const verification_key_type &verification_key,
                                               const primary_input_type &primary_input,
                                               const proof_type &proof) {
 
                        return process(r1cs_gg_ppzksnark_process_verification_key<CurveType>::process(verification_key),
                                       primary_input, proof);
                    }
 
                    static inline bool process(const processed_verification_key_type &processed_verification_key,
                                               const primary_input_type &primary_input,
                                               const proof_type &proof) {
                        bool result = true;
 
                        if (processed_verification_key.gamma_ABC_g1.domain_size() != primary_input.size()) {
                            result = false;
                        } else {
                            result = r1cs_gg_ppzksnark_verifier_weak_input_consistency<CurveType>::process(
                                processed_verification_key, primary_input, proof);
                        }
 
                        return result;
                    }
                };
 
                // /**
                //  *
                //  * A verifier algorithm for the R1CS GG-ppzkSNARK that:
                //  * (1) accepts a non-processed verification key,
                //  * (2) has weak input consistency, and
                //  * (3) uses affine coordinates for elliptic-curve computations.
                //  */
                // template<typename CurveType>
                // class r1cs_gg_ppzksnark_affine_verifier_weak_input_consistency {
                //     typedef detail::r1cs_gg_ppzksnark_basic_policy<CurveType, ProvingMode::Basic> policy_type;
 
                //     typedef typename CurveType::scalar_field_type scalar_field_type;
                //     typedef typename CurveType::template g1_type<> g1_type;
                //     typedef typename CurveType::gt_type gt_type;
                //     typedef typename pairing::pairing_policy<CurveType>::affine_ate_g1_precomp affine_ate_g1_precomp;
                //     typedef typename pairing::pairing_policy<CurveType>::affine_ate_g2_precomp affine_ate_g2_precomp;
 
                // public:
                //     typedef typename policy_type::primary_input_type primary_input_type;
 
                //     typedef typename policy_type::verification_key_type verification_key_type;
                //     typedef typename policy_type::processed_verification_key_type processed_verification_key_type;
 
                //     typedef typename policy_type::proof_type proof_type;
 
                //     static inline bool process(const verification_key_type &verification_key,
                //                                const primary_input_type &primary_input,
                //                                const proof_type &proof) {
 
                //         BOOST_ASSERT(verification_key.gamma_ABC_g1.domain_size() >= primary_input.size());
 
                //         affine_ate_g2_precomp pvk_vk_gamma_g2_precomp =
                //             affine_ate_precompute_g2<CurveType>(verification_key.gamma_g2);
                //         affine_ate_g2_precomp pvk_vk_delta_g2_precomp =
                //             affine_ate_precompute_g2<CurveType>(verification_key.delta_g2);
 
                //         const accumulation_vector<g1_type> accumulated_IC =
                //             verification_key.gamma_ABC_g1.accumulate_chunk(primary_input.begin(),
                //             primary_input.end(),
                //                                                            0);
                //         const typename g1_type::value_type &acc = accumulated_IC.first;
 
                //         bool result = true;
 
                //         if (!proof.is_well_formed()) {
                //             result = false;
                //         }
 
                //         const affine_ate_g1_precomp proof_g_A_precomp =
                //             affine_ate_precompute_g1<CurveType>(proof.g_A);
                //         const affine_ate_g2_precomp proof_g_B_precomp =
                //             affine_ate_precompute_g2<CurveType>(proof.g_B);
                //         const affine_ate_g1_precomp proof_g_C_precomp =
                //             affine_ate_precompute_g1<CurveType>(proof.g_C);
                //         const affine_ate_g1_precomp acc_precomp = affine_ate_precompute_g1<CurveType>(acc);
 
                //         const typename fqk_type::value_type QAP_miller =
                //             affine_ate_e_times_e_over_e_miller_loop<CurveType>(
                //                 acc_precomp, pvk_vk_gamma_g2_precomp, proof_g_C_precomp, pvk_vk_delta_g2_precomp,
                //                 proof_g_A_precomp, proof_g_B_precomp);
                //         const typename gt_type::value_type QAP =
                //             final_exponentiation<CurveType>(QAP_miller.unitary_inversed());
 
                //         if (QAP != verification_key.alpha_g1_beta_g2) {
                //             result = false;
                //         }
                //         return result;
                //     }
                // };
            }    // namespace snark
        }        // namespace zk
    }            // namespace crypto3
}    // namespace nil
 
#endif    // CRYPTO3_ZK_R1CS_GG_PPZKSNARK_BASIC_VERIFIER_HPP