Ed25519 precompile in eth clients

oberstet commented 6 years ago

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 commented 6 years ago

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:

oberstet commented 6 years ago

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:

https://github.com/ethereum/EIPs/pull/949

oberstet commented 6 years ago

Our EIP has been merged!

oberstet commented 6 years ago

next step: get it on the agenda of an ethereum core devs meeting: https://github.com/ethereum/pm/issues/36#issuecomment-377276162

oberstet commented 6 years ago

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

    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 commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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:

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

oberstet commented 6 years ago

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

unit tests in the implementation PRs
a "common test" (consensus test) over all implementations https://github.com/ethereum/tests
make the implementations roughly "the same" from a computational cost perspective => benchmarks
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 commented 6 years ago

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 commented 5 years ago

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

oberstet commented 5 years ago

@ofek coincurve doesn't support ed25519 as far as I see .. however, I am closing this issue anyways, as we don't need ed25519 at this point - and since EIP665 never got into production anyways

wamp-proto / wamp-xbr

Ed25519 precompile in eth clients #3