An Introduction to Zero-Knowledge and ZK SNARKS
16th December 2020 by Dr Mark Blunden @id-3 
An Introduction to Zero-Knowledge and ZK SNARKS
Suppose that you wish to prove to another party (who we will call the Verifier) that we know a secret password. What typically happens is that you tell the password to the Verifier, who checks it against a previously stored version (in practice, the Verifier will not store your actual password, but rather a value derived from it using a cryptographic hash function or similar one-way function).
A clear downside to this is that you (the Prover) are revealing your password to the Verifier. What Zero-Knowledge (ZK) does is enable you to prove something (such as knowledge or possession of a password or a cryptographic secret) to another party but do so without revealing any information about your actual secret. That is, the Verifier gains no (or zero) knowledge about the secret, other than learning that the Prover does indeed know the secret. If the Prover knows the secret then the ZK protocol should always succeed in convincing the Verifier of this, but if a Prover does not know the secret then the proof should always fail (with overwhelming probability).
The concept of Zero-Knowledge dates back to the 1980s. Zero-Knowledge proofs can be interactive or non-interactive, and protocols have evolved over the years. Early schemes include proving knowledge of a cryptographic secret (such as a Discrete Log), which may be used for identification purposes. More recent developments include ZK SNARKS, and new areas of application include cryptocurrencies with both Zcash and Ethereum using ZK protocols to provide privacy.
The acronym ZK SNARK stands for ‘Zero Knowledge Succinct Non-Interactive Argument of Knowledge. The property of succinctness comes from being relatively small in both size and the amount of computation required. SNARKS are a type or class of proof, and examples of ZK SNARKS include Bulletproofs, Plonk, Sonic, and one commonly referred to as Groth16 (denoting the author and year). Schemes differ in size of proof, efficiency of proof creation and verification, and trusted setup requirements.
So, returning to our earlier password example, a SNARK could be used to prove knowledge of a secret (such as a password) that hashes to a given value. However, using a SNARK in such a way for identification purposes does not really make sense – for one thing, it is non-interactive, and user authentication typically requires interaction between the Prover and Verifier to show the presence or ‘aliveness’ of the Prover. However, this example can help illustrate the difference between SNARKs and other more traditional ZK proofs.
An example of an interactive ZK proof for identification is where the Prover has a Public Key and proves in ZK to the Verifier knowledge of corresponding Private Key. To do this, the Verifier asks one or more questions. If the Prover knows the secret (the Private Key), then they can always answer correctly. If they do not know the secret then, depending on the protocol being used, they will either not be able (in any practical sense) to answer correctly, or may only be able to answer correctly some of the time. If the latter case, then the process is repeated sufficiently many times that the likelihood of the Prover not knowing the secret and being able to provide a correct answer every time becomes negligible. In either case, the verification process used by the Verifier is to check that the Public Key and the answer provided by the Prover are mathematically consistent, and the protocol ensures that when doing so the Verifier does not learn any information about the value of the Prover’s Private Key.
SNARKs work in a different way. A proof consists of public and secret inputs and a circuit (or series of mathematical steps or operations) that performs a computation on the inputs. In the example of proving knowledge of an input to a hash function, the public input will be a hash (output) value, and the secret input (such as a password, in the above example) will be an input to the hash function. The circuit computes the hash of the secret input and compares this with the public hash value that formed a part of the proof input, giving a true or false output depending on whether the comparison results in a match. The proof shows that a Prover has knowledge of secret input(s) that for the given public inputs cause the circuit to output a value of true. In a more general sense, the proof also demonstrates that a computation – as defined by the circuit – has been done correctly (in the sense that the circuit evaluates to true). The objective is that once created the proof can be verified at any later time and by any verifying party without requiring any interaction with the Prover.
Non-Interactive Zero Knowledge (NIZK) proofs such as SNARKs require that both the Prover and Verifier have access to some common knowledge defined by a Structured Reference String (SRS), or sometimes referred to as a Common Reference String (CRS). The SRS includes information about the relation or statement (which defines the circuit) being proved. For succinctness, some SNARKS use a summary of the statement being proved. The SRS also includes public Evaluation and Verification Keys, where the former is the set of values required by the Prover to create the proof, and the latter is the set of values required by the Verifier to verify the proof.
It is the creation of the SRS in a pre-processing phase that allows for the succinctness and performance advantages of some SNARKS, with alternative approaches currently having NIZK proofs that are larger or take longer to verify.
The SRS used in many NIZK proofs are dependent on random and secret information, and the security is dependent on this information remaining secret. Knowledge of such information allows the protocol to be subverted, which is why the secret information should be discarded and ‘forgotten’ once the SRS has been generated. The secure creation of the SRS is of vital importance, and is also a distinguishing feature between different SNARK schemes. Furthermore, an SRS is typically specific to a relation (or circuit), and so a new SRS is required whenever the relation changes.
One option is to use a trusted party. However, this can lead to issues such as to how to select a party that is widely trusted and accepted. An alternative option is to use a form of multi-party computation to collaboratively construct the Evaluation and Verification Keys. The aim is to involve a large number of parties, and the process should ensure that the resulting SRS is sound provided at least one of the participants is honest and erases their own secrets. This can result in trusted setup ceremonies that are open to all to participate, a by-product of which may be to engender an affinity for the scheme amongst the participants. An example of the use of trusted setup ceremonies is Zcash which established in such a way two distinct sets of parameters, one in 2016 for Zcash Sprout, and one in 2018 for Sapling.
Another approach is to create a Universal Reference String that can be used for any circuit up to a given size, thus removing the need to generate a new SRS every time the circuit (or relation) changes. Sonic is an example of a scheme that is universal and also updatable. Although Sonic does still require an initial trusted setup, participants can continue to add randomness by updating the SRS. As the reference string is updated, it is strengthened.
ZK SNARKS are a very important tool for providing privacy in blockchain cryptocurrencies such as Zcash, where they enable digital transactions to remain private. Address and transaction information can be selectively shared for auditing or regulatory compliance. However, comprehensive protection requires more than just zero-knowledge proofs. The wider adoption of such currencies, including the entry of institutional capital, also requires the use of extremely secure processing such as for holding in custody and transfers. Secure hardware technology such as Hardware Security Modules (HSMs) such as the Secure Vault HSM from HUB Security provide customisable handling of digital assets in an extremely secure environment. Bringing all these pieces together can ensure the value and protection required.
