Precompiled Contracts and Confidential Assets

Published in

Qtum

12 min readOct 10, 2019

Background

As part of the upcoming hard fork, Qtum will introduce several precompiled contracts to the EVM on top of Qtum, which will enable more efficient smart contracts that offer the creation and transfer of confidential assets.

Smart Contracts

Ethereum has two kinds of accounts, the externally owned account, and the contract account. Externally Owned Account (EOA) is a kind of account controlled by private keys and without any code associated with it. A Contract Account (CA) is an account assigned to a smart contract, controlled by contract. An externally owned account can send a transaction, which can be a transfer transaction or a transaction related to a smart contract to create or trigger a smart contract.

Each transaction of Ethereum will be converted into a Message object, which is passed to the EVM for execution, and then EVM will convert the Message object into a Contract object. If it is a normal transfer transaction, the corresponding account balance will be modified in StateDB. If it is a transaction that creates or invokes a smart contract, the bytecode is loaded and executed by the interpreter in the EVM, and the StateDB may be queried or modified during execution. As you can see from the figure, the Contract object loads the corresponding contract code from the database according to the address of the contract, and then sends it to the interpreter for execution.

The EVM interpreter is a stack-based machine with its PC, stack, memory, and gas pool. A contract code will be interpreted as a strip of opcodes and then executed. Before executing opcode, the EVM interpreter will check the required Gas and the current Gas remaining for the command. If the Gas is insufficient, it will return the ErrOutOfGas error. Because EVM is a stack-based virtual machine, it has no intermediate storage such as registers. All operations are maintained through a stack, so its operation efficiency is relatively low, and it may take a long time to complete a complex operation. More complex operations may not be completed at an effective time. See [1] for details.

Confidential assets

The blockchain is an open distributed transaction ledger, allowing the data on the chain to be publicly visible. Although the sender and receiver of a transaction cannot directly be associated with real-life buyers and sellers, the data on the chain can be analyzed by Address clustering to derive some association information about addresses and identities. Additionally, the amount of the transaction is also public on the chain. It can be seen that although the transparency of the data guarantees the true and tamper-resistant features of the ledger, it also makes many scenarios that require privacy impossible to be applied on the blockchain.

Under this condition, the concept of confidential assets was proposed. The sender, receiver, and transaction amount of the transaction are hidden by using techniques such as cryptography, and the miner (transaction verifier) can verify the legality of a transaction without knowing the specific data. Commonly used methods for implementing confidential assets include Mimble-Wimble, zk-SNARKs, etc.

Due to the widespread use of contract models, some projects such as Nightfall, Zether, AZTEC, and others have thought of using smart contracts to implement private transactions, by deploying smart contracts related to private transactions to achieve the purpose of issuing confidential assets on the chain.

Precompiled Contract

Concept

Because the EVM is a stack-based virtual machine, it calculates gas based on the content of the operation, so if it involves very complicated calculations, it can be very inefficient to execute the operation in EVM and consume a lot of gas. For example, in zk-snark, the addition and subtraction of the elliptic curve and the pairing operation are required. These operations are very complicated and unrealistic to be executed in the EVM. This is the original intention of Ethereum to propose a precompiled contract.

Precompiled contracts are a compromise used in the EVM to provide more complex library functions (usually used for complex operations such as encryption, hashing, etc.) that are not suitable for writing in opcode. They are applied to contracts that are simple but frequently called, or that are logically fixed but computationally intensive. Precompiled contracts are implemented on the client-side with client code, and because they do not require the EVM, they run fast. It also costs less for developers than using functions that run directly in the EVM.

The precompiled contracts that Ethereum has implemented now are as follows：

At the code level, the so-called address is actually the index of the contract array, and an index identifies a precompiled contract. The three precompiled contracts related to the confidential assets are bn256Add(), bn256ScalarMul(), bn256Pairing().

Implementation

In the evm.go file, the operating logic of EVM is encapsulated. There are 4 functions for calling smart contracts, Call(), CallCode(), DelegateCall(), StaticCall(). The work done by these four functions is to generate contract objects, but the specific details such as parameters will have some differences. After the contract is instantiated, the run function in evm.go is called to run the smart contract. This function takes into account both the case of precompiled contracts and non-precompiled contract calls. In the following code, the first branch is to instantiate parameter p by specifying a precompiles index to specify a precompiled contract. The index of the array here actually corresponds to the concept of the address when the precompiled contract array is declared. The RunPrecompiledContract function is then called to execute the precompiled contract. If it is a non-precompiled contract, you can see from the code that the interpreter of EVM is called.

go-ethereum/core/vm/evm.go

// run runs the given contract and takes care of running precompiles with a fallback to the byte code interpreter.
func run(evm *EVM, contract *Contract, input []byte, readOnly bool) ([]byte, error) {
   if contract.CodeAddr != nil {
      precompiles := PrecompiledContractsHomestead
      if evm.ChainConfig().IsByzantium(evm.BlockNumber) {
         precompiles = PrecompiledContractsByzantium
      }
      if p := precompiles[*contract.CodeAddr]; p != nil {
         return RunPrecompiledContract(p, input, contract)
      }
   }
   for _, interpreter := range evm.interpreters {
      if interpreter.CanRun(contract.Code) {
         if evm.interpreter != interpreter {
            // Ensure that the interpreter pointer is set back
            // to its current value upon return.
            defer func(i Interpreter) {
               evm.interpreter = i
            }(evm.interpreter)
            evm.interpreter = interpreter
         }
         return interpreter.Run(contract, input, readOnly)
      }
   }
   return nil, ErrNoCompatibleInterpreter
}

In the RunPrecompiledContract function, you can see that the p variable implements the bn256 curve addition operation and then returns the result. It can be clearly seen that this part of the operation is calculated during the execution on the client’s end.

go-ethereum/core/vm/contracts.go

// RunPrecompiledContract runs and evaluates the output of a precompiled contract.
func RunPrecompiledContract(p PrecompiledContract, input []byte, contract *Contract) (ret []byte, err error) {
   gas := p.RequiredGas(input)
   if contract.UseGas(gas) {
      return p.Run(input)
   }
   return nil, ErrOutOfGas
}

go-ethereum/core/vm/contracts.go

// bn256Add implements a native elliptic curve point addition.
type bn256Add struct{}
// RequiredGas returns the gas required to execute the pre-compiled contract.
func (c *bn256Add) RequiredGas(input []byte) uint64 {
   return params.Bn256AddGas
}
func (c *bn256Add) Run(input []byte) ([]byte, error) {
   x, err := newCurvePoint(getData(input, 0, 64))
   if err != nil {
      return nil, err
   }
   y, err := newCurvePoint(getData(input, 64, 64))
   if err != nil {
      return nil, err
   }
   res := new(bn256.G1)
   res.Add(x, y)
   return res.Marshal(), nil

Instructions

In smart contract code, the precompiled contract can be called directly in the contract file just like a normal contract, but the calling method is somewhat different. A precompiled contract call is made by an assembly code block in the .sol file. The specification and parameters of the call are as follows:

assembly {
    if iszero(call(gasLimit, contractAddress, value, input, inputLength, output, outputLength)) {
        revert(0, 0)
    }
}

An example of implementing elliptic curve addition is as follows:

function ecadd(uint256 ax, uint256 ay, uint256 bx, uint256 by) public constant returns(uint256[2] p) {
  uint256[4] memory input;
  input[0] = ax;
  input[1] = ay;
  input[2] = bx;
  input[3] = by;  
  assembly {
    // ecadd precompile!
    if iszero(call(not(0), 0x06, 0, input, 0x80, p, 0x40)) {
       revert(0, 0)
    }    
  }

Precompiled Contracts in Confidential Assets

Precompiled contract for elliptic curves

Ethereum’s current solution to privacy is to use zk-SNARKs[6][8], but zk-SNARKs require a complex mathematical process involving many elliptic curve calculations. After the previous analysis, this process is very unrealistic to be implemented in the EVM, so in order to support the related operations of zk-SNARKs, Ethereum added three precompiled contracts related to zk-SNARK operations in EIP196[3] and EIP197[4], which can be called by developers.

EIP-196 adds two precompiled contracts, ECADD() and ECMUL(), on the alt_bn128 curve, where ECADD() consumes 500 gas and ECMUL() consumes 40,000 gas.

EIP-197 adds a pairing contract on the alt_bn128 curve, consuming gas of 80,000*k+100000 (k is related to the number of points).

It is not hard to understand the addition and multiplication on the elliptic curve. The pairing appears because there is a KCA (Knowledge of Coefficient Test and Assumption) certification process in zk-SNARKs [6], which needs to be proved by using bilinear mapping, for details, please refer to Vitalik’s medium post[7]. Pairing is the formula that will be used in the proof process. The input of the Pairing function is a list of points, because different zk-snark algorithms may have different data amounts, and the gas consumed by the pairing function is also related to the number of pairs of points.

Many projects that use precompiled contracts to implement privacy now use the pairing process, such as EYBlockchain, AZTEC, and so on. Pairing is a step that zk-snark must use. The cost of gas is huge, and of course, the official is also optimizing. The process of implementing pairing is generally carried out on a pairing-friendly curve. This is a type of curve with special properties, which is mainly manifested in the calculation of pairing speed. So if you want to use the pairing process, then the commonly used curve such as secp256k1 is obviously not suitable, you need additional support for the pairing-friendly curve.

Now the mainstream pairing-friendly curves are Barreto-Naehrig (BN) series and Barreto-Lynn-Scott (BLS) series [9], Ethereum uses BN series, zcash uses BLS series, and Ethereum will also add support for the BLS curve. The overall performance of the BLS curve is much better and the amount of calculation is relatively small. But no matter what, selecting a curve has a trade-off between safety and efficiency.

It is worth mentioning that if you do not need to use the pairing process, you do not need a pairing-friendly curve. Another option is to add support for precompiled contracts for the secp256k1 curve. For example, although the PGC team used two precompiled contracts of bn256ADD and bn256MUL, that is, the curves of the bn series are used, but their algorithm does not need pairing. If the precompiled contract support for secp256k1 is replaced, the algorithm efficiency will be improved.

For the implementation of the C++ version, there are now two external libraries that encapsulate and implement these operations. The first is Libff, which is the library currently being used by Ethereum. LibSnark.cpp in the source code that calls the relevant calculation function of the libff library. There is also an MCL library, which is the library recommended by EIP-1108.

Confidential Assets Project

The four privacy solutions that are now popular are EYBlockchain, PGC, Zether, and AZTEC.

EYBlockchain implements confidential assets based on zk-SNARKs. It performs off-chain zero-knowledge proofing by porting the Ethereum’s recommended ZoKrates toolkit. The algorithm needs to use the add, multiply, and pairing processes of the bn256 curve. The gas consumption of a transfer transaction is around 2.7M.

Zether is an anonymous payment protocol deployed on the Ethereum in the form of a smart contract Zether Smart Contract (ZSC) with tokens called Zether Tokens (ZTH). Tokens can be used as the carrier for transmission between Zether accounts of ElGamal public keys and support anonymous smart contract interactions. The algorithm needs to use the add and multiply algorithms of the bn256 curve.

PGC is an improved version of the Zether algorithm. PGC uses the original Elgamal and the original bulletproof zero-knowledge proof algorithm. PGC uses the add, multiply algorithm of the bn256 curve, but if the precompiled contract of the secp256k1 elliptic curve can be implemented, the efficiency of the PGC algorithm can be greatly improved.

AZTEC combines homomorphic proofs and range proofs to provide zero-knowledge proofs to issue confidential assets on Ethereum. AZTEC needs to use the add, multiply, pairing operations on the bn256 curve. The specific operation amount is (3n+m-1)add+(2n+2m-2)multiply+1pairing (n and m are the numbers of transaction tickets respectively).

gas

The proposed EIP-196 and EIP-197 enable many zero-knowledge proof algorithms to run on Ethereum. But there is still a problem. Although these complex mathematical processes are implemented using precompiled contracts, the consumption of gas is still very large. It is not an exaggeration to say that in some scenarios, the amount of gas consumed to transfer a confidential asset may be higher than the amount transferred. The maximum gas consumption per block on Ethereum is 8M, which makes many privacy projects impossible to really stick.

In order to reduce the gas of the precompiled contract, AZTEC employees proposed improvements on EIP-1108 [5].

EIP-1108 is an optimization of the three precompiled contracts of add, multiply, and pairing. By optimizing the underlying algorithm of the calling library, the efficiency of the code is improved, thereby reducing the gas. The precompiled contract name for the Golang version also became bn256. Bn256 is alt_bn128, just with a different name. 256 refers to the length of p in the formula, and 128 refers to the security level of the curve. These are two different property descriptions of a curve. So the EIP-1108 does not replace the curve to reduce the gas but optimizes the implemented algorithm. The updated gas comparison chart is as follows. EIP-1108 is currently in the draft state, the algorithm part of the code has been improved, but the value of gas has not been updated.

With the improved approach of EIP-1108, many privacy algorithms can be greatly optimized. Gas consumption on a transfer transaction of Zether can be reduced from 7188000 to 170000, that of PGC can be reduced from 6563000 to 1100000, and that of AZTEC can be reduced from 121000n+41000m+219000 to 12200n+6200m+85930.

If you are deploying a precompiled contract, how one determines the gas value of the precompiled contract is a serious problem. The setting of the precompiled contract gas is related to the calculation amount of the operation. For example, the calculation method of the Pairing gas described in EIP-1108 is based on the efficiency of ecrecover and the established gas. An ecrecover call takes 116ms, and its gas is set to 3000, which gives the fact that the 1ms run costs 25.86gas. Because the time spent on pairing calculation is divided into two parts, one is the base time, base_time, which can be understood as the start time of the operation, and the other is the floating time per_pair_time, which is related to the calculation amount of the input. It takes 3037ms to calculate 1 pairing and 14663ms to calculate 10 pairing. Base_time and per_pair_time are derived, multiply by the established 25.86gas, and the gas consumption of the pairing process is derived. In this way, the relevant benchmark can be made according to the specific environment to regulate the setting of gas.

Qtum and Confidential Assets

In Qtum, the maximum gas consumption per block is 40M, and the maximum gas consumption per transaction is 20M, so the confidential assets running on Qtum are basically not limited by gas. But using EVM to run some computationally intensive privacy algorithms is very inefficient. Therefore, we should implement some basic and common privacy algorithms in the form of pre-compiled contracts, so that privacy assets can run on Qtum more efficiently.

For elliptic curves, consider adding the precompiled contracts of BLS and secp256k1. BLS has better performance and security than bn256 and is pairing-friendly, so it can be used instead of bn256. And if you want to deploy the pairing precompiled contract, for its gas settings, you can also find a precompiled contract for reference whose gas has been set, then benchmark respectively. Although secp256k1 is not pairing-friendly, it is widely used in blockchain signature and encryption algorithms because of its better performance and stronger versatility.

For zero-knowledge proofs, consider implementing the Bulletproof algorithm as a precompiled contract. Bulletproof is a widely used range proof algorithm in the blockchain, mainly used to prove that the hidden transaction amount in MimbleWimble is a positive number. Bulletproofs have been implemented and stable in the Grin and Beam projects. Bulletproof’s verification process is computationally intensive, so using precompiled contract implementations is a more appropriate option. With the Bulletproof precompiled contract, MimbleWimble can run efficiently on Qtum in a contractual manner.