Zk-STARK

Basics

• Starkware is implementing zk-STARKs in various blockchains including Ethereum. The advantage of zk-STARKs over zk-SNARKs is that it doesn’t require a trusted setup, although the cryptographic proof sizes become much larger.

• From a transcript (Summer 2019) by Andrew Poelstra (Blockstream) and David Vorick (Sia):

"In confidential transactions, we have a rangeproof attached to every output. This is an example of a zero-knowledge proof, specifically one to prove a range. The purpose of this is to make sure that ranges aren't going to overflow, that the values aren't going to be negative numbers and won't overflow.

But in general, it's possible to prove anything you want in zero knowledge. This has been generally known since the 1980s. Since the early 90s, it was known to be possible to be done and within the bounds of the known universe. More recently in 2013 there's been a tremendous amount of development in really practical general zero-knowledge proof systems.

STARKs are developed by Eli Ben-Sasson's and others here in Tel Aviv. STARKs are very fast to verify. They are asymptotically very small- they grow with the logarithm of the size of your program execution. Unfortunately, they have large constants like 10s or 100s of kilobytes. Practical STARK programs end up being 50 to 100 kilobytes. They are quantum secure, and they are fast to verify. They scale really well.

One application of STARKs if they were to be much smaller would be a quantum resistant rangeproof which would be interesting, which could lead to a confidential transaction proposal for bitcoin. But they are much more general than this. In theory, you could prove script conditions. You could hide your amount but also your spending conditions. You get something like taproot without all the tricks and the interaction and all these caveats about how sometimes you still need to reveal your scripts.

STARKs can also be used to basically do batch validation. You can produce a STARK proof of the validation of every single signature in the bitcoin blockchain for example. This is a little bit outside of feasibility but with special purpose ASICs you could probably produce such a proof. Now validation of every single signature comes down to validating this small STARK proof which is a few hundred kilobytes of size, rather than dealing with the 100s of gigabytes of data you presently need to do EC operations on. You could compress the whole blockchain signature validation workload into a single proof. We're stretching what's practical to encode; you would have to implement an entire script interpreter into a single zero-knowledge proof system which is very far away from our current ability to design programs.

It's promising tech, and it's practical for a lot of purposes even right now. It's mindblowing and surprising that we can even do this. There's lots of ways in the immediate future that these types of things could be used to improve the scalability of the current system, and also they interact pretty well with the other proposals. Utreexo proofs could be replaced with STARK proofs. The utreexo proofs are small, but STARKs could do aggregation of those. Also, you can do it piecemeal and you don't need to get everyone to do that."

0x

• Might be a solution for scaling. 0x is experimenting with this. " “zero knowledge proofs” or ZKPs for short. A zero knowledge proof allows someone to do a computation on some data and prove that they did this computation correctly, without revealing the data. For example, an account can prove that it summed up all of its expenses correctly without showing what those expenses were.'It is a technology that has been known for about two decades, but as often happens with cryptographic inventions the initial versions where impractically hard to use. In the last couple of years, and thanks to the hard work by Ben-Sasson and many others, ZKP technology has become practical in the form of zkSNARKS. Ben-Sasson and others have developed a new ZKP technology called zkSTARKs. They continue researching and developing this technology as a world-class team called Starkware. Compared to earlier ZKPs, it has better security and it’s easier to produce proofs. It is also refreshingly simple, like great inventions tend to be."

• From Proof of Work #79 (19-11-2019):

"We (0x) introduced a new initiative OpenZKP, an open-source zk-STARK implementation."