A Hands-On Tutorial for Zero-Knowledge Proofs: Part I

叁歲伎倆 2023-02-14 10:28 6阅读 0赞

#### Zero Knowledge Proofs ####

Zero Knowledge (AKA ZK) proofs are stories of the following type: side A states a claim and proves it to side B, after some deliberation between them, such that:

1.  B is sure that the claim is true with 99.99999% certainty.
2.  B has learnt nothing new in the process, other than that the claim is true.

[This Wikipedia article][] contains an excellent explanation of the idea, with some concrete examples.

In this series I’ll deal with *ZK arguments of knowledge*, which are not exactly the same as proofs, but they’re close enough. In short: a ZK proof can be trusted completely, even if the side who’s trying to prove their claim (usually referred to as “the prover”) has unlimited computational power. ZK argument-of-knowledge can be trusted under the assumption that if the prover indeed tries to cheat, it is polynomialy bounded (if you use credit cards on the internet, then you already assume that, btw).

In the world of ZK proofs, the other side of the exchange is often called “the verifier”. I’ll stick to this terminology here.

#### The Partition Problem ####

Given a sequence of numbers *a*0,*a*1,…,*a\*\*n*−1a0,a1,…,an−1, can one partition this sequence into two subsets that sum up to the same number?

If the sequence in question is 1,9,8,0,2,21,9,8,0,2,2, then the answer is clearly yes since 2+9=8+1+2+02+9=8+1+2+0.

However if the sequence is 2,3,4,5,6,72,3,4,5,6,7, then the answer is clearly no, since the sum is odd, and therefore there cannot be two subsets summing exactly to half of it each (the numbers are all integers).  
While these are simple enough instances, in general [this problem is NP-complete][] (though it has a pseudo-polynomial algorithm).

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzODYzMTE_size_16_color_FFFFFF_t_70_pic_center]

### Let’s Start Proving! ###

Suppose we have a python list *l*l of numbers, that defines our Partition Problem instance. We’ll say that another list *m*m is a satisfying assignment if:

1.  len(m) == len(l).
2.  All of the elements in *m*m are either 11 or −1−1.
3.  The dot-product of *l*l and *m*m is 0.

Note that this is equivalent to the statement of the partition problem, if we think of a ‘1’ in *m*m as assigning its corresponding number in *l*l to the left side of the equation, and ‘-1’ as assigning it to the right side.

Given *l*l, a proof for its satisfiability can be given by revealing *m*m, but that would violate the ZK requirement.

Let’s rewrite *l*l as the partial sum list of its dot product with *m*m.

Mathematically speaking, let *p\*\*i*:=∑0≤*k*<*i\*\*l*\[*k*\]⋅*m*\[*k*\]pi:=∑0≤k<il\[k\]⋅m\[k\].

So if *l*=\[4,11,8,1\]l=\[4,11,8,1\], and *m*=\[1,−1,1,−1\]m=\[1,−1,1,−1\], then *p*p will be one element longer: *p*=\[0,4,−7,1,0\]p=\[0,4,−7,1,0\].

Note that *p*p now has two interesting properties, if *m*m is indeed a satisfying assignment:

*  (property 1 of p) It starts and ends with 0.
 *  (property 2 of p) For every 0≤*i*<*n*0≤i<n, we have |*l*\[*i*\]|=|*p*\[*i*\+1\]−*p*\[*i*\]||l\[i\]|=|p\[i+1\]−p\[i\]|.

So here’s a first draft for a ZK protocol:

The verifier chooses a random 0≤*i*≤*n*0≤i≤n.

If *i*=*n*i=n, the verifier asks the prover to provide *p*\[0\]p\[0\] and *p*\[*n*\]p\[n\] and checks that they are both 0.

Otherwise, the verifier asks the prover to provide *p*\[*i*\]p\[i\] and *p*\[*i*\+1\]p\[i+1\] and checks that indeed |*l*\[*i*\]|=|*p*\[*i*\+1\]−*p*\[*i*\]||l\[i\]|=|p\[i+1\]−p\[i\]| (recall that *l*l is known to the verifier, as part of the claim made by the prover).

### What if the prover is lying??? ###

The above contains an implicit assumption that when the verifier asks the prover to provide some data, the prover will indeed provide it honestly. We don’t want to assume that, but we postpone dealing with this issue to the next post. For now, let’s assume everything is kosher.

### This doesn’t prove anything! ###

An observant reader will probably point out that asking about a single element doesn’t mean much. And that’s true, we’d like to ask many queries, and after enough of them - we’ll be certain that the claim is true. We’ll quantify this more accurately in the third (and last) post.

### This is not Zero-Knowledge! ###

Each query reveals something about *m*m, and so it is not zero-knowledge. Consequently, after enough queries - *m*m can be completely revealed.

That’s terrible! Let’s fix it.

### Manufacturing Zero-Knowledge ###

Mathematically speaking, we usually say that something provides no new information, if it appears random, or more precisely - if it is uniformly distributed over some appropriately chosen domain. Without getting into the exact definition, this means that to make something ZK, we mix it with randomness. So here’s how we do it here.

1.  Instead of *m*m as it was given to us, we flip a coin. If it shows heads, we leave *m*m as it is, if it shows tails, we multiply all of *m*m’s elements by −1−1. Note that since its elmenets were initially −1−1 and 11, and its dot product with *l*l was 0, this does not change its dot product with *l*l at all.
2.  We choose a random number *r*r and add it to all the elements of *p*p. This does not effect the second property of *p*p, but it changes the first property such that the first and last elements of *p*p now may not be zero. However, **they must still be identical to one another**.

Now suppose that before each query - we recompute this randomness (i.e. - flip the coin and change *m*m, and choose a random number *r*r and add it to the elements of *p*p).

If we choose *r*r carefully, then indeed, every two consecutive elements of *p*p will differ (in absolute value) by the corresponding element in *l*l but look otherwise random.

So, here’s the first piece of code we’ll need, something that takes a problem (i.e. *l*l) and a satisfying assignment (i.e. *m*m) and constructs a witness (i.e. *p*p) that will attest to the satisfiability of the problem instance:

import random
    
    def get_witness(problem, assignment):
        """
        Given an instance of a partition problem via a list of numbers (the problem) and a list of
        (-1, 1), we say that the assignment satisfies the problem if their dot product is 0.
        """
        sum = 0
        mx = 0    
        side_obfuscator = 1 - 2 * random.randint(0, 1)
        witness = [sum]
        assert len(problem) == len(assignment)
        for num, side in zip(problem, assignment):
            assert side == 1 or side == -1
            sum += side * num * side_obfuscator
            witness += [sum]
            mx = max(mx, num)
        # make sure that it is a satisfying assignment
        assert sum == 0
        shift = random.randint(0, mx)
        witness = [x + shift for x in witness]
        return witness

This post didn’t have nearly enough images as a blog post should have. Her’e one to make up for it:

[Part II][]

[Part III][]

--------------------

原文：https://www.shirpeled.com/2018/09/a-hands-on-tutorial-for-zero-knowledge.html

[This Wikipedia article]: https://en.wikipedia.org/wiki/Zero-knowledge_proof
[this problem is NP-complete]: https://en.wikipedia.org/wiki/Partition_problem
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzODYzMTE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200602140047787.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzODYzMTE=,size_16,color_FFFFFF,t_70#pic_center
[Part II]: http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge.html
[Part III]: http://www.shirpeled.com/2018/10/a-hands-on-tutorial-for-zero-knowledge_2.html