Thanks to [Robin](https://x.com/robin_linus) and [Jeremy](https://x.com/JeremyRubin), we now have BitVM3 - an enhanced theoretical version of BitVM2.

This article will not cover the conceptual or protocol details of the BitVM2 Bridge. Readers interested in foundational knowledge can refer to:
1. [BitVM2 Write-up](https://bitvm.org/bitvm2.html)
2. [BitVM2 Paper](https://bitvm.org/bitvm_bridge.pdf)
3. [Fiamma’s BBBB Blog](https://medium.com/@Fiamma.io): introducing the technical details in BitVM2
# What is the bottleneck of BitVM2 Bridge?
As shown in Figure 1, when the Operator is challenged, they must submit critical data to Bitcoin via an Assert transaction (highlighted in green). In order to help user could have a better understand on it, we break it down with 3 questions:
1. What data is published?
2. How large is this data?
3. Impact on practical adoption.


1. What data is published?

The data included by the Operator in the Assert transaction represents commitments to all input and output data of script chunks. In the BitVM2 Bridge framework, this computation specifically refers to the Groth16 verification process. To enable this verification computation to be executed on Bitcoin, the process is intentionally divided into smaller computational units (chunks). Each chunk's corresponding script, including fixed transaction overhead and signature verification scripts, must not exceed Bitcoin's standard transaction size limit of 400 KB (weight unit).

Since the complete computation is fragmented into multiple chunks, the Operator must provide commitments for both the input and output data of each chunk. An honest Challenger can then identify any disputed chunks and initiate a Disprove transaction to penalize (slash) any malicious Operator.
2. How large is it?

Before disclosing the data size, let's first understand some fundamental logic. The purpose of the Assert transaction is to store the Operator's commitment data. However, the script in the Assert transaction isn't simply about storing data - it must also verify at the script level that this data genuinely represents the Operator's commitment.

The commitment mechanism uses Winternitz signatures, meaning the script must include signature verification for these commitments.

Now, how large does this signature verification script need to be? What factors influence its size? Based on implementation data from the Fiamma team, we've obtained the following actual measurements:

<div style="text-align:center">

| Type | Number |
| -------- | -------- |
| Script Chunk | 16095 |
| commitment | 152,039 |
| commitment/Assert tx | 90 |
| Assert tx size | 98,860 bytes |
| Assert tx | 1690 |

</div>

3. Impact on Practical Adoption for BitVM2 Bridge
Let's begin by defining several key metrics:
- K: The cost borne by the Operator when challenged
- M: The cost for a Challenger to initiate a challenge
- S: The Operator's staked amount
We then examine two scenarios:

| | Is the operator malicious? | Is the challenger malicious? | Relation |
| -------- | -------- | -------- | -------- |
| Case 0 | Yes | No | S>M |
| Case 1 | No | Yes | M>K |

Case 0: Incentivizing Honest Challengers
- Requirement: S > M
- Purpose: Ensures sufficient economic incentive for honest challengers to penalize malicious Operators

Case 1: Preventing Griefing Attacks
- Requirement: K < M
- Purpose: Deters malicious challengers from targeting honest Operators
The critical parameter is K (Operator's on-chain cost), which determines the minimum thresholds for both M (challenge cost) and S (stake amount). Using current implementation parameters with Bitcoin fee rate at 2 satoshis/vByte:

K = 1,690 transactions × 98,860 vBytes × 2 sat/vB ~= 3.34 BTC

This establishes minimum requirements:
- Operator stake (S) ≥ 3.34 BTC
- Challenge cost (M) ≥ 3.34 BTC

The "1-of-N" security model becomes vulnerable as high challenge costs reduce the number of potential challengers (N) and then affect overall system security.
It should be noted that the challenge cost (M) is crowdfunding, which introduces additional weaknesses:
- Challengers bear full costs without guaranteed rewards
- Creates disincentives for participation
- Further compromises bridge security
# What's the Garbled Circuit
## Garbled circuit definition
Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit[1].
## Key process of the Garbled circuit
1. Construct the Boolean circuit for any computation
First, the computation must be pre-represented as a logical circuit composed of AND and XOR gates, as illustrated in the following diagram. Note: This circuit generation is a one-time process that depends on the computation itself, but remains independent of the specific computation inputs.

If implementing Groth16 verification computation using this type of logic gate, preliminary estimates suggest it would require billions (B) of gates. However, AlpenLabs' research on DV-SNARK may offer a more efficient solution - their approach aims to represent the entire verification process with just millions (M) of gates, which would constitute a significant improvement.

2.Truth Table and Garbled Table

We generate truth tables for both AND gates and XOR gates respectively. Since each gate has two inputs and one output, and each input is a boolean value, we can enumerate all possible values to obtain the truth tables for different gates.

According to the definition of Garbled circuits, two distrusting parties can complete computations without exposing private data. For easier understanding, we define the operator in the bridge as the garbler, and the challenger as the evaluator. The garbler does not want its values to be exposed, so the truth tables need to be hidden.

The specific method is as follows:
1. Given that each gate has 2 input values and 1 output value. Each value has 2 possible states: 0 or 1.
2. To achieve hiding from the evaluator, the garbler obscures each value of every gate by mapping it to a random value:
* gate_0:
1. input_0: 0 -> random(128); 1 -> random(128)
2. input_1: 0 -> random(128); 1 -> random(128)
3. Output: 0 -> random(128); 1 -> random(128)
* gate_1
1. input_0: 0 -> random(128); 1 -> random(128)
2. input_1: 0 -> random(128); 1 -> random(128)
3. Output: 0 -> random(128); 1 -> random(128)
* gate_2
1. ...
2. ...
3. ...
The values in the truth table are replaced with randomly generated numbers, as shown in the figure below. To ensure distinguishability, each value is assigned a unique representation (called a Label). We use G(0,0,0) and G(0,0,1) to denote the enumerated values of Gate_0's first input, and so forth.

The Garbler encrypts the substituted truth table to ensure that a Gate's output Label can only be decrypted using its corresponding input Labels. This cryptographically binds the relationship between the Gate's outputs and inputs. The encrypted table is called a Garbled Table, as illustrated in the following diagram:

Generally:
$$Enc(X,Y,Z) = Z \oplus H(X||Y)$$, $$Dnc(X,Y,Z) = Z \oplus H(X||Y) = Z \oplus H(X||Y) \oplus H(X||Y) = Z $$
So, the evaluator could only get$$Z$$as long as he knows$$X,Y$$.
3. Data transfer and function compute

The Garbler transmits all input labels and the garbled tables for all gates to the Evaluator. The Evaluator then computes the final result according to the circuit's logic.
Technical Specifications:
* Each label is a 128-bit number, occupying 4 bytes
* Each garbled table occupies 4 * 32 bytes = 128 bytes
* Total data transmission size: a * 4 + b * 128 bytes
- Where:
- a = number of input labels
- b = number of gates

Then, the evaluator will compute the function as follows:

The Garbler sends all the Garbled Tables to the Evaluator, which is equivalent to the Garbler executing all possible computational paths of the entire circuit during the Setup phase and encrypting them. Therefore, the generation of these Garbled Tables is a one-time process. When the Garbler provides different inputs to the Evaluator (i.e., different combinations of input labels), the Evaluator can continuously decrypt and look up the tables for each gate until reaching the final gate, ultimately obtaining the computation result.

# BitVM3: Integrate Garbled Circuit in BitVM2

Garbled circuits have some excellent properties, but in the BitVM2 protocol, some of these features will not be utilized. As a result, when garbled circuits are applied to the BitVM2 protocol, their complexity becomes significantly simpler. For example:
- Removing the OT (Oblivious Transfer) component: The Evaluator does not have its own private inputs, so there is no need to use the OT protocol to securely obtain the corresponding labels while preserving privacy.

The workflow of the BitVM2 protocol based on garbled circuits is illustrated in the figure below. While the overall structure remains consistent with BitVM2, there are slight differences in the details.

Setup Phase
- A one-time Boolean circuit for Groth16 verification is constructed.
- Each operator generates distinct garbled tables for the Boolean circuit.
- Each operator must produce proofs of correctness for the garbled tables, ensuring:
- The logical correctness of each gate.
- Data consistency between gates.
- The bridge protocol can only commence after the bridge committee verifies the validity of the garbled tables.
PegIn & Pre-Sign Phase
- These phases remain identical to the original BitVM2 protocol.
- Users complete Bitcoin transfers and engage in the pre-signing process of the BitVM2 transaction graph with operators and the committee.
PegOut Phase
The transaction types remain consistent with the existing protocol, but the script logic differs slightly:
- Claim Transaction: After fulfilling the payment, the operator initiates a claim transaction for redemption. The transaction only includes the burn transaction and peg-out transaction details.
- Assert Transaction: If a challenger detects an invalid transaction, they initiate a challenge. The operator must provide the following in the assert transaction:
- Proof data: Three elliptic curve points (A, B, C), totaling 256 bytes (compressed to 128 bytes).
- Public input size: A 160-bit (20-byte) hash of the native data.
- Native data size: Variable, typically < 1024 bytes, including transaction data, block headers, etc.
- Disprove Transaction: Only checks whether the output label provided by the operator in the assert transaction matches the challenger’s computed label. If they do not match, the operator is slashed. The script logic is as follows:

//Hardcode the last garbled table in the disprove script
// Assume it's an AND gate
G(Last,2,0)
G(Last,2,0)
G(Last,2,0)
G(Last,2,1)
//Push the input label of the last gate
G(Last,0,*)
G(Last,1,*)
// Dnc to get correspondng output label G(Last,2,*)
OP_HASH160
OP_XOR (Emulation)
// Push output lable of operator
G(Last,2,*)
// Check equality
OP_CHECKEQUALITY

# Differences between BitVM2 and BitVM3
BitVM3 is still in the research phase, and its inherent limitations remain quite apparent. As a result, the BitVM3 protocol has not yet been finalized, with many details still open to optimization. This paper solely highlights the differences between BitVM2 and BitVM3, without making comparisons regarding the merits of either approach.

| | BitVM2 | BitVM3 |
| -------- | -------- | -------- |
| Circuit | Customized Circuit | Boolean Circuit |
| Challenger | Permissionless | Permissioned |
| On-chain Cost | High(3.34BTC) | Low(0.009BTC) |
| Off-chain Cost | Low | High |
| Trust Assumption | 1-N Challengers | 1-N Challengers |
| Cryptographic protocol | Fraud proof | Garbled Circuit |

Let's break down these points one by one to better understand their key differences:
1. Circuit
- BitVM2: Uses a customized circuit that splits Groth16 verification into multiple chunks, with each chunk handling different computations.
- BitVM3: Uses a Boolean circuit composed solely of Boolean gates to construct the Groth16 verification circuit.
2. Challenger
- BitVM2: Permissionless—anyone can act as a challenger. No challenger participation is required during setup, and there is no upper limit on the number.
- BitVM3: Permissioned—challengers must be pre-selected during setup, and the corresponding garbled tables must be distributed to them.
3. On-Chain Cost
- BitVM2: High—requires ~3.34 BTC (assuming feerate = 2) to publish all data on Bitcoin.
- BitVM3: Low—only ~0.009 BTC is needed to publish all labels.
4. Off-Chain Cost
- BitVM2: Low—only involves Groth16 verification, which is computationally lightweight and can even run on mobile devices.
- BitVM3: High—
- The operator must expend significant computational power to generate proofs.
- The operator requires substantial time to transmit data.
- Challengers must perform computations based on the garbled tables (a few billion operations).
5. Trust Assumption
- BitVM2: Trust-minimized—since challengers are permissionless, N can be very large, reducing trust requirements.
- BitVM3: Permissioned challengers—N is limited (typically <100), introducing higher trust assumptions.
6. Cryptographic Protocol
- BitVM2: Based on a fraud-proof mechanism, allowing challenges on any intermediate chunk.
- BitVM3: Based on garbled circuits, requiring challenges only on the final gate.

# Reference
[1] https://docs.google.com/presentation/d/1B-CW8fAqMQ1AYRYx8jv7uOen4X7jUwHzWTc5f-JaCYE/edit?slide=id.p#slide=id.p
[2] https://rubin.io/public/pdfs/delbrag.pdf