ZK-SNARKs: Journey from Zero-Knowledge to Powerhouse Security

In this blog post, I will introduce you to the concept of zk-SNARKs, a powerful cryptographic tool that enables verifiable computation without revealing any information. I will explain how zk-SNARKs work, how they can be used in decentralised identity (DID) systems, and how Hela, a blockchain-based DID platform, leverages zk-SNARKs to provide privacy and security for its users.

What are zk-SNARKs?

zk-SNARKs stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”. It is a type of zero-knowledge proof, which is a way of proving that you know something without revealing what you know. For example, you can prove that you know the solution to a Sudoku puzzle without showing the solution, or that you know the password to a website without typing the password.

zk-SNARKs have some special properties that make them very useful for verifiable computation. Verifiable computation is the process of outsourcing a computation to a third party, and being able to verify that the computation was done correctly, without having to redo the computation yourself. For example, you can ask a cloud service to run a complex algorithm on your data, and get a proof that the result is correct, without having to trust the cloud service or reveal your data. We could also understand a complex function that would need computer for to have an output as on Fig 1. 

function C(x, w)

{

return ( sha256(w) == x );

}

Or this one : t(x)h(x) = w(x)v(x), where t, h, w and v are polynomials, and x is a variable. The equation is satisfied if and only if the computation is correct. For example, the QAP corresponding to the above circuit is :

t(x) = x^3 – x^2 – 2x + 1

h(x) = x – 1

w(x) = x^2 + x

v(x) = x^2 + 2x

t(x)h(x) = w(x)v(x)

And this figure give us the illustration of that.

zk-SNARKs have the following properties:

• Zero-knowledge: The proof does not reveal any information about the input, the output, or the computation itself. Only the validity of the computation is proven.
• Succinct: The proof is very short and easy to verify, compared to the size and complexity of the computation.
• Non-interactive: The proof can be generated and verified without any interaction between the prover and the verifier. The prover only needs to know the public parameters of the computation, which can be generated by anyone.
• Argument of knowledge: The proof convinces the verifier that the prover knows the input and the output of the computation, and that the computation was done correctly.

How do zk-SNARKs work?

The basic idea behind zk-SNARKs is to transform any computation into a polynomial equation, and then use algebraic techniques to prove and verify the equation. The process can be divided into four steps:

• Setup: The computation is encoded as a system of quadratic arithmetic programs (QAPs), which are polynomial equations with some constraints. A trusted party generates a common reference string (CRS), which contains some random values and some public parameters derived from the QAPs. The CRS is published and can be used by anyone to generate and verify proofs.
• Prove: The prover takes the input and the output of the computation, and uses the CRS to generate a proof. The proof consists of a few polynomial evaluations and some cryptographic signatures. The proof does not reveal any information about the input or the output, only that they satisfy the QAPs.
• Verify: The verifier takes the proof and the CRS, and checks that the proof is valid. The verifier does not need to know the input or the output, or the details of the computation. The verification is much faster and simpler than the original computation.
• Extract: The verifier can optionally extract the input and the output from the proof, if they have some additional information, such as a secret key or a hash. This allows the verifier to use the result of the computation for further purposes.

Trusted Setup

What we need to know :

1. -how does the trusted setup work
2. -crucial and challenging part of zk-SNARKs.
3. – The trusted setup phase
4. – The MPC  and zk-SNARK scheme.

• So, how does the trusted setup work, and why is it necessary for zk-SNARKs? To answer these questions, we need to understand some of the technical details of how zk-SNARKs are constructed. Without going into too much detail, zk-SNARKs are based on a technique called quadratic arithmetic programs (QAPs), which are a way of representing any computation as a system of polynomial equations. For example, if we want to prove that we know the solution to a Sudoku puzzle, we can encode the rules and the solution of the puzzle as a QAP, and then use zk-SNARKs to generate a proof that we know the QAP without revealing the solution.
• However, to generate and verify such a proof, we need some public parameters that are derived from the QAP. These parameters include two sets of polynomials, called the proving key and the verification key, that are used to construct and check the proof, respectively. The problem is that these polynomials are not random, but depend on a secret random seed, called the toxic waste, that is used to generate them. If anyone knows the toxic waste, they can create fake proofs that pass the verification, or extract the secret inputs from the proofs. Therefore, the toxic waste must be destroyed after the generation of the public parameters, and the public parameters must be trusted by all the parties involved in the zk-SNARK protocol.
• The trusted setup phase is the process of generating the public parameters and destroying the toxic waste in a secure and verifiable way. There are different methods and protocols for doing this, but the most common one is called the multi-party computation (MPC) ceremony. The MPC ceremony involves multiple participants, who each contribute some randomness to the generation of the public parameters, and then discard their secret keys. The idea is that as long as at least one of the participants is honest and does not keep or leak their secret key, the public parameters are secure and the toxic waste is effectively destroyed. The MPC ceremony also produces some evidence, such as signatures or transcripts, that can be used to verify that the participants followed the protocol correctly and did not cheat or collude.
• The MPC ceremony can be done in different ways, depending on the specific zk-SNARK scheme and the security requirements. For example, the first Zcash ceremony, which used the BCTV14 zk-SNARK scheme, involved six participants, who used a custom hardware device and a multi-layered encryption scheme to generate the public parameters and destroy the toxic waste. The ceremony lasted for three days, and was recorded and broadcasted online. The second Zcash ceremony, which used the Groth16 zk-SNARK scheme, involved over 80 participants, who used a more efficient and scalable protocol, called the Powers of Tau, to generate the public parameters and destroy the toxic waste. The ceremony lasted for six weeks, and was also recorded and broadcasted online.
• The trusted setup phase is a crucial and challenging part of zk-SNARKs, as it affects the security and trustworthiness of the zero-knowledge proofs. The MPC ceremony is a way of mitigating the risk of the trusted setup, by distributing the trust among multiple participants and providing some transparency and verifiability. However, the MPC ceremony is not perfect, and it still relies on some assumptions and trust in the participants and the protocol. Therefore, it is important for the users and developers of zk-SNARKs to understand the benefits and limitations of the trusted setup, and to choose the best method and protocol for their specific use case.

HelaDID

HelaDID is a decentralised identity platform that leverages blockchain technology and zero-knowledge proofs to provide secure, private,and verifiable digital identities for individuals and organisations[1] zk-SNARKs are a type of zero-knowledge proof protocol that allows one to prove that they possess certain information without revealing it and without any interaction between the parties proving and verifying the information[2] zk-SNARKs are used by HelaDID to enable users to create and manage their own identities, as well as to share and verify their credentials with others, without exposing any sensitive or personal data.[1]

References:

[1]https://z.cash/learn/what-are-zk-snarks/

[2] https://www.fool.com/terms/z/zk-snark