Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
274 lines (236 sloc) 11.2 KB
// This code is taken from https://github.com/matter-labs/Groth16BatchVerifier/blob/master/BatchedSnarkVerifier/contracts/BatchVerifier.sol
// Thanks Harry from ETHSNARKS for base code
pragma solidity ^0.5.11;
library BatchVerifier {
function GroupOrder ()
public pure returns (uint256)
{
return 21888242871839275222246405745257275088548364400416034343698204186575808495617;
}
function NegateY( uint256 Y )
internal pure returns (uint256)
{
uint q = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
return q - (Y % q);
}
function getProofEntropy(
uint256[] memory in_proof,
uint256[] memory proof_inputs,
uint proofNumber
)
internal pure returns (uint256)
{
// Truncate the least significant 3 bits from the 256bit entropy so it fits the scalar field
return uint256(
keccak256(
abi.encodePacked(
in_proof[proofNumber*8 + 0], in_proof[proofNumber*8 + 1], in_proof[proofNumber*8 + 2], in_proof[proofNumber*8 + 3],
in_proof[proofNumber*8 + 4], in_proof[proofNumber*8 + 5], in_proof[proofNumber*8 + 6], in_proof[proofNumber*8 + 7],
proof_inputs[proofNumber]
)
)
) >> 3;
}
function accumulate(
uint256[] memory in_proof,
uint256[] memory proof_inputs, // public inputs, length is num_inputs * num_proofs
uint256 num_proofs
) internal view returns (
bool success,
uint256[] memory proofsAandC,
uint256[] memory inputAccumulators
) {
uint256 q = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
uint256 numPublicInputs = proof_inputs.length / num_proofs;
uint256[] memory entropy = new uint256[](num_proofs);
inputAccumulators = new uint256[](numPublicInputs + 1);
for (uint256 proofNumber = 0; proofNumber < num_proofs; proofNumber++) {
if (proofNumber == 0) {
entropy[proofNumber] = 1;
} else {
// entropy[proofNumber] = uint256(blockhash(block.number - proofNumber)) % q;
// Safer entropy:
entropy[proofNumber] = getProofEntropy(in_proof, proof_inputs, proofNumber);
}
require(entropy[proofNumber] != 0, "Entropy should not be zero");
// here multiplication by 1 is implied
inputAccumulators[0] = addmod(inputAccumulators[0], entropy[proofNumber], q);
for (uint256 i = 0; i < numPublicInputs; i++) {
require(proof_inputs[proofNumber * numPublicInputs + i] < q, "INVALID_INPUT");
// accumulate the exponent with extra entropy mod q
inputAccumulators[i+1] = addmod(inputAccumulators[i+1], mulmod(entropy[proofNumber], proof_inputs[proofNumber * numPublicInputs + i], q), q);
}
// coefficient for +vk.alpha (mind +) is the same as inputAccumulator[0]
}
// inputs for scalar multiplication
uint256[3] memory mul_input;
// use scalar multiplications to get proof.A[i] * entropy[i]
proofsAandC = new uint256[](num_proofs*2 + 2);
proofsAandC[0] = in_proof[0];
proofsAandC[1] = in_proof[1];
for (uint256 proofNumber = 1; proofNumber < num_proofs; proofNumber++) {
require(entropy[proofNumber] < q, "INVALID_INPUT");
mul_input[0] = in_proof[proofNumber*8];
mul_input[1] = in_proof[proofNumber*8 + 1];
mul_input[2] = entropy[proofNumber];
assembly {
// ECMUL, output proofsA[i]
// success := staticcall(sub(gas, 2000), 7, mul_input, 0x60, add(add(proofsAandC, 0x20), mul(proofNumber, 0x40)), 0x40)
success := staticcall(sub(gas, 2000), 7, mul_input, 0x60, mul_input, 0x40)
}
if (!success) {
return (false, proofsAandC, inputAccumulators);
}
proofsAandC[proofNumber*2] = mul_input[0];
proofsAandC[proofNumber*2 + 1] = mul_input[1];
}
// use scalar multiplication and addition to get sum(proof.C[i] * entropy[i])
uint256[4] memory add_input;
add_input[0] = in_proof[6];
add_input[1] = in_proof[7];
for (uint256 proofNumber = 1; proofNumber < num_proofs; proofNumber++) {
mul_input[0] = in_proof[proofNumber*8 + 6];
mul_input[1] = in_proof[proofNumber*8 + 7];
mul_input[2] = entropy[proofNumber];
assembly {
// ECMUL, output proofsA
success := staticcall(sub(gas, 2000), 7, mul_input, 0x60, add(add_input, 0x40), 0x40)
}
if (!success) {
return (false, proofsAandC, inputAccumulators);
}
assembly {
// ECADD from two elements that are in add_input and output into first two elements of add_input
success := staticcall(sub(gas, 2000), 6, add_input, 0x80, add_input, 0x40)
}
if (!success) {
return (false, proofsAandC, inputAccumulators);
}
}
proofsAandC[num_proofs*2] = add_input[0];
proofsAandC[num_proofs*2 + 1] = add_input[1];
}
function prepareBatches(
uint256[14] memory in_vk,
uint256[4] memory vk_gammaABC,
uint256[] memory inputAccumulators
) internal view returns (
bool success,
uint256[4] memory finalVksAlphaX
) {
// Compute the linear combination vk_x using accumulator
// First two fields are used as the sum and are initially zero
uint256[4] memory add_input;
uint256[3] memory mul_input;
// Performs a sum(gammaABC[i] * inputAccumulator[i])
for (uint256 i = 0; i < inputAccumulators.length; i++) {
mul_input[0] = vk_gammaABC[2*i];
mul_input[1] = vk_gammaABC[2*i + 1];
mul_input[2] = inputAccumulators[i];
assembly {
// ECMUL, output to the last 2 elements of `add_input`
success := staticcall(sub(gas, 2000), 7, mul_input, 0x60, add(add_input, 0x40), 0x40)
}
if (!success) {
return (false, finalVksAlphaX);
}
assembly {
// ECADD from four elements that are in add_input and output into first two elements of add_input
success := staticcall(sub(gas, 2000), 6, add_input, 0x80, add_input, 0x40)
}
if (!success) {
return (false, finalVksAlphaX);
}
}
finalVksAlphaX[2] = add_input[0];
finalVksAlphaX[3] = add_input[1];
// add one extra memory slot for scalar for multiplication usage
uint256[3] memory finalVKalpha;
finalVKalpha[0] = in_vk[0];
finalVKalpha[1] = in_vk[1];
finalVKalpha[2] = inputAccumulators[0];
assembly {
// ECMUL, output to first 2 elements of finalVKalpha
success := staticcall(sub(gas, 2000), 7, finalVKalpha, 0x60, finalVKalpha, 0x40)
}
if (!success) {
return (false, finalVksAlphaX);
}
finalVksAlphaX[0] = finalVKalpha[0];
finalVksAlphaX[1] = finalVKalpha[1];
}
// original equation
// e(proof.A, proof.B)*e(-vk.alpha, vk.beta)*e(-vk_x, vk.gamma)*e(-proof.C, vk.delta) == 1
// accumulation of inputs
// gammaABC[0] + sum[ gammaABC[i+1]^proof_inputs[i] ]
function BatchVerify (
uint256[14] memory in_vk, // verifying key is always constant number of elements
uint256[4] memory vk_gammaABC, // variable length, depends on number of inputs
uint256[] memory in_proof, // proof itself, length is 8 * num_proofs
uint256[] memory proof_inputs, // public inputs, length is num_inputs * num_proofs
uint256 num_proofs
)
internal
view
returns (bool success)
{
require(in_proof.length == num_proofs * 8, "Invalid proofs length for a batch");
require(proof_inputs.length % num_proofs == 0, "Invalid inputs length for a batch");
require(((vk_gammaABC.length / 2) - 1) == proof_inputs.length / num_proofs, "Invalid verification key");
// strategy is to accumulate entropy separately for some proof elements
// (accumulate only for G1, can't in G2) of the pairing equation, as well as input verification key,
// postpone scalar multiplication as much as possible and check only one equation
// by using 3 + num_proofs pairings only plus 2*num_proofs + (num_inputs+1) + 1 scalar multiplications compared to naive
// 4*num_proofs pairings and num_proofs*(num_inputs+1) scalar multiplications
bool valid;
uint256[] memory proofsAandC;
uint256[] memory inputAccumulators;
(valid, proofsAandC, inputAccumulators) = accumulate(in_proof, proof_inputs, num_proofs);
if (!valid) {
return false;
}
uint256[4] memory finalVksAlphaX;
(valid, finalVksAlphaX) = prepareBatches(in_vk, vk_gammaABC, inputAccumulators);
if (!valid) {
return false;
}
uint256[] memory inputs = new uint256[](6*num_proofs + 18);
// first num_proofs pairings e(ProofA, ProofB)
for (uint256 proofNumber = 0; proofNumber < num_proofs; proofNumber++) {
inputs[proofNumber*6] = proofsAandC[proofNumber*2];
inputs[proofNumber*6 + 1] = proofsAandC[proofNumber*2 + 1];
inputs[proofNumber*6 + 2] = in_proof[proofNumber*8 + 2];
inputs[proofNumber*6 + 3] = in_proof[proofNumber*8 + 3];
inputs[proofNumber*6 + 4] = in_proof[proofNumber*8 + 4];
inputs[proofNumber*6 + 5] = in_proof[proofNumber*8 + 5];
}
// second pairing e(-finalVKaplha, vk.beta)
inputs[num_proofs*6] = finalVksAlphaX[0];
inputs[num_proofs*6 + 1] = NegateY(finalVksAlphaX[1]);
inputs[num_proofs*6 + 2] = in_vk[2];
inputs[num_proofs*6 + 3] = in_vk[3];
inputs[num_proofs*6 + 4] = in_vk[4];
inputs[num_proofs*6 + 5] = in_vk[5];
// third pairing e(-finalVKx, vk.gamma)
inputs[num_proofs*6 + 6] = finalVksAlphaX[2];
inputs[num_proofs*6 + 7] = NegateY(finalVksAlphaX[3]);
inputs[num_proofs*6 + 8] = in_vk[6];
inputs[num_proofs*6 + 9] = in_vk[7];
inputs[num_proofs*6 + 10] = in_vk[8];
inputs[num_proofs*6 + 11] = in_vk[9];
// fourth pairing e(-proof.C, finalVKdelta)
inputs[num_proofs*6 + 12] = proofsAandC[num_proofs*2];
inputs[num_proofs*6 + 13] = NegateY(proofsAandC[num_proofs*2 + 1]);
inputs[num_proofs*6 + 14] = in_vk[10];
inputs[num_proofs*6 + 15] = in_vk[11];
inputs[num_proofs*6 + 16] = in_vk[12];
inputs[num_proofs*6 + 17] = in_vk[13];
uint256 inputsLength = inputs.length * 32;
uint[1] memory out;
require(inputsLength % 192 == 0, "Inputs length should be multiple of 192 bytes");
assembly {
success := staticcall(sub(gas, 2000), 8, add(inputs, 0x20), inputsLength, out, 0x20)
}
return success && out[0] == 1;
}
}
You can’t perform that action at this time.