Zero-Knowledge Proofs: Questionnaire Result Verification in Smart Contracts

TABLE OF LINKS

Abstract and Introduction

Background

Design

Discussion

Conclusions and References

II. BACKGROUND

A. Blockchain and Smart Contracts

Blockchain technologies are being increasingly adopted in different domains for their features regarding transparency and decentralization. Bitcoin [8] was the first proposed protocol based on this architecture, combining in its functioning techniques such as Proof-of-Work (PoW) [3], SHA-256 hashing, Merkle Trees, and the Elliptic Curve Digital Signature Algorithm (ECDSA). It is specially powerful because of its decentralized nature, provided through the Proof-of-Work validation done with each block of transactions added to a public registry known as the Blockchain. In the following years, variations on the protocol proposed by Bitcoin appeared, collectively known as cryptocurrencies, each having their own blockchain where the transactions are registered. Ethereum [4], Monero [12], Polkadot [13], Polygon [6], NEAR, Solana [14] and Avalanche [11] are some examples of these derivate protocols.

Of the protocols we just mentioned, Ethereum is a critical one to talk about as it was the first to work with the Ethereum Virtual Machine (EVM) [4] architecture, an essential feature on which many other blockchains are built upon. The EVM allows protocols to execute code in a decentralized manner and register all of its execution steps on the blockchain, making the results of that code transparent and unbiased. This code is then deployed to an address stored in the blockchain and referred to as a Smart Contract, i.e. a contract that enforces itself automatically.

A simple example of a task that can be performed using a Smart Contract is that of currency exchange. Usually, when two entities, Alice and Bob, each holding a different digital currency, want to exchange one for the other at a certain rate, a level of trust is needed. Indeed, either Alice has to transfer its currency to Bob first or vice versa, making the first entity that transfers vulnerable to the other not fulfilling their part of the deal. One way to balance this trust is by introducing a third-party entity, Charly, to which both parties transfer their funds so that Charly is tasked with ensuring that the deal is fulfilled. However, this only changes the protocol so that now both Alice and Bob have to trust Charly to act correctly. Here is where Smart Contracts come in, instead of having the parties transfer to a third one, transfer to a Smart Contract entity that automatically verifies that the deal is fulfilled without Alice and Bob having to trust in it, as it is executed on a decentralized network. This is illustrated in Figure 1. These trustless features of Smart Contracts then lead the way to a variety of applications to be built.

Decentralized Finance (DeFi) [1], Automated Market Makers [2], and decentralized social media [10], are among the many uses of Smart Contracts that have developed in recent years. Once again, the decentralized and trustless nature in the execution of the code for each of these applications is what allows them to provide an enhanced trustless performance in comparison to their traditional counterparts.

As we have said before, the essential base on which the Smart Contract infrastructure is built is the Blockchain. Let us note some of the implications of one particular attribute of the Blockchain, its functioning as a public registry. Every time a new block of valid transactions appears, it needs to be “mined”, i.e. finding a valid “nonce” value that when added at the end of the transaction block makes its SHA256 hash have certain characteristics. These characteristics are often that the hash has a number of zeros at the beginning, a number determined by the “difficulty” imposed by the network. This mining process is non-trivial by design, so that “work” needs to be performed before adding any transaction to the public ledger, hence the Proof-of-Work name. Notice that in order for the network to reach consensus that the work has been performed and the transactions validated accordingly, it is necessary for everyone to have complete access to each new transaction block. This makes any transfer of funds in the Blockchain public, including its receivers and senders. For this reason, it would be convenient to have a method through which the network could validate transactions without receiving compromising knowledge about its users, this is where Zero-Knowledge Proofs come in to play.

B. Zero-Knowledge Proofs

In the context of Blockchain transactions, one problem that arises is that, due to the public consensus nature of the protocol, all transactions are public. It is straightforward to check the movements of an entities funds by just checking the Blockchain registry. Although this can be partially avoided due to the easiness with which one can create new addresses (if an entity’s address is disclosed, it can just send its funds to a new one), it is still possible to just trace back the origins of any funds. A possible solution to this could work if there was a way for the network to verify the validity of transactions without them knowing the sender or the receiver, i.e. if there was a way to prove that a transaction is valid without disclosing any additional knowledge. Indeed, Zero-Knowledge Proofs are capable of doing this, as we will explaint next.

A Zero-Knowledge Proof (ZKP) is a method through which one entity can prove a statement to another one without disclosing more information than the fact that particular statement is true. For example, given a fixed function f : X −→ Y and a fixed value y ∈ Y . If we wanted to prove to a third party that we know a value x ∈ X such that f(x) = y, a trivial solution would be to just disclose the value of x we know. However, that shares more information than the fact that the statement is true. A ZKP would entail generating a proof generator function P and a proof verifier V . Such that we can generate a witness w = P(x) that does not disclose the value x, and that another entity can then evaluate with the verifier function V (w) and obtain a true or false value that determines whether the witness was created from a valid solution or not. This way, we can prove to another entity that we know a value of x such that f(x) = y, while disclosing zero knowledge about which specific value of x we know.

For a more intuitive example, consider a hashing function hash : I −→ H from an input space I to a hash space H, this function could be SHA-256, SHA-1, etc. Also, consider two entities, Alice A and Bob B. Imagine that Alice guards an entrance to a treasure cave, to which one can only enter by having a password ρ that is verified using its hash, i.e. Alice has the hash of the password h = hash(ρ). However, Alice herself does not have the password and cannot enter the cave. Now consider that Bob does have the password ρ and wants to enter the cave, but he does not want to disclose the password to Alice as to not have to share it with her. For most use cases, this can be achieved by having Bob compute the hash of ρ, and show it to Alice, having her verify that it is the same as h, the one she has. However, say that h is not disclosed to Alice through a private channel but through some public method as to ensure that she verifies passwords correctly and does not commit any dishonesty. This renders just showing the hash value h of the password not a valid method for verification. Usually, the only method left would be for Bob to disclose ρ to Alice and have her compute its hash, but there is another way to do this, which involves Zero-Knowledge Proofs.

Groth16[5] is a Zero-Knowledge Proof system designed to generate a proof-verifier pairing schema for satisfiability of any arithmetic circuit. What is important about the arithmetic circuit satisfiability problem is the fact that it is NP-Complete and thus allows for a wide arrange of statements to be translated into that form, including those which are often of interest in the context of ZKPs. Note that, arithmetic circuits are comprised of gates that compute arithmetic operations (addition and multiplication) on a field F, with wires connecting the gates to represent results from one going to another. Thus, recall the SAT problem, which is NP-Complete and formulated as “given a statement with boolean variables, is it possible to find an assignment for them such that the statement is true?”. Similarly, the arithmetic circuit satisfiability problem is NPComplete too and formulated as “given a statement with variables with values from a field F, is it possible to find an assignment for them such that the statement is true?”. This makes Groth16 an ideal system for working when generating ZKPs, being used for ZK languages like Circom 2 [7].

Coming back to our conundrum with Alice and Bob in the treasure cave. As it happens, hashing functions such as SHA256 can be expressed in terms of arithmetic circuit satisfiability and can thus have a corresponding Zero-Knowledge Proof generated. Therefore, in the situation we had, it is enough for Alice to have a SHA-256 ZK proof verifier V and for Bob to use the prover function P to generate a witness w = P(ρ). Bob then shares w with Alice, so she evaluates it with the verifier V (w) and determines that the witness is valid. Thus, Alice can be sure that Bob does have the password without receiving any information about what is its exact value.

Finally, it is straightforward to see how this can be applied to Blockchain transaction verification. Suppose that we have a transaction t represented in some space T, along with a validation function v that tells whether t is valid with the current state of the Blockchain, having 0 or 1 as output. Then for the transaction to be added by a miner into the registry, it would suffice to send a proof that v(t) = 1. Then, we could translate the computation of v into the Groth16 schema by using a compiler such as Circom 2.This would then allow us to generate a proof-verifier pair P and V . And finally, as was done with the Alice and Bob case, the sender would just generate a witness of the transaction w = P(t) and send it to the miners which would verify it by evaluating V (w). This schema is used by cryptocurrencies such as Monero and Zcash.

Now, see that in the context that concerns this paper, a ZKP could be generated for the validity of the evaluation of a questionnaire according to some set of constraints. This would allow the user or any third party to get a convincing proof of the evaluation having been performed fairly, without revealing any information about the answers that give certain results.