Skip to content

Latest commit

 

History

History
115 lines (73 loc) · 4.08 KB

README.md

File metadata and controls

115 lines (73 loc) · 4.08 KB
Raw

Camp 1: STARKS

Presentation Video Workshop
STARKs Camp 1 STARK 101

Topics

  1. Modular Arithmetic
  2. Finite Field Arithmetic
  3. Polynomials
  4. ZK Terminology
  5. Computational Integrity
  6. STARKs
  7. STARKs vs SNARKs

Modular Arithmetic

A system of arithmetic for integers where numbers "wrap around" when reaching a certain value (aka 'modulus')

A real-world example of modular arithmetic is time-keeping via a clock. When the hour of the day exceed the modulus(12) we "wrap" around and begin at zero.

Example:

python3 finite_fields/python/modular_arithmetic.py

Finite Fields

Much of today's practical cryptography is based on finite fields. A finite field is a field that contains a finite number of elements and defines arithmetic operations for multiplication, addition, subtraction, and divsion. These arithmetic operations are.

A finite field cannot contain sub-fields and therefore typically implements the principles of modular arithmetic over a large, irreducible prime number. The number of elements in the field is also known as its order.

Example:

python3 finite_fields/python/finite_field_arithmetic.py

Polynomials

Polynomials have properties that are very useful in ZK proofs. A polynomial is an expression of more than two algebraic terms. The degree of a polynomial is the highest degree of any specific term.

For an example of how Polynomials can be built and expressed in code run:

python3 finite_fields/python/polynomial.py

ZK Terminology

Zero Knowledge Proof Systems are proof systems in which there is secret information known to the prover that is not known to the verifier, and the verifier is still convinced of the computational claim.

A non-interactive proof system is an abstract machine that models computation between the two parties(prover and verifier). Messages are sent in one direction until the verifier is convinced of the computational claim.

A succinct proof system is one in which the verifier can run an order of magnitute faster than a naive re-execution of the program

SNARKS: Succint Non-Interactive Arguments of Knowledge

STARKs: Scalable Transparent Arguments of Knowled

Computational Integrity

The goal of these proof systems is to prove computational integrity to a verifier. Computational Integrity can be formalized as follow:

Statement of Computational Integrity = (S0, P, T, S1)

S0: Initial State P: Program that changes state T: Number of steps S1: Final State

STARKs

UNDER CONSTRUCTION:

While this section is being built we recommend reading this blog post series(1, 2, 3) on the math behind STARKs.

Arithmetization

Low Degree Extension

Polynomial Constraints

Commitment

FRI

Commitment

Queries

Proof

Sources

[https://eprint.iacr.org/2018/046.pdf , https://vitalik.ca/general/2017/11/09/starks_part_1.html , https://github.com/starkware-libs/ethSTARK , https://consensys.net/blog/blockchain-explained/zero-knowledge-proofs-starks-vs-snarks/ , https://aszepieniec.github.io/stark-anatomy/ , https://github.com/elibensasson/libSTARK , https://eprint.iacr.org/2021/582.pdf]