Non-Interactive Proofs

This post discusses non-interactive zero knowledge proofs, which can also be considered as digital signature algorithms. These can be used in blockchains to verify that the creator of a transaction has access to some secret data satisfying specific defined properties.

I previously discussed zero knowledge proofs, where a party Bob has some secret data satisfying certain properties. For example, this could be the private key associated with a publicly known Bitcoin address, or it could be a file whose SHA256 hash is equal to a given value, or maybe he knows a 3-colouring for a specified graph. In fact, it could be any data satisfying a clearly defined computable property. Bob wants to prove that he has such information to Alice but, as it is secret, he does not want to send her the data itself. Ideally, he wants to prove this without revealing any knowledge besides the simple fact that he knows of something satisfying the claimed properties. As was discussed, this can be achieved by an interactive proof where he exchanges messages with Alice until she is able to conclude with a high degree of confidence that he does indeed have the claimed secret. This as in figure 1 below, where Bob is acting as the prover and Alice is the verifier. As I will build on such zero-knowledge proofs here, if you are not already familiar with them it is suggested to first read the earlier post.

Alice verifies that Bob’s messages satisfy some required properties and, if they do, she accepts his proof. Otherwise, she rejects it. Recall the important properties:

• Completeness: If Bob has the claimed information, he is able to send messages to convince Alice of this fact.
• Soundness: If Bob does not have the claimed information, he is not able to fool Alice that he does, other than with a very small probability.
• Zero-knowledge: The verifier learns no information beyond the fact that Bob has the knowledge.

To ensure soundness, Alice should select her messages at random according to a specific procedure. Essentially, she is challenging Bob with unpredictable questions, which he is very unlikely to be able to answer all correctly unless he has the claimed knowledge. If Alice sticks to this method, she is an honest verifier. Similarly, if Bob has the claimed information then, to ensure completeness and zero-information, he should also construct his messages according to a specific procedure which, again, are randomized to ensure that he does not leak any secret information. If he does this, then he is an honest prover.

In many situations, the setup described above is not desirable or is not possible at all. It may be preferable for Bob to send a single proof to Alice for her to verify without having to respond with further questions. Maybe there is no communication channel from Alice to Bob, or maybe she will check the proof at a later date when she no longer has contact with Bob. This is the case, for example, where Bob is submits a transaction containing the proof to be included in a blockchain, and Alice is a network validator who later verifies this transaction. These are non-interactive proofs, so figure 1 should be updated to only include a single message sent from the prover to the verifier.

Technically, it is not possible for valid non-interactive proofs to be zero-knowledge, at least by the standards described in the previous post. For one thing, Alice could take the message sent from Bob, and pass it off as her own to try and prove that she has access to the secret data, which is incorrect. In fact, Bob may have already done this, and simply passed off a proof originally from someone else as his own. So, the best that we can expect, is for the message to prove that someone had access to the secret and constructed the message.

Furthermore, let us denote the message by m and the verification procedure by a function F(m). This is a computable function returning either True if it successfully verifies the proof, and False otherwise. If Alice does not have access to the original secret data, then she would not be able to construct a message m such that F(m) evaluates to True. However, if Bob sends her the proof, then he is directly giving her such an m. This is information in itself so, strictly speaking, the proof cannot be zero knowledge. Such considerations did not apply to interactive proofs where Bob is demonstrating that he can correctly respond to messages chosen randomly by Alice,.

There is a way around these issues, if we relax the zero-knowledge requirements slightly and make some assumptions regarding random oracles. The idea is that Bob can simulate an interactive proof, generating his messages in the usual way and using a pseudo-random number generator to generate the messages which (honest) Alice would otherwise have sent. The random numbers can use Bob’s previous messages as a seed to ensure that they are not predictable beforehand. The proof then consists of Bob’s sequence of messages from the simulation. A verifier can later reuse these messages and the same random number generator to rerun the simulation and check if it succeeds. This is the Fiat–Shamir heuristic, and is shown in figure 3 using h to denote the pseudo-random number generator.

For cryptographically secure pseudo-random numbers, we use a hash function. Under the random oracle model, these are considered to output random values, but are deterministic in the sense that if they are re-evaluated with the same input, then they regenerate the same output. While this is not strictly possible, hash functions do behave very much like this and there is no known way to predict the output of a secure hash function other than by computing it. The result is that we obtain non-interactive proofs which are zero-knowledge in the sense that, other than possession of the secret data, the only information that they reveal involves the values of the hash function or random oracle for the input values used in the proof.

While the points above suggest that non-interactive proofs can be trickier to construct and to analyse than their interactive versions, there is at least one factor which benefits the non-interactive case. For interactive proofs, the verifier has the freedom to choose her messages in whatever way she likes, taking into account any messages already received from the prover. We cannot assume that she is honest, and follows any particular scheme. She could be trying to extract secret information, rather than following the standard procedure to verify the proof. On the other hand, we know exactly how the verifier constructs messages in non-interactive proofs. This is because she does not really exist, and all of her messages are explicitly simulated by defined functions. Effectively, the ‘verifier’ is honest, allowing more flexibility in arranging the proofs while retaining the zero-knowledge property.

As mentioned at the top of the post, non-interactive zero-knowledge proofs are a kind of digital signature algorithm. The proof itself is just a message which can be verified to determine that it was constructed by someone in possession of some secret data satisfying defined properties. Validating the proof requires applying the hash function to the prover’s messages to simulate the verifier’s choices. This can be modified by appending an arbitrary message m in the hash function argument which, using the Fiat–Shamir heuristic described above, is the same as prepending m to the prover’s list of messages. This has the effect of changing the random number seed, so we still obtain a zero-knowledge proof of the same fact, but with respect to a different pseudo-random number scheme. Such a proof can be verified to confirm that it was constructed by someone in possession of both the secret data and the message m. Effectively, then, the proof acts as a digital signature for the message m, and the secret data is the private key. From this viewpoint, the public key is some data encoding the precise properties that the secret data is required to satisfy.

Taking the example where Bob’s secret data is a private key associated with a given public key, the non-interactive proof is just a signature scheme corresponding to these keys. Alternatively, if Bob’s secret data is a file with a specified SHA256 hash, then it gives a signature scheme where the file is the private key and the hash is the public one. Where Bob is claiming to have a 3-colouring of a given graph, the colouring is the private key and the graph is the public key.

---

Avoiding Brute-Force Attacks

When looking at the security of non-interactive proofs, we need to take into account that the prover could use a brute-force attack. For example, suppose that we start with an interactive proof where, if Bob does not have the claimed secret data, he has a 1 in a million chance of fooling Alice that he does. This may be an acceptable level of security. For the corresponding non-interactive one constructed using the Fiat–Shamir heuristic, Bob builds the proof in private. If he does not have the secret data, this will still only have a 1 in a million chance of being valid. However, Bob could construct lots of proofs, making small changes to his choices of messages in each iteration. It is quite possible that he could could construct millions of them, and then have a high chance of finding a valid proof and fooling the verifier.

Such brute-force attacks need to be considered when looking at the probability of someone without the secret data being able to prove that they do. The probability p of the interactive proof being broken should be multiplied by a large number N representing the number of brute-force iterations to give the updated probability bound Np. Equivalently, if p is the acceptable level of soundness for the interactive proof, then this should be divided by N for the non-interactive one. Suppose that Alice accepts a probability of 1 in a million as being an acceptable chance of incorrectly believing that Bob has the secret, but also that Bob could potentially run a billion iterations of the construction. Then, she should be aiming for a probability bound of 1 in a quadrillion for each attempted proof construction.

In practice, a probability of 2^-128 of breaking the soundness and finding a valid proof is considered sufficient to allow for a huge number of iterations using all the computing power in the world over a long period of time, while still leaving a negligible probability. This consideration is as with any digital signature or secure hashing algorithm, where we must suppose that an attacker has a massive amount of computing power over a long period of time (many many years) to try and brute-force a solution.

A further consideration is that, in a proof built up from many messages, Bob could try and brute-force each individual message rather than the whole proof at once. For example, consider the first proof of private key described in the previous post. After Bob’s first message consisting of a point on the curve, Alice has a binary decision to make, knowing that if Bob does not have the secret, he can only answer one of these two options. So, Bob can only have at most a 50% chance of fooling Alice. Repeating this n times, he only has a 2^–n probability. If we converted this using Fiat–Shamir as in figure 3, then it consists of a sequence of n exchanges with Alice’s choice at each time being determined by a hash of Bob’s previous messages. Even though brute forcing the entire construction would require an infeasible 2ⁿ attempts on average, he can attempt to force each message. On each of the n stages, Bob could try multiple choices for his first message until he can correctly respond to Alice’s choice. On average, this requires 2 choices. So, Bob is able to brute-force a proof that the verifier would accept, and it would only require an average of two tries for each stage.

The issue of brute-forcing each individual stage can be addressed by just looking at 3-message proofs. These consist of an initial random message from Bob, followed by a randomized question from Alice and a response from Bob. If our non-interactive proof is not of this form, and contains multiple messages from Alice, we can try to reorder the messages to put it in this form. This may not be possible in the interactive version while retaining the zero-knowledge property. For non-interactive proofs, the fact that the verifier is always honest since she is simulated by a random oracle, makes this much easier to do. Updating figure 3 gives the 3-message version shown in figure 4 below. The hash function is only applied once, to Bob’s initial message.

---

Example: Proof of Private Key

As an example, consider the second proof of private key given in the previous post. Recall that the keys are defined using an elliptic curve E, which is a cyclic group with generator point G and order equal to a huge prime number. The private key is an integer x in the range from 0 to p – 1 inclusive, and the corresponding public key is given by multiplying this by the group generator, P = x.G. The proof that Bob knows x is a 3-message interactive protocol consisting of the following exchanges.

1. Bob sends curve point R to Alice.
2. Alice chooses integer e and sends to Bob.
3. Bob sends integer s satisfying e.P + R = s.G to Alice.

As long as Alice chooses e at random in the range 0 to p – 1, the probability that Bob can give a valid response without knowing the private key x is bounded by 1/p. We noted that this is not really zero-knowledge, which Alice can exploit by choosing e in a way that depends on R. In the interactive case, this was fixed by adding an additional message where Alice commits to her choice of e up-front. In the non-interactive version, this does not matter since we fix Alice’s message to be honest by simulating it with the hash function h. We can take e = h(R). While this does technically depend on R, under the random oracle model it is effectively a random value so, statistically, is independent of R. It also assumes that the hash function output ranges over the integers from 0 to p – 1. Bob’s simulation of the interactive proof is now as follows.

1. Bob chooses a curve point R.
2. Alice’s message is computed as e = h(R)
3. Bob chooses an integer s satisfying e.P + R = s.G.

The non-interactive proof sent to Alice just consists of Bob’s two messages:

• A point R on the curve.
• An integer s, in the range 0 to p – 1 inclusive.

A verifier can check the proof by rerunning Bob’s simulation, which is the following procedure.

1. Compute the hash e = h(R).
2. Verify that e.P + R = s.G.

If Bob knows the private key, then he produces a valid zero-knowledge proof by selecting his messages in the same way as in the interactive case, which gives the following procedure.

1. Choose an integer t uniformly at random from 0 to p – 1.
2. Set R = t.G.
3. Compute e = h(R) and set s = ex + t.

Note that the non-interactive proof provided here is just the standard Schnorr signature corresponding to an empty message, and the verification procedure is the same as for Schnorr signatures. In fact, if use a string m to seed the random numbers by using h(e‖m) in place of h(e), we recover the Schnorr signature and verification procedure for message m. We have re-invented Schnorr signatures!

---

Example: Alternative Proof of Private Key

I have already demonstrated how one of the proofs of private key from the previous post can be made non-interactive, leading to the Schnorr signature algorithm. However, a different interactive proof was also described in the previous post, consisting of the following steps.

1. Bob sends a curve point R to Alice.
2. Alice chooses a curve point Q equal to either R or P + R, and sends to Bob.
3. Bob sends an integer s satisfying Q = s.G to Alice.

In step 2, Alice selects from her two options with a 50% probability for each. If Bob does not know the private key, then he will only be able to give a corect response for one of these. Hence, the probability that he can fool Alice into accepting the proof is 1/2. Since this is much too large, the steps above are repeated some number n times to reduce the probability bound to a negligible value 2^–n.

If Bob does now the private key x, then he selects R for the first message equal to t.G, where t is chosen at random from 0 to p – 1 inclusive. He can then use s equal to either t or ex + t in the final message, depending on Alice’s choice.

Although it is much less efficient than the Schnorr signatures described above, to demonstrate the ideas, I will describe how this method can also be made interactive. The first problem with this method is that it consists of multiple stages all of which Bob has a relatively large probability of 1/2 of erroneously proving he has the secret. Although these probabilities compound to a negligible value, in the interactive case he could brute-force each stage in turn by trying different choices of message. To fix this, we reorder the interactions to obtain a 3-message proof, with each message consisting of an array of n sub-messages combining the stages from above.

1. Bob sends a curve points R₁, ,R₂, …, R_n to Alice.
2. Alice chooses curve points Q_i, each independently chosen to equal to either R or P + R both with 50% probability, and sends to Bob.
3. Bob sends integers s_i satisfying Q_i = s_i.G.

Here, we are assuming that Alice is honest, so that her binary choices are made independently of Bob’s message. Using the Fiat–Shamir heuristic gives the following proof performed by Bob alone.

1. Bob chooses curve points R₁, ,R₂, …, R_n.
2. Bob computes hash h = h(R₁‖R₂‖⋯‖R_n).
3. Alice’s curve points Q_i are chosen to equal either R_i or P + R_i. The choice is determined by whether the i‘th bit of the hash h is equal to 0 or 1.
4. Bob chooses integers s_i satisfying Q_i = s_i.G.

This construction requires us to use a hash function h with at least n binary digits. The non-interactive proof that Bob sends to Alice is given by his messages from the simulated proof:

• Points R₁, ,R₂, …, R_n on the curve.
• Integers s₁, ,s₂, …, s_n.

To verify the proof, Alice reruns the steps above using the given values for Bob’s messages.

1. Compute the hash h(R₁‖R₂‖⋯‖R_n).
2. For each i, if the i’th bit of the hash is equal to 0, set Q_i = R_i otherwise set Q_i = P + R_i.
3. Verify that Q_i = s_i.G.

If Bob knows the private key, he can construct a valid proof in the same way as described for the non-interactive case. Specifically, he chooses integers t_i randomly in the range 0 to p – 1 inclusive, and sets R_i = t_i.G. If the i‘th bit of the hash is zero, he takes s_i = t_i, otherwise s_i = x + t_i.

If Bob does not know the private key then, as for the interactive case, for any choice of points R₁, ,R₂, …, R_n, the chance that he can find the corresponding integers s_i is no more than 2^–n.

---

Example: Proof of Graph Colouring

For the final example, I will look at how the zero-knowledge proof of a 3-colouring for a specified graph. Since this is an NP-complete problem, every other problem in class NP can be converted to this and, hence, be described by a non-interactive zero-knowledge proof. That is, in theory. It would be rather impractical to convert problems to 3-colourings and apply the method here. Instead, zk-SNARKs and zk-STARKs can be used, which are outside of the scope of this post.

Bob can interactively prove to Alice that he knows a 3-colouring by the following steps.

1. Bob commits to a colouring and sends to Alice.
2. Alice chooses an edge of the graph.
3. Bob reveals the vertices of this edge, so that Alice can confirm that they are coloured differently using only red, green or blue.

The commitment that Bob sends to Alice in the first step is a Merkle root of the tree, whose leaves are the vertex colours (concatenated with random strings, to avoid revealing information). If Bob does not know a 3-colouring, then there must be at least one edge whose vertices are not distinct allowed colours. So, if Alice chooses at random from the m graph edges, the probability of Bob giving a valid response is no more than 1 – 1/m. The steps are repeated a number n times to reduce this probability to (1 - 1/m)ⁿ. Choosing n large enough, this can be made negligible. If Bob does know of a 3-colouring, then he can use this in step 1 combined with a random permutation of the colours to make it zero-knowledge.

As in the alternative proof of private key, all of the n iterations can be combined into a 3-message proof, and the Fiat–Shamir heuristic gives a non-interactive proof.

1. Bob creates commitments C₁, ,C₂, …, C_n.
2. Bob computes hash h = h(C₁‖C₂‖⋯‖C_n).
3. Alice’s choice of graph edges E_i is a function of the hash h.
4. For each i, Bob reveals the Merkel proof for C_i corresponding to the vertices of the edge chosen in the previous step.

The hash function used must have enough binary digits to apply step 3. This is easiest if the number of edges m is a power of two, m = 2^k, so that k digits of the hash can be used to select the edge.

The non-interactive proof sent to Alice consists of Bob’s messages.

• Colouring commitments (Merkle roots) C₁, C₂, …, C_n.
• Pairs of edge colours (Merkle proofs) L₁, R₁, L₂, R₂, …, L_n, R_n, .

This is verified by Alice going through the same steps as for Bob above, using the values of Bob’s messages taken from the proof.