EIP 1922: zk-SNARK Verifier Standard Source

AuthorMichael Connor, Chaitanya Konda, Duncan Westland
Discussions-Tohttps://github.com/ethereum/EIPs/issues/1922
StatusDraft
TypeStandards Track
CategoryERC
Created2018-09-14
Requires 165, 196, 197

Simple Summary

A standard interface for “Verifier” contracts which verify zk-SNARKs.

Abstract

The following standard allows for the implementation of a standard contract API for the verification of zk-SNARKs (“Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge”), also known as “proofs”, “arguments”, or “commitments”.

This standard provides basic functionality to load all necessary parameters for the verification of any zk-SNARK into a verifier contract, so that the proof may ultimately return a true or false response; corresponding to whether it has been verified or not verified.

Motivation

zk-SNARKs are a promising area of interest for the Ethereum community. Key applications of zk-SNARKs include:

  • Private transactions
  • Private computations
  • Improved transaction scaling through proofs of “bundled” transactions

A standard interface for verifying all zk-SNARKs will allow applications to more easily implement private transactions, private contracts, and scaling solutions; and to extract and interpret the limited information which gets emitted during zk-SNARK verifications.

This standard was initially proposed by EY, and was inspired in particular by the requirements of businesses wishing to keep their agreements, transactions, and supply chain activities confidential—all whilst still benefiting from the commonly cited strengths of blockchains and smart contracts.

:warning: TODO: Explain the benefits to and perspective of a consumer of information. I.e. the thing that interfaces with the standard verifier.

Specification

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119.

Terminology in this specification is used consistently with libsnark, as provided in that project’s README.

  • Adhering Contract — A Verifier contract which adheres to this specification.
  • Arithmetic circuit: An abstraction of logical statements into addition and multiplication gates.
  • Public Inputs: often denoted as a vector ‘x’ in zk-SNARKs literature, and denoted inputs in this interface. An arithmetic circuit can be thought of as taking two parameters; the Public Inputs, ‘x’, and a secret ‘witness’, ‘w’. This interface standardises functions which can load the inputs into an Adhering Contract.
  • Proof: A ‘prover’ who wants to ‘prove’ knowledge of some secret witness ‘w’ (which satisfies an arithmetic circuit), generates a proof from: the circuit’s Proving Key; their secret witness ‘w’; and its corresponding Public Inputs ‘x’. Together, a pair (proof, inputs) of satisfying inputs and their corresponding proof forms a zk-SNARK.
  • Verification Key: A ‘trusted setup’ calculation creates both a public ‘Proving Key’ and a public ‘Verification Key’ from an arithmetic circuit. This interface does not provide a method for loading a Verification Key onto the blockchain. An Adhering Contract SHALL be able to accept arguments of knowledge ((proof, inputs) pairs) for at least one Verification Key. We shall call such Verification Keys ‘in-scope’ Verification Keys. An Adhering Contract MUST be able to interpret unambiguously a unique verificationKeyId for each of its ‘in-scope’ Verification Keys.

Every ERC-XXXX compliant verifier contract must implement the ERCXXXX and ERC165 interfaces (subject to “caveats” below):

pragma solidity ^0.5.6;

/// @title EIP-XXXX zk-SNARK Verifier Standard
/// @dev See https://github.com/EYBlockchain/zksnark-verifier-standard
///  Note: the ERC-165 identifier for this interface is 0xXXXXXXXX.
/// ⚠️ TODO: Calculate interface identifier
interface EIPXXXX /* is ERC165 */ {
    /// @notice Checks the arguments of Proof, through elliptic curve
    ///  pairing functions.
    /// @dev
    ///  MUST return `true` if Proof passes all checks (i.e. the Proof is
    ///  valid).
    ///  MUST return `false` if the Proof does not pass all checks (i.e. if the
    ///  Proof is invalid).
    /// @param proof A zk-SNARK.
    /// @param inputs Public inputs which accompany Proof.
    /// @param verificationKeyId A unique identifier (known to this verifier
    ///  contract) for the Verification Key to which Proof corresponds.
    /// @return result The result of the verification calculation. True
    ///  if Proof is valid; false otherwise.
    function verify(uint256[] calldata proof, uint256[] calldata inputs, bytes32 verificationKeyId) external returns (bool result);
}

Interface

interface ERC165 {
    /// @notice Query if a contract implements an interface
    /// @param interfaceID The interface identifier, as specified in ERC-165
    /// @dev Interface identification is specified in ERC-165. This function
    ///  uses less than 30,000 gas.
    /// @return `true` if the contract implements `interfaceID` and
    ///  `interfaceID` is not 0xffffffff, `false` otherwise
    function supportsInterface(bytes4 interfaceID) external view returns (bool);
}

Rationale

Taxonomy

⚠️ TODO: Add a specific reference to libsnark here, explaining the choice of variable names.

:warning: TODO: Explain how C may not necessarily be a satisfiable arithmetic circuit of logical statements. As current, this is a limitation to certain kinds of SNARKS. Whereas the source references also mention polynomials, and other applications.

C — A satisfiable arithmetic circuit abstraction of logical statements.

lambda​ - A random number, generated at the ‘setup’ phase - commonly referred to as ‘toxic waste’, because knowledge of lambda​ would allow an untrustworthy party to create ‘false’ proofs which would verify as ‘true’. lambda​ must be destroyed.

pk​ - The proving key for a particular circuit C​.

vk - The verification key for a particular circuit C.

Both pk​ and vk​ are generated as a pair by some function G​: (pk, vk) = G(lambda, C)​

Note: C can be represented unambiguously by either of pk or vk. In zk-SNARK constructions, vk is much smaller in size than pk, so as to enable succinct verification on-chain. Hence, vk is the representative of C that is ‘known’ to the contract. Therefore, we can identify each circuit uniquely through some verificationKeyId, where verificationKeyId serves as a more succinct mapping to vk.

w - A ‘private witness’ string. A private argument to the circuit C known only to the prover, which, when combined with the inputs argument x, comprises an argument of knowledge which satisfies the circuit C.

x or inputs - A vector of ‘Public Inputs’. A public argument to the circuit C which, when combined with the private witness string w, comprises an argument of knowledge which satisfies the circuit C.

pi or proof - an encoded vector of values which represents the ‘prover’s’ ‘argument of knowledge’ of values w and x which satisfy the circuit C. pi = P(pk, x, w).

The ultimate purpose of a Verifier contract, as specified in this EIP, is to verify a proof (of the form pi​) through some verification function V​.

V(vk, x, pi) = 1, if there exists a w s.t. C(x,w)=1. V(vk, x, pi) = 0, otherwise.

The verify() function of this specification serves the purpose of V​; returning either true (the proof has been verified to satisfy the arithmetic circuit) or false (the proof has not been verified).

Functions

verify

The verify function forms the crux this standard. The parameters are intended to be as generic as possible, to allow for verification of any zk-SNARK:

  • proof Specified as uint256[]. uint256 is the most appropriate type for elliptic curve operations over a finite field. Indeed, this type is used in the predominant ‘Pairing library’ implementation of zk-SNARKs by Christian Reitweissner. A one-dimensional dynamic array has been chosen for several reasons:
    • Dynamic: There are several possible methods for producing a zk-SNARK proof, including PGHR13, G16, GM17, and future methods might be developed in future. Although each method may produce differently sized proof objects, a dynamic array allows for these differing sizes.
    • Array: An array has been chosen over a ‘struct’ object, because it is currently easier to pass dynamic arrays between functions in Solidity. Any proof ‘struct’ can be ‘flattened’ to an array and passed to the verify function. Interpretation of that flattened array is the responsibility of the implemented body of the function. Example implementations demonstrate that this can be achieved.
    • One-dimensional: A one-dimensional array has been chosen over multi-dimensional array, because it is currently easier to work with one-dimensional arrays in Solidity. Any proof can be ‘flattened’ to a one-dimensional array and passed to the verify function. Interpretation of that flattened array is the responsibility of the implemented body of the Adhering Contract. Example implementations demonstrate that this can be achieved.

  • inputs Specified as uint256[]. uint256 is the most appropriate type for elliptic curve operations over a finite field. Indeed, this type is used in the predominant ‘Pairing library’ implementation of zk-SNARKs by Christian Reitweissner. The number of inputs will vary in size, depending on the number of ‘public inputs’ of the arithmetic circuit being verified against. In a similar vein to the proof parameter, a one-dimensional dynamic array is general enough to cope with any set of inputs to a zk-SNARK.

  • verificationKeyId A verification key (referencing a particular arithmetic circuit) only needs to be stored on-chain once. Any proof (relating to the underlying arithmetic circuit) can then be verified against that verification key. Given this, it would be unnecessary (from a ‘gas cost’ point of view) to pass a duplicate of the full verification key to the verify function every time a new (proof, inputs) pair is passed in. We do however need to tell the Adhering Verifier Contract which verification key corresponds to the (proof, inputs) pair being passed in. A verificationKeyId serves this purpose - it uniquely represents a verification key as a bytes32 id. A method for uniquely assigning a verificationKeyId to a verification key is the responsibility of the implemented body of the Adhering Contract.

Backwards Compatibility

  • At the time this EIP was first proposed, there was one implementation on the Ethereum main net - deployed by EY. This was compiled with Solidity 0.4.24 for compatibility with Truffle but otherwise compatible with this standard, which is presented at the latest current version of Solidity.
  • Dr Christian Reitwiessner’s excellent example of a Verifier contract and elliptic curve pairing library has been instrumental in the Ethereum community’s experimentation and development of zk-SNARK protocols. Many of the naming conventions of this EIP have been kept consistent with his example.
  • Existing zk-SNARK compilers such as ZoKrates, which produce ‘Verifier.sol’ contracts, do not currently produce Verifier contracts which adhere to this EIP specification.
    • :warning: TODO: Provide a converter contract or technique which allows ZoKrates verifier.sol contracts to adhere with this EIP.

Test Cases

Truffle tests of example implementations are included in the test case repository.

⚠️ TODO: Reference specific test cases because there are many currently in the repository.

Implementations

Detailed example implementations and Truffle tests of these example implementations are included in this repository.

:warning: TODO: Update referenced verifier implementations so that they are ready-to-deploy or reference deployed versions of those implementations. At current, the referenced code specifically states “DO NOT USE THIS IN PRODUCTION”.

:warning: TODO: Provide reference to an implementation which interrogates a standard verifier contract that implements this standard.

References

:warning: TODO: Update references and confirm that each reference is cited (parenthetical documentation not necessary) in the text.

Standards

  1. ERC-20 Token Standard. https://eips.ethereum.org/EIPS/eip-20

  2. ERC-165 Standard Interface Detection. https://eips.ethereum.org/EIPS/eip-165
  3. ERC-173 Contract Ownership Standard (DRAFT). https://eips.ethereum.org/EIPS/eip-173
  4. ERC-196 Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128. https://eips.ethereum.org/EIPS/eip-196
  5. ERC-197 Precompiled contracts for optimal ate pairing check on the elliptic curve alt_bn128. https://eips.ethereum.org/EIPS/eip-197
  6. Ethereum Name Service (ENS). https://ens.domains
  7. RFC 2119 Key words for use in RFCs to Indicate Requirement Levels. https://www.ietf.org/rfc/rfc2119.txt
Educational material: zk-SNARKs
  1. Zcash. What are zk-SNARKs? https://z.cash/technology/zksnarks.html
  2. Vitalik Buterin. zk-SNARKs: Under the Hood. https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
  3. Christian Reitweissner. zk-SNARKs in a Nutshell. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
  4. Ben-Sasson, Chiesa, Tromer, et. al. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. https://eprint.iacr.org/2013/879.pdf
Notable applications of zk-SNARKs
  1. EY. Implementation of a business agreement through Token Commitment transactions on the Ethereum mainnet. https://github.com/EYBlockchain/ZKPChallenge
  2. Zcash. https://z.cash
  3. Zcash. How Transactions Between Shielded Addresses Work. https://blog.z.cash/zcash-private-transactions/
Notable projects relating to zk-SNARKs
  1. libsnark: A C++ Library for zk-SNARKs (“project README)”. https://github.com/scipr-lab/libsnark
  2. ZoKrates: Scalable Privacy-Preserving Off-Chain Computations. https://www.ise.tu-berlin.de/fileadmin/fg308/publications/2018/2018_eberhardt_ZoKrates.pdf
  3. ZoKrates Project Repository. https://github.com/JacobEberhardt/ZoKrates
  4. Joseph Stockermans. zkSNARKs: Driver’s Ed. https://github.com/jstoxrocky/zksnarks_example
  5. Christian Reitweissner - snarktest.solidity. https://gist.github.com/chriseth/f9be9d9391efc5beb9704255a8e2989d
Notable ‘alternatives’ to zk-SNARKs - areas of ongoing zero-knowledge proof research
  1. Vitalik Buterin. STARKs. https://vitalik.ca/general/2017/11/09/starks_part_1.html
  2. Bu ̈nz, Bootle, Boneh, et. al. Bulletproofs. https://eprint.iacr.org/2017/1066.pdf
  3. Range Proofs. https://www.cosic.esat.kuleuven.be/ecrypt/provpriv2012/abstracts/canard.pdf
  4. Apple. Secure Enclaves. https://developer.apple.com/documentation/security/certificate_key_and_trust_services/keys/storing_keys_in_the_secure_enclave
  5. Intel Software Guard Extensions. https://software.intel.com/en-us/sgx

Copyright and related rights waived via CC0.