Copy Constraints

Recall that gate constraints do not enforce the equalities of wire values making inconsistencies across the circuit. We generalize copy constraints to the following problem.

Let \(k \in \{1, \dots, 3n\}\) and \(\{i_1, \dots, i_k\} \subseteq \mathcal{I}\) satisfying \(i_1 < i_2 < \dots < i_k\). We would like to show that $$ x_{i_1} = x_{i_2} = \dots = x_{i_k}. $$

The technique for proving this problem is tricky. We form the pairs of index-value and make them into a sequence $$ \big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big). $$ It can be observed that if \(x_{i_1} = x_{i_2} = \dots = x_{i_k}\), then, if we rotate the indices among the pairs, we achieve a sequence
$$ \big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big) $$ that is permutation of the previous sequence. Notice that we just rotated the indices \(1\) step to the left and this is the recommended rotation. This fact helps imply the other direction of the fact. For more details, we use the following observation

Observation. \(\big((i_1, x_{i_1}), (i_2, x_{i_2}), \dots, (i_k, x_{i_k})\big)\) is a permutation of \(\big((i_k, x_{i_1}), (i_1, x_{i_2}), \dots, (i_{k - 1}, x_{i_k})\big)\) if and only if \(x_{i_1} = x_{i_2} = \dots = x_{i_k}\).

Proof. The proof is as follows:

"\(\Leftarrow\)": This direction is straightforward.

"\(\Rightarrow\)": Since the two sequences are permutation of each other, for \(j \in \{1, \dots, k\}\) we consider \((i_j, x_{i_j})\) from the first sequence. It can be seen that \((i_j, x_{i_{(j \mod k) + 1}})\) from the second sequence is the only one that is equal \(j \in \{1, \dots, k\}\) since they share the unique prefix \(i_j\). Hence, \(x_{i_j} = x_{i_{(j \mod k) + 1}}\). Following this argument, we see that \(x_{i_1} = x_{i_2}, x_{i_2} = x_{i_3}, \dots, x_{i_{k - 1}} = x_{i_k}, x_{i_k} = x_{i_1}\). Thus, \(x_{i_1} = x_{i_2} = \dots = x_{i_k}\).

General paradigm for proving copy constraints of the entire circuit

Recall that \(x : \mathcal{I} \to \mathbb{F}\). We can deterministically determine a partition of \(\mathcal{I}\) such that $$ \mathcal{I} = \bigcup_{j = 1}^{\ell_{\mathsf{in}} + n} \mathcal{I}_j $$

where \(\ell_{\mathsf{in}} + n\) is the number of wires of the original circuits, namely, \(\ell_{\mathsf{in}}\) input wires and \(n\) output wires of all gates. Hence each subset \(\mathcal{I}_j\) is the set of wire labels whose value are all equal to the same wire value of the original circuit. We hence obtain a rotation of indices for each subset \(\mathcal{I}_j\). By unifying all those rotations, we achieve a permutation \(\sigma : \mathcal{I}\to\mathcal{I}\) such that

$$ \big((a_1, x_{a_1}), \dots, (a_n, x_{a_n}), (b_1, x_{b_1}), \dots, (b_n, x_{b_n}), (c_1, x_{c_1}), \dots, (c_n, x_{c_n})\big) $$

is a permutation of

$$ \big((\sigma(a_1), x_{a_1}), \dots, (\sigma(a_n), x_{a_n}), (\sigma(b_1), x_{b_1}), \dots, (\sigma(b_n), x_{b_n}), (\sigma(c_1), x_{c_1}), \dots, (\sigma(c_n), x_{c_n})\big). $$ Such guaranteed permutation relation implies the consistencies among wires of the circuit.

Recall the example in Breaking Circuit with the following copy constraints. $$ \begin{cases} u = x_{a_1} = x_{a_2} = x_{b_1},\\ v = x_{b_2} = x_{b_5},\\ z_1 = x_{a_4} = x_{c_1},\\ z_2 = x_{a_3} = x_{c_2},\\ z_3 = x_{b_4} = x_{c_3},\\ z_4 = x_{a_5} = x_{c_4},\\ z_5 = x_{a_6} = x_{c_5},\\ z_6 = x_{c_6}.\
\end{cases} $$ We achieve the partition $$ \big\{\{a_1, a_2, b_1\}, \{b_2, b_5\}, \{a_4, c_1\}, \{a_3, c_2\}, \{b_4, c_3\}, \{a_5, c_4\}, \{a_6, c_5\}, \{c_6\}\big\}. $$ We hence can achive the permutation \(\sigma: \mathcal{I}\to\mathcal{I}\) as follows: $$ \begin{array}[ccc]\\ \sigma(a_1) = b_1, &\sigma(a_2) = a_1, &\sigma(b_1) = a_2,\\ \sigma(b_2) = b_5, &\sigma(b_5) = b_2,\\ \sigma(a_4) = c_1, &\sigma(c_1) = a_4,\\ \sigma(a_3) = c_2, &\sigma(c_2) = a_3,\\ \sigma(b_4) = c_3, &\sigma(c_3) = b_4,\\ \sigma(a_5) = c_4, &\sigma(c_4) = a_5,\\ \sigma(a_6) = c_5, &\sigma(c_5) = a_6,\\ \sigma(c_6) = c_6. \end{array} $$