zero-knowledge
Part 6
In part 6, we saw an outline of the Pinocchio zk-SNARK. We were missing two things - an HH that supports both addition and multiplication that is needed for the verifier's checks, and a transition from an interactive protocol to a non-interactive proof system.
In this post we will see that using elliptic curves we can obtain a limited, but sufficient for our purposes, form of HH that supports multiplication. We will then show that this limited HH also suffices to convert our protocol to the desired non-interactive system.
We begin by introducing elliptic curves and explaining how they give us the necessary HH.
Elliptic curves and their pairings
We move on to discussing non-interactive proof systems. We begin by explaining exactly what we mean by 'non-interactive'.
Non-interactive proofs in the common reference string model
The strongest and most intuitive notion of a non-interactive proof is probably the following. In order to prove a certain claim, a prover broadcasts a single message to all parties, with no prior communication of any kind; and anyone reading this message would be convinced of the prover's claim. This can be shown to be impossible in most cases.[5]
A slightly relaxed notion of non-interactive proof is to allow a common reference string (CRS). In the CRS model, before any proofs are constructed, there is a setup phase where a string is constructed according to a certain randomized process and broadcast to all parties. This string is called the CRS and is then used to help construct and verify proofs. The assumption is that the randomness used in the creation of the CRS is not known to any party - as knowledge of this randomness might enable constructing proofs of false claims.
We will explain how in the CRS model we can convert the verifiable blind evaluation protocol of part 4 into a non-interactive proof system. As the protocol of part 6 consisted of a few such subprotocols it can be turned into a non-interactive proof system in a similar way.
A non-interactive evaluation protocol
[5]In computational complexity theory terms, one can show that only languages in BPP have non-interactive zero-knowledge proofs in this strong sense. The type of claims we need to prove in Zcash transactions, e.g. 'I know a hash preimage of this string', correspond to the complexity class NP which is believed to be much larger than BPP.
[6]The images used were taken from the following article and are used under the creative commons license.