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](https://martin.kleppmann.com/papers/curve25519.pdf) and LeastAuthority's [moonmath manual](https://github.com/LeastAuthority/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 $\mathbb{Z}_p = \{0,1,2,\dots,p-1\} = [0,p-1]$
- This just means that for any calculation, you take the normal result $r$ and take $r\%p$.
- Imagine a clock with $\{0,1,2,\dots,p-1\}$ instead of $1,2\dots,11,12$. So anything that overflows wraps around.

### Abelian Group
- It is a set $E$ together with an operation $\cdot$. The operation combines two elements of the set, denoted $a\cdot b$ for $a,b \in E$.
- The operation must satisfy the following requirements:
- Closure: For all $a,b\in E$, the result of the operation $a\cdot b$ is also in $E$.
- Commutativity: For all $a,b \in E$ we have $a\cdot b = b\cdot a$.
- Associativity: For all $a,b,c\in E$ we have $(a\cdot b)\cdot c = a\cdot (b\cdot c)$.
- Identity element: There exists an element $e\in E$, called the identity element or neutral element, such that for all $a\in E$ we have $e\cdot a = a\cdot e = a$.
- Inverse element: For every $a\in E$ there exists an element $b\in E$ such that $a\cdot b = b\cdot a = e$, where $e$ is the identity element.

### Examples of Abelian groups
$\mathbb{Z}=\{\dots,-100,-99,\dots,-2,-1,0,1,2,\dots,99,100,\dots\}$ 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.

$\mathbb{Z}_p = \{0,1,\dots,p-1\}$, and addition modulo $p$
- Closure: $(a+b) \% p \in \mathbb{Z}_p$.
- 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$, $p-a$ is the inverse element.

:::warning
Is $\mathbb{Z}, \cdot$ an abelian group? Here $\cdot$ is the normal multiplication operator.
:::

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

:::info
**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,\cdot)$, *finite fields* requires one set and 2 operators $(E,+,\cdot)$. 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 \backslash \{0\}$ (set $E$ except the element $0$) and the operator $\cdot$ is an abelian group with an identity element denoted as $1$.
- This distribution law is satisfied: $a\cdot (b+c) = (a\cdot b) + (a\cdot c)$.

### Examples of fields
The set of all real numbers $\mathbb{R}$ and the usual addition ($+$) and multiplication operator ($\cdot$) form a field.

$(\mathbb{Z}_p=\{0,1,\dots,p-1\}, +\mod p, \cdot\mod p)$ form a finite field (field with finite elements).

### Cyclic groups
Take any group with set $E$ with an operator $\cdot$ and identify element $e$.

Take any element $a\in E$, and consider the set: $\{e, a, a\cdot a, a\cdot a\cdot a,\dots \}$. If we use the shorthand $a^0=e$ and $a^k=a\cdot a\cdot {\dots} \cdot a$ ($k$ times), the set can be written as: $\{a^0, a^1, a^2,a^3,\dots\}$. 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 $\{a^0, a^1, a^2,\dots\}$ should start repeating at some point. Why? Consider the sequence $a^0, a^1,\dots$ 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:
$$
\{a^0, a^1, \dots, a^{|E|-1}\}; e=a^0=a^{|E|}
$$

### Exercise
Q1. Compute the inverse of $a$ when $a$ is a generator of the group $E$.

A1. Since $a^{|E|-1} \cdot a = a^0 = e$, $a^{|E|-1}$ is the inverse of $a$.

:::info
**Fact**
Group $E$ with a prime number order is always cyclic. That means the group $\mathbb{Z}_p$ is cyclic.
:::

### Finite field $\mathbb{F}_p$
From now on, we'll only consider a finite field $\mathbb{F}_p$ defined as $(\mathbb{Z}_p, + \mod p, \cdot \mod p)$.

We want to implement addition, multiplication, subtraction and division on this finite field. We define addition as $+ \mod p$, multiplication as $\cdot \mod p$.

To do $a-b$, we can rewrite it as $a+(-b)$. We can interpret $-b$ as the additive inverse of $b$. Hence, $-b = p-b$. Remember that $(\mathbb{Z}_p, + \mod p)$ is an abelian group.

To do $a/b$, we can rewrite it as $ab^{-1}$. Remember that $(\mathbb{Z}_p\backslash \{0\}, \cdot \mod p)$ is an abelian group. So, except for $b=0$ (on which division isn't defined anyways), we can find $b^{-1}$ (called multiplicative inverse because we are considering the multiplication operator).

:::info
**Fact**
$b^{-1} = b^{p-2}$ $\mod p$; called *Fermat’s little theorem*.
:::

## Elliptic Curves
Finally!

Elliptic curve $E$ defined over $\mathbb{F}_p$ is an equation:
$$
y^2 = x^3 + ax + b
$$
where $a,b\in \mathbb{F}_p$ satisfy $4a^3+27b^2 \neq 0$.

$x$ and $y$ has to be in $\mathbb{F}_p$, and any $(x,y)$ coordinate satisfying this equation belongs in $E$.

We now define $(E,+)$ as an abelian group by adding the identity element $\mathcal{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:
- $\mathcal{O}$ is the identity element. That means for any $P=(x,y)$, $P+\mathcal{O}=P$.
- Inverse of $P=(x,y)$ is $Q=(x,-y)$. That means $P+Q=\mathcal{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+\dots+P$ ($s$ times).

If $P$ is a generator of $E$, you can derive all the group elements by going over different $s\in [0,n-1]$.

## secp256k1 curve used in Ethereum
Ethereum uses an elliptic curve called secp256k1 defined over the finite field $\mathbb{F}_p$ (for public key generation). It's equation is:
$$
y^2 = x^3+7
$$
- with $p=2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$.
- 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:
<img src="https://hackmd.io/_uploads/ByrWYE-rn.png" width="400" align="middle">

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\in [0,n-1]$. 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.
:::warning
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](https://twitter.com/RyanSAdams/status/1657719032865333249).

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](https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages).*
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\in [1,n-1]$.
3. Calculate $kG$ and take its $x$ coordinate. We denote it as $r$.
4. Calculate $s = k^{-1}(h + r*sk)$ $\mod n$.
- $k^{-1}$ is a value such that $k*k^{-1}=1$ $\mod n$ (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](https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages).

## Further reading
- For an easy to follow guide on Elliptic curve cryptography: https://martin.kleppmann.com/papers/curve25519.pdf.
- LeastAuthority's [moonmath manual](https://github.com/LeastAuthority/moonmath-manual), if you're interested in this topic and ZK.
- [BLS12-381 For The Rest Of Us](https://hackmd.io/@benjaminion/bls12-381) by Ben Edgington. It also has links to other awesome resources.
- If want to go hard, just read [Graduate Course in Applied Cryptography](http://toc.cryptobook.us) by Don Boneh and Victor Shoup.
- Lastly, read about [ECDSA footguns](https://github.com/0xbok/ecdsa-vuln-poc) by yours truly.
---

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](https://twitter.com/blockdeveth)!