Ethereum Signature Verification

But there’s the trouble. To get back the address of the originating account, you have to have both the signature and the original field values. If you supply different field values, you don’t get, “This signature doesn’t match,” you get, “This transaction came from a completely different account.”

Disclaimer: The views in this article are my own, and do not necessarily represent the views of my employer.

As part of the blockchain work I’ve been doing, I’ve been examining designs of the popular existing networks. Ethereum had my attention this week, and I was digging into its transaction authentication mechanisms when I found something confusing. I think it’s easiest to demonstrate with quick example.

Say I’m running a private network, and I submit a transaction to transfer value 1000 from one account to another. I can do that like this:

> eth.getBalance("0xaf4be85b32868c5b7c121115ad8cd93e0ad4f14e")
2025000000000000
> eth.getBalance("0xfab48eb52368c8b5c7211151dac89de3a04d1fe4")
0
> var tx = {"from": "0xaf4be85b32868c5b7c121115ad8cd93e0ad4f14e", "to": "0xfab48eb52368c8b5c7211151dac89de3a04d1fe4", "value": 1000};
undefined
> eth.sendTransaction(tx);
INFO [07-06|08:56:59] Submitted transaction fullhash=0x79c78bb2da3f61ddb2b55ffc89158b4ed0aa06917aa7f3d3813693e4da6deafb recipient=0xFAb48eb52368C8b5c7211151daC89DE3A04D1Fe4
"0x79c78bb2da3f61ddb2b55ffc89158b4ed0aa06917aa7f3d3813693e4da6deafb"

Once the transaction gets mined, I can see the value has moved:

> eth.getTransactionReceipt("0x79c78bb2da3f61ddb2b55ffc89158b4ed0aa06917aa7f3d3813693e4da6deafb").blockNumber
1
> eth.getBalance("0xaf4be85b32868c5b7c121115ad8cd93e0ad4f14e")
1646999999999000 // gas*gasPrice = 378000000000000
> eth.getBalance("0xfab48eb52368c8b5c7211151dac89de3a04d1fe4")
1000

And I can see the raw transaction:

> eth.getRawTransaction("0x79c78bb2da3f61ddb2b55ffc89158b4ed0aa06917aa7f3d3813693e4da6deafb")
"0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e880820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53"

A key component of blockchains is that every transaction is signed by its issuer, and meddling with the details of the transaction will be obvious to all parties. Let’s verify that. Let’s try to resubmit that transaction, and have it transfer value 1001, which requires modifying just one bit:

//              original: 0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e880820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53
// >---modified-bit-is-out-here-------------------------------------------------------modified bit---|
> eth.sendRawTransaction("0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e980820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53")
INFO [07-06|09:14:25] Submitted transaction fullhash=0xa06d51ff57bc41d33c812f08bdb65641db7581d97bd1d524fc8d0dd448a2aa9a recipient=0xFAb48eb52368C8b5c7211151daC89DE3A04D1Fe4
"0xa06d51ff57bc41d33c812f08bdb65641db7581d97bd1d524fc8d0dd448a2aa9a"

Why did we get a receipt? Surely we should have been told that transaction was invalid. Did it just get logged as a failure?

> eth.getTransactionReceipt("0xa06d51ff57bc41d33c812f08bdb65641db7581d97bd1d524fc8d0dd448a2aa9a").blockNumber
2

No. So did value move?

> eth.getBalance("0xaf4be85b32868c5b7c121115ad8cd93e0ad4f14e")
1646999999999000
> eth.getBalance("0xfab48eb52368c8b5c7211151dac89de3a04d1fe4")
2001

Kind of. Value was deposited in the target account, but wasn’t debited from the source account. Where did it come from?

> eth.getTransactionReceipt("0xa06d51ff57bc41d33c812f08bdb65641db7581d97bd1d524fc8d0dd448a2aa9a").from
"0xf2b40cc46f06f8d28a2b021851f721592b1f78e8"
> eth.getBalance("0xf2b40cc46f06f8d28a2b021851f721592b1f78e8")
1646999999998999 // started with the same balance as 0xaf4b...

That’s not the account debited in the original transaction. So, I guess it’s true that we weren’t able to replay that transaction with modifications. But what about this other account? It didn’t sign this transaction.

This is where I had to learn the details of how transaction signing works in Ethereum. To submit a signed transaction, your client must encode a string containing: nonce, gas price, gas limit, destination address, value, contract data, and chain ID. The exact encoding is irrelevant here, but those are the components of the transaction (see this post and EIP 155 for the full details). A representation (hash) of those values is passed to an elliptic curve signing function, along with your account’s private key. That function produces what is called a “recoverable signature”. This recoverable signature is added to the end of the previous list, and the resulting string is a “signed raw transaction”.

A signed raw transaction can be submitted to any Ethereum node, without that node needing to know the private key of the account submitting the transaction. Notice that the list of fields included doesn’t include the address of the account submitting the transaction. Anyone can recover that address using the signature and the original list of signed fields.

But there’s the trouble. To get back the address of the originating account, you have to have both the signature and the original field values. If you supply different field values, you don’t get, “This signature doesn’t match,” you get, “This transaction came from a completely different account.”

This is what happened in the example above. If we recover the address using the original values and signature, we get the address we used to sign the original transaction:

$ tools/ecrecover 0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e880820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53
Recovered: af4be85b32868c5b7c121115ad8cd93e0ad4f14e

But if we recover the address using the altered values and the signature, we get the other address:

$ tools/ecrecover 0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e980820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53
Recovered: f2b40cc46f06f8d28a2b021851f721592b1f78e8

Before you run off to tweet about this, let me say: trying to produce a set of field values to make some signature point to a particular account is not within the realm of your powers. I precalculated the account address that would match, and gave it value in my genesis block for the purposes of this demonstration. If I we try again with a value two greater, we get a completely different address that has no value:

$ tools/ecrecover 0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203ea80820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53
Recovered: c30d2d79cbb88531abeb585dcf4f4fcfbb4ce373
> eth.getBalance("0xc30d2d79cbb88531abeb585dcf4f4fcfbb4ce373")
0
> eth.sendRawTransaction("0xf86980850430e2340083015f9094fab48eb52368c8b5c7211151dac89de3a04d1fe48203ea80820348a0780d4ea898306e700cea578140cc4502d401c5949e7f4cab6a72c08a1a065aaba00cc22d63e2ef8acaaf1f6ead7a68de12e48a79f17d0a5ebab006fa996076ed53")
Error: insufficient funds for gas * price + value
at web3.js:3143:20
at web3.js:6347:15
at web3.js:5081:36
at :1:1

Trying to match a particular address is a process of mashing numbers hoping to accidentally hit one in 2160. Even if you just wanted to hit any in-use address, and each person alive on Earth had their own, you’d still be looking at one in 2127(=2160/233, 233 ≈ 8 billion).

So why do I care? Two reasons:

  1. Being corrected for the wrong mistake makes the protocol harder to use. The error above for the “two greater value” mismatch points a debugger toward balances, not toward signatures.
  2. Fixing this seems simple.

Number 2 is the naïve thing to say. If it’s so simple, why hasn’t it been done? It’s more likely that I just don’t understand the domain and/or design decisions made elsewhere. I’m going to trudge on with explaining anyway, and hope it leads to my education.

I think this can be fixed by including the originating address in the details that are signed. If what was signed was instead: nonce, gas price, gas limit, originating address, destination address, value, contract data, and chain ID; I think the problem would disappear entirely. We can try the same single-bit modification as last time:

# >---changes---------------------------------|-|---------added-from-address-----------|--------------------------------------------------------|---new-signature--->
$ tools/ecrecover 0xf87e80850430e2340083015f9094af4be85b32868c5b7c121115ad8cd93e0ad4f14e94fab48eb52368c8b5c7211151dac89de3a04d1fe48203e880820348a0a6ef55701d8b89007f729cbf0ff5abcabcfbf714017337c9ba3fd7d6fa9d22b1a05b2e8022f0a26f5928b7faa0aa94613328d9d6718a56cd4b951882e092467020
Recovered: af4be85b32868c5b7c121115ad8cd93e0ad4f14e
#          |-------------matches----------------^=|------------------------------------^
# >---modified-bit-is-out-here---------------------------------------------------------------------------------------------------------|
$ tools/ecrecover 0xf87e80850430e2340083015f9094af4be85b32868c5b7c121115ad8cd93e0ad4f14e94fab48eb52368c8b5c7211151dac89de3a04d1fe48203e980820348a0a6ef55701d8b89007f729cbf0ff5abcabcfbf714017337c9ba3fd7d6fa9d22b1a05b2e8022f0a26f5928b7faa0aa94613328d9d6718a56cd4b951882e092467020
Recovered: 8e80dee68fa86c07fe7753fad297a45ee0570eb0
#          |---------does not match-------------^=|------------------------------------^

But this time, we can compare the recovered address to the “from” address in the transaction. They don’t match, so we can say, “This signature doesn’t match.”

And hey, the “attack” gets harder too. It’s not as simple as just changing the from address in the transaction. If we do that, the recovered address also changes, to yet something different:

# >---changes-----------------------------------|----recovered-address-from-above------|---------------------value-is-still-modified---|
$ tools/ecrecover 0xf87e80850430e2340083015f90948e80dee68fa86c07fe7753fad297a45ee0570eb094fab48eb52368c8b5c7211151dac89de3a04d1fe48203e980820348a0a6ef55701d8b89007f729cbf0ff5abcabcfbf714017337c9ba3fd7d6fa9d22b1a05b2e8022f0a26f5928b7faa0aa94613328d9d6718a56cd4b951882e092467020
Recovered: 680d265d9d2c9654e02bd6d46b2db025058a6672
#          |---still-does-not-match-------------^=|------------------------------------^

With this scheme, to find a valid transaction, you’re forced to find a match for a specific address. So, as a side effect of improving usability, we also return to a collision probability of one in 2160.

Is it the case that EIPs 712 and 191 are attempting to address some of this situation, but not directly? It seems like “malleability” of ECDSA signatures, while perhaps slightly different than what is described above, is something that has caused trouble elsewhere.

Finally, thanks to the makers of two tools that helped me debug what was going on: Ethereumjs-tx, which includes a nice “from” recovery function, and Keythereum, which can extract a private key from a geth keystore.

Am I on track, or have I missed something? Let me know.