Trusted Setups, zkSNARKs, zkSTARKs, bulletproofs, and zkSHARKs – An Overview

Trusted Setups, zkSNARKs, zkSTARKs, bulletproofs, and zkSHARKs – An Overview

Zero-Knowledge Proofs are integral to the implementation of a truly private cryptocurrency. They can be trusted for data verification without the need to actually share any data. This means that a transaction in a digital environment can be successfully carried out without the need to share sender, receiver or account specific information.

However, when forming a blockchain supported by Zero-Knowledge Proofs (ZKPs) to run a private cryptocurrency on, the first problem that needs to be tackled is the formation of the Genesis block. The genesis block is the first block of any cryptocurrency.

Because of our dependence on ZKPs, in order to achieve the genesis block, we need to perform a separate ‘ceremony' that creates the parameters for the Zero-Knowledge Proving System. This additional step is what’s commonly known as the “Trusted Setup”.

In order to understand what a “Trusted Setup” is, we first need to define what zk-SNARKs are.

zk-SNARKs

The acronym zk-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” and refers to a proof construction where one can prove possession of certain information, e.g. a secret key, without revealing that information, and without any interaction between the prover and verifier of a Zero-Knowledge Proof system.

Zero-knowledge proofs allow one individual to prove to another that a statement is true, without disclosing any information beyond the validity of the statement. The main objective of a Zero-Knowledge Proof system is the fact that little to no information sharing is required in order to build trust between the two parties.

The “Succinct” part of the acronym means that these proofs are smaller in size and can be quickly verified. “Non-interactive” means that there is little to no interaction between the prover and the verifier of the Zero-Knowledge Proof system.

The “Arguments of Knowledge” part of the acronym points to the fact that zk-SNARKs are considered computationally sound. What this means it that a “dishonest” or invalid prover has a very low probability of guessing the right answers to the questions asked by the verifier.

To sum up, zk-SNARKs are the engine that allows for a transaction to be quickly and efficiently verified and added to the blockchain without revealing any details to the public. However, zk-SNARKs work under the assumption that the prover does not have the computing power to correctly guess the proofs. However, a computational limitation is eventually going to stop working as processors become more powerful.

Trusted Setup

zk-SNARKs require a pre-existing setup between the prover and verifier. A set of public parameters define the “rules of the game” for the construction of zk-SNARKs. On a blockchain, these parameters are required to prove the validity of a transaction.

However, this creates a centralization issue for the first or “Genesis" block because the parameters are often formulated by a very small group. Furthermore, the keys generated for the proof system to work can be used to create unlimited tokens on the chain undetected.

Only when you have trust that the keys generated for the initial setup were destroyed, the setup is called a Trusted Setup.

zk-STARKs

zk-STARK stands for “zero-knowledge succinct transparent argument of knowledge”. Depending on the implementation, a zk-STARKs are the more efficient and cheaper variant of zk-SNARKs. However, the distinctive feature in zk-STARKs is the fact that they do not require a Trusted Setup.

Technically speaking, zk-STARKs do no require an initial trusted setup because they rely on leaner cryptography through collision-resistant hash functions. Furthermore, zk-STARKs are prone to attacks from powerful computers of the future because of the number-theoretic assumptions of zk-SNARKs that are eliminated.

zk-STARKs are safer versions of zk-SNARKs and provide a simpler structure in terms of cryptographic assumptions. However, zk-SNARKs are much smaller in size as compared to zk-STARKs which means they have limitations of their own when scaling up.

Bulletproofs

Bulletproofs are short non-interactive zero-knowledge proofs that were first proposed in 2017 in a whitepaper by Stanford University. They are an efficient and secure form of range proofs that utilize zero-knowledge proofing methods like zk-SNARKS and STARKs, but do not require the trusted setup as required with zk-SNARKS but are closer to zk-STARKs in size.