Implement all precompiled contracts

[zah]

We need implementations and dispatching logic for the following precompiles

Introduced in Homestead:

• 0x1 ecrecover
• 0x2 sha256
• 0x3 ripemd160
• 0x4 identity

Introduced in Byzantium:

• 0x5 modexp
• 0x6 ecadd
• 0x7 ecmul
• 0x8 ecpairing

Reference implementations:
https://github.com/ethereum/py-evm/tree/master/eth/precompiles

[cheatfate]

1. sha256 and ripemd160 is pretty easy to implement because nimcrypto has both primitives.
2. ecrecover is based on secp256k1 curve so we already have everything to implement it.
3. identity is not so hard too.
4. modexp can be implemented in stint.

But
ecadd, ecmul and ecpairing is based on BN128 curve, which we don't have.

[mratsim]

modexp is called powmod in Stint and already available: https://github.com/status-im/nim-stint/blob/master/stint/modular_arithmetic.nim#L113.

For BN128 the fastest ways are in order:

• reuse Aleth/Cpp-ethereum lib (devcrypto?)
• Find another C/C++ lib
• wrap the primitives from Milagro crypto similar to BLS12-381
• DIY

[mratsim]

After reviewing on precompiles.

1. Precompiles live at specified addresses on the blockchain: https://github.com/ethereum/go-ethereum/blob/702b8a7aec97c7ef512335ee44c925bc91c6ae09/core/vm/contracts.go#L40-L60

// PrecompiledContractsHomestead contains the default set of pre-compiled Ethereum
// contracts used in the Frontier and Homestead releases.
var PrecompiledContractsHomestead = map[common.Address]PrecompiledContract{
	common.BytesToAddress([]byte{1}): &ecrecover{},
	common.BytesToAddress([]byte{2}): &sha256hash{},
	common.BytesToAddress([]byte{3}): &ripemd160hash{},
	common.BytesToAddress([]byte{4}): &dataCopy{},
}

// PrecompiledContractsByzantium contains the default set of pre-compiled Ethereum
// contracts used in the Byzantium release.
var PrecompiledContractsByzantium = map[common.Address]PrecompiledContract{
	common.BytesToAddress([]byte{1}): &ecrecover{},
	common.BytesToAddress([]byte{2}): &sha256hash{},
	common.BytesToAddress([]byte{3}): &ripemd160hash{},
	common.BytesToAddress([]byte{4}): &dataCopy{},
	common.BytesToAddress([]byte{5}): &bigModExp{},
	common.BytesToAddress([]byte{6}): &bn256Add{},
	common.BytesToAddress([]byte{7}): &bn256ScalarMul{},
	common.BytesToAddress([]byte{8}): &bn256Pairing{},
}

So 0x0000...0001 for ecrecover for example

2. CALL opcode must catch calls to those addresses and dispatch to the proper precompile, see https://github.com/ethereum/go-ethereum/blob/c1c003e4ff36c22d67662ca661fc78cde850d401/core/vm/evm.go#L163-L225 and https://github.com/ethereum/go-ethereum/blob/c1c003e4ff36c22d67662ca661fc78cde850d401/core/vm/evm.go#L43-L68

For reference here are some discussions, including BN128 C++ implementation concerns:

• Precompiles for ECADD and ECMUL ethereum/EIPs#102
• Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128 ethereum/EIPs#213

3. They are implemented internally and not through EVM native ops for efficiency and gas costs reasons.

[cheatfate]

If we are limited in time on BN128 i will vote on wrap the primitives from Milagro crypto similar to BLS12-381.

[mratsim]

After looking into BN128 with @cheatfate the current situation is somewhat strange:

We don't know if we should use BN128 or BN256 (Note that the data will be stored in a 256-bit integer regardless)

Facts:

• Ethresearch is done on bn128: https://github.com/ethereum/py_ecc/tree/master/py_ecc/bn128
• Geth uses bn256: see previous message and https://github.com/ethereum/go-ethereum/tree/master/crypto/bn256
• Yellow paper mentions BN256, BN512, BN1024 (?)
  
• The EIPs linked previously mention BN128
• Vitalik uses both bn128 and bn256 in the same sentence:
  
  

Also BN128 is not supported in Milagro while BN256 is https://github.com/milagro-crypto/amcl/blob/master/version3/curves.txt#L26

[coffeepots]

ecrecover is implemented already too, but needs testing to make sure it's correct.

[mratsim]

Useful repo, a fuzzer for Ethereum BN256 implementations: https://github.com/guidovranken/bn256-fuzzing

[cheatfate]

https://gist.github.com/artjomb/f2d720010506569d3a39

[mratsim]

Geth uses Cloudflare implementation according to EIP 1108

Still no test vectors though.

[tersec]

To the extent it might help prioritize things, the stPreCompiledContracts2 section of https://github.com/status-im/nimbus/blob/master/GeneralStateTests.md shows which of these are tested by currently running tests.