snarkjs/src/prover.js

/*
    Copyright 2018 0kims association.

    This file is part of snarkjs.

    snarkjs is a free software: you can redistribute it and/or
    modify it under the terms of the GNU General Public License as published by the
    Free Software Foundation, either version 3 of the License, or (at your option)
    any later version.

    snarkjs is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
    more details.

    You should have received a copy of the GNU General Public License along with
    snarkjs. If not, see <https://www.gnu.org/licenses/>.
*/

const BN128 = require("./bn128.js");
const PolField = require("./polfield.js");
const ZqField = require("./zqfield.js");

const bn128 = new BN128();
const PolF = new PolField(new ZqField(bn128.r));
const G1 = bn128.G1;
const G2 = bn128.G2;

module.exports = function genProof(vk_proof, witness) {

    const proof = {};


    const d1 = PolF.F.random();
    const d2 = PolF.F.random();
    const d3 = PolF.F.random();

    proof.pi_a = G1.zero;
    proof.pi_ap = G1.zero;
    proof.pi_b = G2.zero;
    proof.pi_bp = G1.zero;
    proof.pi_c = G1.zero;
    proof.pi_cp = G1.zero;
    proof.pi_kp = G1.zero;
    proof.pi_h = G1.zero;


    // Skip public entries and the "1" signal that are forced by the verifier
    for (let s= vk_proof.nPublic+1; s< vk_proof.nVars; s++) {

        // pi_a  = pi_a  + A[s]  * witness[s];
        proof.pi_a  = G1.add( proof.pi_a, G1.mulScalar( vk_proof.A[s], witness[s]));

        // pi_ap = pi_ap + Ap[s] * witness[s];
        proof.pi_ap = G1.add( proof.pi_ap, G1.mulScalar( vk_proof.Ap[s], witness[s]));
    }

    for (let s= 0; s< vk_proof.nVars; s++) {
        // pi_a  = pi_a  + A[s]  * witness[s];
        proof.pi_b  = G2.add( proof.pi_b, G2.mulScalar( vk_proof.B[s], witness[s]));

        // pi_ap = pi_ap + Ap[s] * witness[s];
        proof.pi_bp = G1.add( proof.pi_bp, G1.mulScalar( vk_proof.Bp[s], witness[s]));

        // pi_a  = pi_a  + A[s]  * witness[s];
        proof.pi_c  = G1.add( proof.pi_c, G1.mulScalar( vk_proof.C[s], witness[s]));

        // pi_ap = pi_ap + Ap[s] * witness[s];
        proof.pi_cp = G1.add( proof.pi_cp, G1.mulScalar( vk_proof.Cp[s], witness[s]));

        // pi_ap = pi_ap + Ap[s] * witness[s];
        proof.pi_kp = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[s], witness[s]));
    }

    proof.pi_a  = G1.add( proof.pi_a, G1.mulScalar( vk_proof.A[vk_proof.nVars], d1));
    proof.pi_ap  = G1.add( proof.pi_ap, G1.mulScalar( vk_proof.Ap[vk_proof.nVars], d1));

    proof.pi_b  = G2.add( proof.pi_b, G2.mulScalar( vk_proof.B[vk_proof.nVars], d2));
    proof.pi_bp  = G1.add( proof.pi_bp, G1.mulScalar( vk_proof.Bp[vk_proof.nVars], d2));

    proof.pi_c  = G1.add( proof.pi_c, G1.mulScalar( vk_proof.C[vk_proof.nVars], d3));
    proof.pi_cp  = G1.add( proof.pi_cp, G1.mulScalar( vk_proof.Cp[vk_proof.nVars], d3));

    proof.pi_kp  = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars  ], d1));
    proof.pi_kp  = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars+1], d2));
    proof.pi_kp  = G1.add( proof.pi_kp, G1.mulScalar( vk_proof.Kp[vk_proof.nVars+2], d3));

/*
    let polA = [];
    let polB = [];
    let polC = [];

    for (let s= 0; s< vk_proof.nVars; s++) {
        polA = PolF.add(
            polA,
            PolF.mul(
                vk_proof.polsA[s],
                [witness[s]] ));

        polB = PolF.add(
            polB,
            PolF.mul(
                vk_proof.polsB[s],
                [witness[s]] ));

        polC = PolF.add(
            polC,
            PolF.mul(
                vk_proof.polsC[s],
                [witness[s]] ));
    }


    let polFull = PolF.sub(PolF.mul( polA, polB), polC);

    const h = PolF.div(polFull, vk_proof.polZ );
*/

    const h = calculateH(vk_proof, witness, d1, d2, d3);

//    console.log(h.length + "/" + vk_proof.hExps.length);

    for (let i = 0; i < h.length; i++) {
        proof.pi_h = G1.add( proof.pi_h, G1.mulScalar( vk_proof.hExps[i], h[i]));
    }

    proof.pi_a = G1.affine(proof.pi_a);
    proof.pi_b = G2.affine(proof.pi_b);
    proof.pi_c = G1.affine(proof.pi_c);
    proof.pi_ap = G1.affine(proof.pi_ap);
    proof.pi_bp = G1.affine(proof.pi_bp);
    proof.pi_cp = G1.affine(proof.pi_cp);
    proof.pi_kp = G1.affine(proof.pi_kp);
    proof.pi_h = G1.affine(proof.pi_h);

//    proof.h=h;

    const publicSignals = witness.slice(1, vk_proof.nPublic+1);

    return {proof, publicSignals};
};


function calculateH(vk_proof, witness, d1, d2, d3) {

    const F = PolF.F;
    const m = vk_proof.domainSize;
    const polA_T = new Array(m).fill(PolF.F.zero);
    const polB_T = new Array(m).fill(PolF.F.zero);
    const polC_T = new Array(m).fill(PolF.F.zero);

    for (let s=0; s<vk_proof.nVars; s++) {
        for (let c in vk_proof.polsA[s]) {
            polA_T[c] = F.add(polA_T[c], F.mul(witness[s], vk_proof.polsA[s][c]));
        }
        for (let c in vk_proof.polsB[s]) {
            polB_T[c] = F.add(polB_T[c], F.mul(witness[s], vk_proof.polsB[s][c]));
        }
        for (let c in vk_proof.polsC[s]) {
            polC_T[c] = F.add(polC_T[c], F.mul(witness[s], vk_proof.polsC[s][c]));
        }
    }

    const polA_S = PolF.ifft(polA_T);
    const polB_S = PolF.ifft(polB_T);

    const polAB_S = PolF.mul(polA_S, polB_S);

    const polC_S = PolF.ifft(polC_T);

    const polABC_S = PolF.sub(polAB_S, polC_S);

    const polZ_S = new Array(m+1).fill(F.zero);
    polZ_S[m] = F.one;
    polZ_S[0] = F.neg(F.one);

    let H_S = PolF.div(polABC_S, polZ_S);
/*
    const H2S = PolF.mul(H_S, polZ_S);

    if (PolF.equals(H2S, polABC_S)) {
        console.log("Is Divisible!");
    } else {
        console.log("ERROR: Not divisible!");
    }
*/

    /* add coefficients of the polynomial (d2*A + d1*B - d3) + d1*d2*Z */

    H_S = PolF.extend(H_S, m+1);

    for (let i=0; i<m; i++) {
        const d2A = PolF.F.mul(d2, polA_S[i]);
        const d1B = PolF.F.mul(d1, polB_S[i]);
        H_S[i] = PolF.F.add(H_S[i], PolF.F.add(d2A, d1B));
    }

    H_S[0] = PolF.F.sub(H_S[0], d3);

    // Z = x^m -1
    const d1d2 = PolF.F.mul(d1, d2);
    H_S[m] = PolF.F.add(H_S[m], d1d2);
    H_S[0] = PolF.F.sub(H_S[0], d1d2);

    H_S = PolF.reduce(PolF.affine(H_S));

    return H_S;
}