Zero Knowledge Proof — Basic unit of ZK Verification

Zero-knowledge proof — is a unique method whereby a user can prove to another user that he/she knows an absolute value without actually revealing any additional information.

What are zero-knowledge proofs?

Zero-knowledge proofs were first described in the research paper «The Complexity of Knowledge in Interactive Proof Systems» in 1985. Their essence is defined as the ability to confirm the correctness of a statement without conveying any additional information. Simply put, they can be used to prove that you know a secret without revealing the secret itself.

A zero-knowledge protocol involves two parties: the prover and the verifier. The prover demonstrates the truth of a statement, and the verifier evaluates the correctness of that statement. The exchange between the parties is limited to confirming that the statement is true; the content of the statement or the method of verification remains hidden.

Source: Сoinloan.io

Why is zero-knowledge proof necessary?

Consider the example of verifying identity or citizenship using a passport or driver's license.

While this method is common, it has privacy concerns: personal information (PII) is shared with a third party and stored in centralized databases. This creates risks, especially given the rise in identity theft—in 2021 alone, about 15 million Americans were affected.

Zero-knowledge proofs offer an alternative. They allow the veracity of a claim to be confirmed without revealing the underlying data. The protocols create compact proofs based solely on the fact (evidence) itself, without transferring personal information.

In an identification scenario, a single piece of zero-knowledge proof may be sufficient. If it is correct, the verifier can be confident in the truth of the statement without seeing any additional data. Similar logic applies to tasks such as the game  «Where's Waldo?»: it is possible to prove where a character is without revealing their exact location.

Source: Сoinloan.io

How zero-knowledge proofs work

Zero-knowledge protocols use special algorithms that take a statement as input and return a result: true or false. Commitment schemes are used for interaction between parties, allowing them to determine in advance the possible actions of the prover and verifier.

The proving party discloses only the information that corresponds to the verifier's choice, and the verifier also uses a commitment scheme to determine their choice.

Basic requirements for ZK protocols

1. Completeness. If the input data is correct and both parties act honestly, the proof will always be accepted.

2. Reliability. It is impossible to fraudulently force the protocol to accept invalid data. The prover will not be able to convince an honest verifier of the falsity, except with a small probability.

3. Zero knowledge. The verifier only learns whether the statement is true and does not receive information about the content of the data or the method of obtaining it.

There are three key elements to interactive ZK proofs:

1. Witness. The prover confirms knowledge of the secret (witness). They randomly select a question from a set corresponding to their knowledge, calculate the answer, and send it to the verifier.

2. Task. One correct answer does not prove knowledge. To reduce the likelihood of guessing, the verifier asks additional questions, selecting them at random.

3. Answer. The prover calculates the answers to the new questions and sends them to the verifier. This exchange is repeated several times to minimize the chance of evidence tampering.

Non-interactive zero-knowledge proofs

Interactive proofs require multiple interactions between the proving and verifying parties. This dependency precludes independent verification, and multiple message exchanges are required to confirm knowledge.

This problem is solved by non-interactive zero-knowledge proofs proposed by Manuel Blum, Paul Feldman, and Silvio Micali. They use a special key that is accessible to both the prover and the verifier. This allows the prover to demonstrate knowledge in a single round without revealing the witness itself.

Here's how it works:

1. The prover sends the secret data to the verification algorithm.

2. The algorithm creates a zero-knowledge proof.

3. The verifier uses a separate algorithm to check the proof.

The non-interactive proof model increases efficiency and allows third parties to verify correctness if they have access to the key and the verification algorithm. These principles underlie modern types of ZK-proofs, which are divided into several categories.

Source: Сoinloan.io

Privacy-focused blockchains

Traditional payment systems do not ensure user privacy: when paying by credit card, transaction information is available to banks, payment systems, and government agencies. Cryptocurrencies were originally created for private transactions between users, but most of them store data in public blockchains.

Most transactions on cryptocurrency networks are pseudonymous, not anonymous. This allows attackers to link virtual addresses to real people, especially if the user publishes the address in open sources. Analysis of data both inside and outside the chain can be used to track transactions.

Completely anonymous transfers are possible with privacy coins. These cryptocurrencies use blockchains that hide transaction details: the type and amount of assets, the time of the transaction, and the addresses of the sender and recipient. By using zero-knowledge proofs, network nodes can verify the correctness of transactions without accessing the data itself.

For example, zk-SNARKs are used in Zcash — a fork of Bitcoin with anonymity features. The system encodes the network consensus rules so that each transaction is verified without revealing any information about it.

During the verification stage, transaction information is converted into mathematical form. The verification function breaks it down into the simplest operations: addition, subtraction, multiplication, and division, forming an arithmetic scheme that ensures the correctness of the transaction.

Source: Сoinloan.io

Public blockchains

Zero-knowledge proofs allow transactions on public blockchains to be anonymized. For example, in the Tornado Cash protocol, user data is hidden, ensuring the confidentiality of transactions on the Ethereum network.

However, the use of such privacy tools remains voluntary, which creates the potential for them to be used for illegal purposes.

Identity protection

Zero-knowledge proofs allow individuals to verify their identity without revealing confidential information. These technologies are used in decentralized identification systems, where users control their digital identities and manage access to them. For example, citizenship can be verified without sharing passwords or other sensitive data.

In such systems, users collect verified information about themselves from certified issuers and store it in a special identity wallet. They then decide for themselves what data to provide to third-party organizations or services.

Source: Сoinloan.io

Verifiable computations

According to Vitalik Buterin's blockchain trilemma, it is impossible to simultaneously increase the security, scalability, and decentralization of a platform. Verifiable computations allow for faster transaction processing without compromising security.

The essence of the method is that calculations are transferred to an external executor, who returns the result along with proof of correct execution. This confirms the correctness of the operation without the need for re-checking.

This approach is used to scale Ethereum outside the main chain. Instead of changing the base protocol, computations are performed at a separate level, which increases network efficiency by using external resources.

1. Each transaction is processed on a separate chain, which generates the result along with ZK proof confirming the correctness of execution.

2. Ethereum immediately updates its state based on these results, without the need to re-execute operations or create additional proofs.

3. This approach reduces the load on the network and increases transaction throughput.

4. Proofs of correctness are used in zero-knowledge rollups and validums, two off-chain scaling methods that ensure security and efficiency.

A trilemma is a situation in which it is impossible to achieve three desired goals or conditions simultaneously.

Source: Сoinloane.io

Disadvantages of using zero-knowledge proofs

There is no such thing as a completely perfect ZK method. Zero-knowledge systems can be difficult to implement and potentially vulnerable to new technologies. One risk is unauthorized access to the private key that defines the protocol parameters. If an attacker creates false proofs, they may appear valid to verifiers.

1. Hardware requirements. Complex computations require specialized hardware that is not available to most users. This also affects the cost of applications using zero-knowledge proofs, which may charge higher fees.

2. Cost of verifying proofs. The complexity of the computations makes verification expensive. For example, verifying a single zk-SNARK proof for zk-rollups on Ethereum can cost around 500,000 gas.

3. Trust assumptions. The main problem with zk-SNARK is that the shared reference string is created once and used by multiple parties. In the trust establishment ceremony, the honesty of the participants is simply assumed, and users cannot verify it. Zk-STARK solves this problem by using publicly verifiable randomness. Other systems, such as zK-ConSNARK, claim to protect privacy without the need for a trust establishment ceremony.

4. Quantum computing threats. Encryption in zk-SNARK is based on elliptic curve-based algorithms (ECDSA). In the future, quantum computers may render this method insecure. Zk-STARK uses collision-resistant hash functions and does not rely on public-private key pairs, making it less vulnerable to quantum attacks.

In conclusion

Zero-knowledge proofs allow one party to convince another of the truth of a statement without revealing the information itself. They increase the throughput of blockchains, enable confidential coins to function, and find applications outside the cryptocurrency sphere.

Technologies such as zk-SNARK, zk-STARK, and Bulletproof share a common goal: to create an environment where users can remain anonymous and control their data.

Subscribe and get access to the GoMining course on cryptocurrency and Bitcoin, which is still free: https://academy.gomining.com/courses/bitcoin-and-mining