Mathematics of Zero-Knowledge Proofs

This page will provide resources and additional information for you to study the Preliminaries of ZKP.

PreviousWhy ZK?NextOPTIONAL: Advanced Resources

Last updated 9 months ago

Mathematics of Zero-Knowledge Proofs

This page will provide resources and additional information for you to study the Preliminaries of ZKP.

Cryptography_?

All mathematics is divided into three parts: cryptography (paid for by CIA, KGB and the like), hydrodynamics (supported by manufacturers of atomic submarines), and celestial mechanics (financed by military and other institutions dealing with missiles, such as NASA).

Cryptography has generated number theory, algebraic geometry over finite fields, algebra, combinatorics and computers.

Hydrodynamics has procreated complex analysis, partial differential equations, Lie groups and algebra theory, cohomology theory and scientific computing.

Celestial mechanics is the origin of dynamical systems, linear algebra, topology, variational calculus and symplectic geometry.

-Vladimir I. Arnold

Until now, Zero-Knowledge proofs are explained in a practical sense. Actually, every concept we explained to you was a part of applied cryptography.

If you heard about Bitcoin and , then you are aware of some topics of computer science and cryptography such as hash function and .

You might ask: 'I am coming from ... Chain ecosystem, why am i supposed to know topics like Finite Fields, Merkle Tree, Witneess etc. to write a smart contract or any app?'

This will end up with an interesting and counter-intuitive answer: Smart contracts or apps in Mina protocol in general are not like some applications that are/will executed inside of a some VM in Mina blockchain. Actually, what you write as a Smart Contract ends up to be converted to a 'ZK Circuit' (we mentioned that before, you remember that right?). The code you write goes through some process to be circuitifed - a.k.a. getting transformed to a set of constraints.

Okay - enough gabbing, right? Now i would suggest you to learn some fundamental mathematics of cryptography from , chapter 5. Feel free to look at other topics, but the topics after chapter 6 can be pretty mathematical and hard to understand if you were a little away from mathematics.

Introduction to Math & Terminology

If you are already familiar with the topics, you can just pass this part. Otherwise, please study following resources just to get the intuition of the structures. You are not supposed to be the master of the mathematical background of Zero-Knowledge, yet it is a must to learn them in order to build ZkApps with them.

Finite Fields

Security: Cryptography needs hard problems ensuring security of the system. The most widely used, , ensures that there is a hard computation that is resistat for attacks.
Finite Field properties: There are operations and algebraic structures that enable finite fields to be used in an efficient and secure way to create functions/structures like encryption techniques and digital signatures.

import {
  Field,
} from 'o1js';

/* This file demonstrates the classes and functions available in o1js */

/* # Field */

/* The most basic type is Field, which is an element of a prime order field.
   The field is the [Pasta Fp field](https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/) 
   of order 28948022309329048855892746252171976963363056481941560715954676764349967630337 
*/

// You can initialize literal field elements with numbers, booleans, or decimal strings
const x0: Field = new Field('37');
// Typescript has type inference, so type annotations are usually optional.
let x1 = new Field(37);
console.assert(x0.equals(x1).toBoolean());

// The `new` keyword is optional as well:
x1 = Field(37);
console.assert(x0.equals(x1).toBoolean());

/* You can perform arithmetic operations on field elements.
   The arithmetic methods can take any "fieldy" values as inputs: 
   Field, number, string, or boolean 
*/
const b = Field(1);
const z = x0.mul(x1).add(b).div(234).square().neg().sub('67').add(0);

Snippet above displays the simple use of Field.

Hashing

Hash functions/algorithms are widely used in software development for enabling security of some data that must not be seen by anyone. Hashing is not encryption, so it is not possible to convert the hashed data to its unhashed input form ( called preimage ). With this property, it can be called a one-way function.

Therefore, they can be used to hide the data and let people who only knows the data access it. It is used in storing passwords in web2 development.

import { Hash, Poseidon, Field} from "o1js";

const toHashed = new Field(3);
/**
 *
 * Here, Hash class has these hash algorithms:
 * - KECCAK256
 * - KECCAK384
 * - KECCAK512
 * - POSEIDON
 * - SHA2_256
 * - SHA3_256
 * - SHA3_384
 * - SHA3_512
 */

const poseidon1 = Hash.hash([toHashed]);
// console.log(poseidon1);
const poseidon2 = Poseidon.hash([toHashed]);
// console.log(poseidon2);

// Both are same. 
console.log(poseidon1.equals(poseidon2).toBoolean());
//Output: true (try if you don't believe :-) );

PreviousWhy ZK?NextOPTIONAL: Advanced Resources

Last updated 9 months ago

Cryptography_?

All mathematics is divided into three parts: cryptography (paid for by CIA, KGB and the like), hydrodynamics (supported by manufacturers of atomic submarines), and celestial mechanics (financed by military and other institutions dealing with missiles, such as NASA).

Cryptography has generated number theory, algebraic geometry over finite fields, algebra, combinatorics and computers.

Hydrodynamics has procreated complex analysis, partial differential equations, Lie groups and algebra theory, cohomology theory and scientific computing.

Celestial mechanics is the origin of dynamical systems, linear algebra, topology, variational calculus and symplectic geometry.

-Vladimir I. Arnold

Until now, Zero-Knowledge proofs are explained in a practical sense. Actually, every concept we explained to you was a part of applied cryptography.

If you heard about Bitcoin and , then you are aware of some topics of computer science and cryptography such as hash function and .

You might ask: 'I am coming from ... Chain ecosystem, why am i supposed to know topics like Finite Fields, Merkle Tree, Witneess etc. to write a smart contract or any app?'

Introduction to Math & Terminology

Finite Fields

are the cornerstone of the modern cryptography - but, why? We can list the reasons as:

Security: Cryptography needs hard problems ensuring security of the system. The most widely used, , ensures that there is a hard computation that is resistat for attacks.
Finite Field properties: There are operations and algebraic structures that enable finite fields to be used in an efficient and secure way to create functions/structures like encryption techniques and digital signatures.

Besides Mina Kimchi Book, if you have time and enthusiasm you can study this . While developing in Mina Protocol, it will be enough for you to understand the Finite Fields. However, if you are eager to understand why/how cross-chain communication is hard, you should try to understand what an is. Of course, you are again not supposed to be an expert for application development - but hey, maybe you want to wink a little to the infrastructure developmen in the future, right?

import {
  Field,
} from 'o1js';

/* This file demonstrates the classes and functions available in o1js */

/* # Field */

/* The most basic type is Field, which is an element of a prime order field.
   The field is the [Pasta Fp field](https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/) 
   of order 28948022309329048855892746252171976963363056481941560715954676764349967630337 
*/

// You can initialize literal field elements with numbers, booleans, or decimal strings
const x0: Field = new Field('37');
// Typescript has type inference, so type annotations are usually optional.
let x1 = new Field(37);
console.assert(x0.equals(x1).toBoolean());

// The `new` keyword is optional as well:
x1 = Field(37);
console.assert(x0.equals(x1).toBoolean());

/* You can perform arithmetic operations on field elements.
   The arithmetic methods can take any "fieldy" values as inputs: 
   Field, number, string, or boolean 
*/
const b = Field(1);
const z = x0.mul(x1).add(b).div(234).square().neg().sub('67').add(0);

Snippet above displays the simple use of Field.

Hashing

Therefore, they can be used to hide the data and let people who only knows the data access it. It is used in storing passwords in web2 development.

In web3, are widely used. Some examples to hash functions are .

OPTIONAL: If you are interested in which hash function is used in Mina Protocol, you can check the explanation video of . It is special since it is used a lot in systems which utilize ZKPs.

import { Hash, Poseidon, Field} from "o1js";

const toHashed = new Field(3);
/**
 *
 * Here, Hash class has these hash algorithms:
 * - KECCAK256
 * - KECCAK384
 * - KECCAK512
 * - POSEIDON
 * - SHA2_256
 * - SHA3_256
 * - SHA3_384
 * - SHA3_512
 */

const poseidon1 = Hash.hash([toHashed]);
// console.log(poseidon1);
const poseidon2 = Poseidon.hash([toHashed]);
// console.log(poseidon2);

// Both are same. 
console.log(poseidon1.equals(poseidon2).toBoolean());
//Output: true (try if you don't believe :-) );

There are various use cases of hash functions. One of them is to create abstract data structures, like , which are used very widely in various ecosystems like Mina, Ethereum, Bitcoin etc.

Tools you've seen so far are used in different infra applications, such as . As you can see, everything is somehow connected, EVERYTHING!