Partnered With:

Debate on the Technical Path of Zero-knowledge Proof: Which is Better, zk-SNARK or zk-STARK?

Read this article in 11 Minutes

zk-SNARK is the most widely adopted by project parties, and zk-STARK is considered superior to zk-SNARK by cryptography experts.

The Technical Path Debate for Zero-Knowledge Proof: Who is Better, zk-SNARK or zk-STARK?

原文作者：Chloe，链茶馆

Zero-knowledge Proof technology, which has been widely concerned in Crypto industry, is not a new technology emerging in recent years, but was proposed in 1980 by mathematicians S.Goldwasser, S. Moali and C.Rackoff.

Zero-knowledge proof involves a series of steps that achieve "useable but unknowable" in cryptography.

However, blockchain is characterized by openness, transparency and impossibility of tampering, which means that crypto investors' on-chain assets and transaction records have no privacy at all. Therefore, zero-knowledge proof technology is introduced into blockchain, among which zk-SNARK and zk-STARK are the most concerned.

zk-SNARK is the most widely adopted by project parties, and zk-STARK is considered superior to ZK-SNARK by cryptography experts. Which is better, technology or application?

zk-SNARK: Simplicity + non-interaction

Alessandro Chiesa et al. developed the zk-SNARK protocol in 2012, which is a compact, non-interactive zero-knowledge proof technique, Its full name is zero-knowledge succinct non-interactive arguments of knowledge, which can be broken down into three parts:

zero-knowledge:

Zero-knowledge proof, proving a thing to the other party without revealing privacy, makes the data "usable but unknowable".

succinct:

Simplicity, little space to prove, and quick verification (milliseconds).

non-interactive:

Non-interactivity means that there is no need for intersection between prover and verifier to get verification results quickly.

The simplicity and non-interaction of zk-SNARK are compared with traditional zero-knowledge proof schemes.

In simple terms, the traditional scheme is an interactive proof, which is repeated confirmation between the demonstrator (who claims that a proposition is true) and the verifier (who confirms that the proposition is indeed true), which you can understand as the demonstrator constantly asking the verifier "Yes or no?" And then the verifier keeps giving answers until they finally hit a correct answer, so it's very inefficient.

zk-SNARK's solution does not require both parties to double-check "yes or no," but instead does a "trusted initialization" ahead of time to generate a common reference string (CRS), which can then be accessed directly by all certifiers.

To use a popular analogy. Interactive proof is equivalent to the teacher correcting every question of every candidate, which is very inefficient, but the correct answer is only mastered by the teacher, and there is basically no stealing the answer.

But zk-SNARK is efficient at uploading the correct answers directly to the system, and then letting candidates verify the answers themselves (sending a question they have solved to a background system will get the final answer). The price is that the answers may be leaked, even though the system is encrypted.

Therefore, for the problem that zk-SNARK is easy to be leaked, there are a lot of solutions around improving the security of the "answer system", and different projects using zk-SNARK have different solutions. The zCloak wallet, for example, sends an algorithm in plain text to users, who download it to a local computer and use it to do their calculations.

zk-STARK: Probability proof + buffer time

zk-STARK was developed by the StarkWare team founded in December 2017 as an alternative solution to zk-SNARK. It took over a year of development and numerous iterations to complete, and it's already 2019.

zk-SNARK generates the public reference string in advance, which improves the proof efficiency by non-interactive proof, but also leaves hidden dangers. Although zk-STARK is interactive, it is a clever interactive proof -- using hash function collisions (a probabilistic proof approach) to ensure safety and therefore efficiency.

This idea is directly borrowed from the Interactive predictive machine proof (IOP) technology launched in 2015. Simply put, the question is first broken in the way of cryptography, and then the verifier randomly raises several questions to the demonstrator. If the demonstrator gives accurate answers after several rounds, then the verification is passed.

So zk-STARK also requires very little computing resources to do the proof, but it is more secure and there is no risk of the answer being leaked. And to further ensure security, a dispute time delay (DTD) is set up as a buffer.

zk-SNARK and zk-STARK

Step 1: Transparency

The public reference string of zk-SNARK is usually kept by a small group and therefore has the potential for leakage, which can be exploited for malicious purposes, such as creating false certificates.

zk-STARK uses parameters that generate randomness directly for verification without the need for any third party "answer system," resulting in a significant increase in transparency.

2. Resist quantum computer attacks

zk-SNARK will be easily brute-force cracked by quantum computers in the future (extracting private keys from public keys by factoring calculations). When quantum computing will arrive is, of course, a question.

zk-STARK uses the hash function collision method to prove that brute force cracking by quantum computers is not valid in theory.

3. Scalability

zk-SNARK's proofs are more scalable on the chain (the generated proofs are smaller in number of bytes), and zk-STARK seems to have no advantage on pure chains.

StarkWare's website claims to be the fastest, possibly because zk-STARK allows for large-scale computing and storage off-chain and then verification on-chain, resulting in significant scalability improvements (up to 10 times) and significant cost reductions.

summarize

zk-SNARK technology has been adopted the most, especially in the Ethereum expansion scenario. zk-SNARK mainly focuses on "privacy protection" to develop identity, payment, DeFi, asset proof and other applications.

zk-STARK is still evolving, but the technology is still immature, at least in terms of versatility, so we're seeing a lot of focus on "scalability."

But according to the StarkWare team in 2022, scalability has been solved and it's time to target "privacy protection" through StarkNet's Layer3 and the fractal Layer4 approach. This does not seem to be directly related to the zk-STARK proof system itself.

At least for the time being, most Ethereum Layer2 projects (zkSync, Aztec, Loopring, Scroll, etc.) are using the zk-SNARK route. In addition to being limited in versatility, there is a general feedback that zk-STARK is too difficult to develop...

In the long run, of course, zk-STARK is more computation-intensive and potentially more promising.

In general, the relationship between Zk-Snark and Zk-Stark is somewhat like that between Optimistic rollups and ZK rollups, in which the former is positive in the short run and the latter in the long run.