ronkathon
Ronkathon is an implementation of plonkish KZG-based proofs. It is inspired by the common python plonkathon repository, and plonk-by-hand. We use the same curve and field as plonk-by-hand (not secure), and are working towards building everything from scratch to understand everything from first principles.
We have found the following resources helpful in understanding the foundational mathematics behind this implementation. After going through these, you should be able to understand the codebase. In order it is recommended to understand:
- Finite Fields
- Extension Fields
- Elliptic Curves over Fields and Extension Fields
- Embedding degree
- Polynomials
- FFTs
- Pairings
Lets start simple with a finite field and work up to creating two elliptic curve groups that have a pairing or bilinear map (more on that later).
First lets pick a finite field of prime order
- finite field
$F_{101}$ - curve
$y^2=x^3+3$ Initially this elliptic curve is just a continuous squiggle, which isn't the most useful. But we can make it discrete by constraining it's points to reside in the field. Now it doesn't look like the squiggle we know and love but instead a lattice (you can see here by switching from real numbers to finite fields ).
Now we have a set of discrete points on the curve over the finite field that form a group, a group has a single operation called the group operation, it is perhaps more abstract than a field. The group operation on this set of curve points is point addition which we all know and love with the squiggly lines, intersections and reflections. From this group operation we can create point doubling, and as a result, scalar multiplication (how many times do we double a point) as handy abstractions over the single group operation.
To review we have a curve group call it
Now to create a pairing friendly curve we first must find the curve groups order.
The order is how many times do we double the generator to get the generator again, the reason we can do this is because our group is cyclic.
Now if our base field
The next step is to construct a field extension from the first field such that
The next step is to construct the structured refrence string SRS with g1 and g2. The structured refrence string is generated by multiplying the generator points by some randomness
TODO: Talk more about plonk.
Commit to a polynomial using the g1_SRS: This is done by multiplying the polynomial coefficients by the g1_SRS points (scalar multiplication in the curve group) and adding the resulting points to each other to get a single point that represents the commitment call it p_commit
.
Opening involves choosing a point to evauluate the polynomial at and dividing the polynomial by .... (need the notes for this). the resulting polynomial is also combined with the g1_SRS to get a new commitment curve point call it q_commit
.
Then we do the pairing check.
- A gentle introduction to Fast Fourier Transforms over Finite Fields
- Introduction to Pairings
- KZG introduction by dankrad
- Pairings in depth
- Plonk by Hand P1
- Plonk by Hand P2
To see computations used in the background, go to the math/
directory.
From there, you can run the .sage
files in a SageMath environment.
In particular, the math/field.sage
computes roots of unity in the PlutoField
which is of size 101. To install sage on your machine, follow the instructions here. If you are on a Mac, you can install it via homebrew with brew install --cask sage
.
Licensed under your option of either:
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.