Overview

This article is a written breakdown of Porter Adam’s seminar delivered at Spearbit, an experienced blockchain security researcher. He delved into the topic of Zero-Knowledge Proofs (ZKP) and their potential applications within the sphere of verifiable computation.

Spearbit is a decentralized and industry-leading blockchain security services firm pairing protocols with top security researchers with deep subject matter expertise to identify vulnerabilities in an ever-evolving landscape.

This article is not meant to be a complete replacement of Porter’s seminar and instead as supplementary material to support deeper understanding. We highly recommend watching the video seminar as well.

Seminar Link: https://youtu.be/QXdoMPzmEbE

Understanding Zero-Knowledge Proofs

In the realm of cryptography, zero-knowledge proofs (ZKPs) are integral, with the "proofs" element playing a vital role. Despite "zero-knowledge" being a prevalent term, the primary focus in many applications, like ZK Roll-Ups, is on the "proofs." These roll-ups frequently utilize proofs to achieve enhanced scalability, even if they do not always implement the privacy aspect of ZKPs.

The fundamental principle behind ZKPs lies in their capacity for verifiable computation. They enable validation that a particular computation was executed correctly, ensuring operational integrity without revealing exhaustive details about the computation.

Applications of Zero-Knowledge Proofs

The real-world applicability of ZKPs is vast, extending across multiple domains:

For example:

ZK Roll-Ups: scaling solution for blockchains that consolidates multiple transactions into a single transaction. The role of ZKPs here is to verify the accuracy of all activities occurring within the roll-up.
Tornado Cash: Ethereum privacy solution that confirms that anyone withdrawing money is rightfully doing so - they are claiming funds that belong to them. This verification is crucial, even if the origins or ownership of the funds aren't known.
Dark Forest: Ethereum-based game that offers an example of their application in blockchain gaming. Most data on a blockchain is public, but some gaming scenarios require hidden elements. Here, ZKPs enable verification that the game is functioning correctly without revealing the hidden components.

In essence, when considering zero-knowledge proofs, the focus should be on "verifiable computation." This understanding helps determine when and how to use ZKPs effectively across various systems. Their versatility and importance are apparent in applications ranging from blockchain scaling solutions to privacy platforms and blockchain gaming.

Demystifying Zero-Knowledge Proof Buzzwords

An aspect of zero-knowledge proofs (ZKPs) that may initially seem daunting is the prevalence of certain buzzwords. Understanding these terms can help demystify ZKPs.

Setup Phase

Creating zero-knowledge proofs generally involves a setup phase. This phase could happen once for an entire blockchain, or it may be required for every single proof. Ideally, ZK protocols would not require extensive public setup.

From this setup phase, a prover key (PK) and a verifier key (VK) are usually generated. Contrary to what the 'key' terminology might suggest, both these keys are public. The setup phase essentially lays the groundwork and establishes trust for the protocol's continued execution.

Prover and Verifier

Following the setup, the process revolves around two entities: the prover and the verifier. The prover is provided with inputs, which typically include the computation they want to prove and a 'witness' for that computation. This witness is another buzzword that can cause confusion. For instance, if you're dealing with modular arithmetic and trying to determine whether a certain number is the square of another number, the computation would be 'squaring modulo something,' and the witness would be one of the square roots. The prover uses these inputs to generate the proof and sends it to the verifier. The verifier then employs the verifier key to check the proof's correctness.

Program Logic

This stage involves the inherent logic of the program. For instance, in ZK Roll-Ups, this might involve the process of performing a transaction on Layer 2.

Computation

From the initial logic, a computation is carried out. This could involve signing a transaction to denote the transfer of funds to someone else.

Circuit Definition

This step begins to delve into the world of zero-knowledge proofs more distinctly. The objective is to transform the standard code into a polynomial due to polynomials' remarkable scaling and error correction properties. A 'circuit' in this context refers to an arithmetic circuit, similar to a flowchart for calculations. This typically involves basic operations like addition and multiplication, converting these operations into a form that suits ZKPs.

Arithmetization

Following the creation of a circuit, arithmetization is the process of converting that circuit into a single polynomial. The circuit, which may resemble a tree, is streamlined into a single entity that can be used in the next stages of the zero-knowledge proof.

Non-interactive Proof

By their original design, many ZKP protocols involve some back-and-forth interaction between the prover and the verifier. However, it's often more practical to convert these into non-interactive proofs for the sake of convenience.

Integration

This final step involves reintegrating the proof back into the main application. Despite having successfully generated a ZKP, it's important to ensure that this proof can be integrated back into the main system without issues. If this step isn't handled correctly, the entire process could result in errors despite the correctness of the zero-knowledge proof itself.

This systematic approach to understanding ZKPs helps in demystifying the process and making it more accessible for those seeking to delve into the space. The process includes transitioning from program logic and computations, through circuit definitions and arithmetization, to non-interactive proof creation and final integration into the main system.

Example: Understanding ZKScroll with Layer 2

The ZKScroll framework helps illustrate how zero-knowledge proofs work in the context of Layer 2 solutions. Several key elements play a role in this setup.

Sequencer

The sequencer in Layer 2 is akin to the miners or stakers in Layer 1, which are responsible for running the nodes. Transactions are typically directed towards the sequencer in this context.

Data Providers and Coordinators

From the sequencer, the transactions are sent to the data providers and coordinators. Their role is to organize the generation of proofs associated with each transaction. This coordination is essential because the proof generation process could potentially exceed the duration of a single block. Therefore, orchestrating the proof production ensures smooth operation.

Proof of Proofs

One of the significant benefits of this approach is that it allows for scalable proof verification. Instead of verifying each proof individually, a 'proof of proofs' can be constructed. This consolidates several proofs into one, which can then be verified collectively, improving the efficiency of the process.

Posting Data Back to Ethereum

Finally, a portion of the transaction data and the associated proof are posted back to Ethereum. Ethereum verifies that the data and the proof are consistent, thereby confirming the validity of the Layer 2 transactions.

The ZKScroll example highlights how zero-knowledge proofs can be used in scalable Layer 2 solutions, managing transaction data, and ensuring transaction validity with efficient proof generation and verification.

From Verifiable Computation to Polynomials

A common question arising in zero-knowledge proofs is understanding how verifiable computation transforms into polynomials. For a detailed understanding of this, Vitalik Buterin's blog on quadratic arithmetic programs offers an extensive insight into how this transition occurs, particularly the segment addressing the concept of Rank One Constraint System (R1CS).

The process of converting computation to a polynomial can be executed in various ways. However, R1CS serves as a default method given its straightforward nature. Planck (PLONK), for instance, offers an enhancement to R1CS. The comprehension of these protocols is greatly facilitated once one grasps the basics of R1CS.

The Necessity of Understanding Math

The depth of mathematical knowledge required in this context can vary greatly. A comprehensive understanding of all mathematical details pertaining to zero-knowledge proofs is achievable with one or two months of dedicated study. However, not all implementations require an extensive understanding of the underlying mathematics.

The mathematical concepts mainly involved are polynomials and finite fields, topics that many will have encountered in their previous studies. Therefore, while having a strong mathematical foundation can be beneficial, it is not necessarily a prerequisite for understanding or using zero-knowledge proofs.

Regarding the recommendation of a first project, further clarification would be needed to provide an appropriate suggestion tailored to the individual's interests and skills.

One can understand most with:

https://zk-learning.org/
College level course in:
- Number Theory
- Abstract Algebra

Test Your Understanding: Zero Knowledge Exercises

For those seeking a practical way to gauge their understanding of zero-knowledge proofs and the associated mathematical concepts, there are several projects that can provide insight.

Tornado Cash White Paper: A highly recommended starting point is reading the Tornado Cash white paper. Despite its brevity (only three pages long), this paper is packed with valuable information about how a successful and widely-used ZK implementation works. For more in-depth discussion and clarification of this white paper, you may consider examining corresponding lecture materials that delve into the specifics of the paper's content.
ZK Battleship: For a more hands-on, interactive introduction to ZK, consider trying ZK Battleship. This online game utilizes ZK proofs, providing you with a chance to see these principles in action. If you feel inclined, you can dig into the game's code to understand how it's built, or even make modifications to suit your learning needs.
Coding Projects: If you're ready to try your hand at creating your own ZK proof, there are several beginner-friendly coding projects available. Implementing a game like tic-tac-toe using ZK proofs can be an excellent practical project. Resources like Mina and Leo offer starter examples to help guide you through the process.

Remember that the best way to learn is often by doing. The more you engage with the material and apply it in practical settings, the better you will understand and remember the principles of ZK proofs.

Spearbit Q&A with Porter Adams

What applied math fundamentals should someone have under their belt while diving into ZK

To fully understand Zero Knowledge (ZK) proofs, it would be advantageous to have an understanding of number theory and abstract algebra equivalent to one college-level course. Porter reassures the listeners that they do not have to delve into the intricacies of elliptic curves to comprehend ZK proofs. For those who desire to delve deeper, there are resources such as the ZK MOOC, taught by leading academics and professionals in the field. The instructors include Shafi Goldwasser, who is credited with the invention of ZK proofs, and Justin Thaler, author of Proofs, Arguments, and Zero-Knowledge.

What lessons were learned from organizing and teaching the ZK classes? Will you do something like this again soon?

Porter mentions that producing high-quality educational content takes considerable time and effort, specifically highlighting that there is currently no ZK class that is both quick and well-explained. As per his experience, good explanations tend to be lengthy, often running for several hours. While Porter sees value in creating more educational content on the subject, he suggests a slower, more deliberate approach in the future, focusing on producing more polished and comprehensive material. This might be a more sustainable way to continue contributing to the ZK education space.

Can you discuss any current challenges or limitations of the zkEVM?

One of the challenges of the zkEVM (a ZK Rollup for general-purpose EVM computation) is the inefficiency of general-purpose circuits. Although it is often cited as a drawback, Porter doesn't view this as a major concern. Instead, more pressing challenges are identified: the computational resources needed to generate the proofs (currently maxing out AWS instances) and the fragmentation of the network. Fragmentation could hamper user experience and interoperability, making it difficult for different ZK rollups and ZK EVMs to interact seamlessly.

The race between scaling solutions is heating up, and will be a must-watch 2023. What are your predictions?

Looking towards 2023, Porter anticipates a surge in ZK programming. As the technology becomes more accessible, more developers are expected to create ZK apps, with educational resources and frameworks becoming increasingly user-friendly.

Privacy debates are also predicted to become more prominent, driven by the rise in the number of ZK applications and the different stances projects take on public and private data. Despite a growing understanding of ZK technology, Porter predicts that marketing might overshadow the technical details, given the array of complex and varied scaling solutions. Lastly, there might be a trend of optimistic roll-ups converting to ZK roll-ups, as projects may initially opt for the simpler optimistic roll-up model to gain market share and transition to the more robust ZK model as the technology matures.

How can one can write zero-knowledge proofs in Rust, instead of using Snarky?

The recommended tool is Arkworks. This library is designed for building cryptographic primitives in Rust and comes highly recommended. One of the co-maintainers of Arkworks is Pratyush Mishra, a figure who, while not as widely recognized as many of the notable professors in the field, possesses significant expertise in zero-knowledge proofs. Pratyush also serves as one of the lead cryptographers at Aleo, a company that is pioneering its own zero-knowledge blockchain.

What sets Pratyush apart is his deep understanding of these complex concepts and his detailed technical knowledge. Furthermore, his role in creating Arkworks showcases his considerable talents in the field. Pratyush comes highly recommended as a figure to look up to in the zero-knowledge proof arena.

What's the distinction between a commitment scheme and a proof system?

Commitment Schemes: Commitment schemes are cryptographic tools that allow a person to commit to a certain value, while keeping that value hidden until they choose to reveal it.

Purpose and Function: The main purpose of a commitment scheme is to commit to a value that will be revealed later. A practical example would be a cryptographic or zero-knowledge coin flip. Here, the outcome of the coin flip is "committed" or sealed, and the commitment is sent to the other party. After a guess is made, the commitment can then be revealed.

Proof Systems: A proof system is a mechanism for proving that certain information is true without revealing the information itself.

Commitment Schemes in Proof Systems: A commitment scheme forms a part of a proof system, particularly contributing to the zero-knowledge aspect of the system. In a proof system, a polynomial is committed, and a verifier needs to be able to verify the polynomial quickly without having to read the entire polynomial. The verifier will make the prover reveal parts of the committed polynomial.

Common Commitment Schemes

There is a variety of commitment schemes used in the field of cryptography. The choice of a scheme largely depends on the specific use case. Here are a few examples:

SNARKs: These offer extremely fast verification but require a trusted setup.
STARKs: These are post-quantum secure and require no trusted setup.

Note: It is important to realize that there are trade-offs with each commitment scheme. One should not view any one system as optimal, as the best choice depends on specific needs and constraints.

Zero-Knowledge Proof Programming Options

There are numerous programming options available for working with zero-knowledge proofs:

SnarkyJS by Mina: Useful if no preference on programming language.
Cairo by Starkware: An alternative that many people seem to favor.
Noir by Aztec: Interesting for implementing a ZK roll-up that uses privacy.
R1CS-Zero: Notable for building a zero-knowledge processor, which allows for the use of any programming language that compiles to LLVM, such as C or Rust. This means you can run regular code, and the processor generates zero-knowledge proofs along the way.

ZK Differences

From an auditor standpoint what areas of ZKA should we be concerned with?

Auditing Concerns in ZKA: From an auditor's standpoint, there are numerous areas to consider when dealing with Zero-Knowledge Algorithms (ZKA).

Resources: The recommended resources include talks by JP Aumasson, who is known for his expertise in cryptography. He has written a practical cryptography textbook called "Serious Cryptography" that could be beneficial for auditors.
Common Vulnerabilities: A common concern in ZKA is potential flaws in the zero-knowledge scheme. For example, Zcash, despite employing some of the best zero-knowledge cryptographers in the world, has experienced issues due to a broken zero-knowledge scheme.

Zero-Knowledge Security: Given the potential vulnerabilities, it's important to consider safety measures when using ZKAs. Justin Drake, an Ethereum researcher, proposed using SGX secure enclaves to counter vulnerabilities in zk-SNARKs roll-ups.

Two-Factor Authorization (2FA): This method involves needing both a zk-SNARK proof and an SGX proof to perform on-chain state transitions. It's intended to safeguard against malicious hackers who might exploit flaws in zk-SNARKs. However, it's worth noting that this method hasn't been widely adopted yet.
Ongoing Discussion: As this field is still evolving, there are many ongoing discussions about how to enhance safety in the usage of ZKAs. These conversations are open for participation, and interested parties are encouraged to join and contribute to the discourse.

What are some of the common pitfalls there's projects make in relation to ZK?

Common Pitfalls: For the common pitfalls projects encounter in relation to Zero-Knowledge (ZK) algorithms, JP Aumasson's work is again recommended as a valuable resource.

Recommended Materials and Exercises: For exercises and studying resources, there are several options available.

Matter Labs GitHub: This resource offers a comprehensive collection of resources related to Zero-Knowledge proof algorithms.
Scrolls Blog: This blog is highly recommended for its insightful content.
zklearning.org: This is the link to the ZK Massive Open Online Course (MOOC) by five professors.
xeronowledge.fm: Run by Anna Rose, this is an excellent resource offering in-depth podcasts on ZK proof algorithms. Each episode of the podcast is an hour-long deep dive into a specific ZK topic.

People to Follow in the Field of ZK Proofs:

Pratyush Mishra: He is the co-maintainer of Arc Works, a platform for writing zero-knowledge proofs.
Toghrul: worth following for insightful contributions to the ZK proof discussion.
Psuedo Theos: worth following for insightful contributions to the ZK proof discussion.
Daira Hopwood: As one of the top cryptographers in the Zcash ecosystem, Daira Hopwood is another excellent source of knowledge.
Justin Drake: An Ethereum researcher, Justin Drake's insights are valuable to anyone interested in ZK proofs.
Professors: While not always active in practical implementation, the professors in the field provide the foundational theories behind ZK proofs. Following their work can provide a deeper understanding of the field.

Looking for a Security Review?

Please contact us below via our submission form:

https://airtable.com/shrkxrtMKYJkLaXhT

You may also reach out to us via our Twitter: https://twitter.com/SpearbitDAO :

For a brief overview of what Spearbit is and what we have to offer please see: https://twitter.com/SpearbitDAO/status/1656786350601846787?s=20

Demystifying ZKPs with Porter Adams