BitVM

Why do we need BitVM?

To transform Bitcoin’s virtual machine from Turing incomplete to Turing complete.

What difference will ordinary users notice?

Previously, Bitcoin had few dApps, such as AMMs or L2s is missing. After implementing BitVM, these applications can be realized on Bitcoin L1.

Why is it feasible now? What was the most important discovery?

Previously, Bitcoin scripts were limited to 200 logical operations per transaction [related code], but after Taproot went live on the mainnet, script size can be increased to the segregated witness limit of 4MB.

Why implement ZKP in BitVM?

Once ZKP verification is implemented, BitVM’s verification upper limit is established. If we implement ZKP verification using a 2MB transaction on the Bitcoin mainchain, then with ZKP technology, no matter how complex the computation in the virtual machine becomes, we can complete it within this 2MB transaction.

It sounds like we just need to implement the ZKP verification code once. I see the verification code isn’t long, so why hasn’t it been implemented yet?

The verification code appears short because it typically uses libraries and other methods to package complex functionality. The actual logic is much more complex, and in solutions like BitVM, everything needs to be reimplemented from the ground up.

Currently, some experts have claimed to have implemented it, but the complexity (script length) is too high for practical use, so many experts are still working on optimization.

Many L2s claim to be based on BitVM. What should we focus on?

Most current L2s claim they will implement true Bitcoin Settlement L2 after BitVM is implemented.

Therefore, for technical personnel, the key is to focus on BitVM’s progress. Recommended to follow the TG group.

I heard that complex scripts now exceed 4MB (Bitcoin’s segregated witness limit). How can they be put on-chain?

• Simple approach: Use Lamport signatures (hash signatures) to break down complex programs into multiple steps, each executed on the blockchain. This method allows challenging the prover without permission but occupies a lot of on-chain space.

• Balanced approach: Transfer part of the prover’s heavy work to the verifier’s fraud proof, significantly reducing on-chain space. The prover only needs to submit the final result and all intermediate step results once, and the verifier can perform operations in a single step to deny any assertion.

• Optimistic approach: Improves the above design process in most cases, but adds two rounds of interaction in the worst case: the prover first submits the final output state, which anyone can challenge if incorrect; then the prover submits the results of intermediate steps, which anyone can deny if incorrect.

In short, the three approaches, from simple to complex, progressively optimize on-chain verification space occupation and interaction frequency, but the most optimistic approach requires the most interaction rounds in the worst case.

Challenges

Script Level

Divided into script logic and script mechanism parts.

Bitcoin was deliberately designed as a non-Turing-complete virtual machine, so the functions it can execute are very limited. How to use script operators with limited functionality to complete complex script logic is very challenging. This problem is solved through two types of methods: optimizing the implementation of script logic and finding appropriate script mechanisms.

Coin Locking Logic Level

Bitcoin uses the UTXO locking and unlocking mechanism. The locking script cannot control the characteristics of subsequent transactions, so how to design a scheme that not only allows coins to be unlocked but also meets the needs of subsequent business changes is challenging.

For example, in Ethereum, after a transaction comes in, the logic of the smart contract controls the changes of various variables in the contract; while in Bitcoin, once the UTXO is unlocked, the subsequent creation of new locking scripts (i.e., UTXOs) is not controlled by this transaction.

Basic Concepts

Bitcoin Addresses

Reference: https://learnmeabitcoin.com/technical/script/

Electronic Circuit

https://circuitverse.org/users/1958/projects/8-bit-adder-295e9ba0-485c-4d65-acce-82435aad5e32

Bitcoin’s OP_XOR is disabled, so OP_NUMNOTEQUAL is used instead.

Connector

A “connector” is a special type of output used to ensure the atomicity of transaction plans. The purpose of a connector is to let the blockchain check whether a specific transaction ID exists, and if it already exists, the transaction is invalid. This is accomplished by attaching an output of that transaction to the consuming transaction and pre-signing all previous outputs of the consuming transaction, utilizing the blockchain’s prohibition of double-spending the same output (connector) during transaction processing.

Groth16

The core computation is pairing calculation.

Pairing

Here are some common bilinear pairing calculation methods:

Weil Pairing: Important in theoretical research, but due to its computational complexity, it is not common in practical applications.

Tate Pairing: Widely used in many practical cryptographic applications, including identity-based cryptosystems and attribute-based encryption. More computationally efficient than Weil pairing.

Ate Pairing: Very common in practical applications, especially when efficient computation of bilinear pairings is needed. Highly computationally efficient, one of the most commonly used bilinear pairing calculation methods in practical applications.

R-ate Pairing: Suitable for application scenarios requiring higher efficiency, especially in environments with limited computational resources. This is a variant of Ate pairing; by choosing better “target” points, R-ate pairing is more computationally efficient than Ate pairing.

Optimal Ate Pairing: Suitable for application scenarios requiring the highest efficiency, especially in environments with very limited computational resources. By selecting specific elliptic curves, the computation process of Optimal Ate pairing can be completed through a shorter Miller loop, thus achieving the highest computational efficiency.

According to references [1-3], most implementations on Intel CPUs are below 2M cycles. In implementation [4], the project uses the RISC-V instruction set to convert the groth16 verification in the mcl library (C++ implementation) to RISC-V instructions, approximately 17B cycles.

[5] is the groth16 verifier code on mina, implementing the Optimal Ate Pairing algorithm.

[6] is a detailed explanation of the Optimal Ate Pairing algorithm on BN curves, [7] briefly describes the algorithm flow in the previous text. Note: [7-8] both mention that the bn128 curve on Ethereum has slightly different parameters from those in the paper, so be careful to select the correct curve parameters.

[9] is the reference code for Ethereum’s ECC implementation, and its code logic can be referenced in the appendix algorithm description in [10].

SNARG vs SNARK

SNARG (Succinct Non-interactive Argument): Only requires computational soundness, allowing acceptance of incorrect statements with a certain probability, without guaranteeing that the prover possesses a valid witness.

SNARK (Succinct Non-interactive Argument of Knowledge): Requires knowledge soundness, ensuring that the prover must possess a valid witness and provides stronger guarantees in terms of security.

Feature	Computational Soundness (SNARG)	Knowledge Soundness (SNARK)
Soundness Type	Computational soundness	Knowledge soundness
Prover Capability	Limited computational ability, i.e., the prover finds it difficult to deceive the verifier	The prover must possess a valid witness
Verifier’s Confidence	Identifies errors with negligible probability	High trust in accepted statements
Application Scenarios	Systems with low security requirements	Systems requiring strict privacy and security

Why BitVM2 chooses SNARG? (Selection basis, original text as follows, where [7] is the GROTH16 paper)

Peg-in vs Peg-out

“peg-in” is used to describe the process of transferring bitcoin to a sidechain “peg-out” is used to describe the process of returning bitcoin from a sidechain

Reference: https://dev.rootstock.io/concepts/powpeg/#peg-inpeg-out-and-other-properties-of-rootstock-powpeg

Multisig

https://jimmysong.github.io/taproot-multisig/

Bitcoin Script Enhancement

Bitcoin script itself is designed to be simple and stateless, which makes smart contract development difficult. We need to use some methods to enhance the capabilities of Bitcoin script to implement richer scenarios.

Some BIP proposals can enhance the capabilities of Bitcoin script, but BitVM’s overall approach is based on the limitations of existing Bitcoin, with the premise of not making fork changes.

Stateful Bitcoin Scripts

Bitcoin script is stateless, meaning subsequent scripts cannot continue calculations based on the execution results of previous scripts or the same input values. A typical idea is that we expect to be able to enforce the use of the same value in two stateless scripts.

Example:

• Script 1 needs to use X=234 as the starting point for calculation
• Script 2 also needs X=234 as a variable in the calculation process

The implementation approach is to use signatures, i.e., both scripts verify that the signature of X is valid.

If forks are allowed, the OP_CHECKSIGFROMSTACK proposal can be used.

Hash-based signatures can be used below.

OP_CSFS

OP_CHECKSIGFROMSTACK (OP_CSFS)

Feature	OP_CHECKSIG	OP_CHECKSIGFROMSTACK
Message Source	Automatically generated from transaction data	Can specify any message
Parameters	Signature, public key	Signature, message, and public key
Usage	Verify transaction signatures	Verify signatures of arbitrary messages
Security	Suitable for protecting Bitcoin UTXO	Extends the application range of digital signatures
Implementation Platform	Bitcoin mainchain	Sidechains based on ElementsProject.org, proposed for Bitcoin

Reference: https://bitcoinops.org/en/topics/op_checksigfromstack/

Lamport Signature

Signature generation: By using a 256-bit cryptographic hash function (such as SHA-256), the message is hashed to obtain a 256-bit hash value.

For each bit, depending on whether the bit value is 1 or 0, the corresponding number is selected from the number pair in the private key. If the bit value is 0, the first number in the number pair is selected; if the bit value is 1, the second number is selected. This way, a sequence of 256 numbers is generated, which is her signature.

Winternitz

Signature generation: Use the SHA-256 hash function to hash the message, resulting in a 256-bit digest. This digest is further broken down into 32 8-bit values (N1, N2, …, N32).

Then, for each 8-bit value, perform 256 minus the value itself (to get the number of changes) hashes. For example, if N1’s value is 10001000, which is 136 in decimal, in the hashing process, N1 needs to execute 256 minus 136 equals 120 hashes. After repeating the above operation for each 8-bit value, a digital signature for the message is formed.

Bit-Commitment

To learn more, please refer to the related documents:

https://www.geeksforgeeks.org/lamport-one-time-signature-scheme/

https://www.geeksforgeeks.org/winternitz-one-time-signature-scheme/

Emulated Covenants

Connector Outputs

Understanding the Connector mechanism principle

BitVM

Advanced Bitcoin Script

BitVM can be considered an advanced version of Bitcoin script. Its features include:

• Expressing complex Bitcoin contracts
• Script template language
• Expanding loops
• Combining functions
• Composite opcodes (xor, shift, mul, blake3, field arithmetic, …)
• Stateful Bitcoin scripts
• Lamport signatures (48, u32, u160, …)
• Connector Outputs
• Potentially complex scripts, complex Tap trees, and large transaction graphs

SNARK Verifier in Script

• Pairing-based proofs are constant size (Groth16, fflonk, …)
• Implementation in Script is huge (gigabytes!)
• Script size limit is 4 MB (a full block)

Idea: commit to 1000 intermediate results

f(x) = y f1(x) = z1 f2(z1) = z2 f3(z2) = z3 … f1000(z999) = y

Disproving a single step suffices For example f42(z41) != z42

Every f_i can be up to 4 MB. That’s 4 GB in total!

Advantages

• BitVM makes Bitcoin contracts smarter
• No soft fork needed
• Better options: TXHASH, OP_MUL, OP_BLOCKHASH

Cross-chain Bridge

Bridge Definition

The purpose of cross-chain bridges is to bridge BTC to any other system. Currently, Bitcoin has many limitations, so it’s acceptable if the solution is not so elegant. BitVM Bridge is currently not the most perfect and elegant solution.

BitVM defines its bridge as:

• BitVM Bridge is limited to low-frequency use, so it’s mainly used for large transactions
• End users should use cross-chain exchanges (such as Lightning Network)
• Fixed set of operators, but anyone can become a verifier

Security Guarantees

Security guarantees are defined as follows:

Two coalitions, each requiring only one honest member:

• 1000 participants in the trusted setup
• 100 bridge operators

Security guarantees:

• Security: No one can steal deposits (1 honest person out of 1000)
• Liveness: No one can prevent valid Peg-outs (1 honest person out of 100)
• Anyone is allowed to join, so users don’t have to trust anyone

Limitations

• Complexity, which can easily lead to security vulnerabilities
• How to balance incentives to ensure that all parties participating in the system can continue to operate honestly
• Operators must pre-commit (lock) funds for two weeks
• But no need for 1:1 collateral (TODO: how much should it be?)
• For each Peg-in, all 1000 parties must pre-sign 100 Peg-out transactions
• The coalition can censor Peg-ins

BitVM Team’s Plan

• BitVM2 Draft version has been released
• The BitVM team believes the current design is practical
• Mainnet version expected to launch this year (2024)

BitVMX

https://www.youtube.com/watch?v=fMsRJbzwrEw

https://x.com/danielfogg/status/1816566761296199819

https://www.rootstocklabs.com/content-hub/exploring-lamport-and-winternitz-signatures-for-stateful-bitcoin-scripts/

https://www.rootstocklabs.com/content-hub/bitvm-vs-bitvmx/

https://www.rootstocklabs.com/content-hub/bitvmx-whitepaper-explained/

Bitfinity

https://github.com/bitfinity-network/whitepapers/tree/main

https://github.com/bitfinity-network/whitepapers/blob/main/BitFusion.pdf

https://github.com/bitfinity-network/whitepapers/blob/main/Bitfinity_Network.pdf

Script

SHA256

The sha256 visualization tool [12] can provide visualization of process data, which is extremely convenient for process debugging. Code implementation references [13], and constant and basic operation definitions come from [11].

Why do we need to reimplement op_sha256 when it already exists in Bitcoin script?

The problem with op_sha256 is that strings cannot be concatenated in Bitcoin script, which limits its use, such as being unable to verify data hashes.

GROTH16

Current implementation, BitVM script is 1.3GB (Pairing only)

The fastest implementation currently is the 2M Cycles implementation method on Intel CPU. Considering that Intel CPU is a CISC architecture, while BitVM is more like a RISC architecture, it is roughly estimated that there could be more than 20 times the script quantity, i.e., at least 40M in size, unless there is room for optimization in the underlying algorithm implementation.

”On Proving Pairings”

Paper: https://eprint.iacr.org/2024/640

Description: Used by Alpen Labs in SNARKnado

Improvement methods:

• The final exponentiation step in pairing verification can be replaced by a more efficient “residue check” that can be incorporated into the Miller loop.
• Reduce the cost of the Miller loop by precomputing all necessary rows.
• Improve the protocol of [gar] by combining quotients, which allows us to prove higher-order relationships more efficiently.

Instance: https://hackmd.io/@70xfCGp1QViTYYJh3AMrQg/S1cU7YJGC

Other Implementations

OP_CAT

Address to follow: https://github.com/bitcoin/bips/blob/master/bip-0347.mediawiki

Reason for disabling: The crash of OP_LSHIFT once led to a large number of op codes being disabled, including OP_CAT.

Possibility of enabling: The C++ code already has a 520-byte maximum limit, so the possibility of using OP_CAT is not great; enabling it only requires a soft fork.

Focus point: The proposal only requires OP_CAT to be enabled in taproot.

Personal opinion: It took Taproot more than two years to go live, and for this OP_CAT to form a consensus in the community and then go live, the most optimistic estimate is also a year away.