1/*
  2    Sonobe's Nova + CycleFold decider verifier.
  3    Joint effort by 0xPARC & PSE.
  4
  5    More details at https://github.com/privacy-scaling-explorations/sonobe
  6    Usage and design documentation at https://privacy-scaling-explorations.github.io/sonobe-docs/
  7
  8    Uses the https://github.com/iden3/snarkjs/blob/master/templates/verifier_groth16.sol.ejs
  9    Groth16 verifier implementation and a KZG10 Solidity template adapted from
 10    https://github.com/weijiekoh/libkzg.
 11    Additionally we implement the NovaDecider contract, which combines the
 12    Groth16 and KZG10 verifiers to verify the zkSNARK proofs coming from
 13    Nova+CycleFold folding.
 14*/
 15
 16
 17/* =============================== */
 18/* KZG10 verifier methods */
 19{{ kzg10_verifier }}
 20
 21/* =============================== */
 22/* Groth16 verifier methods */
 23{{ groth16_verifier }}
 24
 25
 26/* =============================== */
 27/* Nova+CycleFold Decider verifier */
 28/**
 29 * @notice  Computes the decomposition of a `uint256` into num_limbs limbs of bits_per_limb bits each.
 30 * @dev     Compatible with sonobe::folding-schemes::folding::circuits::nonnative::nonnative_field_to_field_elements.
 31 */
 32library LimbsDecomposition {
 33    function decompose(uint256 x) internal pure returns (uint256[{{num_limbs}}] memory) {
 34        uint256[{{num_limbs}}] memory limbs;
 35        for (uint8 i = 0; i < {{num_limbs}}; i++) {
 36            limbs[i] = (x >> ({{bits_per_limb}} * i)) & ((1 << {{bits_per_limb}}) - 1);
 37        }
 38        return limbs;
 39    }
 40}
 41
 42/**
 43 * @author  PSE & 0xPARC
 44 * @title   NovaDecider contract, for verifying Nova IVC SNARK proofs.
 45 * @dev     This is an askama template which, when templated, features a Groth16 and KZG10 verifiers from which this contract inherits.
 46 */
 47contract NovaDecider is Groth16Verifier, KZG10Verifier {
 48    /**
 49     * @notice  Computes the linear combination of a and b with r as the coefficient.
 50     * @dev     All ops are done mod the BN254 scalar field prime
 51     */
 52    function rlc(uint256 a, uint256 r, uint256 b) internal pure returns (uint256 result) {
 53        assembly {
 54            result := addmod(a, mulmod(r, b, BN254_SCALAR_FIELD), BN254_SCALAR_FIELD)
 55        }
 56    }
 57
 58    /**
 59     * @notice  Verifies a nova cyclefold proof consisting of two KZG proofs and of a groth16 proof.
 60     * @dev     The selector of this function is "dynamic", since it depends on `z_len`.
 61     */
 62    function verifyNovaProof(
 63        // inputs are grouped to prevent errors due stack too deep
 64        uint256[{{ 1 + z_len * 2 }}] calldata i_z0_zi, // [i, z0, zi] where |z0| == |zi|
 65        uint256[4] calldata U_i_cmW_U_i_cmE, // [U_i_cmW[2], U_i_cmE[2]]
 66        uint256[3] calldata U_i_u_u_i_u_r, // [U_i_u, u_i_u, r]
 67        uint256[4] calldata U_i_x_u_i_cmW, // [U_i_x[2], u_i_cmW[2]]
 68        uint256[4] calldata u_i_x_cmT, // [u_i_x[2], cmT[2]]
 69        uint256[2] calldata pA, // groth16 
 70        uint256[2][2] calldata pB, // groth16
 71        uint256[2] calldata pC, // groth16
 72        uint256[4] calldata challenge_W_challenge_E_kzg_evals, // [challenge_W, challenge_E, eval_W, eval_E]
 73        uint256[2][2] calldata kzg_proof // [proof_W, proof_E]
 74    ) public view returns (bool) {
 75
 76        require(i_z0_zi[0] >= 2, "Folding: the number of folded steps should be at least 2");
 77
 78        // from gamma_abc_len, we subtract 1. 
 79        uint256[{{ public_inputs_len - 1 }}] memory public_inputs; 
 80
 81        public_inputs[0] = {{pp_hash}};
 82        public_inputs[1] = i_z0_zi[0];
 83
 84        for (uint i = 0; i < {{ z_len * 2 }}; i++) {
 85            public_inputs[2 + i] = i_z0_zi[1 + i];
 86        }
 87
 88        {
 89            // U_i.u + r * u_i.u
 90            uint256 u = rlc(U_i_u_u_i_u_r[0], U_i_u_u_i_u_r[2], U_i_u_u_i_u_r[1]);
 91            // U_i.x + r * u_i.x
 92            uint256 x0 = rlc(U_i_x_u_i_cmW[0], U_i_u_u_i_u_r[2], u_i_x_cmT[0]);
 93            uint256 x1 = rlc(U_i_x_u_i_cmW[1], U_i_u_u_i_u_r[2], u_i_x_cmT[1]);
 94
 95            public_inputs[{{ z_len * 2 + 2 }}] = u;
 96            public_inputs[{{ z_len * 2 + 3 }}] = x0;
 97            public_inputs[{{ z_len * 2 + 4 }}] = x1;
 98        }
 99
100        {
101            // U_i.cmE + r * u_i.cmT
102            uint256[2] memory mulScalarPoint = super.mulScalar([u_i_x_cmT[2], u_i_x_cmT[3]], U_i_u_u_i_u_r[2]);
103            uint256[2] memory cmE = super.add([U_i_cmW_U_i_cmE[2], U_i_cmW_U_i_cmE[3]], mulScalarPoint);
104
105            {
106                uint256[{{num_limbs}}] memory cmE_x_limbs = LimbsDecomposition.decompose(cmE[0]);
107                uint256[{{num_limbs}}] memory cmE_y_limbs = LimbsDecomposition.decompose(cmE[1]);
108            
109                for (uint8 k = 0; k < {{num_limbs}}; k++) {
110                    public_inputs[{{ z_len * 2 + 5 }} + k] = cmE_x_limbs[k];
111                    public_inputs[{{ z_len * 2 + 5 + num_limbs }} + k] = cmE_y_limbs[k];
112                }
113            }
114
115            require(this.check(cmE, kzg_proof[1], challenge_W_challenge_E_kzg_evals[1], challenge_W_challenge_E_kzg_evals[3]), "KZG: verifying proof for challenge E failed");
116        }
117
118        {
119            // U_i.cmW + r * u_i.cmW
120            uint256[2] memory mulScalarPoint = super.mulScalar([U_i_x_u_i_cmW[2], U_i_x_u_i_cmW[3]], U_i_u_u_i_u_r[2]);
121            uint256[2] memory cmW = super.add([U_i_cmW_U_i_cmE[0], U_i_cmW_U_i_cmE[1]], mulScalarPoint);
122        
123            {
124                uint256[{{num_limbs}}] memory cmW_x_limbs = LimbsDecomposition.decompose(cmW[0]);
125                uint256[{{num_limbs}}] memory cmW_y_limbs = LimbsDecomposition.decompose(cmW[1]);
126        
127                for (uint8 k = 0; k < {{num_limbs}}; k++) {
128                    public_inputs[{{ z_len * 2 + 5 + num_limbs * 2 }} + k] = cmW_x_limbs[k];
129                    public_inputs[{{ z_len * 2 + 5 + num_limbs * 3 }} + k] = cmW_y_limbs[k];
130                }
131            }
132        
133            require(this.check(cmW, kzg_proof[0], challenge_W_challenge_E_kzg_evals[0], challenge_W_challenge_E_kzg_evals[2]), "KZG: verifying proof for challenge W failed");
134        }
135
136        {
137            // add challenges
138            public_inputs[{{ z_len * 2 + 5 + num_limbs * 4 }}] = challenge_W_challenge_E_kzg_evals[0];
139            public_inputs[{{ z_len * 2 + 5 + num_limbs * 4 + 1 }}] = challenge_W_challenge_E_kzg_evals[1];
140            public_inputs[{{ z_len * 2 + 5 + num_limbs * 4 + 2 }}] = challenge_W_challenge_E_kzg_evals[2];
141            public_inputs[{{ z_len * 2 + 5 + num_limbs * 4 + 3 }}] = challenge_W_challenge_E_kzg_evals[3];
142        
143            uint256[{{num_limbs}}] memory cmT_x_limbs;
144            uint256[{{num_limbs}}] memory cmT_y_limbs;
145        
146            cmT_x_limbs = LimbsDecomposition.decompose(u_i_x_cmT[2]);
147            cmT_y_limbs = LimbsDecomposition.decompose(u_i_x_cmT[3]);
148        
149            for (uint8 k = 0; k < {{num_limbs}}; k++) {
150                public_inputs[{{ z_len * 2 + 5 + num_limbs * 4 }} + 4 + k] = cmT_x_limbs[k]; 
151                public_inputs[{{ z_len * 2 + 5 + num_limbs * 5}} + 4 + k] = cmT_y_limbs[k];
152            }
153        
154            // last element of the groth16 proof's public inputs is `r`
155            public_inputs[{{ public_inputs_len - 2 }}] = U_i_u_u_i_u_r[2];
156            
157            bool success_g16 = this.verifyProof(pA, pB, pC, public_inputs);
158            require(success_g16 == true, "Groth16: verifying proof failed");
159        }
160
161        return(true);
162    }
163}