# [DRAFT]BitVM2-GC: Verifiable Arithmetic Garbling

[NOTE] This is a draft for public review.

## 0. Introduction to BitVM3 and GOAT BitVM2

**BitVM** [1] enables Turing-complete smart contracts on Bitcoin by offloading computations off-chain and verifying results on-chain via Taproot scripts, similar to Optimistic Rollups in Ethereum [2,3]. The initial version required fixed two-party setups (prover-verifier) with inefficient multi-round challenges and high setup costs. BitVM2 [4] later introduced permissionless verification, allowing any user to challenge invalid claims in just two rounds. While it prevented fund theft (malicious actors can only burn deposits), its on-chain transaction costs remained prohibitively high for bridge scalability.

BitVM3 [6](also termed Delbrag in [5]) dramatically reduces costs using **garbled circuits** (GC) [7]. During setup, a *garbler* commits to a circuit in a Taproot tree and shares it with an evaluator. If the garbler submits an invalid SNARK proof, the evaluator generates a fraud proof using this pre-shared circuit. This retains BitVM2’s trust model but minimizes on-chain footprints by embedding gate computations as Taproot leaves. Implementation balances off-chain bandwidth and computational overhead to ensure circuit correctness, and BitVM3 leverages Bitcoin-compatible hashing (BitHash) for script-based validation.

The BitVM2-GC Protocol aims to integrate GOAT BitVM2 [9]—A BitVM2 variant in combination with Decentralized Sequencer to build Bitcoin-native zkRollup—with efficient arithmetic garbled circuits to reduce off-chain communication overhead. It combines this with ZK-friendly components: the Poseidon2 [10] hash algorithm and Ziren [11] (formally zkMIPS). This architecture merges Bitcoin’s robust security with minimal on-chain footprint while efficiently proving GC correctness.

## 1. Arithmetic Garbled Circuits

[9] introduces a novel GC approach for arithmetic circuits over arbitrary moduli $\mathbb{Z}_m$, using circular correlation robust hashes (CCRH) and Free XOR techniques.

### 1.1 Arithmetic Labels and Free Operations

Labels encode integers modulo $2^k$ (e.g., for short integers), enabling free addition/subtraction and modular reduction. Each label is a vector in $\mathbb{Z}_{2^k}^{\lambda}$:

$$
K_x = \left[K_{x}^0 + x \cdot \Delta\right]_{2^k},
$$

*with $K_{x}^0, \Delta \in \mathbb{Z}_{2^k}^{\lambda}$*.

The construction supports affine operations $f(\cdot)$, including addition/subtraction and multiplication by constants:

$$
f\left(\left[K_{x}^0 + x \cdot \Delta\right]_{2^k}\right) = \left[f(K_{x}^0) + f(x) \cdot \Delta\right]_{2^k}.
$$

### 1.2 Switch Systems

A computational model formalizing GCs as bidirectional constraint systems. Gates include:
- Switches ( $x \vdash \text{ctrl}$)
- Joins ( $x \bowtie y$)
- Affine maps $f(\cdot)$
- Modulus operations, ‘downcasts’ large words to small words
- Divisions, only when divisible
, with only join width dictating material cost.

### 1.3 One-Hot Garbling for Gneneral Multiplication

**One-hot encoding** represents values as sparse vectors, e.g., $H(x)$ for $x \in \mathbb{Z}_{2^k}$, enabling linear-cost scaling and conversion. The construction uses a switch system that converts a binary encoding $\text{bin}(x)$ into a binary one-hot encoding $H(x)$. This is implemented recursively: given a one-hot encoding of the first $i$ bits of $x$ as $\mathbf{h}$, we extend it to the first $i+1$ bits with $k \bowtie x[k-i-1]$ using the scale formula：

$$
\text{scale}_k(\mathbf{h})\triangleq
\biggl( s,\ \mathbf{y} = \begin{bmatrix}
y[0] \\ \vdots \\ y[2^k-1]
\end{bmatrix} \biggr)
\quad \text{with} \quad y[i] =
\begin{cases}
\vdash h(i) & \text{if } h[i] = 0 \\
s - \sum_{j \neq i} y(i) & \text{otherwise}
\end{cases}
$$

, and returns $(\mathbf{h} + \mathbf{y}) || \mathbf{y}$.

**Half Multiplication** multiplies one-hot-encoded values $x$ with a word label $y$ at $O(k \cdot \lambda)$ bits materials, enabling efficient inner products. It first uses the scale formula to reset the one hot value as $y$ with a join gate, then uses multiplication with fiexed values and addition to solve the production as follows:

$$
\text{half-mul}(\mathbf{h} = H(x), y) \triangleq
\Big( (k, \mathbf{h'}) \leftarrow \text{scale}_k(\mathbf{h}) \Big) ;
\Big( s \bowtie y \Big) ;
\operatorname{return} \sum_{i} i \cdot h'[i]
$$

**Word-to-Hot Conversion** efficiently transforms word labels to one-hot encodings using iterative refinement, joining only $2k-1$ bits (i.e., with $(2k-1) \cdot \lambda$ bits material). The conversion of words to arithmetic one-hot vectors is complex due to modulus mismatch between bits and words. While extracting the least significant bit (LSB) of a word $x (\text{mod } 2^k)$ is straightforward using a mod gate, higher bits require subtracting the LSB first. However, the LSB’s modulus ($2$) mismatches the word’s modulus ($2^k$), preventing direct subtraction.

The naive solution individually *upcasts each bit* from  $\mathbb{Z}_2$ *to $\mathbb{Z}_{2^k}$* using a switch gate:

$$
\big([0]_{2^k} \vdash [x]_2\big) \bowtie \big([1]_{2^k} \vdash \neg[x]_2\big)
$$

This converts $[x]_2$ to $[x]_{2^k}$ but requires $O(k)$ bits per bit and $O(k^2)$ total cost, making it prohibitively expensive for practical use. The optimized solution leverages *bidirectional gate constraints* to simultaneously solve for both the binary encoding $\mathbf{bin}(x)$ and one-hot vector $\mathbf{h}(x)$:

- Extract LSB: Obtain $[x]_2 \in \mathbb{Z}_2$ using a modulus gate $[x]_2 \leftarrow x \mod 2$
- Batch Upcast LSB: Convert $[x]_2$ *to $\mathbb{Z}_{2^k}$* word $[[x]_2]_{2^k}$ *without per-bit overhead* using parallel switching
- Subtract and Shift: Compute $x' \leftarrow \dfrac{x - [[x]_2]_{2^k}}{2}$ (guarantees lsb is 0 for recursion)
- Recurse: Solve $\mathbf{bin}(x')$ and $\mathbf{h}_{x'}$ for higher bits by propagating constraints bidirectionally

### 1.4 Long Integer Handling via CRT

Chinese Remainder Theorem (CRT) splits a long integer $x \in \mathbb{Z}_m$ into residues $[x \bmod m_1, \dots, x \bmod m_k]$ where $\{m_i\}$ are pairwise coprime moduli. This enables parallel arithmetic on residues. Suppose the first $k$ primes $p_0 = 2, p_1 = 3, ..., p_{k−1},$ and let $N = \prod_i{p_i}$. Then

$$
[x]_N = \left[ \sum_{i=0}^{k-1} s_i \cdot \left[ x_i \cdot s_i^{-1} \right]_{p_i} \right]_N, \quad \text{where} \quad s_i = \frac{N}{p_i}.
$$

The above equation is linear in the sense that $p_i, s_i, s^{-1}$ are public constants.

## 2. BitVM2-GC Protocol

### 2.1 High-Level Design

GOAT BitVM-GC extends GOAT BitVM2's foundational “assert-disprove” framework through three coordinated phases:

- **Setup**:
1. The Operator (Garbler) constructs a garbled circuit for SNARK verification.
2. Commits input/output labels to Bitcoin.
3. Publishes the circuit off-chain and proves its correctness via a zero-knowledge proof.
- **Assertion**: The Operator publishes a SNARK proof along with corresponding input labels on chain, claiming validity of off-chain state transitions.
- **Disprove:** If the SNARK proof or circuit is invalid, the Challenger (Evaluator):
-- Evaluates the garbled circuit using published input labels.
-- Derives the “0” output label.
-- Submits “0” output label on-chain as a fraud proof to falsify the assertion.

### 2.2 Arithmetic Garbled Circuit Construction and Evaluation

GOAT BitVM-GC employs the Poseidon2 hash algorithm $H(\cdot)$ as the cryptographic primitive for GC construction, leveraging the efficient arithmetic gabling schme in [10]. The Garbler generates the GC by adhering to the following rules:

- **Global Setup**:

-- Global offset $\Delta \in \mathbb{Z}_{2^k}^{\lambda}$, for $k = 512$ large enough for multiplication output of two 254-bit values and security parameter $\lambda = 128$.

-- Choose first 110 primes form $2$ to $601$ as the CRT residues for $2^{512}$.

-- Poseidon2 Hash with KoalarBear prime field $\mathbb{F}_p$ for $p = 2^{31} - 2^{24} + 1$.

- **Input Labels and Output Labels**:

Inputs and outputs are expressed as bits in $\mathbb{Z}_2$.

- **Garbling**:

Intermediate values (usually with bit length 254) are expressed as values in $\mathbb{Z}_{2^{512}}$, encoded as a vector of length $128$.

The labels of addition/subtraction/multiplication by constants are directed calculated. For multiplication (integer multiplication, we can’t directly deal with large mod multiplication with labels), calculate under each CRT residue, using arithmetic-to-bin/one-hot conversion for first multiplication factor and then use half multiplication in Section 1.3. The output is transform form CRT residues to $\mathbb{Z}_{2^{512}}$.

[](https://)Record all join materials during arithmetic-to-bin/one-hot conversion and half multiplication as garbling materials.

**The Evaluator** directly calculates addition/subtraction/multiplication by constants, follows the rules of arithmetic-to-bin/one-hot conversion and half multiplication with garbling materials to calculate multiplication.

## 3. Complexity Analysis

**On-chain complexity** remains the same:

- Assertion Transaction ( $\approx 38 \text{ kB}$) to reveal the committed input labels. Use Winternitz signatures (32 bytes/bit) to commit input labels, combining SNARK proof (128 bytes) and the public input (20 bytes) .
- Disproval Transaction ( $\approx 16 \text{ B}$ ). Falsifies the SNARK proof by revealing the circuit's ‘0' output label, proving verification failure.

**Off-chain complexity**:

- Communication Complexity ( $\approx 1.6 \text{ GB}$). The total bit width of 110 CRT residues is about 560. For each 254-bit multiplication, the total garbling materials are $3 \cdot 128 \cdot 560/8 = 53.76$ KB. For Groth16.verifer , totally 30,000 multiplications (one integer multiplication for each mod multiplication in Montgomery form) result 1.6 GB, which is reduced by 30x compared to traditional GC construction.
- Computational Complexity ( $\approx 2.2$ Billion Hashes). The sum of 110 CRT residues is 24,113. The number of hashes used for each multiplication is about $3 \cdot 24,113 \approx 72,339$ . So the total hash number is about 2.2 billion, which is of the same order as traditional GC.

## Reference

1. R. Linus, “BitVM: Compute Anything on Bitcoin,” https://bitvm.org/bitvm.pdf, 2023.
2. J. Poon and V. Buterin, “Plasma: Scalable Autonomous Smart Contracts,” https://plasma.io/plasma-deprecated.
pdf, 2017.
3. V. Buterin, “Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform,” https:
[//github.com/ethereum/wiki/wiki/White-Paper](https://github.com/ethereum/wiki/wiki/White-Paper), 2014.
4. R. Linus et al., “BitVM 2: Permissionless Verification on Bitcoin,” https://bitvm.org/bitvm bridge.pdf, 2024,
[Online; accessed 2025].
5. J. Rubin, “Delbrag,” https://rubin.io/public/pdfs/delbrag.pdf, 2025, [Online; accessed 2025].
6. R. Linus, “BitVM 3s – Garbled Circuits for Efficient Computation on Bitcoin,” 2025.
7. A. C. Yao, “Protocols for Secure Computations,” https://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf, 1982.
8. V. Kolesnikov et al., “DUPLO: Unifying Cut-and-Choose for Garbled Circuits,” https://eprint.iacr.org/2017/
344.pdf, 2017.
9. G. N. R. Group, “GOAT BitVM2 Whitepaper,” https://www.goat.network/bitvm2-whitepaper, 2025.
10. D. Heath, “Efficient Arithmetic in Garbled Circuits,” https://eprint.iacr.org/2024/139.pdf, 2024.
11. L. Grassi et al., “Poseidon2: A Faster Version of the Poseidon Hash Function,” https://eprint.iacr.org/2023/323.pdf, 2023.
12. L. Fraga et al., “zkMIPS: a high-level specification,” https://www.zkm.io/whitepaper/zkm-new, 2024.
13. V. Kolesnikov and T. Schneider, “Improved Garbled Circuit: Free XOR Gates and Applications,” [https://www](https://www/).[cs.toronto.edu/∼vlad/papers/XOR](http://cs.toronto.edu/%E2%88%BCvlad/papers/XOR) ICALP08.pdf, 2008.
14. S. Zahur et al., “Two Halves Make a Whole Reducing Data Transfer in Garbled Circuits using Half Gates,”
https://eprint.iacr.org/2014/756.pdf, 2015.
15. B. Alliance, “Garbled SNARK Verifier Implementation,” https://github.com/BitVM/garbled-snark-verifier,