# A Note on BitVM3 RSA Garbling

The garbling scheme proposed in [BitVM3](https://bitvm.org/bitvm3.pdf) is likely broken in general for circuits with gates of fanout greater than $1$. This renders the scheme impractical for SNARK verification on bitcoin. Before continuing work on the BitVM3 garbling scheme, we believe these issues should be addressed. We understand that several other teams have discovered attacks on the BitVM3 garbling scheme as well.

The general technique of using conditional disclosure of secrets primitives, such as Yao garbling, [Delbrag](https://rubin.io/public/pdfs/delbrag.pdf), ABE, etc., remains in principle sound. Several teams, including us at Alpen Labs, are working on alternative schemes to move verification off chain using garbled circuits.

**Note** Robin has proposed an alternative version of the BitVM3 scheme privately to me, which seems to avoid this attack at the cost of rerandomizability.

## Overview
A Garbling scheme consists of two parties, the Garbler and the Evaluator. The Garbler takes as input some kind of circuit $\mathcal{C}$ which consists of wires and gates. Each wire can take on some finite set of values, and each gate maps input values to output values. In the case of many schemes, such as that in BitVM3, the wires take on binary values and each gate is either an XOR or an AND gate. Such a circuit is called binary.

The Garbler garbles this circuit by mapping each wire value to some secret label and by publishing some data that allows evaluating the gates on these secret wire values. We call this data the garbling of the gate. For example, in Yao's original scheme, this is an encrypted truth table. The Garbler also publishes exactly one label for each input wire to the circuit.

The Evaluator will use the garbled gates and the input wire labels to evaluate the circuit. Since they only know one input label for each input wire, they can only evaluate the circuit on a single input and learn one label for each wire. It must be the case that the evaluator cannot learn any other secret wire labels in order for the scheme to be secure.

## The BitVM3 Scheme
Input labels are encoded as elements of the multiplicative subgroup of the ring $\Bbb{Z}_N$, the integers modulo an RSA-hard semiprime $N$. Gates are computed by taking public affine combinations gate labels in $\Bbb{Z}_N^\times$. In general, given wire values $u,v \in \{0,1\}$, input lables $x, y \in \Bbb{Z}_N^\times$ the output label $z$ of gate $g$ is computed via
$$ z = x^{a^{(g)}_{u}} y^{b^{(g)}_{v}} C^{(g)}_{g(u,v)}. $$

Where $a^{(g)}_{b}, b^{(g)}_{b} \in \Bbb{Z}$ and $C^{(g)}_{b} \in \Bbb{Z}_N^\times$ are gate-dependent constants. These are chosen in such a way that evaluating the garbled gate preserves the semantics of the logical gate. The constants $C^{(g)}_{b}$ are called ``adaptor" elements and are necessary to garble circuits with fanout great than $1.$ The scheme also includes a mechanism for reblinding input labels to allow bounded circuit reuse, although this is not relevant for the attack.

The security of the scheme requires keeping the output labels $\ell^{(o)}_{b}$ secret, and it is claimed that this reduces to keeping the ``plain" input labels $\ell^{(i)}_b$ for $i \in [n]$ and $b \in \{0, 1\}$ secret. We show this is not the case in general, and in particular for circuits with fanout greater than $1$. There exists a PPT adversary that can derive $\ell^{(o)}_b$ from the public information $\big(a^{(g)}, b^{(g)}, C^{(g)}\big)_{g \in \text{gates}(\mathcal{C})}.$

## The Attack
Fix a circuit $\mathcal{C}$ with fanout greater than $1$. That is, with some non-trivial adaptor elements. For a fixed binary input $\textbf{x} \in \{0,1\}^n$ there exists a constant $C(\textbf{x}) \in \Bbb{Z}_N$ that is purely a function of the adaptors, and a vector of exponents $e(\textbf{x}) \in \Bbb{Z}^{2n}$ with $(1 - x_i) e(\textbf{x})_{2 i + b} = 0$, i.e. non-zero with parity equal to $x_i$. The output labels of the circuit are
$$ \ell^{(o)}_{\mathcal{C}(\textbf{x})} = C(\textbf{x}) \prod_{i=0}^{n} \big(\ell^{(i)}_{x_i} \big)^{e(\textbf{x})_{2 i + x_i}}. $$

In particular, the output labels are an affine combination of the $2n$ possible input labels. This linear combination is public and depends only on the circuit input, not the label values themselves. Call this linear combination
$$ \textbf{v}(\textbf{x}) = \big(-1 \| \textbf{e}(\textbf{x})\big). $$

If we can find a set of inputs $I \subseteq \{0,1\}^n$ such that $\mathcal{C}(\textbf{x}) = 0$ for $\textbf{x} \in I$, $|I| > 2n+1$ and $\text{rank}(\textbf{v}(\textbf{x}) : \textbf{x} \in I) > \text{rank}(\textbf{e}(\textbf{x}) : \textbf{x} \in I)$, we can find an integer linear combination $\textbf{y}$ of these vectors such that $$ \sum_{\textbf{x}_i \in I} y_i \textbf{v}(\textbf{x}_i) = -1 \| \textbf{0}. $$

Such a linear combination guarantees that
$$ \ell^{(o)}_0 = \prod_{x_i \in I} C(\textbf{x}_i)^{y_i}. $$

In short, we can cancel all the dependence on the input labels and write the output labels entirely in terms of the adaptors. Symmetrically, we can find the output label $\ell^{(o)}_1$ by using some $I$ where $\mathcal{C}(I) = 1.$

Interestingly, it may be the case that finding inputs that map to either zero or one is computationally infeasible. However, at least one must be easy, and in the case of SNARK verification finding an input that fails to verify is by definition always easy. Since this is the case we care about for SNARK verification on bitcoin, this attack is practical.

### Argument for Why it Works
Suppose the attack failed to work for some circuit, even though there was a non-trivial adaptor element. By non-trivial, we mean one such that there is not a transformation of the circuit that eliminates the adaptor element that is generic over input labels. That is, we cannot find an element $\textbf{y}$ such that
$$ \sum_{\textbf{x}_i \in I} y_i \textbf{v}(\textbf{x}_i) = 1 \| \textbf{0}. $$

Where $I$ is the set of all inputs that evaluate to $0.$ This means that the all ones vector is in the span of the rows of the matrix $\big( \textbf{e}(\textbf{x})\big)_{\textbf{x} \in I}$ and equivalently that for all $\textbf{y}'$ such that $\sum_i y'_i \textbf{e}(\textbf{x}_i) = \textbf{0}$ that $$\sum_i C(\textbf{x}_i)^{y'_i} = 1.$$

Since this holds for all $\textbf{y}'$ it must follow that there exists some sequence of $2n$ constants $C'_j$ such that for all inputs $\textbf{x}_i$ where $\mathcal{C}(\textbf{x}_i) = 0$
$$ C(\textbf{x}_i) = \prod_{j = 0}^{2n-1} {C'_j}^{e(\textbf{x}_i)_j} $$

Such constants can be computed by finding the [pseudo-inverse](https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse) of the matrix formed by the $\textbf{e}(\textbf{x}_i)$ vectors and exponentiating the vector $\big(C(\textbf{x}_i)\big)_i.$ In that case, it is possible to eliminate the adaptor elements and redefine the inputs to the circuit, not necessarily uniquely, as $${\ell'}^{(i)}_b = {C'_{2 i + b}} \ell^{(i)}_b.$$

However, we cannot compute the pseudo-inverse with respect to this matrix as it depends on all inputs that evaluate to zero. If we can sample a set of inputs that both evaluate to zero and have maximal rank exponent vectors, we can apply this method to those inputs. Heuristically, we expect that sampling sufficiently many random inputs will have maximal rank exponent vectors, though it remains to actually show this.

It is also possible that the output exponent does not vanish, but the adaptor elements do vanish. In that case, the attack works and the output label must be $1.$

## Future Work
We still need to show that it is possible to sample inputs with exponent vector rank equal to that of the space of all possible inputs. The linear structure of the evaluator may yield other attacks, for example by solving for linear relations among the inputs. This attack also likely generalizes to other, similar schemes where the evaluation process is entirely group linear. For example, an unpublished generalization of Linus' scheme to pairing groups with unbounded reblinding can be broken in the same way.