// SPDX-License-Identifier: MIT pragma solidity ^0.8.0; /// @title Groth16 verifier template. /// @author Remco Bloemen /// @notice Supports verifying Groth16 proofs. Proofs can be in uncompressed /// (256 bytes) and compressed (128 bytes) format. A view function is provided /// to compress proofs. /// @notice See for further explanation. contract Verifier { /// Some of the provided public input values are larger than the field modulus. /// @dev Public input elements are not automatically reduced, as this is can be /// a dangerous source of bugs. error PublicInputNotInField(); /// The proof is invalid. /// @dev This can mean that provided Groth16 proof points are not on their /// curves, that pairing equation fails, or that the proof is not for the /// provided public input. error ProofInvalid(); // Addresses of precompiles uint256 constant PRECOMPILE_MODEXP = 0x05; uint256 constant PRECOMPILE_ADD = 0x06; uint256 constant PRECOMPILE_MUL = 0x07; uint256 constant PRECOMPILE_VERIFY = 0x08; // Base field Fp order P and scalar field Fr order R. // For BN254 these are computed as follows: // t = 4965661367192848881 // P = 36⋅t⁴ + 36⋅t³ + 24⋅t² + 6⋅t + 1 // R = 36⋅t⁴ + 36⋅t³ + 18⋅t² + 6⋅t + 1 uint256 constant P = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47; uint256 constant R = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001; // Extension field Fp2 = Fp[i] / (i² + 1) // Note: This is the complex extension field of Fp with i² = -1. // Values in Fp2 are represented as a pair of Fp elements (a₀, a₁) as a₀ + a₁⋅i. // Note: The order of Fp2 elements is *opposite* that of the pairing contract, which // expects Fp2 elements in order (a₁, a₀). This is also the order in which // Fp2 elements are encoded in the public interface as this became convention. // Constants in Fp uint256 constant FRACTION_1_2_FP = 0x183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea4; uint256 constant FRACTION_27_82_FP = 0x2b149d40ceb8aaae81be18991be06ac3b5b4c5e559dbefa33267e6dc24a138e5; uint256 constant FRACTION_3_82_FP = 0x2fcd3ac2a640a154eb23960892a85a68f031ca0c8344b23a577dcf1052b9e775; // Exponents for inversions and square roots mod P uint256 constant EXP_INVERSE_FP = 0x30644E72E131A029B85045B68181585D97816A916871CA8D3C208C16D87CFD45; // P - 2 uint256 constant EXP_SQRT_FP = 0xC19139CB84C680A6E14116DA060561765E05AA45A1C72A34F082305B61F3F52; // (P + 1) / 4; // Groth16 alpha point in G1 uint256 constant ALPHA_X = 4049029244477351443083306418794153952021012725933818807286985639593651886110; uint256 constant ALPHA_Y = 1329763025147336715492883585163373110715505025433855305931170870643675078033; // Groth16 beta point in G2 in powers of i uint256 constant BETA_NEG_X_0 = 20658514946693480113160126569978442286318852289954056033651872761504783515193; uint256 constant BETA_NEG_X_1 = 20399057544535393951015420565047526967970007296563139970082555918078196877944; uint256 constant BETA_NEG_Y_0 = 2925489870308121815252784684966772618205553838082039705525009011096686069582; uint256 constant BETA_NEG_Y_1 = 4426826819198293610003175592059970325974606674828111714026904311673797096840; // Groth16 gamma point in G2 in powers of i uint256 constant GAMMA_NEG_X_0 = 7253237805730266753811047349423861973202435805378982469725625209778349728741; uint256 constant GAMMA_NEG_X_1 = 20535251859336498409588163760056333587042007997979705979434216255465941258703; uint256 constant GAMMA_NEG_Y_0 = 7718919081940520509570492162023875850370121851514110053828631198589106243031; uint256 constant GAMMA_NEG_Y_1 = 12631707830989671259575003287782727747050713220651750163984915806443954328443; // Groth16 delta point in G2 in powers of i uint256 constant DELTA_NEG_X_0 = 5103671671329861131324970203591866343070008547040712355630109953767034930709; uint256 constant DELTA_NEG_X_1 = 9864653096589723308654389746589362490888397823347493685298210722949226699746; uint256 constant DELTA_NEG_Y_0 = 1198992409988856276728638320543481892366304243973836884492071114626369348862; uint256 constant DELTA_NEG_Y_1 = 11685184740943895319903067327525690040193404762706467691456637667110916786927; // Constant and public input points uint256 constant CONSTANT_X = 20904315891667909790471578502082894236715374585849038130756078187829118545369; uint256 constant CONSTANT_Y = 5077016144144203174703192661358684905413631167358361620585544495862273402374; uint256 constant PUB_0_X = 13131574407026113316262743238026643957021678458938596910941952715264788567300; uint256 constant PUB_0_Y = 7603417928583567507294915658413633109980835213019708050021302524209827182496; uint256 constant PUB_1_X = 16832777107046727792404347160112243512109425075526019943619788513328181137942; uint256 constant PUB_1_Y = 2569778660227144225939468074866196945243053460216299433621319373548974697632; uint256 constant PUB_2_X = 18576331754771684297738399323117849676042892908287120286935096202298784106002; uint256 constant PUB_2_Y = 14545354345137902727662904356696938085044694026251386121633230048359109717452; uint256 constant PUB_3_X = 12758477394964092625327185880110373063843308648444883037077901404743460794059; uint256 constant PUB_3_Y = 15690117772479888094025373273733898837837844237031912868295239408403865688134; uint256 constant PUB_4_X = 19446746107434274688344210031235959067425233610808806944055253971835434003070; uint256 constant PUB_4_Y = 4778415489510668070916622111843622255189369538600414371553494030842785628999; uint256 constant PUB_5_X = 9710628775582173051633466250354704255047118808623027414153922401964703365470; uint256 constant PUB_5_Y = 12867673785427136118326847035996470195718851037869955683869221377266214289659; uint256 constant PUB_6_X = 20544080177937256535282010876448859425196964161474504215756847840923124266594; uint256 constant PUB_6_Y = 518926748312043979837637723802711205031647429708012513216921359575427131397; uint256 constant PUB_7_X = 4899399157616988274886927307279117310842269159929165999680780867660400883747; uint256 constant PUB_7_Y = 7758246138089776760601743236781863140443916881589926605364056702663765239997; uint256 constant PUB_8_X = 16320319110443484852512191831951920435872098631200317291592298004092931639227; uint256 constant PUB_8_Y = 5299839146170829783532113683390452938912542294323325114881459097752641486878; uint256 constant PUB_9_X = 5847263808263914514099502254587387567558304935774781791923309348425829947883; uint256 constant PUB_9_Y = 16477755795111704422182019180669691950483153686171724789213719609637644268261; uint256 constant PUB_10_X = 5422897071801454235892184218606606123122356470326306831526420441387019113365; uint256 constant PUB_10_Y = 10657292689359109210349466221786152185189565432540515024244617816821348818793; uint256 constant PUB_11_X = 12674016685055259838378931330216091636577219780547224700183049012665619915920; uint256 constant PUB_11_Y = 101108242932223103932789366165232873873627163260418669264494219767954931580; uint256 constant PUB_12_X = 11491394967750854427763481785102045991966212486094708865879196096668758400548; uint256 constant PUB_12_Y = 3052866071496317470988827740056151343357313270165186778793619733216093370713; uint256 constant PUB_13_X = 15432099017639660367198759135934375116052088826478966935904766261612071114033; uint256 constant PUB_13_Y = 2638082376170225069537256318476060079667071380066830076251453144820283488185; uint256 constant PUB_14_X = 16585857800931420531693321070161223763788776191824136435611184975703280058411; uint256 constant PUB_14_Y = 2922522822937586141863986369045033908239198907931463279486298717607478667648; uint256 constant PUB_15_X = 5488563746058908748187690373634836887197480639969559097615349295285826282778; uint256 constant PUB_15_Y = 11298333677722938697221176820692704856666731444579535187063846012603884657242; uint256 constant PUB_16_X = 14097071521995987518870710438693216189788727319613626297132836201937028415191; uint256 constant PUB_16_Y = 19931393854950333251787929884054557473386385651127043448259446393699589884687; uint256 constant PUB_17_X = 11311635860175268480235550625191361687974748671319988636763886481173947086848; uint256 constant PUB_17_Y = 9179579077260140790856953727876005839573809568199783910384000484853255899700; uint256 constant PUB_18_X = 2666657272712910241471920965022936871334066622507784847718782429254342396301; uint256 constant PUB_18_Y = 17632303477948337949298132861640315363958500563426951500366116182463088770322; uint256 constant PUB_19_X = 14296088718390232942542287355649564946424430665726397177787836413060131429745; uint256 constant PUB_19_Y = 15421368653434737938294312442154121491202734977067226487505645957549639608801; uint256 constant PUB_20_X = 883899854965287665029323792813734716988550638229818278062967871505824880832; uint256 constant PUB_20_Y = 5458581024984374406492332178463128737189227928422079420852002454469764117266; uint256 constant PUB_21_X = 12061157168843719984131846893122230871800094061937082142331409962267755565518; uint256 constant PUB_21_Y = 20457545019696402511969783405901738703232226067591621766808314791010937447986; uint256 constant PUB_22_X = 21836789920528342890766730552597598131602549361960496379729285837841197204928; uint256 constant PUB_22_Y = 12002315436075980010400830300735757391028024724385025493246401029773828951886; uint256 constant PUB_23_X = 898271417296598298592889524797074141535355580112023234769948833630445698870; uint256 constant PUB_23_Y = 18686529504964900763982774051591201323947004653000704911812817351580879287453; uint256 constant PUB_24_X = 15114915505552874492128850304852996796553012111434208753987896572524621039647; uint256 constant PUB_24_Y = 6606070814943642749810414294860249402969845407275443223316698809448813312682; uint256 constant PUB_25_X = 17319422928943999992187093765864266570201178613452972124769167832439929179070; uint256 constant PUB_25_Y = 20648238269397673750781061831939709477415157043915876939690469389826271377717; uint256 constant PUB_26_X = 6406398263396889241150071476605866921420545419659296469671260106532736023264; uint256 constant PUB_26_Y = 124159808226615818330556530552989831256167213180342395964624414357238497056; uint256 constant PUB_27_X = 11012561581559100469491937100887837472079419421420418077669366876518825552930; uint256 constant PUB_27_Y = 16531067475259112565674457532631815055317387313602174125818721547143968554624; uint256 constant PUB_28_X = 1746630727242429632189002760411166178617059801431493986520766922309285610170; uint256 constant PUB_28_Y = 4164851940136318451722516446323784857071315674226507369503497261258770656904; uint256 constant PUB_29_X = 16442588239044940806897974501969129323378208647061897378668776262552715172637; uint256 constant PUB_29_Y = 18730683142613071821803501047264137281127052209889033912637880491987809555784; uint256 constant PUB_30_X = 7078907154631252317840191858121741217192061655693473108471338998094766598883; uint256 constant PUB_30_Y = 2199231351304665771265445467899371989024069650483415965592454196759216144091; uint256 constant PUB_31_X = 10920492044381396233247580656380513217510550831086842677698303994550305871656; uint256 constant PUB_31_Y = 19797736120091069897487023918182452130840218710708649450159218553186757721630; uint256 constant PUB_32_X = 7322956534393719978348617006149419175127736010621857055808018120616950171059; uint256 constant PUB_32_Y = 14834238512971640462584388586830985211554334089139489587031827975357129102704; uint256 constant PUB_33_X = 276506227999241265936961334317258531316345865423118772612897869877943870605; uint256 constant PUB_33_Y = 10269714174283362494563076584911209837438837509647243048091774926041717648529; uint256 constant PUB_34_X = 9534258202354065216226573001547623116775195960702411941916515976154111005484; uint256 constant PUB_34_Y = 6035483298873081375532707144591311263031220466232081606969966169100068042602; uint256 constant PUB_35_X = 17441231519376140977663071306249989383624519632924097433724189583602041002459; uint256 constant PUB_35_Y = 5396850836489487487866616714685571190123755387597120181236866333174641991560; uint256 constant PUB_36_X = 9453828957311810030700423901114188987103201376351516651613662093813895005836; uint256 constant PUB_36_Y = 1775753252335038626893920653039118548264275872644067125960799559816089598055; uint256 constant PUB_37_X = 3170612248930392604647370258702596024385877034569198442886158813760384434214; uint256 constant PUB_37_Y = 14251492172352407321689653539491099193857876137455594411909133774633043913511; uint256 constant PUB_38_X = 14719442259635412658839245070376126877524951205383307250299653326824501205220; uint256 constant PUB_38_Y = 8303123639576197131317806233286134331199424413944782627122257252318967170937; uint256 constant PUB_39_X = 2446420220890039869413881669203121236989185672515503286561909271777961217466; uint256 constant PUB_39_Y = 7576117725403834753709314051589501234666766424941483838729100294809350064661; uint256 constant PUB_40_X = 15622012348776979744337342779933428047609321533178582723325790482981603834984; uint256 constant PUB_40_Y = 16042825063810970396798543393059152949828757756015609022511957240065095399666; uint256 constant PUB_41_X = 3921610370268239557470131047869012222297721148107983690430805030757523173486; uint256 constant PUB_41_Y = 5201286676969716775173132629353782807526597167000800092554998927886780250841; /// Negation in Fp. /// @notice Returns a number x such that a + x = 0 in Fp. /// @notice The input does not need to be reduced. /// @param a the base /// @return x the result function negate(uint256 a) internal pure returns (uint256 x) { unchecked { x = (P - (a % P)) % P; // Modulo is cheaper than branching } } /// Exponentiation in Fp. /// @notice Returns a number x such that a ^ e = x in Fp. /// @notice The input does not need to be reduced. /// @param a the base /// @param e the exponent /// @return x the result function exp(uint256 a, uint256 e) internal view returns (uint256 x) { bool success; assembly ("memory-safe") { let f := mload(0x40) mstore(f, 0x20) mstore(add(f, 0x20), 0x20) mstore(add(f, 0x40), 0x20) mstore(add(f, 0x60), a) mstore(add(f, 0x80), e) mstore(add(f, 0xa0), P) success := staticcall(gas(), PRECOMPILE_MODEXP, f, 0xc0, f, 0x20) x := mload(f) } if (!success) { // Exponentiation failed. // Should not happen. revert ProofInvalid(); } } /// Invertsion in Fp. /// @notice Returns a number x such that a * x = 1 in Fp. /// @notice The input does not need to be reduced. /// @notice Reverts with ProofInvalid() if the inverse does not exist /// @param a the input /// @return x the solution function invert_Fp(uint256 a) internal view returns (uint256 x) { x = exp(a, EXP_INVERSE_FP); if (mulmod(a, x, P) != 1) { // Inverse does not exist. // Can only happen during G2 point decompression. revert ProofInvalid(); } } /// Square root in Fp. /// @notice Returns a number x such that x * x = a in Fp. /// @notice Will revert with InvalidProof() if the input is not a square /// or not reduced. /// @param a the square /// @return x the solution function sqrt_Fp(uint256 a) internal view returns (uint256 x) { x = exp(a, EXP_SQRT_FP); if (mulmod(x, x, P) != a) { // Square root does not exist or a is not reduced. // Happens when G1 point is not on curve. revert ProofInvalid(); } } /// Square test in Fp. /// @notice Returns whether a number x exists such that x * x = a in Fp. /// @notice Will revert with InvalidProof() if the input is not a square /// or not reduced. /// @param a the square /// @return x the solution function isSquare_Fp(uint256 a) internal view returns (bool) { uint256 x = exp(a, EXP_SQRT_FP); return mulmod(x, x, P) == a; } /// Square root in Fp2. /// @notice Fp2 is the complex extension Fp[i]/(i^2 + 1). The input is /// a0 + a1 ⋅ i and the result is x0 + x1 ⋅ i. /// @notice Will revert with InvalidProof() if /// * the input is not a square, /// * the hint is incorrect, or /// * the input coefficients are not reduced. /// @param a0 The real part of the input. /// @param a1 The imaginary part of the input. /// @param hint A hint which of two possible signs to pick in the equation. /// @return x0 The real part of the square root. /// @return x1 The imaginary part of the square root. function sqrt_Fp2(uint256 a0, uint256 a1, bool hint) internal view returns (uint256 x0, uint256 x1) { // If this square root reverts there is no solution in Fp2. uint256 d = sqrt_Fp(addmod(mulmod(a0, a0, P), mulmod(a1, a1, P), P)); if (hint) { d = negate(d); } // If this square root reverts there is no solution in Fp2. x0 = sqrt_Fp(mulmod(addmod(a0, d, P), FRACTION_1_2_FP, P)); x1 = mulmod(a1, invert_Fp(mulmod(x0, 2, P)), P); // Check result to make sure we found a root. // Note: this also fails if a0 or a1 is not reduced. if (a0 != addmod(mulmod(x0, x0, P), negate(mulmod(x1, x1, P)), P) || a1 != mulmod(2, mulmod(x0, x1, P), P)) { revert ProofInvalid(); } } /// Compress a G1 point. /// @notice Reverts with InvalidProof if the coordinates are not reduced /// or if the point is not on the curve. /// @notice The point at infinity is encoded as (0,0) and compressed to 0. /// @param x The X coordinate in Fp. /// @param y The Y coordinate in Fp. /// @return c The compresed point (x with one signal bit). function compress_g1(uint256 x, uint256 y) internal view returns (uint256 c) { if (x >= P || y >= P) { // G1 point not in field. revert ProofInvalid(); } if (x == 0 && y == 0) { // Point at infinity return 0; } // Note: sqrt_Fp reverts if there is no solution, i.e. the x coordinate is invalid. uint256 y_pos = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P)); if (y == y_pos) { return (x << 1) | 0; } else if (y == negate(y_pos)) { return (x << 1) | 1; } else { // G1 point not on curve. revert ProofInvalid(); } } /// Decompress a G1 point. /// @notice Reverts with InvalidProof if the input does not represent a valid point. /// @notice The point at infinity is encoded as (0,0) and compressed to 0. /// @param c The compresed point (x with one signal bit). /// @return x The X coordinate in Fp. /// @return y The Y coordinate in Fp. function decompress_g1(uint256 c) internal view returns (uint256 x, uint256 y) { // Note that X = 0 is not on the curve since 0³ + 3 = 3 is not a square. // so we can use it to represent the point at infinity. if (c == 0) { // Point at infinity as encoded in EIP196 and EIP197. return (0, 0); } bool negate_point = c & 1 == 1; x = c >> 1; if (x >= P) { // G1 x coordinate not in field. revert ProofInvalid(); } // Note: (x³ + 3) is irreducible in Fp, so it can not be zero and therefore // y can not be zero. // Note: sqrt_Fp reverts if there is no solution, i.e. the point is not on the curve. y = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P)); if (negate_point) { y = negate(y); } } /// Compress a G2 point. /// @notice Reverts with InvalidProof if the coefficients are not reduced /// or if the point is not on the curve. /// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1) /// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i). /// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0). /// @param x0 The real part of the X coordinate. /// @param x1 The imaginary poart of the X coordinate. /// @param y0 The real part of the Y coordinate. /// @param y1 The imaginary part of the Y coordinate. /// @return c0 The first half of the compresed point (x0 with two signal bits). /// @return c1 The second half of the compressed point (x1 unmodified). function compress_g2(uint256 x0, uint256 x1, uint256 y0, uint256 y1) internal view returns (uint256 c0, uint256 c1) { if (x0 >= P || x1 >= P || y0 >= P || y1 >= P) { // G2 point not in field. revert ProofInvalid(); } if ((x0 | x1 | y0 | y1) == 0) { // Point at infinity return (0, 0); } // Compute y^2 // Note: shadowing variables and scoping to avoid stack-to-deep. uint256 y0_pos; uint256 y1_pos; { uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P); uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P); uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P); y0_pos = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P); y1_pos = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P)); } // Determine hint bit // If this sqrt fails the x coordinate is not on the curve. bool hint; { uint256 d = sqrt_Fp(addmod(mulmod(y0_pos, y0_pos, P), mulmod(y1_pos, y1_pos, P), P)); hint = !isSquare_Fp(mulmod(addmod(y0_pos, d, P), FRACTION_1_2_FP, P)); } // Recover y (y0_pos, y1_pos) = sqrt_Fp2(y0_pos, y1_pos, hint); if (y0 == y0_pos && y1 == y1_pos) { c0 = (x0 << 2) | (hint ? 2 : 0) | 0; c1 = x1; } else if (y0 == negate(y0_pos) && y1 == negate(y1_pos)) { c0 = (x0 << 2) | (hint ? 2 : 0) | 1; c1 = x1; } else { // G1 point not on curve. revert ProofInvalid(); } } /// Decompress a G2 point. /// @notice Reverts with InvalidProof if the input does not represent a valid point. /// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1) /// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i). /// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0). /// @param c0 The first half of the compresed point (x0 with two signal bits). /// @param c1 The second half of the compressed point (x1 unmodified). /// @return x0 The real part of the X coordinate. /// @return x1 The imaginary poart of the X coordinate. /// @return y0 The real part of the Y coordinate. /// @return y1 The imaginary part of the Y coordinate. function decompress_g2(uint256 c0, uint256 c1) internal view returns (uint256 x0, uint256 x1, uint256 y0, uint256 y1) { // Note that X = (0, 0) is not on the curve since 0³ + 3/(9 + i) is not a square. // so we can use it to represent the point at infinity. if (c0 == 0 && c1 == 0) { // Point at infinity as encoded in EIP197. return (0, 0, 0, 0); } bool negate_point = c0 & 1 == 1; bool hint = c0 & 2 == 2; x0 = c0 >> 2; x1 = c1; if (x0 >= P || x1 >= P) { // G2 x0 or x1 coefficient not in field. revert ProofInvalid(); } uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P); uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P); uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P); y0 = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P); y1 = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P)); // Note: sqrt_Fp2 reverts if there is no solution, i.e. the point is not on the curve. // Note: (X³ + 3/(9 + i)) is irreducible in Fp2, so y can not be zero. // But y0 or y1 may still independently be zero. (y0, y1) = sqrt_Fp2(y0, y1, hint); if (negate_point) { y0 = negate(y0); y1 = negate(y1); } } /// Compute the public input linear combination. /// @notice Reverts with PublicInputNotInField if the input is not in the field. /// @notice Computes the multi-scalar-multiplication of the public input /// elements and the verification key including the constant term. /// @param input The public inputs. These are elements of the scalar field Fr. /// @return x The X coordinate of the resulting G1 point. /// @return y The Y coordinate of the resulting G1 point. function publicInputMSM(uint256[42] calldata input) internal view returns (uint256 x, uint256 y) { // Note: The ECMUL precompile does not reject unreduced values, so we check this. // Note: Unrolling this loop does not cost much extra in code-size, the bulk of the // code-size is in the PUB_ constants. // ECMUL has input (x, y, scalar) and output (x', y'). // ECADD has input (x1, y1, x2, y2) and output (x', y'). // We reduce commitments(if any) with constants as the first point argument to ECADD. // We call them such that ecmul output is already in the second point // argument to ECADD so we can have a tight loop. bool success = true; assembly ("memory-safe") { let f := mload(0x40) let g := add(f, 0x40) let s mstore(f, CONSTANT_X) mstore(add(f, 0x20), CONSTANT_Y) mstore(g, PUB_0_X) mstore(add(g, 0x20), PUB_0_Y) s := calldataload(input) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_1_X) mstore(add(g, 0x20), PUB_1_Y) s := calldataload(add(input, 32)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_2_X) mstore(add(g, 0x20), PUB_2_Y) s := calldataload(add(input, 64)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_3_X) mstore(add(g, 0x20), PUB_3_Y) s := calldataload(add(input, 96)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_4_X) mstore(add(g, 0x20), PUB_4_Y) s := calldataload(add(input, 128)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_5_X) mstore(add(g, 0x20), PUB_5_Y) s := calldataload(add(input, 160)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_6_X) mstore(add(g, 0x20), PUB_6_Y) s := calldataload(add(input, 192)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_7_X) mstore(add(g, 0x20), PUB_7_Y) s := calldataload(add(input, 224)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_8_X) mstore(add(g, 0x20), PUB_8_Y) s := calldataload(add(input, 256)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_9_X) mstore(add(g, 0x20), PUB_9_Y) s := calldataload(add(input, 288)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_10_X) mstore(add(g, 0x20), PUB_10_Y) s := calldataload(add(input, 320)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_11_X) mstore(add(g, 0x20), PUB_11_Y) s := calldataload(add(input, 352)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_12_X) mstore(add(g, 0x20), PUB_12_Y) s := calldataload(add(input, 384)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_13_X) mstore(add(g, 0x20), PUB_13_Y) s := calldataload(add(input, 416)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_14_X) mstore(add(g, 0x20), PUB_14_Y) s := calldataload(add(input, 448)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_15_X) mstore(add(g, 0x20), PUB_15_Y) s := calldataload(add(input, 480)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_16_X) mstore(add(g, 0x20), PUB_16_Y) s := calldataload(add(input, 512)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_17_X) mstore(add(g, 0x20), PUB_17_Y) s := calldataload(add(input, 544)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_18_X) mstore(add(g, 0x20), PUB_18_Y) s := calldataload(add(input, 576)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_19_X) mstore(add(g, 0x20), PUB_19_Y) s := calldataload(add(input, 608)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_20_X) mstore(add(g, 0x20), PUB_20_Y) s := calldataload(add(input, 640)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_21_X) mstore(add(g, 0x20), PUB_21_Y) s := calldataload(add(input, 672)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_22_X) mstore(add(g, 0x20), PUB_22_Y) s := calldataload(add(input, 704)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_23_X) mstore(add(g, 0x20), PUB_23_Y) s := calldataload(add(input, 736)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_24_X) mstore(add(g, 0x20), PUB_24_Y) s := calldataload(add(input, 768)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_25_X) mstore(add(g, 0x20), PUB_25_Y) s := calldataload(add(input, 800)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_26_X) mstore(add(g, 0x20), PUB_26_Y) s := calldataload(add(input, 832)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_27_X) mstore(add(g, 0x20), PUB_27_Y) s := calldataload(add(input, 864)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_28_X) mstore(add(g, 0x20), PUB_28_Y) s := calldataload(add(input, 896)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_29_X) mstore(add(g, 0x20), PUB_29_Y) s := calldataload(add(input, 928)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_30_X) mstore(add(g, 0x20), PUB_30_Y) s := calldataload(add(input, 960)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_31_X) mstore(add(g, 0x20), PUB_31_Y) s := calldataload(add(input, 992)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_32_X) mstore(add(g, 0x20), PUB_32_Y) s := calldataload(add(input, 1024)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_33_X) mstore(add(g, 0x20), PUB_33_Y) s := calldataload(add(input, 1056)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_34_X) mstore(add(g, 0x20), PUB_34_Y) s := calldataload(add(input, 1088)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_35_X) mstore(add(g, 0x20), PUB_35_Y) s := calldataload(add(input, 1120)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_36_X) mstore(add(g, 0x20), PUB_36_Y) s := calldataload(add(input, 1152)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_37_X) mstore(add(g, 0x20), PUB_37_Y) s := calldataload(add(input, 1184)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_38_X) mstore(add(g, 0x20), PUB_38_Y) s := calldataload(add(input, 1216)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_39_X) mstore(add(g, 0x20), PUB_39_Y) s := calldataload(add(input, 1248)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_40_X) mstore(add(g, 0x20), PUB_40_Y) s := calldataload(add(input, 1280)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) mstore(g, PUB_41_X) mstore(add(g, 0x20), PUB_41_Y) s := calldataload(add(input, 1312)) mstore(add(g, 0x40), s) success := and(success, lt(s, R)) success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40)) success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40)) x := mload(f) y := mload(add(f, 0x20)) } if (!success) { // Either Public input not in field, or verification key invalid. // We assume the contract is correctly generated, so the verification key is valid. revert PublicInputNotInField(); } } /// Compress a proof. /// @notice Will revert with InvalidProof if the curve points are invalid, /// but does not verify the proof itself. /// @param proof The uncompressed Groth16 proof. Elements are in the same order as for /// verifyProof. I.e. Groth16 points (A, B, C) encoded as in EIP-197. /// @return compressed The compressed proof. Elements are in the same order as for /// verifyCompressedProof. I.e. points (A, B, C) in compressed format. function compressProof(uint256[8] calldata proof) public view returns (uint256[4] memory compressed) { compressed[0] = compress_g1(proof[0], proof[1]); (compressed[2], compressed[1]) = compress_g2(proof[3], proof[2], proof[5], proof[4]); compressed[3] = compress_g1(proof[6], proof[7]); } /// Verify a Groth16 proof with compressed points. /// @notice Reverts with InvalidProof if the proof is invalid or /// with PublicInputNotInField the public input is not reduced. /// @notice There is no return value. If the function does not revert, the /// proof was successfully verified. /// @param compressedProof the points (A, B, C) in compressed format /// matching the output of compressProof. /// @param input the public input field elements in the scalar field Fr. /// Elements must be reduced. function verifyCompressedProof( uint256[4] calldata compressedProof, uint256[42] calldata input ) public view { uint256[24] memory pairings; { (uint256 Ax, uint256 Ay) = decompress_g1(compressedProof[0]); (uint256 Bx0, uint256 Bx1, uint256 By0, uint256 By1) = decompress_g2(compressedProof[2], compressedProof[1]); (uint256 Cx, uint256 Cy) = decompress_g1(compressedProof[3]); (uint256 Lx, uint256 Ly) = publicInputMSM(input); // Verify the pairing // Note: The precompile expects the F2 coefficients in big-endian order. // Note: The pairing precompile rejects unreduced values, so we won't check that here. // e(A, B) pairings[ 0] = Ax; pairings[ 1] = Ay; pairings[ 2] = Bx1; pairings[ 3] = Bx0; pairings[ 4] = By1; pairings[ 5] = By0; // e(C, -δ) pairings[ 6] = Cx; pairings[ 7] = Cy; pairings[ 8] = DELTA_NEG_X_1; pairings[ 9] = DELTA_NEG_X_0; pairings[10] = DELTA_NEG_Y_1; pairings[11] = DELTA_NEG_Y_0; // e(α, -β) pairings[12] = ALPHA_X; pairings[13] = ALPHA_Y; pairings[14] = BETA_NEG_X_1; pairings[15] = BETA_NEG_X_0; pairings[16] = BETA_NEG_Y_1; pairings[17] = BETA_NEG_Y_0; // e(L_pub, -γ) pairings[18] = Lx; pairings[19] = Ly; pairings[20] = GAMMA_NEG_X_1; pairings[21] = GAMMA_NEG_X_0; pairings[22] = GAMMA_NEG_Y_1; pairings[23] = GAMMA_NEG_Y_0; // Check pairing equation. bool success; uint256[1] memory output; assembly ("memory-safe") { success := staticcall(gas(), PRECOMPILE_VERIFY, pairings, 0x300, output, 0x20) } if (!success || output[0] != 1) { // Either proof or verification key invalid. // We assume the contract is correctly generated, so the verification key is valid. revert ProofInvalid(); } } } /// Verify an uncompressed Groth16 proof. /// @notice Reverts with InvalidProof if the proof is invalid or /// with PublicInputNotInField the public input is not reduced. /// @notice There is no return value. If the function does not revert, the /// proof was successfully verified. /// @param proof the points (A, B, C) in EIP-197 format matching the output /// of compressProof. /// @param input the public input field elements in the scalar field Fr. /// Elements must be reduced. function verifyProof( uint256[8] calldata proof, uint256[42] calldata input ) public view { (uint256 x, uint256 y) = publicInputMSM(input); // Note: The precompile expects the F2 coefficients in big-endian order. // Note: The pairing precompile rejects unreduced values, so we won't check that here. bool success; assembly ("memory-safe") { let f := mload(0x40) // Free memory pointer. // Copy points (A, B, C) to memory. They are already in correct encoding. // This is pairing e(A, B) and G1 of e(C, -δ). calldatacopy(f, proof, 0x100) // Complete e(C, -δ) and write e(α, -β), e(L_pub, -γ) to memory. // OPT: This could be better done using a single codecopy, but // Solidity (unlike standalone Yul) doesn't provide a way to // to do this. mstore(add(f, 0x100), DELTA_NEG_X_1) mstore(add(f, 0x120), DELTA_NEG_X_0) mstore(add(f, 0x140), DELTA_NEG_Y_1) mstore(add(f, 0x160), DELTA_NEG_Y_0) mstore(add(f, 0x180), ALPHA_X) mstore(add(f, 0x1a0), ALPHA_Y) mstore(add(f, 0x1c0), BETA_NEG_X_1) mstore(add(f, 0x1e0), BETA_NEG_X_0) mstore(add(f, 0x200), BETA_NEG_Y_1) mstore(add(f, 0x220), BETA_NEG_Y_0) mstore(add(f, 0x240), x) mstore(add(f, 0x260), y) mstore(add(f, 0x280), GAMMA_NEG_X_1) mstore(add(f, 0x2a0), GAMMA_NEG_X_0) mstore(add(f, 0x2c0), GAMMA_NEG_Y_1) mstore(add(f, 0x2e0), GAMMA_NEG_Y_0) // Check pairing equation. success := staticcall(gas(), PRECOMPILE_VERIFY, f, 0x300, f, 0x20) // Also check returned value (both are either 1 or 0). success := and(success, mload(f)) } if (!success) { // Either proof or verification key invalid. // We assume the contract is correctly generated, so the verification key is valid. revert ProofInvalid(); } } }