# Is this a valid construction of ZKP for this class of problems?

Let’s say we have a problem $$P$$ that can be described in $$a_1$$ bits and that its solution can be described in $$a_2$$ bits. Say there exists a program $$S$$ that can check whether the described solution is indeed a solution for the described problem using no more than $$m$$ bits of memory and terminates after performing no more than $$t$$ instructions. I attempt to construct a ZKP for this problem that proves with $$1$$ bit of certainty that the adversary has a solution for an instance of $$P$$ in $$mathcal{O}((mt)^2)$$. More precisely, for certainty $$1-varepsilon$$ that he has the solution, it takes $$mathcal{O}(mtlog(varepsilon))$$ queries, each of size $$mathcal{O}(mt)$$ and $$mathcal{O}(mt)$$ time complexity.

Firstly, for any program $$S$$ that uses no more than $$m$$ bits of memory (including the code, inputs and outputs) and terminates after no more than $$t$$ instructions there must exist a logic circuit $$C$$ that performs the program $$S$$ in time (and space) complexity $$mathcal{O}(mt)$$ because the standard personal computer is an example of it: CPU (as without cache) will take $$mathcal{O}(t)$$ cycles, each of which will take at least that amount of time that RAM (+ CPU cache) needs to serve the memory to the registers, which is $$mathcal{O}(m)$$ in our case. If the program $$S$$ isn’t branchless and doesn’t randomly access the memory, we can easily construct a simple circuit for it.
Say we have that problem $$P$$, a program $$S$$ for it and the circuit $$C$$ for $$S$$. Say the first layer of $$C$$ consists of $$a_1+a_2$$ bits and the last layer consists of only one bit. Say that $$C$$ only has binary gates: with two input bits and one output bit. This is possible if we include all $$2^4$$ possible gates and if we use at least $$2$$ vertices in the circuit. Let’s give each ipnut bit and gate of $$C$$ a unique index. The value of the input bit indexed by $$k$$ or of the output bit of the gate indexed by $$k$$ we will call $$b_k$$. The binary operator that the gate indexed by $$k$$ uses we will call $$G_k$$. If the first and the second input for the gate indexed by $$k_3$$ come from input bits or gates indexed by $$k_1$$ and $$k_2$$ (in that order), then we can say $$b_{k_3}=G_{k_3}(b_{k_1},b_{k_2})$$. Say the indices represent the order in which we can calculate these $$b$$‘s using these equations: we can calcuate $$b_k$$ if we already calculated $$b_{k’}$$ for all $$k’in{rinmathbb{N}|0. Let’s call the set of indices $$I$$. Now we will include another variable $$p$$ to the system which is a whole number greater than $$0$$ and not greater than $$8$$. Let $$O$$ be the set of all binary strings of length $$8$$. Let $$O’subset O$$ be the set of all binary strings of length 8 that contain exactly $$2,4$$ or $$6$$ ones. Let $$O”subset O’subset O$$ be the set of all binary strings of length 8 that contain exactly $$4$$ ones and $$4$$ zeros. Let’s define a "probabilistic function" $$R_p:O’rightarrow O”times O”$$ that operates like this on the input $$xin O$$: we pick a random index $$qneq p$$ such that bits at indices $$p$$ and $$q$$ in $$x$$ are different. We pick a random $$yin O”$$ which coincides with $$x$$ at indices $$p$$ and $$q$$. We pick another random index $$q’$$ such that $$pneq q’neq q$$ and that bits at indices $$p$$ and $$q’$$ in $$y$$ are different. We pick a random $$zin O”$$ which coincides with $$y$$ at indices $$p$$ and $$q’$$. We define $$R_p(x)=(y,z)$$. Let’s define another "probabilistic function" $$D_p(x,y):O”times O”rightarrow O”$$ that operates on the input $$xin O”$$ like this: We pick a random $$zin O”$$ such that there are exactly two indices at which both $$x$$ and $$z$$ have ones, and such that $$y$$ and $$z$$ coincede at index $$p$$. We define $$D_p(x,y)=z$$. And at last, let’s define a "probabilistic function" $$E_p:{0,1}rightarrow O”$$ to map the bit $$x$$ to a random element from $$O”$$ which at index $$p$$ has the bit equal to $$x$$. All "randoms" are taken with uniform probabilities.
If index $$k$$ belongs to an input bit (and not to a gate), then we write the equation:
$$B_k=E_p(b_k).$$
If index $$k_3$$ belongs to a gate (and not to an input bit) (we define $$k_1$$ and $$k_2$$ the same way as the previous time), then we define the equations:
$$(B’_{k_3,1},B”_{k_3,1}):=R_p(B_{k_1}),$$
$$(B’_{k_3,2},B”_{k_3,2}):=R_p(B_{k_2}),$$
$$B”’_{k_3,2}:=D_p(B”_{k_3,1},B”_{k_3,2}),$$
$$B_{k_3}:=G_{k_3}(B”_{k_3,1},B”’_{k_3,2}),$$
where $$G_{k_3}$$ operates bit-wise, on each index independently.
In each query of the ZKP, the prover will randomly choose $$p$$ and calculate all $$B$$‘s using the new equations. Then, it will commit to $$B_k$$ only, if $$k_3$$ belongs to an input bit, and commit to $$B_{k_1}oplus B’_{k_3,1},B’_{k_3,1},B’_{k_3,1}oplus B”_{k_3,1},B”_{k_3,1},B_{k_2}oplus B’_{k_3,2},B’_{k_3,2},B’_{k_3,2}oplus B”_{k_3,2},B”_{k_3,2},B”_{k_3,2}oplus B”’_{k_3,2},B”’_{k_3,2}$$ and $$B_{k_3}$$ ($$*$$).
Now the verifier will ask to reveal one of these data, with equal probabilities:
1. Every $$B_k$$ whenever $$k$$ is an index of an input bit that belongs to the description of the problem and not to the solution, and every $$text{xor}$$‘ed value from the line ($$*$$). If the $$text{or}$$ of all $$text{xor}$$‘ed values has a zero at index $$p$$ and if all the "input bytes" $$B_k$$ at index $$p$$ all coincide with the original description of the problem, the prover has passed.
2. Some $$text{xor}$$‘ed value from the line ($$*$$) and those two bytes that the former is the "$$text{xor}$$" of. If the $$text{xor}$$ of these $$3$$ bytes is $$0$$, the prover has passed.
3. $$B_{k_3},B”_{k_3,1}$$ and $$B”’_{k_3,2}$$ for some $$k_3$$ that is an index of a gate. If these $$3$$ bytes satisfy the relation $$G_{k_3}$$, the prover has passed.
This query has to repeat that many times as there are gates in the circuit in order to prove one bit of certainty. #### Is this a valid construction of ZKP for this class of problems?

Shopping cart
There are no products in the cart!
Continue shopping
0