Understanding Zero-Knowledge Proof through a Top-Down Approach

Part 1: Introduction to the Zero-Knowledge Proof

By Jinghui Liao, Core Developer, Neo

Introduction

Neo is ready to bring support to zero-knowledge proof functionality after nearly one year of validation and development by Neo Global Development (NGD). This work is driven by Doubi, a senior NGD developer, and Erik, the co-founder of Neo. As a result, we will be presenting a series of zero-knowledge proof articles to the community in a top-down approach. This first article in an upcoming series introduces the concept of the zero-knowledge proof to the Neo community and explores some simple new examples that illustrate this functionality. Further articles will explore new uses that this functionality enables in the blockchain environment and the Neo ecosystem, and more.

The Zero-Knowledge Proof in Daily Life

First, as a simple definition, the zero-knowledge proof is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, while the prover avoids conveying any additional information apart from the fact that the statement is indeed true.

For those who are unfamiliar with cryptography and the concept of the zero-knowledge proof, let’s first establish some foundational context for this method of proof. To do this, we’ll consider some examples illustrated by familiar, every-day situations. Some of these concepts are overly-simplified to a degree in the interest of providing easily understood examples.

Example 1: Reclaiming your lost phone

The best example of a required zero-knowledge proof would be a situation where you must prove to someone who found your phone that this phone is exactly your phone. In this example:

• The best proof will be to enter your phone’s password or to unlock the phone with your fingerprint.
• Unlocking the phone itself is proof of the phone ownership.
• During this process, you do not disclose any password or other biometric information to the finder, so this proof process is a simple zero-knowledge proof.

Example 2: Buying alcohol when you are at least 18 years old

In this next example, let us assume that you live in an area where local law requires you to be at least 18 years old in order to buy alcohol. If you want to let someone know that you are at least 18 years old without disclosing your actual date of birth, you can use the zero-knowledge proof concept to meet this need.

For example, you could accomplish this outcome by allowing the person to whom you want to prove that you are over 18 to see you buy alcohol in a supermarket that is publicly recognized as law-abiding. The logic for this example works this way:

• We know that law-abiding supermarkets always check customer IDs when the customers try to buy alcohol.
• It is known that only customers who are at least 18 can successfully buy alcohol in this supermarket.
• By allowing this person to see you purchase alcohol at this supermarket (but not showing this person your ID), you can show this person that you are 18 or over without revealing your specific age to them. This process is the zero-knowledge proof in this case.

Example 3: Creating a solvable Sudoku puzzle

In this example, let’s imagine that you created a Sudoku puzzle that is solvable, but you are challenged by someone who believes that there is no solution to this Sudoku puzzle. Further, imagine that you want to prove to this person (the challenger) that this puzzle does indeed have a solution, but you cannot directly tell him the answer.

You can use the zero-knowledge proof concept to solve this challenge:

• First, you will write the numbers in this Sudoku puzzle on cards, and then arrange them in a 9×9 grid according to the solved Sudoku. Then you turn them all over so that the numbers are facing down (not allowing the challenger to see the cards as you arrange them).
• Following this, you will let the challenger choose any card in any row or column. You will then collect all of the remaining cards in that row or column, shuffle them, and give them to the challenger.
• The challenger will now review the cards and verify that the numbers of these cards all fall within the range of 1 to 9, without duplication.
• After you have repeated this process for each column and each row, you will have proven to the doubter that the Sudoku puzzle has a solution. And you did not give away the answer to the puzzle in the process of proving it.

Example 4: The “Spot the differences” game

In a final example of a simple, zero-knowledge proof, let’s consider one more real-life scenario. This scenario is called the “spot the differences” game. In this game, you must locate a single, square dot that is randomly located on a drawing board among another 9,999 dots, all of which are round. The total number of dots is 10,000 dots. As a further requirement, you will need to prove that this square dot does exist by showing it to the other players without revealing its exact position to them.

Using the concept of zero-knowledge proof, you will hide all of the information about the square dot–especially its location–except for the shape of this dot. To do so:

• You will mask the drawing board with a piece of black cardboard much larger than the board, leaving in the middle of this black cardboard a single, small gap that is the same size as a dot on the board.
• You can then move this gap to the position of the square dot and show this particular dot to the other players.
• Because the black cardboard is much larger than the drawing board, it completely obscures the drawing board. Therefore the other player can see the square dot, but they cannot see its location within the larger arrangement on the board.

Blockchain and the zero-knowledge proof

Now, with some baseline understanding of what the zero-knowledge proof represents, let’s consider how this functionality can come into play within the world of blockchain technology.

First, as a reminder, the very nature of blockchain is built on decentralized trust. A trustworthy system requires users to make all data public. It is only when any of the nodes on the blockchain can verify the data on the whole blockchain that we can realize decentralized trust on the blockchain. There is a price to be paid in this model: Privacy of the data on the blockchain is sacrificed. On the blockchain network, all transaction information is public. In other words, everyone on the network is able to know the account actions of anybody else on the network.

There is a key challenge to this situation: Because there is no on-chain privacy protection, many application scenarios that must protect user privacy cannot be realized on the blockchain.

We can consider anonymous voting as one such example: Anonymous voting cannot be implemented in a public network. All of the network’s users will know who signed the transaction and will see the identity of the voter when that person votes. Thus, if we want to enable anonymous voting on the blockchain, we would need to create some type of privacy protection feature.

The transparent nature of the blockchain poses another challenge: When a user performs multiple on-chain operations through one account, hackers may be able to infer a user’s identity in real life through the user’s operation history.

Research regarding on-chain privacy protection has been initiated to solve problems such as these that stem from the lack of privacy in on-chain transactions. This research is very much early stage and in process today.

Researchers are taking several different technical approaches to address the need for privacy protection in the blockchain area:

• One approach uses a hardware-less, trusted execution environment, or TEE
• Some solutions use homomorphic encryption to hide user information
• Some projects use ring signatures to hide the user’s transaction information
• Additionally, third-party services such as obfuscators can hide user transactions

However, the most widely studied and widely used technical approach to addressing the need for on-chain privacy is the zero-knowledge proof scheme, as explored at a basic level in this article.

Building on this baseline level of understanding, the upcoming Part 2 in this series of articles will explore a range of zero-knowledge proof applications within the blockchain environment.

Copyright © 2023, All rights reserved