Welcome to this comprehensive tutorial on ZK-SNARKs, ZK-STARKs, and Bulletproofs! These three cryptographic protocols are powerful tools for maintaining privacy and security in the digital world, particularly within the realm of blockchain technology.
In the evolving field of cryptography, the need for systems that provide privacy, security, and efficient verification is paramount. ZK-SNARKs, ZK-STARKs, and Bulletproofs are solutions that respond to these needs. They are variations of zero-knowledge proofs, a fascinating concept that allows one party to prove to another that they know a specific piece of information, without revealing any details about the information itself.
In this tutorial, we’ll delve into the intricacies of these three systems, explore how they function, and understand their applications and limitations. We’ll look into the specifics of ZK-SNARKs, exploring their structure and functionality.
Next, we’ll turn to ZK-STARKs, a newer variation of zero-knowledge proof systems, discussing their unique properties, including their resistance to quantum attacks and the lack of a trusted setup.
Finally, we’ll examine Bulletproofs, another type of zero-knowledge proof system, which is primarily used to efficiently prove that a secret value lies within a certain range, without revealing any other information about the value.
While these topics may seem complex, I’ll strive to make them accessible and understandable, whether you’re a student, a developer, a researcher, or simply an enthusiastic learner. So, let’s embark on this journey of understanding the intriguing world of ZK-SNARKs, ZK-STARKs, and Bulletproofs!
ZK-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.” It’s a form of zero-knowledge proof that is especially useful in the context of blockchain and distributed systems.
The “Zero-Knowledge” part we’ve already discussed. “Succinct” means that the proofs are small and quick to verify. “Non-Interactive” means that the proof consists of a single message from the prover to the verifier — there’s no back-and-forth communication required. “Argument of Knowledge” is a technical term meaning that if the verifier accepts a proof, then the prover must actually know a secret related to the statement being proved (rather than just convincing the verifier that the statement is true).
ZK-SNARKs have two main steps: a setup phase and a proving phase.
- Setup Phase: This phase involves a trusted party generating a pair of keys: a proving key and a verification key. The proving key is used to construct proofs, while the verification key is used to verify them. The keys are related to a specific statement or computation that the prover wants to prove they know a secret input to. Importantly, the secret input isn’t part of the setup phase. After the keys are generated, the trusted party must destroy their “toxic waste” — the intermediate values used during key generation — because if these values are leaked, they can be used to create false proofs that the verifier can’t distinguish from true ones.
- Proving Phase: After the setup phase, anyone with the proving key can create a proof that they know a secret input to the statement or computation associated with the keys. The proof is a small piece of data that can be verified using the verification key.
ZK-SNARKs are used in various blockchain systems, such as Zcash, to provide privacy features. However, they have a significant drawback: the need for a trusted setup. If the setup process is compromised, the security of the entire system can be broken.
These libraries are extremely useful because implementing zk-SNARKs from scratch would be extremely complex and time-consuming. The theory behind zk-SNARKs is advanced and involves a mix of computer science, cryptography, and advanced mathematics, making it inaccessible for many developers.
- libsnark: This is a C++ library for zk-SNARKs. It provides a set of tools to construct zero-knowledge proofs for computational integrity. It’s widely used in research and development in the field. The library is open source and available on GitHub. It requires some understanding of C++ and zk-SNARKs theory to use effectively.
Learn more here
- Zokrates: Zokrates is a toolbox for zk-SNARKs on Ethereum and can be used on Celo. It includes an easy-to-use domain-specific language (DSL) for developers to write programs and generate zk-SNARKs for them. Zokrates can be used to develop smart contracts on Ethereum that use zk-SNARKs for privacy or scalability purposes. It’s written in Rust and also open source.
Learn more here
- Snarky: Developed by O(1) Labs for the Coda Protocol (now Mina Protocol), Snarky is an OCaml library for writing zk-SNARKs. It features a high-level language that simplifies the process of writing and verifying proofs. Like the other libraries mentioned, Snarky is also open source.
Learn more here
- Bellman: This is a Rust-language library for building zk-SNARKs. Developed by the Electric Coin Company for use in Zcash, Bellman includes tools for creating and verifying zk-SNARK proofs. It’s designed for use with the pairing-based zk-SNARKs that Zcash uses.
Learn more here
Learn more here Circom and Snarkjs
- Abstraction: These libraries offer a high level of abstraction, handling the underlying complexities of zk-SNARKs. They allow developers to create and verify zk-SNARK proofs without needing to understand all the intricate details of the underlying cryptography.
- Security: zk-SNARK libraries have been reviewed and tested by many experts in the field. Using these libraries reduces the risk of introducing security flaws in your own implementation.
- Time and cost efficiency: Implementing zk-SNARKs from scratch would require considerable effort, time, and expertise. By using these libraries, developers can integrate zk-SNARKs into their projects in a much shorter time frame.
- Community support: These libraries are often maintained by dedicated teams or communities. They provide support, fix bugs, and continually improve the libraries. Users can leverage this collective knowledge and experience.
- Interoperability: Many of these libraries are designed to work with popular blockchain and smart contract platforms, making it easier to implement zk-SNARKs in these environments.
- Learning resources: Along with the libraries themselves, there are often a wealth of tutorials, examples, and documentation provided by the maintainers and the community, making the learning curve for implementing zk-SNARKs more manageable.
ZK-STARK stands for “Zero-Knowledge Scalable Transparent Argument of Knowledge.” It’s another form of zero-knowledge proof, but with some different properties compared to ZK-SNARKs.
The “Zero-Knowledge” and “Argument of Knowledge” parts have the same meaning as in ZK-SNARKs. “Scalable” means that the proofs can handle large statements or computations efficiently. “Transparent” means that there’s no need for a trusted setup phase — the keys used in ZK-STARKs are derived purely from public data.
Here are the main steps involved in ZK-STARKs:
- Arithmetization: The computational problem is turned into a system of polynomial equations over a finite field. This involves representing the computation as a sequence of steps, and then turning these steps into polynomials.
- Low-degree Testing: The prover must convince the verifier that these polynomials have a low degree, which is done using a process called the “FRI protocol”. This process involves the prover sending a commitment to the polynomial, and then the verifier sending a random challenge point for the prover to evaluate their polynomial at.
- Interactive Oracle Proof: This is a sequence of interactions between the prover and verifier that allows the verifier to be convinced that the polynomial evaluations are correct, without needing to check them all.
ZK-STARKs have some important advantages over ZK-SNARKs. They don’t require a trusted setup, and they’re post-quantum secure, meaning they’re resistant to attacks by quantum computers. However, ZK-STARK proofs are larger than ZK-SNARK proofs, which can be a disadvantage in systems where space is at a premium.
- StarkWare Libraries: StarkWare is the leading provider of ZK-STARKs technology, and they have developed a series of libraries and tools for ZK-STARKs. The StarkWare-Task-Library provides an interface for defining and interacting with tasks that rely on STARK proofs, while the StarkWare-Statement-Library allows developers to construct and manipulate statements that can be proven or disproven by a STARK.
Learn more here
- LibSTARK: LibSTARK is an open-source library that implements ZK-STARKs. It’s designed for use in C++ projects and is maintained by the same team behind StarkWare. LibSTARK provides a basic framework for creating and verifying STARK proofs and includes examples and tutorials to help developers get started.
Learn more here
- Winterfell: This is another open-source library developed by Facebook’s Novi team. It uses ZK-STARKs to create proofs for computations in a user-friendly way, including a high-level interface for defining computations and generating proofs.
Learn more here
The STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge) libraries offer numerous benefits, especially for systems where data privacy and transparency are critical. Here are some of the key advantages:
- Quantum Resistance: One of the most significant benefits of STARK-based systems is their post-quantum security. They don’t rely on any cryptographic assumptions that could be broken by quantum computers, making them a future-proof choice for systems that need to maintain security in a post-quantum world.
- Scalability: STARKs can handle large computations efficiently, which makes them suitable for scaling complex systems. They can handle much more extensive computations than some other types of zero-knowledge proofs.
- Transparency: STARKs do not require a trusted setup. This means that there’s no need to trust that a certain setup phase was executed correctly without leaking any secret information. This is a significant advantage in terms of transparency and trust.
- Privacy: Like all zero-knowledge proof systems, STARKs provide a strong privacy guarantee. They allow one party to prove to another that a certain statement is true, without revealing any other information beyond the truth of that statement.
- Efficiency: While STARK proof sizes are larger than some other types of zero-knowledge proofs, the overall computational and communication efficiency of STARKs can still be quite high, especially for large computations.
- Versatility: STARK libraries like those provided by StarkWare offer a versatile tool for implementing privacy-preserving systems. They can be used in a wide range of applications, from scaling blockchain systems to enabling private computation in cloud computing scenarios.
- Community and Support: Using established libraries like StarkWare, OpenSTARK, or Distaff VM provides access to a community of developers and users who can offer support and guidance. This can be very valuable for troubleshooting and optimizing your implementation.
Bulletproofs are another type of zero-knowledge proof system. They were developed by researchers at Stanford University and are used for a different set of applications compared to ZK-SNARKs and ZK-STARKs.The main use case for Bulletproofs is to efficiently prove that a secret value is in a certain range, without revealing anything else about the value. This is useful in cryptocurrencies for proving that a transaction doesn’t create or destroy coins (i.e., the transaction is “balanced”). For example, in Bitcoin, a Bulletproof can be used to prove that the amount of an output coin is between 0 and 21 million (the total supply of Bitcoin), without revealing the exact amount of the coin.Bulletproofs don’t require a trusted setup, like ZK-STARKs, and they produce relatively small proofs, like ZK-SNARKs. However, verifying a Bulletproof is more computationally intensive than verifying a ZK-SNARK or ZK-STARK.Here’s a simple explanation of how Bulletproofs work:
- Pedersen Commitment: The prover commits to a secret value by generating a commitment. This commitment can be opened to reveal the value, but it’s computationally infeasible to find the value from the commitment alone.
- Range Proof: The prover generates a proof that the committed value is in a certain range. This involves a clever protocol that uses binary decomposition of the value, and a series of commitments and challenges between the prover and verifier.
- Verification: The verifier checks the proof by performing a series of computations involving the commitments and challenges. If the proof is valid, the verifier can be sure that the committed value is in the required range, without learning anything else about the value.
There are several libraries and ways to implement Bulletproofs. Here are a few examples:
Bulletproofs Library in Rust
Dalek Cryptography has created a high-quality, open-source library in Rust for working with Bulletproofs. The library is easy to use and includes comprehensive documentation. It’s specifically designed to support range proofs, which are the main use case for Bulletproofs.
libsecp256k1 in C
The Bitcoin Core project maintains a library called
libsecp256k1 that includes a Bulletproofs implementation. This is particularly useful for those who are working on Bitcoin or Bitcoin-like systems.
The Monero project has a C++ implementation of Bulletproofs that’s used in their cryptocurrency. Monero’s implementation is focused on performance and security.
In conclusion, ZK-SNARKs, ZK-STARKs, and Bulletproofs are powerful cryptographic tools that enable a range of secure and private applications, particularly in the field of blockchain and cryptocurrencies. These zero-knowledge proof systems, each with their unique properties and trade-offs, allow a prover to demonstrate the validity of a statement without revealing any other information beyond the truth of the statement itself.
ZK-SNARKs are Applauded for their succinctness, resulting in small proof sizes and quick verification times. However, they require a trusted setup, which could potentially compromise the system if mishandled.
On the other hand, ZK-STARKs remove the need for a trusted setup, offer post-quantum security, and provide scalability. But they come at the cost of larger proof sizes, which might not be suitable for all applications.
Bulletproofs fill a different niche by efficiently proving that a secret value falls within a certain range, a common requirement in cryptocurrency transactions. They generate relatively small proofs and don’t require a trusted setup, but the verification process is more computationally intensive.
Each of these techniques has its role to play, depending on the specific requirements and constraints of the application. They all contribute to the broader goal of enhancing privacy and security in digital systems, underlining the significance and potential of zero-knowledge proof systems.
We encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy
I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.