ZK-Land

A public repository consisting of all my initial ZK experimentations

1. Encrypted QAP Evaluations

• QAP: Quadratic Arithmetic Programs.
• QAP is a system of equations of univariate polynomials, and their valid solutions result in a single polynomial equality.
  • They are quadratic because they have exactly one polynomial multiplication
• QAPs (because of their polynomial equality and the Schwartz-Zippel Lemma) allow ZK-Snarks to be succinct.

1.1 What is the process of arriving at QAPs?

• Start with a function logic (from any programming language). The function must be bounded.
• The function logic is converted into a set of polynomial equations via a process called either flattening or arithmetization.
• Now, using these flattened equations from the step above (which are of the form k + c = a * b), we convert all these equations into an R1CS or the Rank-1 Constraint System.
  • Given a circuit encoded as a rank 1 constraint system, it is quite possible to create a zk-proof of having a witness, albeit not a succinct one. Here's an article on how to do that.
• But since having succinct proofs is kind of important to us, we now convert the R1CS into another form of representation called QAP, which when solved correctly, gives us one single polynomial equality.
  • If that polynomial equality holds true for any random point in our prime field, then we can conclusively (and succinctly) say that the prover indeed knows the solution to the initial function logic.

1.2 What code does this repo contain?

This repo contains a segment of code that takes an R1CS as an example, converts that into QAP and then solves it to get a single polynomial equality, and then does an evaluation of the two sides of the equality with encrypted field points.

That's it.