ERC: Cryptography Engine Standard

[zac-williamson]

eip: 1723
title: Cryptography Engine
author: AZTEC
discussions-to: https://github.com/ethereum/EIPs/issues/1723
status: Draft
type: Standards Track
category: ERC
created: 2019-01-25

Cryptography Engine Standard

Simple Summary

This EIP defines the interface and behaviours of a zero-knowledge proof validation engine, supporting multiple compatible types of zero-knowledge proof. The Cryptography Engine enables developers to construct customized transaction semantics for confidential digital digital assets.

Abstract

This standard defines a mechanism by which multiple confidential digital assets and confidential DApps can efficiently communicate with one another, whilst enabling developers to customize the transaction semantics of their confidential smart contract.

The Cryptography Engine acts as a validator for a set of mutually compatible zero-knowledge proofs that conform to the AZTEC protocol. These proofs can be used by digital asset builders to construct confidential transaction semantics for digital assets and dApps. By subscribing to the same Cryptography Engine, smart contracts can efficiently communicate with one another while preserving confidentiality.

Motivation

Confidential transactions, where the values inside a transaction are encrypted, are made possible through zero-knowledge proofs. Currently, existing zero-knowledge proofs define unilateral transactions - transfers of value of one asset type only, issued by a single user.

While useful, there is a significant shortfall between the functionality of current confidential digital assets and public assets. Specifically, when comparing confidential digital assets with the ERC20 token standard, the following functionality is missing:

1. Smart contracts cannot easily issue confidential transactions on behalf of users (as opposed to external accounts controlled by humans).
2. Confidential assets cannot efficiently communicate with one another confidentially. For example, a confidential decentralized exchange which enacts trades between confidential assets, where observers cannot identify the values inside the trade.

Bridging the Gap with the Cryptography Engine

The AZTEC protocol enables confidential transactions on Ethereum and the construction of confidential digital assets. At the core of the protocol is the AZTEC commitment function - a method of encrypting data that enables the highly efficient construction and verification of range proofs.

This in turn enables highly efficient Sigma protocols - simple zero-knowledge proofs that validate relationships between encrypted numbers via homomorphic arithmetic.

The AZTEC protocol's "join-split" transaction enables basic unilateral confidential transfers of value. If a digital asset builder wishes to define more advanced confidential transaction semantics, these can be expressed as a Sigma protocol layered on top of a "join-split" transaction.

The Cryptography Engine defines a set of these Sigma protocols, that developers can use in a modular fashion to construct complex confidential transaction semantics.

Cross-Asset Interoperability

Confidential settlement, where an exchange of value between different assets occurs confidentially, is necessary for a wide degree of financial applications. However this is, traditionally, a computationally expensive endeavour: every smart contract in a transaction sequence must validate its own zero-knowledge proof in order to prevent double spending. However this results in redundant computation - the proof statements that these smart contracts are validating will overlap significantly.

This problem is solved by using a single verification engine. A confidential AZTEC transaction must satisfy a balancing relationship - the transaction inputs must be equal to the transaction outputs. If multiple smart contracts require the same balancing relationship to be satisfied, the Cryptography Engine can identify this and prevent redundant computation from being performed. To summarise:

1. The Cryptography Engine validates AZTEC zero-knowledge proofs.
2. If a proof satisfies one or more balancing relationships, these are recorded by the engine.
3. The Cryptography Engine can use these recorded proofs to validate whether a transfer instruction satisfies a balancing relationship.

For example consider a confidential decentralized exchange dApp

When the DeX processes an order, it validates a bilateral swap zero-knowledge proof via the Cryptography Engine

Once validated, the Cryptography Engine converts the proof into transfer instructions and returns these to the DeX

The DeX forwards the transfer instructions to two confidential digital assets

Each asset queries the Cryptography Engine with the transfer instruction

The Cryptography Engine can validate the mathematical legitimacy of the transfer instruction, without performing additional proof verification

In the above example, the bilateral swap zero-knowledge proof costs approximately 500,000 gas to verify. If each confidential asset also required their own zero-knowledge proof, this would add over 1,000,000 gas to the transaction's gas cost.

Security and Trust

The Cryptography Engine's AZTEC proofs all utilize the same common reference string. As a consequence, all confidential smart contracts that use the Cryptography Engine can share the same single trusted setup - a trusted setup is not required per dApp, and all dApps can share the same security assumptions.

Example Set of Zero-Knowledge Proofs

The following is an initial set of AZTEC protocol proofs that an MVP Cryptography Engine can support. As more use-cases and requirements become apparent, Sigma protocols can be developed that satisfy these use-cases and then added to the Cryptography Engine.

name	description	# of balancing relationships satisfied	gas costs
join-split	enables unilateral confidential value transfer	1	~800,000
bilateral-swap	enables a trade between two confidential assets	2	~500,000
dividend	verifies an AZTEC note is a public percentage of another AZTEC note. Used for interest and dividend payments	0	~700,000
public-range	verifies an AZTEC note is greater than/less than a public integer	0	~300,000
private-range	verifies an AZTEC note is greater than/less than a secret integer	0	~700,000

Note: the gas costs above do NOT include the costs associated with sending the transaction or paying for the input data.

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.

Every ERC-1723 compliant contract MUST implement the following interface:

/**
 * @title The Cryptography Engine
 * @dev See https://github.com/ethereum/EIPs/issues/1723
 **/
interface CryptographyEngine {

    /// @dev emitted when the Cryptography Engine adds or modifies a proof
    event LogSetProof(uint16 _proofType, address _validatorAddress, bool _isBalanced);

    /// @dev emitted when the Cryptography Engine changes the common reference string
    event LogSetCommonReferenceString(bytes32[6] _commonReferenceString);

    /// @dev Get the common reference string
    function getCommonReferenceString() external view returns (bytes32[6] _commonReferenceString);

    /// @dev Get whether a proof satisfies a balancing relationship
    function getIsProofBalanced(uint16 _proofType) external view returns (bool _balanced);

    /// @dev Get the validator address of a given _proofType
    function getValidatorAddress(uint16 _proofType) external view returns (address _validator);

    /// @dev Query the engine for a previously validated proof.
    ///      _sender is the address of the entity that originally validated the proof
    function validateProofByHash(bytes32 _proofHash, uint16 _proofType, address _sender) external view returns (bool _valid);

    /// @dev Set the Cryptography Engine's common reference string. Will change if a new
    ///      trusted setup ceremony is performed
    function setCommonReferenceString(bytes32[6] _commonReferenceString) public;

    /// @dev Set an AZTEC zero-knowledge proof validator contract against a _proofType.
    ///      _isBalanced defines whether a balancing relationship is satisfied by the proof
    function setProof(uint16 _proofType, address _proofValidatorAddress, bool _isBalanced) public;

    /// @dev Validate an AZTEC zero-knowledge proof according to _proofType.
    ///      and return transfer instructions to sender
    function validateProof(uint16 _proofType, address _sender, bytes _proofData) external returns (bytes _proofOutputs);

    /// @dev Clear storage variables set when validating proofs.
    ///      Will only work if sent by address that validated the proofs
    function clearProofByHashes(uint16 _proofType, bytes32[] _proofHashes) external;
}

The token contract MUST implement the above interface to be compatible with the standard. The implementation MUST follow the specifications described below.

Methods

validateProofByHash

function validateProofByHash(bytes32 _proofHash, uint16 _proofType, address _sender) view returns (bool _valid);

After a dApp calls validateProof, it may issue confidentialTransferFrom instructions to one or more confidential digital assets, supplying a bytes proofOutput object as a transfer instruction.

This digital asset can then compute the keccak256 hash of bytes proofOutput and query whether this instruction satisfies a balancing relationship by calling validateProofByHash.

If bytes32 _proofHash comes from a satisfying balancing relationship from a proof sent by address _sender, with type _proofType, the Cryptography Engine MUST return true. If bytes32 _proofHash does not come from a satisfying balancing relationship, the Cryptography Engine MUST return false.

setCommonReferenceString

function setCommonReferenceString(bytes32[6] _commonReferenceString) public;

Changes the Cryptography Engine's AZTEC common reference string. This string is generated via a trusted setup ceremony, and can be created via a multiparty computation protocol. The same restrictions that apply to setProof should apply to setCommonReferenceString.

setProof

function setProof(uint16 _proofType, address _proofValidatorAddress, bool _isBalanced) public;

Maps a given _proofType to the address of a validator smart contract. This is a privileged action, as providing faulty validator smart contracts fatally undermines the security of the Cryptography Engine. Ideally this method is restricted by a consensus mechanism, where the protocol's stakeholders decide the proof types and validator smart contracts supported by the Cryptography Engine.

validateProof

function validateProof(uint16 _proofType, address _sender, bytes _proofData) returns (bytes _proofOutputs)

Validate an AZTEC zero-knowledge proof according to the proof's _proofType, proof's _proofData and the message _sender.
If the proof is not valid, this method MUST throw an error.
If the proof is valid, bytes proofOutputs MUST be formatted according to the Cryptography Engine's ABI specification.

The field address _sender corresponds to the address of the entity issuing the original transaction - it is the responsibility of the contract calling the Cryptography Engine to correctly supply this variable. To do otherwise does not affect the security of the Cryptography Engine or its zero-knowledge proofs, however it makes the contract calling validateProof vulnerable to front-running attacks.

The Cryptography Engine then MUST record the correctness of bytes proofOutput and the _proofType against a unique combination of the following components:

1. The keccak256 hash of bytes proofOutput
2. The _proofType
3. The message sender msg.sender (not _sender)

clearProofByHashes

function clearProofByHashes(uint16 _proofType, bytes32[] _proofHashes)

Function is designed to utilize EIP-1283 to reduce gas costs. It is highly likely that any storage variables set by validateProof are only required for the duration of a single transaction.

E.g. a decentralized exchange validating a swap proof and sending transfer instructions to two confidential assets.

This method allows the calling smart contract to recover most of the gas spent by setting validatedProofs, by clearing any set state variables before the transaction terminates.

Motivation and Rationale for uint16 _proofType

The uint16 _proofType variable defines which zero-knowledge proof to verify. It functions in a similar way to a function signature, where IDs are represented by 16-bit integers instead of 4-bytes of a keccak256 hash.

The rationale behind this is to provide digital asset builders with an efficient method to define the set of zero-knowledge proofs that their asset subscribes to, without having to set a storage variable for every proof. For the uint16 type one can use a bit-filter to completely define the set of proofs the asset listens to.

The potential downside is being limited to 65535 proofs. Every proof supported by the crypto-engine must be extensively vetted before being integrated into the engine, with a formal soundness proof - a single insecure proof renders the entire cryptosystem insecure. As a result, a maximum cap of 65535 proofs seems reasonable, as one would question the security of such a broad cryptography engine.

ABI Encoding of proofOutputs

Due to the nature of zero-knowledge cryptography, the data structure of a zero-knowledge proof is relatively complex. To abstract this away from users and developers, AZTEC zero-knowledge proofs supplied to the Cryptography Engine are encoded as a bytes argument.

It falls to the Cryptography Engine to process this bytes argument and present, as an output to a valid proof, transfer instructions to the sender via: bytes proofOutput. A transfer instruction involves the following:

• What are the AZTEC notes that are inputs to this transaction? (to be destroyed)
• What are the AZTEC output notes? (to be created)
• If public ERC20 tokens are being converted to/from AZTEC note form, who is the owner?
• If owner !== address(0), how many tokens are being converted? Is this a conversion of public tokens to AZTEC notes, or the opposite?

These transfer instructions are not simple. The natural instinct is to encode this data as a struct, however ABI encoding for structs is still experimental and should not be included in a standard.

To this end, bytes types are used to define the structure of proofOutputs and its constituent components. A JSON schema of how these types are encoded is provided below. The two key custom types used are an encoding for an AZTEC note, aztecNote, as well as the encoding for a proofOutput. Encoded data is NOT packed.

Any implementation of the Cryptography Engine spec MUST format its output according to this specification.

In order to allow developers to easily manipulate proofOutputs and its child components, utilities libraries are provided to convert this data into its constituent Solidity types.

JSON Schemas

aztecNote

{
    "name": "aztecNote",
    "type": "bytes",
    "description": "a formatted AZTEC note",
    "components": [
        {
            "name": "owner",
            "type": "address",
            "description": "owner of the note"
        },
        {
            "name": "noteHash",
            "type": "bytes32",
            "description": "keccak256 hash of uncompressed Note coordinates"
        },
        {
            "name": "noteData",
            "type": "bytes",
            "description": "compressed AZTEC note data. Used when emitting events",
            "components": [
                {
                    "name": "gamma",
                    "type": "bytes32",
                    "description": "compressed AZTEC group element 'gamma'. y-coordinate represented by a bit in the 255th bit position"
                },
                {
                    "name": "sigma",
                    "type": "bytes32",
                    "description": "compressed AZTEC group element 'sigma'. y-coordinate represented by a bit in the 255th bit position"
                },
                {
                    "name": "metadata",
                    "type": "bytes",
                    "description": "metadata required by note owner to decrypt note. Usually a compressed secp256k1 group element but can have additional data"
                }
            ]
        }
    ]
}

proofOutput

{
    "name": "proofOutput",
    "type": "bytes",
    "description": "a transfer instruction generated from an AZTEC zero-knowledge proof",
    "components": [
        {
            "name": "inputNotes",
            "type": "bytes",
            "description": "AZTEC input notes. Formatted as a `bytes` type that contains a dynamic array of `aztecNote` objects"
        },
        {
            "name": "outputNotes",
            "type": "bytes",
            "description": "AZTEC output notes. Formatted as a `bytes` type that contains a dynamic array of `aztecNote` objects"
        },
        {
            "name": "publicOwner",
            "type": "address",
            "description": "if public tokens are being transferred into/from AZTEC note form, this is the owner of the tokens. Otherwise is 0"
        },
        {
            "name": "publicValue",
            "type": "int256",
            "description": "quantity of tokens being transferred into AZTEC note form. Negative value signifies withdrawal from AZTEC notes into token form"
        }
    ]
}

Cryptography Engine Utilities

pragma solidity 0.4.24;

library ProofOutputs {
    function length(bytes memory _proofOutputs) internal pure returns (
        uint _numProofOutputs
    ) {
        assembly {
            _numProofOutputs := mload(add(_proofOutputs, 0x20))
        }
    }

    function getProofOutput(bytes memory _proofOutputs, uint _i) internal pure returns (
        bytes _proofOutput
    ) {
        assembly {
            _proofOutput := add(_proofOutputs, mload(add(add(_proofOutputs, 0x40), mul(_i, 0x20))))
        }
    }

    function extractProofOutput(bytes memory _proofOutput) internal pure returns (
        bytes memory _inputNotes,
        bytes memory _outputNotes,
        address _publicOwner,
        int256 _publicValue
    ) {
        assembly {
            _inputNotes := add(_proofOutput, mload(add(_proofOutput, 0x20)))
            _outputNotes := add(_proofOutput, mload(add(_proofOutput, 0x40)))
            _publicOwner := mload(add(_proofOutput, 0x60))
            _publicValue := mload(add(_proofOutput, 0x80))
        }
    }
}

library Notes {
    function length(bytes memory _notes) internal pure returns (
        uint _numNotes
    ) {
        assembly {
            _numNotes := mload(add(_notes, 0x20))
        }
    }

    function getNote(bytes memory _notes, uint i) internal pure returns (
        bytes _note
    ) {
        assembly {
            _note := add(_notes, mload(add(add(_notes, 0x40), mul(i, 0x20))))
        }
    }

    function extractNote(bytes memory _note) internal pure returns (
            address _owner,
            bytes32 _noteHash,
            bytes memory _metadata
        ) {
        assembly {
            _owner := mload(add(_note, 0x20))
            _noteHash := mload(add(_note, 0x40))
            _metadata := add(_note, mload(add(_note, 0x60)))
        }
    }
}

Implementation

See the following resources for a work in progress implementation:

• AZTEC Cryptography Engine PoC
• Join-Split Transaction Validator

To see more code, head to the AZTEC monorepo. Many thanks to @PaulRBerg, @thomas-waite, @ArnSch and the @AztecProtocol team for their contributions to this document.

Copyright

Work released under LGPL-3.0.

[adamdossa]

Great to see you standardising this and making great progress in the corresponding Aztec protocol!

Couple of thoughts / questions:

1. If _proofType always maps to whether or not a _proofType is of a balancing relationship(s) or not, I’m wondering why this needs to be stored on chain (i.e. the mapping from _proofType to _isBalanced)? Did you have a use-case for this in mind (i.e. where a caller would not know the details of the _proofType it was using, but would need to know whether the specific _proofType satisfied a balancing relationship)?

2. Should a call to setProof and setCommonReferenceString clear existing proofs (for the specific type in the first case, and all types in the second case)? Otherwise a caller to validateProofByHash would not have any guarantees about the terms under which the outputs which it is validating were proven.

3. You mention that the reason validateProof needs to take in a _sender address is to avoid a possible front-running attack - could you elaborate a bit on this with an example?

4. The links under the Implementation section are out of date although the contracts can be easily found in your repo.

5. With clearProofByHashes do you foresee the validateProof and validateProofByHash always happening inside a single transaction (and hence no one can call this function in-between to grief the caller of validateProofByHash)? If that is the case, and in both instances it is smart contracts calling out to the Cryptography Engine then I guess validateProofByHash would only be needed if the smart contract calling this function didn't trust the smart contract that was asserting the proofOutput which seems unusual unless this contract could be upgraded or otherwise tampered with.

[zac-williamson]

Great to see you standardising this and making great progress in the corresponding Aztec protocol!

Couple of thoughts / questions:

1. If _proofType always maps to whether or not a _proofType is of a balancing relationship(s) or not, I’m wondering why this needs to be stored on chain (i.e. the mapping from _proofType to _isBalanced)? Did you have a use-case for this in mind (i.e. where a caller would not know the details of the _proofType it was using, but would need to know whether the specific _proofType satisfied a balancing relationship)?
2. Should a call to setProof and setCommonReferenceString clear existing proofs (for the specific type in the first case, and all types in the second case)? Otherwise a caller to validateProofByHash would not have any guarantees about the terms under which the outputs which it is validating were proven.
3. You mention that the reason validateProof needs to take in a _sender address is to avoid a possible front-running attack - could you elaborate a bit on this with an example?
4. The links under the Implementation section are out of date although the contracts can be easily found in your repo.
5. With clearProofByHashes do you foresee the validateProof and validateProofByHash always happening inside a single transaction (and hence no one can call this function in-between to grief the caller of validateProofByHash)? If that is the case, and in both instances it is smart contracts calling out to the Cryptography Engine then I guess validateProofByHash would only be needed if the smart contract calling this function didn't trust the smart contract that was asserting the proofOutput which seems unusual unless this contract could be upgraded or otherwise tampered with.

Heya! Sorry for the slow reply.

1. any smart contract that intends to manipulate a registry of AZTEC notes based on proofs from the Cryptography Engine (e.g. ERC1724) will need to know whether a given proof type satisfies a balancing relationship. isBalanced enables a contract to validate this, without having to have foreknowledge about the proofs supported by the Cryptography Engine

2. Thanks for bringing that up. That issue might get resolved because we're thinking of changing setProof so that existing proofs cannot be modified, so that developers can have surety over a given proof if they intend to use it in their smart contract. You're correct that we'll need to invalidate previous proofs if the CRS gets updated. I'll update the EIP to reflect this.

3. If I construct a valid zero-knowledge proof and then broadcast it to the network, theoretically an attacker could grab my proof out of the mining pool and broadcast it themselves, and use it for their own purposes. By integrating _sender into the zero-knowledge proof, the proof is only valid when broadcast from a single account.

4. Thanks for identifying that, I'll update the links

5. This is correct. If I'm building a zero-knowledge Dapp that interacts with confidential assets, these assets cannot assume any instructions sent to them from my Dapp are legitimate, and must validate the instructions with the Cryptography Engine.

[github-actions[bot]]

There has been no activity on this issue for two months. It will be closed in a week if no further activity occurs. If you would like to move this EIP forward, please respond to any outstanding feedback or add a comment indicating that you have addressed all required feedback and are ready for a review.

[github-actions[bot]]

This issue was closed due to inactivity. If you are still pursuing it, feel free to reopen it and respond to any feedback or request a review in a comment.