The application of Zero Knowledge Proofs (ZKPs) in the blockchain space needs little introduction. Whether we look at scalability solutions or on-chain 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 Crypto-Toys project, a collection of functions for computing points on a curve, torsion points computation, support for degree-2 extension fields and pairings computation. It's an educational tool. So once ready, I wanted a good example to demonstrate Crypto-Toys in action, which is what this article is about.

Anyone learning ZKPs most likely came across the articles from Joshua Fitzgerald, a zero-knowledge cryptography researcher & protocol developer at Metastate. His three-part series, named PLONK by Hand takes the reader through a PLONK-based 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 Crypto-Toys instead. I will only be covering the first article of Joshua's series, the proof setup. Here almost every step can be computed using Crypto-Toys. 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:

Crypto-Toys Repository
PLONK by Hand (Part 1: Setup)

 

Get Started with Crypto-Toys

Crypto-Toys requires node v14 or later. It may be included as a library in any node.js project using:

  npm i crypto-toys

Otherwise, one may clone the Crypto-Toys repository, build it, and run it interactively from the console. Here, I will be using this method. Start by cloning the repository and building the project:

  git clone https://github.com/kaxxa123/crypto-toys.git
  npm install
  npm run build

Next, we can run the Crypto-Toys command line. Check the available commands using:
node ./build/src/toyscli --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/src/toyscli ecpoints --fieldN 37 --coeffA -5 --coeffB 8

...and for the same curve over F_37^2, we get the points using:
node ./build/src/toyscli ecipoints --fieldN 37 --coeffA -5 --coeffB 8

This article won't use the command-line tool. It rather runs Crypto-Toys from the node console. We thus need to learn how Crypto-Toys is organized.

./build/src/toys.js	EC computations over finite fields of the type F_q.
./build/src/i-toys.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/src/p-toys.js	Support for projective coordinates.
./build/src/pairings.js	Pairings computations.

In this article only toys.js and i-toys.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 sub-group 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 i-squared 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 Crypto-Toys.

Assuming you already cloned and built Crypto-Toys, it's time to fire node and import the necessary functions with:

let toys = require('./build/src/toys.js')
let itoys = require('./build/src/i-toys.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 sub-group 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 i-toys.js. To begin, let's see what happens when we work with the simplest extension field definition (i^2 = -1).

// Crypto-Toys 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 sub-group 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 sub-group 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 sub-group 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 sub-groups. These are respectively the base-field and the trace zero sub-groups obtainable by applying the Frobenius trace map and anti-trace 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 anti-trace map.

// Apply the Frobenius Trace Map to all order-17 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 Anti-Trace Map to all order-17 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 order-17 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. Crypto-Toys includes a lot more functionality. Hopefully today I showed you enough to try it out and maybe contribute to its improvement!

 

References

Crypto-Toys Repository

PLONK by Hand (Part 1: Setup)

Pairings for beginners - Craig Costello (2012)