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.
See pervious sections
Inputs and outputs to these circuits are arrays where each element of the array is less than
Find the implementation of base2^85 Adder here
Find the implementation of base2^85 Subtractor here
Find the implementation of base2^85 Multiplier here. The algorithm is basically standard long multiplication, where the carry is handled in the end.
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.
First, we must represent all the Ed25519 operations as polynomials so that they can be represented in the R1CS constraint model.
Let's start with point addition. Re-arranging the point addition equation discussed in the previous section, we get:-
x3 = x1y2 + x2y1 + (121665/121666)x1x2x3y1y2
y3 + (121665/121666)x1x2y1y2y3 = y1y2 + x1x2
Hence, if three points
(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.
Find the implementation of scalar multiplication here
Find the implementation of a single signature verification here
Find the implementation of a batch signature verification here