We will now discuss how we can define the Ed25519 maths in the R1CS model, by using Circom. We will then use SnarkJS to generate zk-proofs of Ed25519 signatures. This section assumes a working knowledge of zk-snarks and Circom/SnarkJS.

### Step 1: Define representation in large numbers

See pervious sections

### Step 2: Defining adder, multiplier, and modulus in base 2^85

Inputs and outputs to these circuits are arrays where each element of the array is less than `2^85`

Find the implementation of base2^85 Adder here

#### Subtractor

Find the implementation of base2^85 Subtractor here

#### Multiplier

Find the implementation of base2^85 Multiplier here. The algorithm is basically standard long multiplication, where the carry is handled in the end.

#### Modulus

Find the implementation of base2^85 Modulus here. This template takes a base2^85 array as input and applies modulo `p = 2^255 - 19`. In the code, `p` is also represented as base2^85.

### Step 3: Defining Ed25519 Point Addition in Circom

First, we must represent all the Ed25519 operations as polynomials so that they can be represented in the R1CS constraint model.

x3 = x1y2 + x2y1 + (121665/121666)x1x2x3y1y2
y3 + (121665/121666)x1x2y1y2y3 = y1y2 + x1x2

Hence, if three points `(x1, y1)`, `(x2, y2)` and `(x3,y3)` satisfy these two polynomials, we can say that the third point is the sum of the first two points.

In our circom implementation, rather than using cartesian coordinates, we use the radix format as defined in the reference implementation (given here). This changes the polynomials a bit, but the core logic is the same. Please see the code here.

### Step 4: Defining Ed25519 Scalar Multiplication in Circom

Find the implementation of scalar multiplication here

### Step 5: Defining Full Signature Verification in Circom

Find the implementation of a single signature verification here

### Step 5: Defining Batched (Multi) Signature Verification in Circom

Find the implementation of a batch signature verification here