Electron Labs
Search…
Welcome to Electron Labs
ZK for Beginners
Intro to Circom
Circom ED25519
Overview
Maths of ED25519
Circom Implementation
Batch of Signatures
How to Integrate in your project?
Powered By GitBook
Maths of ED25519
ED25519 signature uses a curve and involves performing operations on this curve. Let's dive deeper.
All operations in this signature scheme are defined under modulo p where
p=2255−19p = 2^{255} - 19
The curve equation is defined as follows:-
ax2+y2=1+dx2y2 ax^2 + y^2 = 1 + dx^2y^2
where a = -1 and d = - 121665/121666
Base Point is defined as (Bx, By) where By = 4/5. Here the / operator represents the inverse modulo operation wrt p. Hence By = 4*mod_inverse(5,p) => By = 46316835694926478169428394003475163141307993866256225615783033603165251855960
Substitute By in the curve equation to calculate Bx = 15112221349535400772501151409588531511454012693041857206046113283949847762202

Defining Point Addition

Say you have two points P and Q on the curve. If we draw a straight line through P and Q, it will intersect the curve at another point R as shown in the diagram. When this happens, we say that R is the sum of points P and Q. This is how pt addition is defined. Now let’s calculate R given P and Q.
Point Addition on the Curve
Given that P + Q = R . R is calculated as follows:-
(x1,y1)+(x2,y2)=(x1y2+x2y11+dx1x2y1y2,y1y2−ax1x21−dx1x2y1y2)(x_1, y_1) + (x_2, y_2) = \left( \frac{x_1y_2 + x_2y_1}{1 + dx_1x_2y_1y_2}, \frac{y_1y_2 - ax_1x_2}{1-dx_1x_2y_1y_2} \right)
This formula is derived by finding a point R that lies both on the curve and on the straight line through P and Q. To see detailed derivation, see https://martin.kleppmann.com/papers/curve25519.pdf (although it's for a different curve, but the concept is the same)
The above equation can be re-arranged to a polynomial form (R1CS). Points that satisfy this polynomial will always satisfy the property P + Q = R

Defining Multiplication of a pt on the Curve

Given a point P on the curve, we define another point on the curve Q as the “scalar multiplication” of P and k such that Q =k*P where k is a constant under mod p. Scalar multiplication is defined as the repeated addition of pts:-
k=2,Q=P+Pk=4,Q=2P+2Pk=8,Q=4P+4P...k=256,Q=128P+128Pk=2, Q = P+P \newline k=4, Q = 2P + 2P \newline k=8, Q = 4P + 4P \newline ... \newline k = 256, Q = 128P + 128P
Hence, we can calculate Q in log(k) steps. Since max(k) < 2^255-19, we need to perform a max of log(2^255-19) ~ 255 steps to calculate a scalar multiple.

Verifying an ED25519 signature

Let’s see some definitions:-
The ED25519 key-pair consists of:
  • Private Key (integer under mod p) : privKey
  • Public key (curve point): pubKey = privKey * B where B is the base pt as defined above

Verification Algorithm

The ED22519 signature verification algorithm takes as input a text message msg + the signer's ED25519 public key pubKey + the ED25519 signature {R, s} and produces as output a boolean value (valid or invalid signature). Here s is a scalar, and R is a pt on the curve. ED25519 verification works as follows (with minor simplifications):
EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> valid / invalid
  1. 1.
    Calculate h = SHA512(R + pubKey + msg) mod q
  2. 2.
    Calculate P1 = s * B
  3. 3.
    Calculate P2 = R + h * pubKey
  4. 4.
    Return P1 == P2
Here q is the curve order. q = 2^252 + 27742317777372353535851937790883648493
In step one, you must be wondering how can we use pubKey as an input to SHA512 as pubKey is a curve point (not a scalar). pubkey in this step is represented as a "compressed" curve pt i.e only the y-coordinate. In step, 3, pubkey is used as a curve point.

References

EdDSA and Ed25519
Practical Cryptography for Developers
Circom ED25519 - Previous
Overview
Next - Circom ED25519
Circom Implementation
Last modified 2mo ago
Copy link
Edit on GitHub
Contents
Defining Point Addition
Defining Multiplication of a pt on the Curve
Verifying an ED25519 signature
References