Proof systems have fascinated computer scientists for the last forty years, especially in the context of computation complexity theory.

Blockchain has brought to light the Zero-Knowledge technology which has since evolved tremendously.

This article will try to explain how Zero-Knowledge protocols work and how this technology can revolutionize the world as we know it today.

To understand the origin of Zero-Knowledge proofs, we have to go back to the 90's when cryptography researchers Shafi Goldwasser, Silvio Micali (now CEO of Algorand) & Charles Rackoff first introduced it.

At the time, research was purely theoretical and mathematical and was based on interactive proof systems where 2 parties intervened in an exchange: the prover and the verifier.  The prover must convince the verifier of the truth of a mathematical statement.

However, these systems are not mature enough to be implemented, and it will be necessary to wait until 2013 for blockchain to be the first concrete application of these systems.

Seven scientists will then propose Zcash, a protocol using ZK proofs to exchange tokens in a more confidential way than Bitcoin.

These scientists noticed that Bitcoin does not guarantee the anonymity behind public addresses and that a lot of confidential information can be deduced from its decentralized public register.

In ZK protocols, two parties are involved in an information exchange: a prover and a verifier. The prover will have to prove that a statement is true, but without ever revealing it to the verifier.

Let me illustrate my point with the famous game Where's Charlie.

If I ask you to find Charlie you can spend time and energy looking for him, but I can also prove to you that I know where Charlie is without revealing his location.

In the context of blockchain, this means that the prover will be able to prove that he has verified thousands of transactions without having to reveal the content of these transactions only through proof.

3 properties must be satisfied:

• Completeness: if the prover and the verifier strictly follow the protocol rules, the verifier has no reason to refuse the proof.

• Soundness: an honest verifier cannot be corrupted (with a very high probability) despite a malicious prover.

• Zero-Knowledge: the verifier learns nothing more from the prover than the veracity of the statement.

Whether ZK-SNARKs or ZK-STARKs, both cryptographic proof technologies have greatly reduced interaction between the prover and the verifier (N comes from Non-Interactive). The interaction has been reduced so that the prover and the verifier exchange only the proof.

Non-interactive also means that the code can be deployed and act autonomously.

The S is for Succinct: the proof size has been reduced and the time to verify the proof is exponentially faster than the execution time.

The K for Of Knowledge means that it’s impossible to construct proof without having the required information.

AR for argument means that SNARKs are considered "rational" from a computational point of view. To simplify, a dishonest prover has not much chance of successfully cheating.

Let's go into more detail about these 2 technologies and discover what makes them different.

ZK-SNARKs were first introduced in 2012.

They are based on a circuit construction allowing to prove mathematically the different steps of computation. These circuits will be defined by public parameters and size.

The public parameters must be generated in an initial configuration phase: the Parameter Generation Ceremony, a key process in this type of protocol.

A public key and private key pair will be generated in a chunk way as part of this ceremony.  The public key is kept but the private key is destroyed because a malicious actor could counterfeit tokens if he got his hands on it.

Six geographically dispersed people, without knowing each other until the end of the ceremony, will then use the MPC (Multi-Party Computation) to fragment the creation of the key pair.

Once the key pair is generated, the participants will combine their fragments to generate the circuit parameters and will end up destroying their private key fragments.

A single participant destroying his fragment makes the entire reconstitution of the private key impossible.

Clips from the Zcash ceremony are available on YouTube (by the way, Edward Snowden was one of the participants).

The first disadvantage of SNARKs is that the ceremony involves a small circle of participants, both in number and in required computing power, which is not optimal for decentralization.

In addition to being difficult to perform, this key generation process causes toxic waste.

The second disadvantage is the slowness of the prover, which limits SNARKs in terms of scaling.

The third disadvantage is that SNARKs are threatened by quantum computing because a prover with enough computing power could create fake proofs and thus threaten the security of the network.

All these limitations make ZK-SNARKs unsuitable for long-term use, both in terms of security and scaling.

STARKs were introduced in 2018 and can be considered an enhancement to the ZK-SNARK protocol.

I'll talk more about STARKs in an upcoming article on StarkWare, but keep in mind that they offer many advantages compared to SNARKs.

The first is that STARKs rely on more symmetric cryptography with collision-resistant hash functions protecting them from quantum computers.

Secondly STARKs, unlike SNARKs, don’t need a ceremony requiring trust (hence the T for Transparency).

STARKs proofs are larger than SNARKs (288 bytes vs. a few hundred ko), however, their implementation is faster and cheaper, the proof time is more efficient in terms of size, and they are also more secure.

STARKs are more documented than SNARKs and the ecosystems around this technology are growing fast, bringing a large number of developers.

Proofs are a means to an end, and this end is integrity. A term at the heart of proof systems and cryptography in general.

As Clive Staples Lewis defines it perfectly: "Integrity is doing the right thing, even when no one is watching".

Applied to cryptographic proof systems, integrity means that users' funds are processed correctly and honestly without the need to verify the security process.

As you can see, using cryptography to prove a statement without revealing its content would save time, money, and privacy in many areas.

For example, proof of password possession could be provided rather than having to enter it at each connection, which would limit the number of attacks.

In the context of signing confidential documents, one could simply provide proof of signature without having to reveal the content of these documents.

Or prove the discovery of a new vaccine without revealing its composition.

The possibilities are limitless.

Proof systems have fascinated computer scientists for the last forty years, especially in the context of computation complexity theory.

Blockchain has brought to light the Zero-Knowledge technology which has since evolved tremendously.

This article will try to explain how Zero-Knowledge protocols work and how this technology can revolutionize the world as we know it today.

To understand the origin of Zero-Knowledge proofs, we have to go back to the 90's when cryptography researchers Shafi Goldwasser, Silvio Micali (now CEO of Algorand) & Charles Rackoff first introduced it.

At the time, research was purely theoretical and mathematical and was based on interactive proof systems where 2 parties intervened in an exchange: the prover and the verifier.  The prover must convince the verifier of the truth of a mathematical statement.

However, these systems are not mature enough to be implemented, and it will be necessary to wait until 2013 for blockchain to be the first concrete application of these systems.

Seven scientists will then propose Zcash, a protocol using ZK proofs to exchange tokens in a more confidential way than Bitcoin.

These scientists noticed that Bitcoin does not guarantee the anonymity behind public addresses and that a lot of confidential information can be deduced from its decentralized public register.

In ZK protocols, two parties are involved in an information exchange: a prover and a verifier. The prover will have to prove that a statement is true, but without ever revealing it to the verifier.

Let me illustrate my point with the famous game Where's Charlie.

If I ask you to find Charlie you can spend time and energy looking for him, but I can also prove to you that I know where Charlie is without revealing his location.

In the context of blockchain, this means that the prover will be able to prove that he has verified thousands of transactions without having to reveal the content of these transactions only through proof.

3 properties must be satisfied:

• Completeness: if the prover and the verifier strictly follow the protocol rules, the verifier has no reason to refuse the proof.

• Soundness: an honest verifier cannot be corrupted (with a very high probability) despite a malicious prover.

• Zero-Knowledge: the verifier learns nothing more from the prover than the veracity of the statement.

Whether ZK-SNARKs or ZK-STARKs, both cryptographic proof technologies have greatly reduced interaction between the prover and the verifier (N comes from Non-Interactive). The interaction has been reduced so that the prover and the verifier exchange only the proof.

Non-interactive also means that the code can be deployed and act autonomously.

The S is for Succinct: the proof size has been reduced and the time to verify the proof is exponentially faster than the execution time.

The K for Of Knowledge means that it’s impossible to construct proof without having the required information.

AR for argument means that SNARKs are considered "rational" from a computational point of view. To simplify, a dishonest prover has not much chance of successfully cheating.

Let's go into more detail about these 2 technologies and discover what makes them different.

ZK-SNARKs were first introduced in 2012.

They are based on a circuit construction allowing to prove mathematically the different steps of computation. These circuits will be defined by public parameters and size.

The public parameters must be generated in an initial configuration phase: the Parameter Generation Ceremony, a key process in this type of protocol.

A public key and private key pair will be generated in a chunk way as part of this ceremony.  The public key is kept but the private key is destroyed because a malicious actor could counterfeit tokens if he got his hands on it.

Six geographically dispersed people, without knowing each other until the end of the ceremony, will then use the MPC (Multi-Party Computation) to fragment the creation of the key pair.

Once the key pair is generated, the participants will combine their fragments to generate the circuit parameters and will end up destroying their private key fragments.

A single participant destroying his fragment makes the entire reconstitution of the private key impossible.

Clips from the Zcash ceremony are available on YouTube (by the way, Edward Snowden was one of the participants).

The first disadvantage of SNARKs is that the ceremony involves a small circle of participants, both in number and in required computing power, which is not optimal for decentralization.

In addition to being difficult to perform, this key generation process causes toxic waste.

The second disadvantage is the slowness of the prover, which limits SNARKs in terms of scaling.

The third disadvantage is that SNARKs are threatened by quantum computing because a prover with enough computing power could create fake proofs and thus threaten the security of the network.

All these limitations make ZK-SNARKs unsuitable for long-term use, both in terms of security and scaling.

STARKs were introduced in 2018 and can be considered an enhancement to the ZK-SNARK protocol.

I'll talk more about STARKs in an upcoming article on StarkWare, but keep in mind that they offer many advantages compared to SNARKs.

The first is that STARKs rely on more symmetric cryptography with collision-resistant hash functions protecting them from quantum computers.

Secondly STARKs, unlike SNARKs, don’t need a ceremony requiring trust (hence the T for Transparency).

STARKs proofs are larger than SNARKs (288 bytes vs. a few hundred ko), however, their implementation is faster and cheaper, the proof time is more efficient in terms of size, and they are also more secure.

STARKs are more documented than SNARKs and the ecosystems around this technology are growing fast, bringing a large number of developers.

Proofs are a means to an end, and this end is integrity. A term at the heart of proof systems and cryptography in general.

As Clive Staples Lewis defines it perfectly: "Integrity is doing the right thing, even when no one is watching".

Applied to cryptographic proof systems, integrity means that users' funds are processed correctly and honestly without the need to verify the security process.

As you can see, using cryptography to prove a statement without revealing its content would save time, money, and privacy in many areas.

For example, proof of password possession could be provided rather than having to enter it at each connection, which would limit the number of attacks.

In the context of signing confidential documents, one could simply provide proof of signature without having to reveal the content of these documents.

Or prove the discovery of a new vaccine without revealing its composition.

The possibilities are limitless.