The application of Zero Knowledge Proofs (ZKPs) in the blockchain space needs little introduction. Whether we look at scalability solutions or onchain privacy,
ZKPs are almost always in the mix.
While planning to embark on another ZKP project, I set myself to reorganize my scripts for computing Elliptic Curve (EC) cryptography toy examples. This gave birth
to the node.js CryptoToys project, a collection of functions for computing points on a curve,
torsion points computation, support for degree2 extension fields and pairings computation. It's an educational tool. So once ready, I wanted a good example to
demonstrate CryptoToys in action, which is what this article is about.
Anyone learning ZKPs most likely came across the articles from Joshua Fitzgerald, a zeroknowledge cryptography researcher & protocol developer at Metastate.
His threepart series, named PLONK by Hand takes the reader through a PLONKbased
ZKP setup, proof creation, and verification. What makes Joshua's series awesome is his workings of cryptographic and other mathematical operations. By hand, of course!
So, my idea is to demonstrate how to cheat and use CryptoToys instead. I will only be covering the first article of Joshua's series, the proof setup. Here almost
every step can be computed using CryptoToys. If you like my article, I might write a follow up covering the proof and verification. You should consider this article
as an Appendix to Joshua's work, which hopefully will occasionally offer some additional insight.
Thus, to follow the rest of the article the following is required:
CryptoToys Repository
PLONK by Hand (Part 1: Setup)
Get Started with CryptoToys
CryptoToys requires node v14 or later. Start by cloning the repository and build the project:
git clone https://github.com/kaxxa123/cryptotoys.git
npm install
npm run build
Next, we can run the CryptoToys command line. Check the available commands using:
node ./build/index help
Let's take an example curve from Craig Costello's Pairings for beginners.
E: y^2 = x^3  5x + 8
over the finite field F_37
To get all the points run the command:
node ./build/index.js ecpoints fieldN 37 coeffA 5 coeffB 8
...and for the same curve over F_37^2, we get the points using:
node ./build/index.js ecipoints fieldN 37 coeffA 5 coeffB 8
This article won't use the commandline tool. It rather runs CryptoToys from the node console. We thus need to learn how CryptoToys is organized.
./build/toys.js

EC computations over finite fields of the type F_q. 
./build/itoys.js

EC computations over an extension field F_q^2. Only extension fields
having embedding degree 2 are supported. This is often the case when dealing with toy examples. 
./build/ptoys.js

Support for projective coordinates. 
./build/pairings.js

Pairings computations. 
In this article only ./build/toys.js
and ./build/itoys.js
are used.
An important parameter that is required by most functions, is the one describing the EC:
interface ECurve {
fieldN: number;
coeffA?: number;
coeffB?: number;
rorder?: number;
iSQR?: number;
}
fieldN
 the integer defining the finite field F_N
over which the group operations are computed.
coeffA
, coeffB
 the A
and B
coefficients defining the EC y^2 = x^3 + Ax + B
rorder
 the subgroup order over which G1
and G2
are defined.
iSQR
 the constant for customizing the degree 2 extension field. By default, iSQR = 1
, hence the extension
field is computed for i^2 = 1
. Setting iSQR
changes the isquared value of course.
Depending on the function being invoked some of the ECurve
properties may not be required.
PLONK Setup
We now turn our attention to the computations presented in PLONK by Hand. Here I will not repeat Joshua's explanation. We will jump from one computation to another, showing how each would be performed using CryptoToys.
Assuming you already cloned and built CryptoToys, it's time to fire node and import the necessary functions with:
let toys = require('./build/toys.js')
let itoys = require('./build/itoys.js')
We start by exploring the EC over F_101
, for which the ZKP is being set up.
E/F101: y^2 = x^3 + 3
Let's retrieve all points and determine the group cardinality.
// Define the EC and the finite field over which it will be computed
ec = {fieldN: 101, coeffA: 0, coeffB: 3}
// Retrieve all points
pts = toys.ecpoints(ec)
// Get the group cardinality
pts.length // Should return 102
ecpoints
returns an array of points. Each point is itself an array in the format [x, y]
.
Next, we compute all points for the generator (1,2) and discover the subgroup order.
// Discover the cyclic group for generator point (1,2)
toys.ecCycle(ec, [1,2], true)
// Returns:
// P = (1,2)
// 2P = (68,74)
// 3P = (26,45)
// 4P = (65,98)
// 5P = (12,32)
// 6P = (32,42)
// 7P = (91,35)
// 8P = (18,49)
// 9P = (18,52)
// 10P = (91,66)
// 11P = (32,59)
// 12P = (12,69)
// 13P = (65,3)
// 14P = (26,56)
// 15P = (68,27)
// 16P = (1,99)
// 17P = (0)
// Point (1,2) has order 17
Note how ecCycle
is fed the curve configuration, and the generator point as an [x, y]
array. The last flag simply enables verbose mode.
PLONK by Hand computes the embedding degree to be 2 and explains how the extension field must be defined using u^2= 2
. This is where the
iSQR
configuration comes into play.
Computations over an extension field require itoys.js
. To begin, let's see what happens when we work with the simplest extension field
definition (i^2 = 1
).
// CryptoToys works with the default extension i^2 = 1
// but let's set it explicitly for clarity.
// Here we want to see why we cannot work with i^2 = 1
// and should instead work with i^2 = 2
ec = {fieldN: 101, coeffA: 0, coeffB: 3, rorder: 17, iSQR: 1}
// Compute embedding degree
itoys.eciEmbeddingDegree(ec, true)
// Returns:
// Embedding Degree k = 2
// Let's discover the cardinality of #E/Fq^k
ipts = itoys.ecipoints(ec,true)
ipts.length // Should return 10202
// But does it satisfy this condition?
// order  #E/Fq^k
// Try retrieving the order 17 points for #E/Fq^k
tor17 = itoys.eciTorsion(ec,true)
// FAILED! with error 'r (17) is not a factor of #E (10202)'
The above functions simply take the EC configuration and a flag that enables a more verbose output. However,
note that eciEmbeddingDegree
and eciTorsion
both require the subgroup order to also be included (rorder
).
eciTorsion
fails as the extension field resulting from i^2 = 1
generates a group whose cardinality (10202) is not divisible
by the subgroup order (17).
Also if we look into the points returned by ecipoints
, note how each is now encoded as:
[[xa, xb],[ya, yb]]
. This is so, as each coordinate is in the form a + ib
.
Let's redefine the extension field to i^2 = 2
. This time, eciTorsion
succeeds as the new cardinality (10404)
is indeed divisible by the subgroup order.
// Repeat computations with i^2 = 2
ec = {fieldN: 101, coeffA: 0, coeffB: 3, rorder: 17, iSQR: 2}
itoys.eciEmbeddingDegree(ec, true) // k = 2
ipts = itoys.ecipoints(ec,true)
ipts.length // Should return 10404 (= 17*612)
tor17 = itoys.eciTorsion(ec,true)
tor17.length // Should return 289 (= 17*17)
Next, we discover the G1
and G2
subgroups. These are respectively the basefield and the trace zero subgroups obtainable by
applying the Frobenius trace map and antitrace map.
Indeed, we already got the G1
points on computing the cycle for generator (1,2)
. However, it is still interesting to see how the
unique points resulting on applying the trace map, generates G1
. As for G2
, this is obtained by applying the antitrace map.
// Apply the Frobenius Trace Map to all order17 points
// obtaining the set of unique points that compose G1
G1 = itoys.eciFrobeniusTrMap(ec, 2, tor17, true)
itoys.eciShowPoints(G1)
// Total Points 17: (0,0), (68,74), (68,27), (18,52), (18,49),
// (91,35), (91,66), (12,69), (12,32), (65,3), (65,98), (1,99),
// (1,2), (32,59), (32,42), (26,45), (26,56)
// Apply the AntiTrace Map to all order17 points
// obtaining the set of unique points that compose G2
G2 = itoys.eciAntiFrobeniusTrMap(ec, 2, tor17, true)
itoys.eciShowPoints(G2)
// Total Points 17: (0,0), (36,31i), (36,70i), (66,78i), (66,23i),
// (41,22i), (41,79i), (63,66i), (63,35i), (10,85i), (10,16i),
// (90,19i), (90,82i), (2,34i), (2,67i), (74,89i), (74,12i)
The eciFrobeniusTrMap
and eciAntiFrobeniusTrMap
both take as input the EC configuration, the embedding degree 2, the array of
points order17 and the verbosity flag.
Lastly, we compute the SRS points. Here PLONK by Hand picks a random secret s
and generators g1
and g2
. The
computations ultimately boil down to point multiplications.
SRS: s^0 g1, s^1 g1, s^2 g1, s^3 g1, s^4 g1, s^5 g1, s^6 g1 s^0 g2, s^1 g2
...where s = 2
, g1 = (1, 2)
and g2 = (36, 31i)
// Computing the SRS points
g1 = [[1,0], [2,0]]
g2 = [[36,0], [0,31]]
secret_s = 2
gates = 4
srsG1 = []
srsG2 = []
for (cnt = 0; cnt <= gates+2; ++cnt) {
srsPt = itoys.eciMultiply(ec, secret_s**cnt, g1)
srsG1.push(srsPt)
}
srsPt = itoys.eciMultiply(ec, secret_s, g2)
srsG2.push(g2)
srsG2.push(srsPt)
itoys.eciShowPoints(srsG1)
// Total Points 7: (1,2), (68,74), (65,98), (18,49), (1,99), (68,27), (65,3)
itoys.eciShowPoints(srsG2)
// Total Points 2: (36,31i), (90,82i)
Here eciMultiply
is fed the EC configuration, the integer multiplier s^x
, and a generator point.
We thus complete the set of computations necessary for the PLONK by Hand setup. CryptoToys includes a lot more functionality.
Hopefully today I showed you enough to try it out and maybe contribute to its improvement!
References
CryptoToys Repository
PLONK by Hand (Part 1: Setup)
Pairings for beginners  Craig Costello (2012)