Ed25519 precompile in eth clients

[oberstet]

moved from https://github.com/xbr/xbr-network/issues/13

---

needed in https://github.com/xbr/xbr-network/issues/8, and there is only ECDSA built in.

The latest Ethereum hard fork should have brought the features needed in Solidity (or the VM under the hood) to implement Ed25519, which is used by WAMP-cryptosign and WAMP-cryptobox.

What changes are included in the Byzantium hard fork? https://blog.ethereum.org/2017/10/12/byzantium-hf-announcement/

---

https://ethereum.stackexchange.com/questions/42771/ed25519-in-smart-contracts

[oberstet]

Looks like the main thing will be: as Ed25519 is not available in Solidity as a precompiled function (such as ecrecover)

• http://solidity.readthedocs.io/en/develop/units-and-global-variables.html#mathematical-and-cryptographic-functions

we will need to provide it ourself while minimizing gas consumption of the resulting function.

Eg a SHA1 implemention (linked below): "It requires roughly 56k gas per 512 bit block hashed."

Here are some noteworthy pointers:

• http://solidity.readthedocs.io/en/develop/assembly.html
• https://github.com/Arachnid/solsha1/blob/master/contracts/sha1.sol
• https://gist.github.com/D-Nice/43d60515263f9854bd92e952dfc0dea5
• https://github.com/musalbas/solidity-BN256G2

[oberstet]

Here is my SO question touching on the topic:

• https://ethereum.stackexchange.com/questions/42771/ed25519-in-smart-contracts/43333#43333

And here is the PR for merging an EIP to add Ed25519 signature verification as a precompiled contract to the EVM:

• EIP 665 - Add precompile for Ed25519 ethereum/EIPs#949

[oberstet]

Our EIP has been merged!

• http://eips.ethereum.org/EIPS/eip-665
• https://github.com/ethereum/EIPs/blob/master/EIPS/eip-665.md

[oberstet]

next step: get it on the agenda of an ethereum core devs meeting: ethereum/pm#36 (comment)

[oberstet]

Rgd implementation in cpp-ethereum, here are some hints I dug out:

• https://github.com/comaeio/porosity/wiki/Ethereum-Internals#evm-call
• https://github.com/ethereum/EIPs/blob/master/EIPS/eip-196.md

	precompiled.insert(make_pair(Address(1), PrecompiledContract(3000, 0, PrecompiledRegistrar::executor("ecrecover"))));
	precompiled.insert(make_pair(Address(2), PrecompiledContract(60, 12, PrecompiledRegistrar::executor("sha256"))));
	precompiled.insert(make_pair(Address(3), PrecompiledContract(600, 120, PrecompiledRegistrar::executor("ripemd160"))));
	precompiled.insert(make_pair(Address(4), PrecompiledContract(15, 3, PrecompiledRegistrar::executor("identity"))));

• NaCl vs plain C single file (in https://github.com/ethereum/cpp-ethereum/tree/develop/libdevcrypto)?

[oberstet]

find . -type f -exec grep -Hi "alt_bn128" {} \;:

./libethashseal/genesis/test/byzantiumTest.cpp
./libethashseal/genesis/test/constantinopleTransitionTest.cpp
./libethashseal/genesis/test/EIP158ToByzantiumAt5Test.cpp
./libethashseal/genesis/test/mainNetworkNoProofTest.cpp
./libethashseal/genesis/test/mainNetworkTest.cpp
./libethashseal/genesis/test/byzantiumTransitionTest.cpp
./libethashseal/genesis/test/transitionnetTest.cpp
./libethashseal/genesis/test/constantinopleTest.cpp
./libethashseal/genesis/ropsten.cpp
./libethashseal/genesis/mainNetwork.cpp
./cmake/ProjectLibFF.cmake
./test/unittests/libdevcrypto/LibSnark.cpp
./test/unittests/libethcore/PrecompiledTest.cpp
./test/unittests/libethereum/ClientTest.cpp
./libdevcrypto/LibSnark.cpp
./libethcore/Precompiled.cpp

libethereum/ChainParams.cpp:

ChainParams::ChainParams()
{
	for (unsigned i = 1; i <= 4; ++i)
		genesisState[Address(i)] = Account(0, 1);
	// Setup default precompiled contracts as equal to genesis of Frontier.
	precompiled.insert(make_pair(Address(1), PrecompiledContract(3000, 0, PrecompiledRegistrar::executor("ecrecover"))));
	precompiled.insert(make_pair(Address(2), PrecompiledContract(60, 12, PrecompiledRegistrar::executor("sha256"))));
	precompiled.insert(make_pair(Address(3), PrecompiledContract(600, 120, PrecompiledRegistrar::executor("ripemd160"))));
	precompiled.insert(make_pair(Address(4), PrecompiledContract(15, 3, PrecompiledRegistrar::executor("identity"))));
}

[oberstet]

oberstet@thinkpad-t430s:~/scm/3rdparty/cpp-ethereum$ find ./lib* -type f -name *.cpp -exec grep -Hi "alt_bn128_G1_add" {} \; | grep -v "0000"
./libdevcrypto/LibSnark.cpp:pair<bool, bytes> dev::crypto::alt_bn128_G1_add(dev::bytesConstRef _in)
./libethcore/Precompiled.cpp:ETH_REGISTER_PRECOMPILED(alt_bn128_G1_add)(bytesConstRef _in)
./libethcore/Precompiled.cpp:	return dev::crypto::alt_bn128_G1_add(_in);
oberstet@thinkpad-t430s:~/scm/3rdparty/cpp-ethereum$ 
oberstet@thinkpad-t430s:~/scm/3rdparty/cpp-ethereum$ find ./lib* -type f -name *.cpp -exec grep -Hi "ecrecover" {} \; | grep -v "0000"
./libethcore/Precompiled.cpp:ETH_REGISTER_PRECOMPILED(ecrecover)(bytesConstRef _in)
./libethereum/ChainParams.cpp:	precompiled.insert(make_pair(Address(1), PrecompiledContract(3000, 0, PrecompiledRegistrar::executor("ecrecover"))));
oberstet@thinkpad-t430s:~/scm/3rdparty/cpp-ethereum$ 

[oberstet]

oberstet@thinkpad-t430s:~/scm/3rdparty/go-ethereum$ find . -type f -exec grep -Hi "alt_bn128" {} \; 
./cmd/puppeth/genesis.go:			Name: "alt_bn128_G1_add", StartingBlock: (hexutil.Uint64)(genesis.Config.ByzantiumBlock.Uint64()), Linear: &cppEthereumGenesisSpecLinearPricing{Base: 500},
./cmd/puppeth/genesis.go:			Name: "alt_bn128_G1_mul", StartingBlock: (hexutil.Uint64)(genesis.Config.ByzantiumBlock.Uint64()), Linear: &cppEthereumGenesisSpecLinearPricing{Base: 40000},
./cmd/puppeth/genesis.go:			Name: "alt_bn128_pairing_product", StartingBlock: (hexutil.Uint64)(genesis.Config.ByzantiumBlock.Uint64()),
./cmd/puppeth/genesis.go:	AltBnPairing *parityChainSpecAltBnPairingPricing `json:"alt_bn128_pairing,omitempty"`
./cmd/puppeth/genesis.go:			Name: "alt_bn128_add", ActivateAt: genesis.Config.ByzantiumBlock.Uint64(), Pricing: &parityChainSpecPricing{Linear: &parityChainSpecLinearPricing{Base: 500}},
./cmd/puppeth/genesis.go:			Name: "alt_bn128_mul", ActivateAt: genesis.Config.ByzantiumBlock.Uint64(), Pricing: &parityChainSpecPricing{Linear: &parityChainSpecLinearPricing{Base: 40000}},
./cmd/puppeth/genesis.go:			Name: "alt_bn128_pairing", ActivateAt: genesis.Config.ByzantiumBlock.Uint64(), Pricing: &parityChainSpecPricing{AltBnPairing: &parityChainSpecAltBnPairingPricing{Base: 100000, Pair: 80000}},
oberstet@thinkpad-t430s:~/scm/3rdparty/go-ethereum$ find . -type f -exec grep -Hi "ecrecover" {} \; 
./core/vm/contracts_test.go:// Benchmarks the sample inputs from the ECRECOVER precompile.
./core/vm/contracts_test.go:func BenchmarkPrecompiledEcrecover(bench *testing.B) {
./core/vm/contracts.go:	common.BytesToAddress([]byte{1}): &ecrecover{},
./core/vm/contracts.go:	common.BytesToAddress([]byte{1}): &ecrecover{},
./core/vm/contracts.go:// ECRECOVER implemented as a native contract.
./core/vm/contracts.go:type ecrecover struct{}
./core/vm/contracts.go:func (c *ecrecover) RequiredGas(input []byte) uint64 {
./core/vm/contracts.go:	return params.EcrecoverGas
./core/vm/contracts.go:func (c *ecrecover) Run(input []byte) ([]byte, error) {
./core/vm/contracts.go:	const ecRecoverInputLength = 128
./core/vm/contracts.go:	input = common.RightPadBytes(input, ecRecoverInputLength)
./core/vm/contracts.go:	// but for ecrecover we want (r, s, v)
./core/vm/contracts.go:	pubKey, err := crypto.Ecrecover(input[:32], append(input[64:128], v))
./core/types/transaction_signing.go:	pub, err := crypto.Ecrecover(sighash[:], sig)
./core/genesis.go:			common.BytesToAddress([]byte{1}): {Balance: big.NewInt(1)}, // ECRecover
./cmd/puppeth/genesis.go:		Name: "ecrecover", Linear: &cppEthereumGenesisSpecLinearPricing{Base: 3000},
./cmd/puppeth/genesis.go:		Name: "ecrecover", Pricing: &parityChainSpecPricing{Linear: &parityChainSpecLinearPricing{Base: 3000}},
./params/protocol_params.go:	EcrecoverGas            uint64 = 3000   // Elliptic curve sender recovery gas price
./p2p/discv5/node.go:	pubkey, err := crypto.Ecrecover(hash, sig)
./consensus/clique/clique.go:// ecrecover extracts the Ethereum account address from a signed header.
./consensus/clique/clique.go:func ecrecover(header *types.Header, sigcache *lru.ARCCache) (common.Address, error) {
./consensus/clique/clique.go:	pubkey, err := crypto.Ecrecover(sigHash(header).Bytes(), signature)
./consensus/clique/clique.go:	return ecrecover(header, c.signatures)
./consensus/clique/clique.go:	signer, err := ecrecover(header, c.signatures)
./consensus/clique/snapshot.go:	sigcache *lru.ARCCache        // Cache of recent block signatures to speed up ecrecover
./consensus/clique/snapshot.go:		signer, err := ecrecover(header, s.sigcache)
./internal/ethapi/api.go:// EcRecover returns the address for the account that was used to create the signature.
./internal/ethapi/api.go:// addr = ecrecover(hash, signature)
./internal/ethapi/api.go:// https://github.com/ethereum/go-ethereum/wiki/Management-APIs#personal_ecRecover
./internal/ethapi/api.go:func (s *PrivateAccountAPI) EcRecover(ctx context.Context, data, sig hexutil.Bytes) (common.Address, error) {
./internal/ethapi/api.go:	rpk, err := crypto.Ecrecover(signHash(data), sig)
./internal/web3ext/web3ext.go:			name: 'ecRecover',
./internal/web3ext/web3ext.go:			call: 'personal_ecRecover',
./internal/jsre/deps/web3.js:    var ecRecover = new Method({
./internal/jsre/deps/web3.js:        name: 'ecRecover',
./internal/jsre/deps/web3.js:		call: 'personal_ecRecover',
./internal/jsre/deps/web3.js:        ecRecover,
./contracts/chequebook/contract/chequebook.sol:        require(owner == ecrecover(hash, sig_v, sig_r, sig_s));
./crypto/signature_nocgo.go:// Ecrecover returns the uncompressed public key that created the given signature.
./crypto/signature_nocgo.go:func Ecrecover(hash, sig []byte) ([]byte, error) {
./crypto/crypto_test.go:	recoveredPub, err := Ecrecover(msg, sig)
./crypto/crypto_test.go:		t.Errorf("ECRecover error: %s", err)
./crypto/crypto_test.go:		t.Errorf("ECRecover error: %s", err)
./crypto/signature_test.go:func TestEcrecover(t *testing.T) {
./crypto/signature_test.go:	pubkey, err := Ecrecover(testmsg, testsig)
./crypto/signature_test.go:func BenchmarkEcrecoverSignature(b *testing.B) {
./crypto/signature_test.go:		if _, err := Ecrecover(testmsg, testsig); err != nil {
./crypto/signature_test.go:			b.Fatal("ecrecover error", err)
./crypto/signature_cgo.go:// Ecrecover returns the uncompressed public key that created the given signature.
./crypto/signature_cgo.go:func Ecrecover(hash, sig []byte) ([]byte, error) {
./crypto/signature_cgo.go:	s, err := Ecrecover(hash, sig)
oberstet@thinkpad-t430s:~/scm/3rdparty/go-ethereum$ 
oberstet@thinkpad-t430s:~/scm/3rdparty/go-ethereum$ subl ./core/vm/contracts.go

https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L49

// 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{},
}

[oberstet]

The core of the subject is about associating eth-secp256k1 and ed25519 public keys with each other by cross-signing, and then be able to check such cross-signatures within contracts.

On the classic EVM, this is too costly without a precompile. Adding one is what the task list below is about.

Another option would be eWASM, which could make such precompiles superfluous as it compiles to native code. However, it is currently unclear, if and when eWASM actually comes onto the street.

Task list:

1. EIP 665 and EIP 665 update PR
2. go-ethereum PR
3. pyethereum PR
4. parity PR
5. cpp-ethereum PR

Note: above is missing actual unit tests (test vectors) still - only the test skeletons are there.

[oberstet]

ok, from eth core devs chatting, we need 2 things to move this forward:

1. unit tests in the implementation PRs
2. a "common test" (consensus test) over all implementations https://github.com/ethereum/tests
3. make the implementations roughly "the same" from a computational cost perspective => benchmarks
4. verify choice of gas price 2000 for verify => benchmarks

we need to do in-depth verification that the different underlying implementations behave more or less exactly identical in all cases. Re consensus errors, python will reject input larger than 128 bytes

It relies on the relative cost of different operations being roughly the same on different clients.

the EIP 665 text could also be more precise:

• any input length != 128 is an error, and
• return value is 4 octets (little endian uint32) with 0 for success, 1 for invalid input and 2 for invalid signature

[oberstet]

rgd the choice of ed25519 implementation that can be trusted and that is available over all major eth clients:

• libsec256k1
• libsodium

seem good. for Python, above 2 libraries are available via CFFI wrappers:

• coincurve
• PyNaCl

then there is HACL, and a possible implementation based on that: https://gist.github.com/oberstet/ef534c0cd060d0b9bd15a9e4a2529efb

---

footprint (stripped) of libsec256k1 and libsodium shared libraries (here, builds used with Python/cffi).

• libsodium: 353,064 bytes
• libsecp256k1: 196,736 bytes

(cpy365_3) oberstet@thinkpad-t430s:~/scm/xbr/xbr-network$ ll /home/oberstet/cpy365_2/lib/python3.6/site-packages/nacl/_sodium.abi3.so
-rwxrwxr-x 1 oberstet oberstet 353064 Apr 15 06:43 /home/oberstet/cpy365_2/lib/python3.6/site-packages/nacl/_sodium.abi3.so*
(cpy365_3) oberstet@thinkpad-t430s:~/scm/xbr/xbr-network$ ll /home/oberstet/cpy365_2/lib/python3.6/site-packages/coincurve/_libsecp256k1.cpython-36m-x86_64-linux-gnu.so
-rwxrwxr-x 1 oberstet oberstet 196736 Apr 15 06:45 /home/oberstet/cpy365_2/lib/python3.6/site-packages/coincurve/_libsecp256k1.cpython-36m-x86_64-linux-gnu.so*
(cpy365_3) oberstet@thinkpad-t430s:~/scm/xbr/xbr-network$ 

[ofek]

@oberstet Hello there! Is anything blocking your use of coincurve?