Try   HackMD

Just Enough Elliptic Curve for Ethereum

The goal of this post is to get through just enough theory to understand the key generation process in Ethereum.

Ethereum also uses other elliptic curves for different use cases like validator signatures which is out of scope here.

Heavy inspiration has been taken from Martin Kleppmann's Tutorial on Elliptic Curve Cryptography and LeastAuthority's moonmath manual.

There may be errors and gaps in this post, so just use it for a broad understanding. Better resources, like the one linked above, are available if you're looking for a detailed description.

Prerequisites for Elliptic curves

Modular Arithmetic

  • Cryptography doesn't operate on real numbers or integers.
  • Computation is often performed modulo prime
    p
    .
  • Set of integers modulo
    p
    is
    Zp={0,1,2,,p1}=[0,p1]
  • This just means that for any calculation, you take the normal result
    r
    and take
    r%p
    .
  • Imagine a clock with
    {0,1,2,,p1}
    instead of
    1,2,11,12
    . So anything that overflows wraps around.

Abelian Group

  • It is a set
    E
    together with an operation
    . The operation combines two elements of the set, denoted
    ab
    for
    a,bE
    .
  • The operation must satisfy the following requirements:
    • Closure: For all
      a,bE
      , the result of the operation
      ab
      is also in
      E
      .
    • Commutativity: For all
      a,bE
      we have
      ab=ba
      .
    • Associativity: For all
      a,b,cE
      we have
      (ab)c=a(bc)
      .
    • Identity element: There exists an element
      eE
      , called the identity element or neutral element, such that for all
      aE
      we have
      ea=ae=a
      .
    • Inverse element: For every
      aE
      there exists an element
      bE
      such that
      ab=ba=e
      , where
      e
      is the identity element.

Examples of Abelian groups

Z={,100,99,,2,1,0,1,2,,99,100,} and the standard addition operator
+

  • Closure: Addition of any two integers is always an integer.
  • Commutative: For any two integers
    a,b:a+b=b+a
    .
  • Associativity: For any three integers
    a,b,c:(a+b)+c=a+(b+c)
    .
  • Identity element:
    e=0
    .
  • Inverse element: For any integer
    a
    ,
    a
    is the inverse element.

Zp={0,1,,p1}, and addition modulo
p

  • Closure:
    (a+b)%pZp
    .
  • Commutative:
    (a+b)%p=(b+a)%p
    .
  • Associativity: For any three integers
    a,b,c:(((a+b)%p+c)%p=(a+((b+c)%p))%p
    . This can be seen by simplifying both the sides as both of them are equivalent to
    (a+b+c)%p
    .
  • Identity element:
    e=0
    .
  • Inverse element: For any integer
    a
    ,
    pa
    is the inverse element.

Is

Z, an abelian group? Here
is the normal multiplication operator.

There are non-abelian groups which have to satisfy all the above properties except commutativity.

Order of a group
Number of elements in set

E is referred to as the order of that group.

Fields

Where in defining a group, we only need one set and one operator

(E,), finite fields requires one set and 2 operators
(E,+,)
. We call these operators addition and multiplication but they can be defined arbitrarily as long as all these properties are satisfied:

  • (E,+)
    is an abelien group with some identity element
    e
    . Let's call this identity element
    0
    . This is just a notation and this need not be the literal integer
    0
    .
  • The set
    E{0}
    (set
    E
    except the element
    0
    ) and the operator
    is an abelian group with an identity element denoted as
    1
    .
  • This distribution law is satisfied:
    a(b+c)=(ab)+(ac)
    .

Examples of fields

The set of all real numbers

R and the usual addition (
+
) and multiplication operator (
) form a field.

(Zp={0,1,,p1},+modp,modp) form a finite field (field with finite elements).

Cyclic groups

Take any group with set

E with an operator
and identify element
e
.

Take any element

aE, and consider the set:
{e,a,aa,aaa,}
. If we use the shorthand
a0=e
and
ak=aaa
(
k
times), the set can be written as:
{a0,a1,a2,a3,}
. That's why this set is often referred to as the set of power of
a
. These element are always in
E
due to closure property. Hence, the set of powers of
a
is a subset of
E
.

This new set is also a group (you can go through the properties) and is called a subgroup of

E generated by
a
. The order of the group element
a
is defined to be the number of elements in the subgroup generated by
a
.

If

E is finite, then this subgroup is also finite and hence
{a0,a1,a2,}
should start repeating at some point. Why? Consider the sequence
a0,a1,
and so on. Since it's a finite sequence, at some point point it will see a duplicate element, after which the subsequent elements will all be duplicate.

There can be cases where this subgroup is exactly equal to

E, which means
a
generates the entire group. When this happens, order of
a
is the same as the order of the group
E
.
a
is now called a generator of the group
E
, and
E
is called a cyclic group. The cyclic group
E
can be written as:
{a0,a1,,a|E|1};e=a0=a|E|

Exercise

Q1. Compute the inverse of

a when
a
is a generator of the group
E
.

A1. Since

a|E|1a=a0=e,
a|E|1
is the inverse of
a
.

Fact
Group

E with a prime number order is always cyclic. That means the group
Zp
is cyclic.

Finite field
Fp

From now on, we'll only consider a finite field

Fp defined as
(Zp,+modp,modp)
.

We want to implement addition, multiplication, subtraction and division on this finite field. We define addition as

+modp, multiplication as
modp
.

To do

ab, we can rewrite it as
a+(b)
. We can interpret
b
as the additive inverse of
b
. Hence,
b=pb
. Remember that
(Zp,+modp)
is an abelian group.

To do

a/b, we can rewrite it as
ab1
. Remember that
(Zp{0},modp)
is an abelian group. So, except for
b=0
(on which division isn't defined anyways), we can find
b1
(called multiplicative inverse because we are considering the multiplication operator).

Fact

b1=bp2
modp
; called Fermat’s little theorem.

Elliptic Curves

Finally!

Elliptic curve

E defined over
Fp
is an equation:
y2=x3+ax+b

where
a,bFp
satisfy
4a3+27b20
.

x and
y
has to be in
Fp
, and any
(x,y)
coordinate satisfying this equation belongs in
E
.

We now define

(E,+) as an abelian group by adding the identity element
O
(also called point at infinity). Remember that a group need not have only integers. Element can be anything as long as its properties are satisfied.

To define it as a group, we need to define

+. It's not the simple addition operator. We define this operator according to the Chord-and-tangent rule. I am not adding it here as it's not important for this high-level discussion, but you'll find plenty of resources online.

What you need to know is:

  • O
    is the identity element. That means for any
    P=(x,y)
    ,
    P+O=P
    .
  • Inverse of
    P=(x,y)
    is
    Q=(x,y)
    . That means
    P+Q=O
    . Note that if
    (x,y)
    satisfies the elliptic curve equation,
    (x,y)
    does too. Also, notice that if
    P
    is of the form
    (x,0)
    , it is its own inverse.
  • We have well-defined formula to calculate
    P+P
    and
    P+Q
    .

With this,

(E,+) becomes a finite and cyclic group. Let's denote the order of this group by
n
.

Scalar multiplication

Scalar multiplication is multiplying any non-negative integer

s with a group element
P
in
E
. So
sP=P++P
(
s
times).

If

P is a generator of
E
, you can derive all the group elements by going over different
s[0,n1]
.

secp256k1 curve used in Ethereum

Ethereum uses an elliptic curve called secp256k1 defined over the finite field

Fp (for public key generation). It's equation is:
y2=x3+7

  • with
    p=225623229282726241
    .
  • Order
    n
    of this elliptic curve group is 115792089237316195423570985008687907852837564279074904382605163141518161494337
  • A specific generator is picked
    G=(x,y)
    :
    x=
    55066263022277343669578718895168534326250603453777594175500187360389116729240
    y=
    32670510020758816978083085130507043184471273380659243275938904335757337482424

This curve is used for key generation and signatures (for example, transaction signing) in Ethereum.

This is how it looks when defined over real numbers:

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

There is no point in visualizing it over the field as there is no pattern there.

Private and public key generation for Ethereum

This is the process followed to generate keys for Ethereum:

  1. Generate a random scalar value
    sk[0,n1]
    . This becomes your secret key.
  2. sG
    becomes your public key.
  3. Hash the public key using keccak256 and take the last 20 bytes. This is the your Ethereum EOA address.

Given the value

sG, it is computationally hard to derive
s
from it, so consider this impossible for randomly generated secret key. Otherwise, anyone would be able to derive your private key from your public key and this time Ethereum (and much more) will actually break.

This is called the elliptic curve discrete logarithm problem.

Cryptographic signature

Given a message

m and a private key
privKey
(with corresponding public key
pubKey
):

  • S=Sig(m,privKey)
    is a byte sequence called "signature".
  • Verify(S,m,pubKey)
    returns true if the signature is correct, otherwise false.
  • It can be used for authentication.
  • Ethereum uses it for transaction authentication.
  • This can also be used in smart contracts. For example, ERC20 permits.
  • Specifically, ECDSA signature (a specific signature algorithm based on elliptic curves) is used by Ethereum for this purpose.

ECDSA signature

Heavily inspired from cryptobook.nakov.com.
Signature algorithm takes a message

m and a secret key
sk
and produces signature which is a sequence of bytes.

  1. Take a hash of your message
    m
    . When you issue a transaction on Ethereum, it is the JSON with fields like "to", "value", "data" and so on. Ethereum uses keccak256 hash which outputs a 256 bit output
    h
    .
  2. Generate a random scalar value
    k[1,n1]
    .
  3. Calculate
    kG
    and take its
    x
    coordinate. We denote it as
    r
    .
  4. Calculate
    s=k1(h+rsk)
    modn
    .
    • k1
      is a value such that
      kk1=1
      modn
      (you may know it as multiplicative inverse).
  5. (r,s)
    is your signature.

ECDSA verification

Verification algorithm takes the signature, message and a public key and verifies signature validity.

I'll defer the rest to this amazing post by Svetlin Nakov on cryptobook.

Further reading


There is always more nuance to add and more details to cover, but I hope this gives you a good idea on what's going on behind the scene when you create a key pair in your Ethereum wallet.

For feedback and errors, please reach out on Twitter @blockdeveth!