What Are Zk-SNARK and Zk-STARK Proofs?

Basics

Cryptocurrency enthusiasts place a high value on privacy, which is considered essential for fungibility to be achieved, an important feature for money to be widely accepted. Most crypto holders prefer not to disclose their holdings and transaction history. Various cryptographic methods have been developed to provide privacy to the blockchain. Two of the most notable are zk-SNARK and zk-STARK proofs.

The zk-SNARK and zk-STARK proofs are abbreviations for the zero-knowledge succinct non-interactive argument of knowledge and zero-knowledge succinct transparent argument of knowledge, respectively. The zk-SNARKs are already in use in Zcash, JP Morgan Chase's blockchain-based payment system, and as a way to authenticate clients to servers. Though zk-SNARKs have been widely accepted, zk-STARK proofs have been introduced as an improved version of the protocol, addressing some of the issues that zk-SNARKs had previously faced.

The Ali Baba's Cave Parable

The cryptographer Jean-Jacques Quisquater and his collaborators published a paper in 1990, titled "How to Explain Zero-Knowledge Protocols to Your Children," which introduced the concept of zk proofs through a parable featuring Ali Baba's Cave. Several adaptations of the story have been created since then, but the fundamental concept remains the same.

The parable centers on a ring-shaped cave with a single entry and a magical door separating two paths. To pass through the door, one must whisper the correct secret words. In the story, Emma wants to prove to David that she knows the secret words, but without revealing them. To accomplish this, David agrees to stay outside while Emma enters the cave and walks to the end of one of the two paths. In this case, Emma chooses to take Path 1.

David calls out from the entrance for Emma to exit through a specific path, in this case, Path 2. If Emma knows the secret, she will appear from the designated path. This process can be repeated to confirm that Emma is not guessing correctly by chance.

The Ali Baba’s Cave story serves as an example of zero-knowledge proofs, a vital component of the zk-SNARK and zk-STARK protocols. These proofs enable the confirmation of possession of certain information without disclosing any information about it.

How Do zk-SNARKs Work?

The concept of zero-knowledge proofs has been applied to create the first widely available privacy coin called Zcash, using zk-SNARKs. Unlike other privacy-focused projects that use ring signatures and other techniques to create smokescreens around transactions, Zcash fundamentally changes the way data is shared. Transactions in the Zcash network remain encrypted, yet can still be verified as valid by using zero-knowledge proofs, enabling enforcement of consensus rules without revealing data underlying each transaction. However, privacy features in Zcash are not active by default and are dependent on manual setup.

Zero-knowledge proofs enable an individual to prove to another that a statement is true without revealing any information beyond the validity of the statement. The parties involved in zero-knowledge proofs are a prover and a verifier, and the statement they hold in secret is called a witness. The objective of zero-knowledge proofs is to reveal as little data as possible between the two parties.

Within the zk-SNARK acronym, “succinct” means that proofs are smaller in size and can be quickly verified, while “non-interactive” means that there is little to no interaction between the prover and verifier. Older versions of zero-knowledge protocols require the prover and verifier to communicate back and forth, making them “Interactive” ZK proofs. However, provers and verifiers only have to exchange one proof in “non-interactive” constructions.

Although zk-SNARK proofs are dependent on an initial trusted setup between a prover and verifier, researchers are working to find alternatives to reduce the amount of trust required in the process. The initial setup phase is essential to prevent counterfeit spending, and in Zcash, it is known as the Parameter Generation Ceremony.

The soundness property of zk-SNARKs assumes that a dishonest prover has limited computing power and a prover with enough computational power could create fake proofs. This is why quantum computers are considered a threat to zk-SNARKs and blockchain systems.

Finally, zero-knowledge proofs are quickly verifiable and take up fewer data than standard Bitcoin transactions, making them suitable for use as both a privacy and scalability solution.

How Do zk-STARKs Work?

Eli-Ben Sasson, a professor at Technion-Israel Institute of Technology, created zk-STARKs as an alternative version of zk-SNARK proofs. zk-STARKs are considered more efficient - potentially faster and cheaper depending on the implementation. Unlike zk-SNARKs, zk-STARKs do not require an initial trusted setup, hence the "T" for "transparent."

zk-STARKs rely on collision-resistant hash functions, which eliminates the number-theoretic assumptions of zk-SNARKs that are computationally expensive and theoretically prone to attack by quantum computers. This approach presents a simpler structure in terms of cryptographic assumptions.

However, zk-STARK proofs have at least one major disadvantage: they have bigger proof sizes compared to zk-SNARKs. This difference in data size may limit their use in some contexts, but this is something that can be improved through further testing and investigation.

Conclusion

The potential of zk-SNARKs and zk-STARKs in the world of cryptocurrency is apparent as both protocols cater to the growing need for privacy. These technologies hold promise and could be a significant factor in the wider adoption of cryptocurrency.