Ronkathon: Learn Cryptography from First Principles

Ronkathon is a Rust implementation of a collection of cryptographic primitives inspired by Plonkathon. This is technical content aimed at demonstrating theoretical properties of applied cryptography alongside a concrete application in a programming language well-suited for cryptography.

Ronkathon is constructed from first principles so there is no assumed knowledge of external libraries or verbose dependancies (other than rand and itertools). Much of the code here is not optimized in efforts of mathematical transparency and simplicity.

This work serves as a toy implementation of cryptographic primitives to help cultivate an understanding of the implementation details — therefore, much of the code is not optimized, not secure, and is not intended for commercial use. We started with implementing primitives to build KZG proofs and then kept building additional primitives from there. An outline of this content is presented below.

Fields and their extensions Polynomials Elliptic Curves Elliptic Curve Pairings KZG Asymmetric Primitives Hashes Conclusion

Fields and their extensions

Finite Fields are a core primitive used extensively in cryptography. This library has a Finite Field module. We use this to define a field of prime order with , which we use as our base field in our KZG construction. Note that this prime came from Plonk by hand and has some nice properties such as:

The first curve group is defined over our base field. The library also supports the field extension . We use the extension (we will explain this rationale later in the elliptic curve section) for our KZG construction. It’s common to denote the curve group over the field extension as . In order to build the extensions in general, we needed a polynomial module.

Polynomials

Polynomials are a ubiquitous construction with many applications. We use our polynomial module for our extension fields, Reed-Solomon encodings, and polynomial commitment schemes. A polynomial commitment scheme is another core cryptographic primitive that allows a prover to commit to a polynomial in a way that its evaluations at any point can be efficiently verified by others, ensuring the polynomial’s integrity. This is used later in our KZG polynomial commitment scheme.

Elliptic Curves

Elliptic curves are beautiful primitives used both in asymmetric cryptography as well as zero-knowledge proofs. In asymmetric cryptography, elliptic curves provide a high level of security with relatively small key sizes, making them more efficient and faster than traditional methods like RSA. We also use elliptic curves in pairing-based cryptography with KZG proofs. We support a handmade curve library with elliptic curve point addition over a finite field. We use a pairing-friendly curve in our KZG commitments of the form . We say the number of points in the largest elliptic curve group is the scalar field of the elliptic curve.

For our KZG construction the base field is , and the scalar order of our curve group is .

Elliptic Curve Pairings

The pairing is described formally as a bilinear map that takes in two arguments:

a point in our first cyclic curve subgroup

a point in our second cyclic subgroup

and maps them to a third group such that a pairing:

The curves cyclic sub groups and are both of the of same order (e.g., they have the same scalar field which implies they are isomorphic). The pairing is a map between these different subgroups. If this is not immediately clear, that is okay — give it some time. We will go into more details.

Now that we have a rough idea of the abstract structure of a pairing, let’s look into how to construct pairing friendly curve groups.

To construct pairing friendly curves, we start by finding the first curve group’s scalar field. The scalar field of a curve is the curve order, or the amount of points in the cyclic group generated by our generator. For our curve group the scalar field is with our chosen generator . Now that we have the curve scalar field we can find the curves embedding degree.

The embedding degree is defined as the smallest number such that our curve order (size of scalar field) divides .

We can see that for , does not divide . But for , does divide , so the embedding degree of our first curve group is .

We then construct our extension field with this new embedding degree and our second curve group over this extension field. All of the elliptic curve points of order 17 can be found using coordinates from so it is convenient to work over . We have documented the pairing in detail in the repository.

KZG

In KZG, we need a trusted setup in the form of a structured reference string (SRS). We generate an SRS from the generators of our two isomorphic curve groups and . The SRS is a list of points on our two curves. The number of points in the SRS from is greater than or equal to the number of constraints we want to prove (degree of the polynomial we are proving), and the number of elements in the SRS from the second curve group is greater than or equal to the degree of our masking divisor polynomial. We then pick a random number in our curve scaler field and construct the SRS as:

and similarly:

where is both the number of gates and number of coefficients in our polynomial. Once we have the SRS, we can make commitments that are both binding and hiding for our polynomials assuming the setup was created properly. We first commit to our polynomial that we want to prove by multiplying the coefficients of our polynomial with the points in our SRS and then adding them together to get a single point in our first curve group.

where is the degree of our polynomial and is the coefficient of the polynomial. We then pick a value to evaluate our polynomial at with and the result of the evaluation of this polynomial . Note that our polynomial has the same order of our curve . We then commit to the evaluation and call the the result

The pairing check then takes these inputs and checks these two pairings are equal while utilizing the bilinear properties of the pairing to achieve multiplication, while preserving hiding properties.

Asymmetric Primitives

We also have implementations of some asymmetric cryptographic primitives (linked below) in which a different key is used to encrypt information than the key used to decrypt information. These primitives make up a good amount of public key infrastructure and are critical for blockchain accounts and wallets.

We have a simple implementation of Rivest, Shair, Alderman (RSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)

Hashes

We have support for both a Sha256 and a Poseidon Implementation (Thanks to our open source contributor Sambhav!). Hash functions are crucial in computing for ensuring data integrity, as they convert input data into a fixed-size string of characters that uniquely represents the original data. They are used in various applications such as data storage, digital signatures, and password management, providing efficient and secure ways to verify data without storing the original data. Poseidon is unique in that it falls into a new family of hash functions: Algebraic hash functions which have desired properties in constructing zero knowledge proofs.

Conclusion

Stay tuned as we continue to add primitives to the repository and feel free to reach out in the Telegram with any questions. We are actively exploring MPC primitives.