Sigma Protocol is Proof of Knowledge
通过证明Sigma Protocol is Proof of Knowledge，整理了heavy-row argument证明方法，此方法在SNARK和lattice-based ZK 中证明PoK时都有出现。
Definition 1: -protocol
A protocol is said to be a -protocol for relation if:
is of the "commit-challenge-response" 3-move form Completeness: if follow the protocol on input and private input to where the verifier always accepts. Special Soundness : From any and any pair of accepting conversations on input , where one can efficiently compute such that Special Honest-Verifier Zero Knowledge(SHVZK): There exists a polynomial-time simulator which on input and a random outputs an accepting conversation of the form with the same probability distribution as conversations between the honest on input .
Definition 2: Proof of Knowledge
Let be a function from bit strings to the interval The protocol is said to be a proof of knowledge for the relation with knowledge error if the following are satisfied:
Completeness On common input if the honest prover gets as private input such that then the verifier always accepts. Knowledge Soundness There exists a probabilistic algorithm called the knowledge extractor. This gets input and rewindable black-box access to the prover and attempts to compute such that For any prover let be the probability that accepts on input . There exists a constant such that whenever will output a correct in expected time at most
where access to counts as one step only.
One can think of the error as the probability that one can convince the verifier without knowing a correct . Being better than that requires some ability to actually compute and computing gets more efficient, the better you are at convincing .
Theorem: Let be a -protocol for relation with challenge length . Then is a proof of knowledge with knowledge error .
Completeness is clear by definition.
For knowledge soundness, we use a standard heavy-row argument. Let be the -matrix with a row for each possible set of random choices by and one column for each possible challenge value . An entry is 1 if accepts with this random choice and challenge, and 0 otherwise. Using as black-box and choosing a random challenge, we can probe a random entry in By rewinding we can probe a random entry in the same row, i.e., where uses the same internal random coins as before. Our goal is to find two 1 's in the same row; using special soundness the resulting two conversations give us sufficient information to compute a witness for efficiently. equals the fraction of 1-entries in .
Lemma 1: More than half of the 1’s are located in heavy rows.
: Let be the sub-matrix of consisting of all rows that are not heavy, and write for the total number of entries in and for those in . The number of 1 's in is and the number of 1 's in is smaller than by the definition. Then the number of 1 's in heavy rows satisfies
Lemma 2: Assume , a heavy row contains at least two 1’s.
Let be the number of rows in . be the number of rows in : So
Our approach will be to first repeatedly probe at random, until we find a 1 entry, a "first hit." This happens after an expected number of tries.
With probability greater than 1/2, the first hit lies in a heavy row. Now, if it does, we continue probing at random along this row the probability of finding another 1 in one attempt is
The expected number of tries to find 'the second hit satisfies
: Assume ,then . So
We would therefore be done in tries, which is good enough, as argued above.
However, with some probability smaller than the first hit is not in a heavy row. In that case we might spend too much time finding another 1 (if it exists at all!). To remedy this, we include an "emergency break", resulting in the following algorithm:
Probe random entries in until the first 1 is found (the first hit). Then start the following two processes in parallel, and stop when either one stops: Probe random entries in the row in which we found a 1 before, until another 1-entry is found (the second hit). Repeatedly flip a coin that comes out heads with probability for some constant , until get heads. This can be done by probing a random entry in and choosing a random number among . Outputs heads if the entry was a 1 and the number was
The probability that finishes after attempts is Using the estimate we get that the probability of finishing after or fewer attempts is at most For this bound is so we conclude that the probability that needs more than trials to finish is at least Now choose "large", say This will mean that with probability at least finishes after more than tries.
As before, if indeed the first hit is in a heavy row, then with probability at least Pr is done after fewer than tries (from Markovs inequality).
Therefore, with probability greater than finishes before in this case.
Overall, this procedure finds two 1's along the same row if we hit a heavy row and the right process finishes first, which happens with probability greater than and it runs in expected time
The required knowledge extractor now repeats the above algorithm until we have success. Since the expected number of repetitions is constant (at most 8 ), we obtain an algorithm that achieves its goal in expected time as desired.
So what if ? We treat this case by a separate algorithm, using the fact that when is so small, we are in fact allowed time enough to probe an entire row. The algorithm we describe then simply runs in in parallel with the above algorithm.
Define by so that (derived by ) Then we have at least 1's among the entries. At most of these can be alone in a row, thus at least of them must be in rows with at least two 1 's. Such a row is called semi-heavy. The algorithm now does the following:
Probe random entries until a 1 is found. Search the entire row for another 1 entry. If no such entry was found, go to step 1 .
To analyze this, note that the fraction of ones in semi-heavy rows is among all ones and among all entries. The expected number of probes to find a 1 is The expected number of probes to find a 1 in a semi-heavy row is So we expect to find a one in a semi-heavy row after finding 1's. For each 1 we find, we try the entire row, so we spend probes on this. In addition, we spend probes on finding 1 's in step so altogether we spend
which is certainly But this is no more than the time we are allowed: