<!-- Elliptic curves and ZK security -->

<!-- 给出基本定义 曲线形式 ZK安全性关系 以及zkBLS tendermint等方案 through 解决方案

安全那一张讲public key private key等 ecdh

pairing 给概念 也给图 -->

This article discusses the security foundations of ZK and elliptic curve-related concepts such as pairing, while also exploring ZK schemes related to BLS signatures and light clients.

# Elliptic curves

As one of the most important representative of algebraic curves, elliptic curves contain a large quantity of deep mathematical knowledge. Here we briefly introduce the basic concepts and some rare appeared notations could be found in the textbook of algebraic geometry without detailed explanations.

**Elliptic curves are projective curves of genus 1 having a specified base point.**

Projective space initially appeared through the process of adding
points at infinity, as a method to understand the geometry of
projections. Suppose a field $K$, and its algebraic closure $\overline{K}$, we give its general definition below:

**Projective space**
The projective space of dimension $n$, denoted by $\mathbb{P}^n$ or $\mathbb{P}^n(\bar{K})$, is the set of all $(n+1)$-tuples
$(x_0,\dots,x_n) ∈ \bar{K}^{n+1}$, such that $(x_0,\dots,x_n) ≠ (0,\dots,0)$, taken modulo the equivalence relation $(x_0,\dots,x_n) \sim (y_0,\dots,y_n)$ if and only if there exists $λ\in\bar{K}$ such that
$x_i=λ_iy_i$ for all $i$.

The equivalence class of a projective point $(x_0,\dots,x_n)$ is customarily denoted by $(x_0:\cdots:x_n)$. By fixing arbitrarily the coordinate $x_n=0$, we define a projective
space of dimension $n-1$, which we call the space at infinity; its points are called points at infinity.

**Weierstrass equation**

<!-- Mathematicians' study of elliptic curves throughout the last century has resulted in a rich and fascinating history. These curves have been applied to solve various mathematical problems, including Fermat's last theorem. The elliptic curve's ability to construct a group structure is advantageous for implementing public-key cryptography(PKC). The difficulty of finding discrete logarithms in a group, due to the absence of a sub-exponential time algorithm, makes the elliptic curves a preferred choice for systems based on the multiplicative group for the finite field. In practical applications, Elliptic curve cryptography(ECC) is utilized for its compact implementation and high performance. The Weierstrass equation is the fundamental concept behind ECC, as discussed below. -->

A Weierstrass equation over $K$ is an equation of the form given in

\begin{equation}
y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6
\end{equation}
where $a_i \in K$ and $1 \le i \le 6$.

We generally suppose that the field $K$ has characteristic different from $2$ and $3$, which would greatly simplify the representation of an elliptic curve.

**An elliptic curve defined over $K$** is the locus in $\mathbb{P}^2(\bar{K})$ of an equation:

$Y^2Z = X^3 + aXZ^2 + bZ^3$ , with $a,b∈K$ and $4a^3+27b^2\ne0$.

The point $(0:1:0)$ is the only point on the line $Z=0$; it is called the point at infinity of the curve. By defining the coordinates $x=X/Z$ and $y=Y/Z$, we equivalently define the elliptic curve as the locus of **the equation** **$y^2 = x^3 + ax +b$** plus the point at infinity $\mathbb{O}=(0:1:0)$.

In characteristic different from $2$ and $3$, we can show that any projective curve of genus $1$ with a distinguished point $\mathbb{O}$ is isomorphic to a Weierstrass equation by sending $\mathbb{O}$ onto the point at infinity $(0:1:0)$. Since any elliptic curve is defined by a cubic equation, Bezout's theorem tells us that any line in $\mathbb{P}^2$ intersects the curve in exactly three points, taken with multiplicity. We define a group law by requiring that three co-linear points sum to zero.

## **Group law**

Let $E\;:\;y^2=x^3+ax+b$ be an elliptic curve. Let $P_1=(x_1,y_1)$
and $P_2=(x_2,y_2)$ be two points on $E$ different from the point at
infinity, then we define a composition law $⊕$ on $E$ as
follows:

* $P ⊕ \mathbb{O} = \mathbb{O} ⊕ P = P$ for any point $P∈E$;

* If $x_1=x_2$ and $y_1=-y_2$, then $P_1⊕P_2 = \mathbb{O}$;
* Otherwise set a slope parameter λ =
\begin{cases} \frac{y_2-y_1}{x_2-x_1} &\text{if $P≠Q$,}\\ \frac{3x_1^2+a}{2y_1} &\text{if $P=Q$,}
\end{cases}

then the point $(P_1⊕P_2)=(x_3,y_3)$ is defined by
\begin{align*}
x_3 &= λ^2 - x_1 - x_2,\\
y_3 &= -λx_3 - y_1 + λx_1.
\end{align*}

Below we give examples for elliptic curves over $\mathbb{Q}$


The above law defines an Abelian group, thus we will simply write $+$ for $⊕$. The $n$-th scalar multiple of a point $P$ will be denoted by $[n]P$. When $E$ is defined over $k$, the subgroup of its rational points over $K$ is customarily denoted $E(K)$. The smallest positive integer $q$ such that $qP=\mathbb{O}$ is known as the order of point $P$. The points $<O,P,2P,3P,..(q-1)P>$ form a group generated by $P$, denoted as $< P>$.

**Torsion group**
A torsion group on an elliptic curve plays a primary role in understanding the concept of Pairing-based cryptography(PBC).

Suppose an elliptic curve $E$ and a positive integer $q$, we define the $q$-torsion group of $E$ by $E[q]$, that is defined as

$$ E[q] = \{P \in E(K)| [q]P=\mathbb{O}\}$$

It can be seen that if $P,Q \in E[q]$ then $P+Q \in E[q]$ and $-P \in E[q]$. Thus, $E[q]$ is said to be a subgroup of $E$. Here, $P=E(K)$ is represented as the point $P$ lies on the particular field $K$, like $\mathbb{Q}$ or $\mathbb{R}$ and $\mathbb{F}_p$. The torsion group has the following structure:

* $E[q] ≃ (ℤ/qℤ)^2$ if the characteristic of $K$ does not divide $q$;
* If $p>0$ is the characteristic of $K$, then $E[p^i]$ $≃$
\begin{cases}
ℤ/p^iℤ & \text{for any $i≥0$, or}\\
\{\mathbb{O}\} & \text{for any $i≥0$.}
\end{cases}

For curves defined over a field of positive characteristic $p$, the case $E[p]≃ℤ/pℤ$ is called ordinary, while the case $E[p]≃\{\mathbb{O}\}$ is called supersingular.

**Elliptic Curve over Finite Field**
A finite field is a set of a finite number of elements, for example, the set of integer modulo prime number p, denoted as $\mathbb{Z}_p$ or $\mathbb{F}_p$ or $\mathbb{GF}(p)$ is the finite fields. The finite field $\mathbb{F}_p$ have $p$ elements from $0$ to $(p-1)$. It is noted that the value of p must be prime; otherwise, it will not be a field as it does not have the multiplicative inverse of all integers. For example, a set of integer modulo 14 is not a field because 4 has no multiplicative inverse in the field.

The elliptic curves E over finite fields $\mathbb{F}_p$, denoted as $E(\mathbb{F}_p)$, hold the required properties to form an abelian group structure. The total number of points in a group is called the order of that group, denoted as $\#E(\mathbb{F}_p)$. We have the following estimate with Hasse's theorem:
$$|\#E(\mathbb{F}_p) - p - 1| ≤ 2\sqrt{p}.$$

For a larger prime, Schoof’s algorithm computes the order of the prime field which is run in polynomial time $O(logp)$.

**Embedding degree**
Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}_{p^k}$, and let $r$ be a prime dividing $\#E(\mathbb{F}_p)$. The embedding degree of E with respect to $r$ is the smallest value of$k$such that $r$ divides $p^ {k-1}$ but does not divide $p^{i-1}$ for all $0 < i < k$.

**Ed25519 signature**
Elliptic curves could have many forms, such as Weierstrass, Montgomery and twisted Edwards. They could be transferred by mappings of their rational points. We briefly introduce Curve25519 and its signature scheme below.

Ed25519 is defined over $F_q$ with the following equation and parameters:
$$ax^2+y^2 = 1+dx^2y^2$$


The Ed25519 signature scheme has three steps: key generation, signing and verification.


For verification, it takes the public key $A$ and the message $m$(denoted as $M$ below) as inputs and tries to verify the signature $(R,S)$:


**Notification:** Ed25519 and ECDSA are for digital signature schemes, while Curve25519 and P-256 are for key exchange schemes.

## **Pairing**

It is essential to introduce divisor class group for clarifying the definition of pairing on elliptic curves, including the Tate pairing and Weil pairing. We won't expand the deep mathematical knowledge here and only introduce the critical terminology.


With the definition of torsion group, we could explain $\mathbb{G}_1$ and $\mathbb{G}_2$ under a small example:


Below we introduce some important notations in pairing-based cryptography:


# **Security**

(Discrete Logarithm): Let $G$ be a cyclic group generated by an element $g$. For any element $A∈G$, we define the discrete logarithm of $A$ in base $g$}, denoted $\log_g(A)$, as the unique integer in the interval $[0,\#G]$ such that $g^{\log_g(A)} = A$.

We know algorithms to compute discrete logarithms in a generic group $G$ that require $O(\sqrt{q})$ computational steps, where $q$ is the largest prime divisor of $\#G$; we also know that these algorithms are optimal for abstract cyclic groups. For this reason, $G$ is usually chosen so that the largest prime divisor $q$ has size at least $\log_2 q ≈ 256$.

However, the proof of optimally does not exclude the existence of better algorithms for specific groups $G$. When $G$ is the abelian group of elliptic curves, the best algorithm is parallel Pollard Rho which is of exponential complexity; When $G$ is the multiplicative group of finite fields $F_{p^k}$, the best algorithm is the variants of number field sieve, which is of sub-exponential complexity.


## **Secure parameters**
The security of pairing-based cryptographic protocols depends on the hardness of DLP on elliptic curve $E(\mathbb{F}_p)$ of order $r$ and finite field extension $\mathbb{F}_{p^k}$ of order $p$. Both problems are defined on their group order, so a new parameter denoted as $\rho$, evaluates the closeness of size of subgroup $r$ w.r.t. the size of field $p$, given below:

\begin{equation}
\rho = \frac{{\log(p)}}{{\log(r)}}
\end{equation}

A general guideline for these parameters are in the following table:


Relevant (tower) number field sieve records are far from these secure parameters:


To choose a pairing-friendly curve, it is necessary to satisfy the three conditions:
* The subgroup of order $r$ is large enough so that Pollard’s rho method for solving DLP is hard
* The embedding degree $k$ is big enough so that the index calculus method for computing DLP in $\mathbb{F}_{p^k}$ is equally hard as in $E(\mathbb{F}_p)$
* $k$ is relatively small enough so that the arithmetic (pairing) in $\mathbb{F}_{p^k}$ is easily computable.

**BLS signature**
Not exactly the same name as BLS-curve, BLS signature has the following procedures:

It is different from ECDSA signature in the following:


# ZK PoS & Tendermint Light Client


There are generally three types of nodes in Ethereum:
* Validator: build, propose, and agree on valid blocks
* Full Node: download the entire block, including headers and transactions; can self-verify blocks and applies state changes
* Light Client: download only block headers; can verify Merkle proof to check for transaction inclusion; need to “trust” other nodes on consensus for transaction data

The ZK circuit for the Ethereum PoS light client mainly consists of 2 sub-circuits：
* The SSZ Sync Committee Commitment circuit that updates the SSZ commitment for the 512 current validators in the sync committee, which rotates every 27 hours
* The aggregate BLS12-381 signature verification for the 512 validators, which mainly conducts hash-to-curve calculations and BLS12-381 pairing over the scalar field of BN254.

For ZK-BLS, the existing codebase or techniques are the following:
* Nova: https://hackmd.io/@wrinqle/rye7Dju92
* Halo2: https://github.com/DelphinusLab/halo2ecc-s
* gnark: https://github.com/celer-network/brevis-circuits

Take Brevis's gnark implementation for an example, the benchmark results for Ethereum PoS Light-client Circuit implementation on a Linux server with 384GB memory and 20 cores@2.3GHz are the following:


## Brevis & ZK Tendermint
Brevis is a smart Zero-Knowledge (ZK) coprocessor for blockchains that enables dApps to access, compute, and utilize arbitrary data across multiple blockchains in a completely trust-free way.

They put the Ed25519 verification circuit into an on-chain Tendermint light client contract based on Tendermint-sol. The light client first verifies a protobuf-serialized Tendermint block header by performing basic checks that are not particularly computationally intensive. It then delegates the validation of validator signatures to the Ed25519 verification contract. In the current simplified implementation, the circuit validates signatures from 2/3 of the validators in a single proof with a constant estimated proof verification cost of 300k gas. The benchmark results on the same machine above are the following:


<!--
a + b = c
# jshgk
hsdfjh
### smdjhgfkjs

$$ \alpha $$

$$ \begin{aligned}
f(x) &= a+ b \\
&= c+ d
\end{aligned}
$$ -->