zk-FOAKs Algorithm

The Protocol of ZK-FOAKS is as follows:

Public Input: The evaluation point x, parsed as a tensor product r = r0 ⊗ r1;
Private Input: polynomial p with coefficient w
C: a [n,k,d]-linear code
EC: the encoding function
N = k×k

function Commit(p):
    Parse w as a k×k matrix. 
    The prover computes the tensor code encoding C1, C2.
    (Here C1 is a k×n matrix and C2 is a n×n matrix.)
    for i ∈ [n]:
        Compute the Merkle tree root Root_i = Merkle.Commit(C2[:, i]).
    Compute a Merkle tree root R = Merkle.Commit([Root_0, ..., Root_(n−1)]).
    return R

function Foaks.Prove(ϕ,x,R):
    The prover receives v0∈F^k from the verifier.
    c1 = Sum r0[i]C1[i] from i = 0 to k-1
    y1 = Sum r0[i]w[i] from i = 0 to k-1
    R(c1) = Merkel.Commit(c1)
    cv0 = Sum v0[i]C1[i] from i = 0 to k-1
    yv0 = Sum v0[i]w[i] from i = 0 to k-1
    R(v0) = Merkel.Commit(cv0)
    The prover sends R(c1), R(v0), and  y=<y1,r1> to the verifier.
    The verifier randomly samples t∈[n] indexs as an array J and sends it to the prover.
    The verifier randomly samples another index set I⊆[k] (|I|=t) and sends it to the prover.
    The prover calls ZK.P on C_CS, yield the proof π, and sends C2[I[j],idx] ∀idx∈J, c1[I[j]], cv0[I[j]], and π to the verifier.
    The prover sends the Merkle tree proofs of C2[I[j],idx] ∀idx∈J under Root_idx.
    The prover sends the Merkle tree proofs of Root_idx ∀idx∈J under R.
    The prover sends the Merkle tree proofs of c1[I[j]], cv0[I[j]] under R(c1) and R(cv0).

function Foaks.Verify(π, x, y=ϕ(x), R):
    The verifier calls ZK.V on C_CS.
    The verifier checks the Merkel tree proofs of C2[I[j],idx] ∀idx∈J.
    The verifier checks the Merkel tree proofs of Root_idx ∀idx∈J using R.
    The verifier checks the Merkel tree proofs of c1[I[j]], cv0[I[j]] using R(c1) and R(cv0).
    Return (all checks pass) ? ACCEPT : REJECT

Note: Here, ZK=(ZK.P, ZK.V) can be any zero-knowledge argument protocol. C_CS is the Code Switching Statement as follows:

Witness: yv0, y1, C1[:, idx] ∀idx∈J in the above protocol
Public input: v0, r0, r1, y
Public information: J and I are chosen by the verifier

Encode cv0 := EC(yv0), c1 := EC(y1)

for idx∈J:
    Encode C2[:, idx] := EC(C1[:, idx])

for idx∈J:
    Proximity check: check if cv0[idx] == <v0, C1[:, idx]>
    Consistency check: check if c1[idx] == <r0, C1[:, idx]>

Tensor product check: check if <r1, y1> == y

Encoder check:
for 0 ≤ j < |I|:
    Output c1[I[j]], cv0[I[j]].
    for idx∈J:
        Output C2[I[j], idx]