During the match-settle process in Renegade’s system, we submit a bundle of proofs over a distributed witness. We have a need to “link” the witnesses in between proofs; that is, prove that specific witness values have the same underlying assignment between two proofs.
For example, in VALID COMMITMENTS, we prove the existence of a privately held order in a wallet. This order is then used as input to the MPC matching engine — and thereafter a collaborative proof of VALID MATCH SETTLE — meaning we need to convince the verifier that the same order is used throughout the match process.
To this end we devise a simple polynomial protocol that we refer to as a “proof linking protocol”, detailed below.
Suppose we want to link witness elements $w_1, \ldots, w_n$ between two Plonk proofs: $\pi_1$ and $\pi_2$. To do so, we add $n$ dummy constraints to the proof system by setting all selectors $q_L = q_R = \ldots = q_C = 0$ and setting $x_{a_i} = w_i$ (i.e. the first input wire). This is similar to the way in which vanilla Plonk “prepares” the circuit for public inputs.
These wire assignments are interpolated in Plonk into univariate polynomials over some subset of our finite field $\mathbb{F}p$. Suppose the left hand wire polynomial for $\pi_1$ is $a_1(x)$ and $a_2(x)$ for $\pi_2$. Our task is to prove that $a_1(x) = a_2(x)$ for $x \in [\omega_i]{i = 1..n}$. This is equivalent to verifying that $\forall x \in [\omega_i]_{i = 1..n}, a_1(x) - a_2(x) = 0$.
To check this identity, we can build off the already existing commitments to these wire polynomials that come from the standard Plonk protocol. Suppose that $c_1 = \text{KZG}.\text{Commit}(a_1), c_2 = \text{KZG}.\text{Commit}(a_2)$. We can get a commitment to $a_1 - a_2$ via the homomorphic properties of KZG as $c^\prime = c_1 - c_2$. We then wish to prove that this commitment opens to $0$ over all of $1, \ldots, n$.
To convince the verifier of this, the prover sends a commitment $c_f$ to:
$$ f(x) = \frac{a_1(x) - a_2(x)}{Z_n(x)} $$
Where $Z_n(x) = (x - \omega_1)(x - \omega_2)\cdots (x-\omega_n)$. This polynomial exists iff $a_1 - a_2$ vanishes on $\{\omega_1, \ldots, \omega_n\}$, so the opening of this commitment at a point is proof of existence.
The verifier chooses $\alpha \stackrel{\$}{\leftarrow} \mathbb{F}$, and requests openings from the prover of $c^\prime$ and $c_f$ at $\alpha$. Suppose that $c^\prime$ opens to $a^\prime$ at $\alpha$ and $c_f$ opens to $a_f$ at $\alpha$; let $z_\alpha = Z_n(\alpha)$ computed by the verifier, then the verifier may check:
$$ a^\prime \stackrel{?}{=} z_a * a_f $$
to verify that the proofs are properly linked.
Note that this is essentially a special case of the linearized polynomial protocols from the Plonk paper with $F_i = G(h_1(v_1(x)), h_2(v_2(x)))$ where:
$$ \begin{align*}
h_1(x) & = a_1(x) \\ h_2(x) & = a_2(x) \\ G(x, y) & = x - y \\ \end{align*} $$
and we prove over the range $S = \{1, \ldots, n\}$.