ZK-STARKs Create Verifiable Trust, even against Quantum Computers

Adam Luciano 

June 26, 2018 

Note: unless you have familiarity with zero-knowledge or ZK-SNARKs, I would suggest reading Part 1 and Part 2 of this blog series.

Now that we’ve covered the basics of ZK-SNARKs, let’s expand into some of the issues that are often encountered when dealing with ZK-SNARKs and discuss some rather recent innovations in zero-knowledge cryptography: ZK-STARKs (zero-knowledge Scalable Transparent Arguments of Knowledge)

ZK-SNARKs have a few underlying issues that will lead to reduced adoption for leveraging zero-knowledge cryptography in blockchains and other areas as well. These issues include the following:

  1. The trusted setup phase can be compromised (there is an underlying assumption that when using ZK-SNARKs the trusted setup phase is secure)
  2. Scalability of ZK-SNARKs can be improved, as run-time increases, the time needed to generate and verify the proof needs to be improved
  3. ZK-SNARK cryptography is vulnerable to attacks from quantum computers

Now let’s break down each of the above issues and compare to the up and coming ZK-STARKs.

 

Trusted Setup Phase

What if a government or powerful entity tried to incentivize parties involved with the setup of the ZK-SNARK to share the setup parameters? If that powerful entity was successful, they would be able to generate false proofs in a system widely known to be trusted. If for example, a Presidential vote for a country took place on a blockchain that was using ZK-SNARKs for transactions, there could be significant incentives to change the outcome of the election by creating false proofs for votes taking place.

The biggest problem with the ZK-SNARK approach is that users need to trust in the setup phase and the parties involved to setup the system honestly. Users of the system will never actually know if the setup phase was compromised at the point of setup, or at some point in the future. So, if this is the case, the door remains open for a system where users do not implicitly need to trust the parties involved in the system’s setup to be honest. When a system is used where the incentives are high to potentially break the system, entities will eventually try to break it.

In ZK-STARKs, there is no external trusted setup phase and the randomness used by the verifier is public information. Public randomness utilization is exceptionally important for the public to trust ZK proof systems, otherwise a powerful entity could exert their influence to obtain the setup parameters and generate false proofs. Given that there is no third party trusted setup phase and publicly verifiable randomness is used instead, ZK-STARK systems create verifiable trust.

 

Scalability

For those who pay attention to ongoing technical challenges in the blockchain space, the scalability discussion is center stage. Although outside the scope of this blog post, there are numerous ways to scale blockchains, all with their associated tradeoffs. For zero-knowledge proof systems, scalability of the system is paramount to achieve widespread adoption as you do not want to be waiting long periods of time to generate proofs or more importantly verify proofs. ZK-STARKs exhibit much higher scalability than ZK-SNARKs. Let’s breakdown the associated complexity of the ZK-STARK vs. the ZK-SNARK calculations into four different categories relative to scalability (results leveraged from ZK-STARK whitepaper):

  1. Arithmetic circuit complexity (an arithmetic circuit is a standard way to compute polynomials where addition and multiplication can be computed): In ZK-SNARK and ZK-STARK systems, the code to create the ZK programs is written in such a way for them to be broken down into circuits, and then computed — effectively the simplicity of the circuits complexity is relative to its computational efficiency. 
  2. Communication complexity (the amount of communication needed to solve a problem distributed among two of more parties): As the size of the computation grows, so does the communication complexity of the ZK-SNARK in a linear fashion, as opposed to the ZK-STARK which grows only slightly as computation size grows — a large advantage of ZK-STARKs vs. ZK-SNARKs.
  3. Prover complexity: ZK-STARKs are 10x faster than ZK-SNARKs as computation size increases, another significant advantage of ZK-STARKs vs. ZK-SNARKs.
  4. Verifier complexity: As computation size grows, ZK-STARKs grow only slightly again vs. ZK-SNARKS, which tend to grow in a linear fashion -> another significant advantage of ZK-STARKs vs. ZK-SNARKs.

The below is a simpler view of a benchmarking analysis completed between ZK-STARKS vs. ZK-SNARKs in the ZK-STARK whitepaper.

The above benchmarking illustrates that the ZK-STARK’s communication rises much slower than the ZK-SNARK as the underlying proof increases in complexity.

The above benchmarking illustrates that the ZK-STARK’s time to generate a proof rises much slower than the ZK-SNARK as the underlying proof increases in complexity.

The above benchmarking illustrates that the ZK-STARK’s time to verify a proof rises very slowly compared to the ZK-SNARK as the underlying proof increases in complexity.

Source: ZK-STARK white paper

In proof systems, there is a statement that the prover wants to assert as true to anyone who would like to verify the statement. For example:

Prover statement: Alice wants to prove she is the owner of a bank account with Acme Bank.

Effectively, when you slice up the above statement (statement broken up in code logic in post #2) into pieces for the zero-knowledge circuit to calculate and then generate a proof, the verifier mathematically checks the proof for correctness along with the associated verifier key. This process (especially the verification process) has been substantially sped up by using a newer algorithm called the Fast Reed-Solomon Interactive Oracle Proof of Proximity. For more detail on how the new algorithm utilized to increase the scalability of the ZK-STARK, I suggest reading Vitalik Buterin’s blog posts for an in-depth review.

  1. STARKs, Part I: Proofs with Polynomials
  2. STARKs, Part II: Thank Goodness It’s FRI-day

 

Quantum Computing

More recently, quantum computing has become a general topic of interest, and to some degree a more specific interest in the blockchain world (Qubit Protocol). IBM and Intel are both working on developing quantum computers however, estimates point to quantum computing being years away from large adoption. Quantum computing however does pose a risk to blockchain systems. Let’s dig into why quantum computers pose a risk to some aspects of blockchain cryptography.

Classical computers (the computers we utilize today) operate with bits, that store one of two states, 0 or 1. Quantum computers operate with qubits, which utilize a quantum physics principle called superposition to store state in either 0 or 1 when measured. However, when not being observed, qubits exist simultaneously between 0 and 1. (example of a qubit can be a photon, nucleus, or an electron)

Quantum computers will be designed to describe all correlations between qubits, i.e. effectively exponentially increasing computational throughput by 2^n (n = correlation per qubit). For example, 2 qubits is = 4 classical bits, 3 qubits = 8 bits, and 20 qubits = 1,048,576 bits. Considering quantum computers can process data in parallel vs. in serial for specific operations, they can significantly speed up certain computations, such as database searches, or finding the private key from a public key. 

 

Implications of Quantum Computing for Blockchains

Quantum computers are not good at everything, only specific types of calculations that parallel computation could exploit. For example, there is an algorithm called Shor’s algorithm that can be run on a quantum computer and will have the capability to run integer factorization calculations in parallel, thereby finding the prime factors of any given integer. Many of today’s current encryption schemes will not be resistant to quantum computing, such as RSA and ECDSA (Elliptic Curve Cryptography), the latter, which is used in Bitcoin and Ethereum for generation of private keys and public keys. For example, below is a basic depiction of the process that Bitcoin uses to generate the private key, public key, and public address.

Bitcoin key generation and address generation. 

The private key is generated from a number with an added level of entropy (randomness), the public key is generated from the private key, and the public address is generated from the hash of the public key. Quantum computers could utilize Shor’s algorithm to derive the private key, and then leverage the private key to forge transactions or steal a user’s balance (Bitcoin/Ethereum). Shor’s algorithm is really an issue with re-used addresses. For addresses that have yet to be used after generation, quantum computers could leverage Grover’s algorithms to solve for SHA-256 or SHA3–256 to find the public key from the public key hash. However, quantum computers would only be able to find the public key in half the time. Even at half the time, the key would not be found within anyone’s lifetime currently on Earth. Additionally, merkle-tree hashing is not currently susceptible to quantum computing attacks.

In the future, my expectation is cryptocurrencies will implement algorithms that are quantum resistant and will retain privacy. There are currently algorithms being developed that will be difficult to break with quantum computers, such as Lattice-based cryptography or multivariate cryptography.

ZK-STARKS do not rely on private-public key pairings (such as ECDSA), but rely on collision resistant hashing for interactive solutions (which Grover’s algorithm does not meaningfully break), and a random oracle model (a model that is typically used instead of general cryptographic hash functions where strong randomness assumptions are required for the oracle output) for non-interactive proofs (zk-nSTARK, n = non-interactive), therefore ZK-STARKs are currently secure against quantum computers.

Quantum computers are still years away from production capability (estimates point to 2026–2035), so no need to worry about their capabilities today. Also, quantum resistance and quantum proof are two terms to reflect on, like a watch that is resistant to water to a certain depth, and a watch that water cannot impact its functionality (water proof) -> until the true capabilities of quantum computers are known, it is hard to tell if an algorithm may be found that leverages quantum computers to circumvent current potential quantum resistant algorithms today, such as lattice or multivariate cryptography. However, blockchains such as Bitcoin and Ethereum will need to migrate to different algorithms to avoid quantum computers from potentially being used to attack their respective networks or users’ accounts.

An additional video that I found very insightful in understanding the difference between classical computers: https://www.youtube.com/watch?v=JhHMJCUmq28

 

Current State and Final Thoughts

Currently, ZK-SNARKs are available in the cryptocurrency Zcash, as well as the library libSNARK to build ZK-SNARK programs that can be leveraged in blockchains. ZK-STARKs are a newer technology, and not deployed in production capacity as of 6/2018. There is a new company called Starkware that is looking to solve some of the challenges with leveraging ZK-STARKs (one being the size of the proof) to commercialize the technology and leverage across multiple industries, including blockchains.

ZK-STARKs are scalable, transparent, have universal application, and currently quantum resistant. This allows for the creation of trust in the technology, as it is verifiable. There are many areas that can be enhanced by using a technology such as ZK-STARKs where trust is required, and there are large incentives to cheat, such as:

  1. Voting systems
  2. Running a computation and verifying its results, such as a blockchain’s past transactions
  3. Secure verification of information (minimizing data in transit)

My current thinking is we will see Zcash adopt zk-nSTARKs (n standing for non-interactive) technology into its blockchain in the future. Additionally, Ethereum may leverage ZK-STARKS in verifiable computation and potentially secure/anonymous transactions, as well as Dapps where privacy is important such as Brave’s web browser.

ZK-STARKs is an exciting technology that will enable trust to be achieved in computing systems that has not been achieved previously, as the trust created is verifiable. It will take time for this type of technology to be adopted however, it can give rise to increased transparency and trust where trust in storing data and sharing data has been shaken by the likes of Equifax and Facebook.

Get out this blog post on Medium as well! 

Close Menu