ZK & ZKVM
Zero-knowledge
A zero-knowledge proof is a cryptographic technique that allows one party (the prover) to prove to another party (the verifier) that a statement is true, without revealing any specific information about the statement itself. The main idea behind ZKPs is to ensure privacy and security in various applications, including authentication, secure voting, and confidential transactions on blockchain networks.
These zero-knowledge proof systems aim to solve problems where one party, in this case, Alice, possesses knowledge of a specific polynomial, and another party, Bob, wants to verify that she knows the correct polynomial. The challenge lies in designing a protocol that allows Alice to prove her knowledge without revealing any additional information about the polynomial itself.
Here's a high-level overview of how zero-knowledge proofs work:
Setup: The prover and verifier agree on a specific problem statement and a common reference string (CRS), which serves as a public key for the proof.
Commitment: The prover generates a commitment, which is a representation of the secret information they want to prove without revealing the information itself. The commitment is usually created using cryptographic hash functions or other commitment schemes.
Challenge: The verifier sends a challenge to the prover. This challenge is typically a random value or a set of random values.
Response: The prover constructs a response based on the secret information, the commitment, and the challenge. The response should be generated in such a way that it doesn't reveal the secret information but is still verifiable by the verifier.
Verification: The verifier checks the prover's response against the problem statement and the CRS. If the response is valid, the verifier accepts the proof, concluding that the prover knows the secret information without learning what the information is.
An essential property of zero-knowledge proofs is that they must be:
Complete: If the statement is true, an honest prover can always convince an honest verifier.
Sound: If the statement is false, a dishonest prover cannot convince an honest verifier with a high probability.
Zero-knowledge: The verifier learns nothing about the secret information, other than the fact that the statement is true.
Various zero-knowledge proof systems exist, such as zk-SNARKs, zk-STARKs, and Bulletproofs, each with its own trade-offs in terms of efficiency, complexity, and setup requirements.
Zero-knowledge Virtual Machine
The Zero-Knowledge Virtual Machine (zkVM) is an application of zero-knowledge proofs. In general, zkVM technology allows programs to be executed on a single computer, producing both an output and a Zero-Knowledge proof. This proof enables anyone to verify that the program has been executed correctly without revealing any sensitive information or tampering with the process. Essentially, zkVM technology uses advanced mathematical methods to create a trusted computing environment that ensures security and privacy.
We will explain zkVM using STARK and Cairo as examples, as they are among the most well-known zero-knowledge algorithms and programming languages, respectively.
To generate the zero-knowledge proof, a high-level programming language is employed (in our case, Cairo). Once the program is written in Cairo, an interpreter compiles it into CASM, a middle language resembling assembly language. CASM adheres to strict rules, which include:
No variables, only constants;
No loops (since there are no loop variables), using recursion instead;
Limited static type.
By following these strict rules, CASM can be converted into a combination of trace polynomials and constraint polynomials. By employing the zero-knowledge proof system (in our example, STARK), these polynomials and the published source code generate a zero-knowledge proof that demonstrates the program has been executed correctly.
In summary, zkVM technology leverages zero-knowledge proofs, such as STARK, and programming languages like Cairo, to enable the secure and private execution of programs. By converting high-level programs into lower-level representations, like CASM, and applying strict rules, it becomes possible to create trace and constraint polynomials. These polynomials, combined with the zero-knowledge proof system, produce a proof that verifies the correct execution of a program without revealing sensitive information, thus ensuring security and privacy.
You could see more about zk & ZKVM on the attched material.
Last updated
