ZKPs for FMD flag consistency

Cryptography Zoo Shielded State Sync
2

Another problem is to enforce correctness of the flags generation. See also this post for more context. We define this problem as follows.

Problem 3: Correctness of FMD flags: Given a commitment \mathsf{cm} of pk_\mathsf{fmd}, and flag ciphertexts \vec{f}, we want to enforce that \vec{f} has been generated with the committed pk_\mathsf{fmd}.

For concreteness we will focus on the FMD2 construction of the FMD paper. We assume it is instantiated over an elliptic curve \mathbb{G} = E(\mathbb{F}_p) and that G is a point of order q. The flag generation is as follows.

\underline{\mathsf{FMD2.flag}:}
Input:

  • Public key pk:=(H_1,\ldots,H_\gamma)\in\mathbb{G}^\gamma
  • Randomness r,z\in \mathbb{Z}_q
  1. U:=r\cdot G, W:=z\cdot G
  2. For 1\leq i\leq \gamma do:
    a. D_i:=r_i\cdot H_i
    b. k_i := \mathsf{H}(U,D_i,W) // Hash to \mathbb{Z}_2
    c. c_i:=k_i+1 // Arithmetic in \mathbb{Z}_2
  3. m:=\mathsf{G}(U,c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
  4. y:=(z-m)r^{-1} // Arithmetic in field \mathbb{Z}_q
  5. Output flag ciphertexts \vec{f}:=(U,y,c_1,\ldots,c_\gamma)

Note we pass the randomness r,z\gets\mathbb{Z}_q as input, which allows to use r,z in the arithmetic circuit below. The relation for which we want to generate proofs is

\mathcal{R}_{fmd} := \left\{(\mathsf{cm},\vec{f})\ ;\ (pk,r,z,s)\ \big\lvert\ \begin{aligned} & \mathsf{cm} = \mathsf{commit}(pk;s) \\ & \vec{f} = \mathsf{FMD2.flag}(pk,r,z) \end{aligned} \right\}

The instance is (\mathsf{cm},\vec{f}), and the witness is (pk,r,z,s).

The arithmetic circuit

The most expensive operations are the three scalar multiplications in the calculations of U,W,D_i. For this reason, we define the arithmetic circuit below over the base field \mathbb{F}_p of \mathbb{G}.

Getting rid of the hash \mathsf{G} in the circuit. The inputs of the hash \mathsf{G} are derived from the flag ciphertext, which is part of the instance of \mathcal{R}_{fmd}. This means we do not need to enforce in zero-knowledge that m = \mathsf{G}(U,c_1,\ldots,c_\gamma). Instead, the circuit enforces correctness of a modified algorithm \mathsf{FMD2.flag}' that takes m as an additional input, and skips step 3. Thus, we will generate proofs for the relation

\mathcal{R}'_{fmd} := \left\{(\mathsf{cm},\vec{f},m)\ ;\ (pk,r,z,s)\ \big\lvert\ \begin{aligned} & \mathsf{cm} = \mathsf{commit}(pk;s) \\ & \vec{f} = \mathsf{FMD2.flag}'(pk,r,z,m) \end{aligned} \right\}

It clearly holds

\begin{aligned} &(\mathsf{cm},\vec{f},m);(pk,r,z,s))\in\mathcal{R}'_{fmd} \land m = \mathsf{G}(U,c_1,\ldots,c_\gamma)\\ &\Rightarrow(\mathsf{cm},\vec{f});(pk,r,z,s))\in\mathcal{R}_{fmd}\\ \end{aligned}

So what the verifier does is, first derive m from the flag \vec{f}, and then verify a ZKP for \mathcal{R}'_{fmd}.

The hash \mathsf{H} in the circuit. We use Poseidon hash over \mathbb{F}_p to hash (the coordinates of) points U,D,W onto a single field element and then take its LSB bit:

\underline{\mathsf{H}(U,D,W):}

  1. h = \mathsf{Poseidon}(x_U,y_U,x_D,y_D,x_W,y_W)
  2. Output LSB bit of field element h

Committing to the public key. In a similar way to commit to the public key pk:=(H_1,\ldots,H_\gamma), which are points in \mathbb{G} we hash with Poseidon all their coordinates, along with a hiding field element s. The commitment \mathsf{cm} is a single field element.

The circuit for \mathsf{FMD2.flag}'. It has parameter \gamma hard-coded. It is defined as follows.

\underline{\mathsf{CircuitFMD2Flag'}:}
Public input:

  • Commitment \mathsf{cm}
  • Flag ciphertext \vec{f}:=(U,y,c_1,\ldots,c_\gamma)
  • m // Purportedly, the result of the hash \mathsf{G}

Private input:

  • Public key pk:=(H_1,\ldots,H_\gamma)
  • Randomness r,z\in \mathbb{Z}_q
  • Blinding factor s
  1. Check \mathsf{cm}=\mathsf{Poseidon}(H_1,\ldots,H_\gamma,s)
  2. Check U = r\cdot G and W = z\cdot G
  3. For 1\leq i \leq\gamma:
    a. Check D_i = r \cdot H_i
    b. Check bit c_i and bit \mathsf{H}(U,D_i,W) are different
  4. Check yr = z-m\mod q // Emulate arithmetic modulo q in \mathbb{F}_p.