Path: csiph.com!aioe.org!eoyRQiYg/rXMvkXw3etlLg.user.gioia.aioe.org.POSTED!not-for-mail
From: Boris Dorestand <bdorestand@example.com>
Newsgroups: comp.programming,comp.misc,comp.lang.lisp
Subject: an ethereum ECDSA-difficulty
Followup-To: comp.programming
Date: Thu, 28 Jan 2021 16:35:05 -0300
Organization: Aioe.org NNTP Server
Lines: 207
Message-ID: <868s8c4zyu.fsf@example.com>
NNTP-Posting-Host: eoyRQiYg/rXMvkXw3etlLg.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
X-Notice: Filtered by postfilter v. 0.9.2
Cancel-Lock: sha1:6Ijxf2cM7i3iB84Vp32j1J/c6xc=
Xref: csiph.com comp.programming:11998 comp.misc:20467 comp.lang.lisp:34669

I know these groups aren't Ethereum-related, but I have failed to find
any Ethereum community out there that can shed any light on this.  (I
found many communities on the web in various places, but none that could
give me any directions on this.)  Maybe someone here has enough
understanding to investigate this with me.

Here's an Ethereum transaction which I built myself:

--8<---------------cut here---------------start------------->8---
0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a7640000802ea042bf4dc13103df95cc5d8af2e4dd00932086c29578ecce67e8b16ec99af70fdfa0cefb6ea512f7d46b36f10a3b437e9652e4747627c9ed9b2048161524f9352663
--8<---------------cut here---------------end--------------->8---

There is something wrong with it.  If I try to relay it to my Ethereum
node, it replies saying the sender is invalid.

out.rkt> (eth-send-raw-transaction "0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a7640000802ea042bf4dc13103df95cc5d8af2e4dd00932086c29578ecce67e8b16ec99af70fdfa0cefb6ea512f7d46b36f10a3b437e9652e4747627c9ed9b2048161524f9352663")
'#hasheq((error . #hasheq((code . -32000) (message . "invalid sender")))
         (id . 3)
         (jsonrpc . "2.0"))

Using the helpeth command-line tool, it also reports inability to check
the signature:

--8<---------------cut here---------------start------------->8---
%helpeth parseTx 0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a7640000802ea042bf4dc13103df95cc5d8af2e4dd00932086c29578ecce67e8b16ec99af70fdfa0cefb6ea512f7d46b36f10a3b437e9652e4747627c9ed9b2048161524f9352663
/usr/local/lib/node_modules/helpeth/node_modules/ethereumjs-tx/index.js:198
      if (!this.verifySignature()) throw new Error('Invalid Signature')
                                   ^
Error: Invalid Signature
    at FakeTransaction.getSenderPublicKey (/usr/local/lib/node_modules/helpeth/node_modules/ethereumjs-tx/index.js:198:42)
    at FakeTransaction.getSenderAddress (/usr/local/lib/node_modules/helpeth/node_modules/ethereumjs-tx/index.js:187:25)
    at Object.<anonymous> (/usr/local/lib/node_modules/helpeth/helpeth:348:56)
    at Module._compile (node:internal/modules/cjs/loader:1108:14)
    at Object.Module._extensions..js (node:internal/modules/cjs/loader:1137:10)
    at Module.load (node:internal/modules/cjs/loader:973:32)
    at Function.Module._load (node:internal/modules/cjs/loader:813:14)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:76:12)
    at node:internal/main/run_main_module:17:47
--8<---------------cut here---------------end--------------->8---

If we inspect the RLP-encoding (Recursive Prefix Length, see a reference
to this at the end of this message) of the transaction, here's what we
find:

--8<---------------cut here---------------start------------->8---
%helpeth rlpInspect 0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a7640000802ea042bf4dc13103df95cc5d8af2e4dd00932086c29578ecce67e8b16ec99af70fdfa0cefb6ea512f7d46b36f10a3b437e9652e4747627c9ed9b2048161524f9352663
The RLP encoded input consists of the following fields:
  0x01 (1)
  0x04a817c800 (20000000000)
  0x5208 (21000)
  0x79e4e5c6309eab8df0299973ef29ce2b001704a5 (possibly an address)
  0x0de0b6b3a7640000 (1000000000000000000)
  0x (0)
  0x2e (46)
  0x42bf4dc13103df95cc5d8af2e4dd00932086c29578ecce67e8b16ec99af70fdf (30190652438768558380735263684943397541547868147655542157485309011183437025247)
  0xcefb6ea512f7d46b36f10a3b437e9652e4747627c9ed9b2048161524f9352663 (93620689063899170013813414230496747665687050654128603934107115817203536307811)
%
--8<---------------cut here---------------end--------------->8---

The nonce is 1, the gas price is 20 gwei, the maximum gas units is
21000, the to-address is correct, the amount is 1 ether = 10^18 wei, the
data payload is empty, the v value of the signature is 46, as I intended
and the r, s values of the signature are precisely those I intended to
encode.  Everything looks perfectly as it should.

--8<---------------cut here---------------start------------->8---
out.rkt> r
30190652438768558380735263684943397541547868147655542157485309011183437025247
out.rkt> s
93620689063899170013813414230496747665687050654128603934107115817203536307811
--8<---------------cut here---------------end--------------->8---

The reason v = 46 is (due to EIP-155,
https://eips.ethereum.org/EIPS/eip-155) because this transaction is
meant for the Goerli test network, which has chainID = 5, so v = 0-or-1
+ 2*5 + 35 (by definition).  That makes v either 45 or 46.  It is 45
when the y-coordinate of r on the secp256k1 curve is even; otherwise it
is 46.  In this case, y is odd.  Here's y:

--8<---------------cut here---------------start------------->8---
y is odd
y = 97263189503256030944775998069009591544331988098129998739106059461942370082431
--8<---------------cut here---------------end--------------->8---

My code checks that y is indeed the square root of r^3 + 7 and it also
checks that the point (r^3 + 7, y^2) is on the curve.  So there
can't be any problems there, I think.

Ethereum does not use any special formatting for the signature.  It
defines that we are to send r, s encoded in RLP, that is, encoded as
big-endian bytes with no leading zeros.  We can see that this is
properly done in the rlpInspect command of helpeth.

However, recovery of the public key from the signature does need the
value v = 46 there (or v = 45, depending on r) along with r, s.  The
problem must be somewhere in v, r, s.

Here's another example that could be enlightening.  I encode the same
transaction but for mainnet (not Goerli) now.  The difference will be only
seen in v, r, s (because v depends on the chainID, which is 1 for
mainnet and not 5) and r, s change too because every time I sign, a new
ephemeral private key is used in the signing procedures.  Here's the new
transaction for mainnet:

--8<---------------cut here---------------start------------->8---
0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a76400008026a0086d7d973c6ce84204a9c92feaabeecb17e9496db573039d21e9536340f7c823a061fb8c437a7dc0e9eb946f2e98817ef1ee3e820031d0bf3874d1617b29b80207
--8<---------------cut here---------------end--------------->8---

Looking at it with helpeth, it is able to parse it this time:

--8<---------------cut here---------------start------------->8---
%helpeth parseTx 0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a76400008026a0086d7d973c6ce84204a9c92feaabeecb17e9496db573039d21e9536340f7c823a061fb8c437a7dc0e9eb946f2e98817ef1ee3e820031d0bf3874d1617b29b80207
Signed by: 0xd3a138b5098a2289550ff59454d0d699e83b7dbe
Nonce: 0x01
To: 0x79e4e5c6309eab8df0299973ef29ce2b001704a5
Value: 1000000000000000000 (1 ETH)
Data: 0x
Gas limit: 21000
Gas price: 20000000000 (20 Gwei)
Potential total transaction cost: 0.00042 ETH
Minimum required account balance: 1.00042 ETH
--8<---------------cut here---------------end--------------->8---

However, this is not quite correct.  The address that signed this
transaction is

--8<---------------cut here---------------start------------->8---
out.rkt> real-address
"3e21c651dfc21ee198bc2f735502eb82a2e8c4f0"
--8<---------------cut here---------------end--------------->8---

and not ``d3a138b5098a2289550ff59454d0d699e83b7dbe''.  This does suggest
that something is wrong involving v, r, s because helpeth is not able to
derive the public key properly from these values.  (I'm trusting helpeth
right now, but I began using it today.)

The signing private key is

  0x6e0811f6a74a20135dd515d32e337f163e084e1a02139dc41b33efa96e4f28d8

and we can confirm the correct address by deriving the public key,
computing its Keccak-256 hash, formatting it as a hex-string and keeping
the last 20 bytes, giving us 3e21c651dfc21ee198bc2f735502eb82a2e8c4f0.

I have checked (with a basic knowledge of ASN.1) that the numbers r, s
that I use are indeed in the bytes produced by my lower-level
crypto-interface to OpenSSL.

--8<---------------cut here---------------start------------->8---
signature: #"0D\2 \bm}\227<l\350B\4\251\311/\352\253\356\313\27\351Im\265s\3\235!\351Sc@\367\310#\2 a\373\214Cz}\300\351\353\224o.\230\201~\361\356>\202\0001\320\2778t\321a{)\270\2\a"
r = 3811955914335809906321639406407038345231693819676868261733215514491310557219
s = 44318792989541023118386825272377226684497402086368461384807702757712898556423
y is odd
y = 65707960067704166733376143728173268835536019097445456731784218952113748072321
v is 38
--8<---------------cut here---------------end--------------->8---

That ``#"0D\2..."'' is Racket's notation for byte-strings.  Here are all
the bytes contained in that signature:

--8<---------------cut here---------------start------------->8---
'(48 68 2 32 8 109 125 151 60 108 232 66 4 169 201 47 234 171 238 203 23
233 73 109 181 115 3 157 33 233 83 99 64 247 200 35 2 32 97 251 140 67
122 125 192 233 235 148 111 46 152 129 126 241 238 62 130 0 49 208 191
56 116 209 97 123 41 184 2 7)
--8<---------------cut here---------------end--------------->8---

You might think the problem is here because we have a header there and
sometimes a leading zero, sometimes a suffix.  (This is looking like
maybe BER encoding, I'm not sure.)  But keep in mind that Ethereum is
not seeing this format.  I extract r, s from this byte sequence and
encode r, s in the Ethereum way, which is RLP.  There can't be a
formatting misunderstanding on my part, apparently.

Inspecting the RLP-encoding, I find it all there as expected:

--8<---------------cut here---------------start------------->8---
%helpeth rlpInspect 0xf86c018504a817c8008252089479e4e5c6309eab8df0299973ef29ce2b001704a5880de0b6b3a76400008026a0086d7d973c6ce84204a9c92feaabeecb17e9496db573039d21e9536340f7c823a061fb8c437a7dc0e9eb946f2e98817ef1ee3e820031d0bf3874d1617b29b80207
The RLP encoded input consists of the following fields:
  0x01 (1)
  0x04a817c800 (20000000000)
  0x5208 (21000)
  0x79e4e5c6309eab8df0299973ef29ce2b001704a5 (possibly an address)
  0x0de0b6b3a7640000 (1000000000000000000)
  0x (0)
  0x26 (38)
  0x086d7d973c6ce84204a9c92feaabeecb17e9496db573039d21e9536340f7c823 (3811955914335809906321639406407038345231693819676868261733215514491310557219)
  0x61fb8c437a7dc0e9eb946f2e98817ef1ee3e820031d0bf3874d1617b29b80207 (44318792989541023118386825272377226684497402086368461384807702757712898556423)
--8<---------------cut here---------------end--------------->8---

So I can't so far find where the problem is.  Any advice will be very
appreciated.  Thank you.

(*) References

The crypto library I'm using, Racket's ``crypto'':
https://docs.racket-lang.org/crypto/pk.html

RLP encoding, Appendix B:
https://files.gitter.im/ethereum/yellowpaper/VIyt/Paper.pdf

Ethereum's Recursive Length Prefix in ACL2
https://arxiv.org/abs/2009.13769

My implementation of RLP uses the design of Alessandro Coglio in this
ACL2 paper above.  I could have flaws in my encoding too, since I ported
it to Racket.