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. Continue reading “Non-Interactive Proofs” →