Citrea’s Role in Achieving Verification on Bitcoin with BitVM

Introduction to BitVM

For years, executing custom computations on Bitcoin has remained a challenging research topic. In October 2023, Robin Linus introduced BitVM, an approach that proposed expressing arbitrary computations using Boolean circuits. This was theoretically sound because all Boolean expressions can be built from primitive logic gates—primarily AND and OR, which together form a functionally complete set. These allow for the construction of anything from simple adders to complex SHA256 hashing circuits (examples). The parties then would proceed to play a bisection game over the logic gates to pinpoint wrong execution if any. Citrea developers immediately grasped the main idea and made a toy BitVM implementation.

A novel variant of BitVM: BitVM2

Even though the idea of BitVM was groundbreaking, it was infeasible due to its limitations:

• Excessive on-chain overhead.
• Multiple challenge windows.
• Irreparably big scripts due to exclusive reliance on logic gates, despite Bitcoin Script offering more capable opcodes like OP_ADD.

For example, the addition of two 32-bit numbers required hundreds of gates in BitVM while a single OP_ADD opcode could also do that. This potential improvement on top of the core idea of expressing a computation using the available opcodes was radical, so it was honored with the name “BitVM2”. This also marked the beginning of Citrea developers contributing to the open-source codebase of BitVM2. 

The main goal was to create a SNARK verifier script using bitcoin opcodes. The math behind SNARK verifiers usually involves pairing calculations, finite field and elliptic curve arithmetic and sometimes hashing. The construction of all these scripts began to create a firm foundation.

BitVM Alliance

As BitVM2 matured, collaboration intensified. In September 2023, the BitVM Alliance was formed to accelerate efforts and coordinate development. Founding members included ZeroSync, Citrea, Alpen, ElementLabs, and Fiamma, later joined by BitLayer, BOB, and Babylon.

While the development of BitVM2 has been a collaborative effort by the teams mentioned above, this article specifically highlights Citrea’s contributions.

Problems Needed to Be Solved for BitVM2

When BitVM2 was proposed, it  lacked many components to achieve SNARK proof verification. For this, we needed to identify the cryptographic primitives and optimize these primitives to overcome constraints of Bitcoin scripting language. Citrea contributed to the following major problems to achieve SNARK verification. 

Finite Field and Elliptic Curve Arithmetic

The elliptic curve used in BitVM is BN254 with a huge 254-bit prime. Representing the elements of this prime field is not easy because the arithmetic opcodes in bitcoin scripting language only works on at most 4-byte elements in the stack. A possible solution was to represent the field elements using limbs. However, arithmetic opcodes allow the result to overflow to a 5-byte number but this result can not be used again in another calculation. The solution for that was to work with numbers consisting of less than 32 bits and to use conditionals to make the result suitable for being used again in calculations. The data type u29 fulfills this purpose and ceil(254/29)=9 limbs are enough to represent a field element denoted by Fq.

In pairing based SNARKs such as Groth16, a key ingredient is field extensions. Fq2, Fq6, and Fq12 represent the extensions used in Groth16 and consist respectively of 2, 6 and 12 Fq elements. Considering the multipliers added at each level and the limitations about the script size and the number of stack elements, it is not hard to foresee a nightmare with, for example, the multiplication of two Fq12 elements. That’s why the initial optimizations to these primitive elements were crucial, for example using the Montgomery forms. 

Citrea's contributions to finite field and elliptic curve arithmetic: #37, #41, #43, #47, #49, #106.

Pairing

Bilinear mappings are what make it possible to use mighty elliptic curves in cryptological arguments. The implementation of pairing was done by Joe Payne by following an article on that topic. It was later improved and cleared of bugs.

Citrea’s contribution: #210.

Hashing

The opcodes in bitcoin script related to hashing work on single elements on the stack and therefore are unusable when dealing with data that is represented in small units such as bytes. That’s why the actual algorithms for widely used hashing algorithms had to be implemented in bitcoin script and SHA256 and BLAKE3 scripts were added in BitVM2 for that purpose. The implementation of SHA256 had even a bounty on it since it was representing a milestone in the context of developing custom functionality with bitcoin scripts. Optimizations to that SHA256 script began right after its initial creation. On the other hand, BLAKE3 script was also a necessity and additional functionality was added to it later by Citrea developers. 

Citrea’s contributions to hash functions: #60, #61, #62, #263.

Chunking

The obstacles were being overcome one by one. However, a few things were still resisting all efforts. Even though the script size of Groth16 verifier was brought down to around 1GB, it was far from the block limit of 4MB. To solve this piece of the puzzle, the idea of splitting the program into subscripts, called chunks, emerged. Each chunk would calculate and verify a specific part of the whole script.

The first initiative was an automatic chunker, which would take a huge Bitcoin script and would locate possible points to split and choose an efficient configuration. Although it is easy to say, it was not easy to create for many reasons. First, alongside the script size limitation, the total number of elements on stack in Bitcoin scripting language is restricted to 1000. That required a potential automatic chunker to be able to divide the script from cleverly selected breakpoints. That would also make the size of the conveyed information from one script to another smaller. Also, the verifier script is pretty complex, and consists of many logical conditions and huge variables that were hard to keep track of, so the idea was put on the shelf. Instead, manual chunking was preferred, merging Rust functions that create these scripts, which proved to be fruitful, resulting in numbers that are possible to create bridges on Bitcoin. 

Winternitz

While the chunking idea was smart, in order to be functional, the idea of running a single program in pieces requires some kind of communication between one another: the persistence of information between scripts. This problem is actually solvable with the usage of signatures, since they enable the functionality of linking each chunks’ input with another one’s output. With this information, one might mistakenly assume that the problem would be trivial with Bitcoin’s own methods, which utilize Schnorr and ECDSA signatures, but since they only allow signing transaction information, it would not be possible to sign arbitrary variables that are maintained between chunks using them. 

Understanding this obstacle, the BitVM Alliance chose Winternitz signatures for this task because they were more efficient to verify compared to contemporary methods, as they did not require heavy machinery like pairings or any arithmetic operations on hashes that would need to be maintained with Bitcoin’s own opcodes. While Winternitz signatures had their own disadvantages, like big signature sizes, these problems were also tackled by the BitVM team and Citrea with various optimizations. These signatures were further utilized for the persistence of information on various bridge designs, including our own.

Citrea’s contribution to Winternitz improvement: #127.

TMUL

TMUL is a new field multiplication method added to BitVM2 by Alpen which utilizes hints. It is substantially better than the old method which uses the Montgomery forms. Using hints is a clever way of proving a computation by providing an auxiliary value that simplifies the calculations and can be verified easily. An elemental example of that is to prove a division by providing the result as a hint and verifying the multiplication instead since division is a much more complex operation and multiplication. 

The integration of TMUL into the codebase required the need to change the form of all scripts to a form expecting hints. As is the case with almost every new component, TMUL was also open to optimizations. And clearing the Montgomery form usage at the end was also necessary. 

Citrea’s contribution to integrating and optimizing TMUL:

• TMUL integration to codebase: #93.
• TMUL and hinted functions optimizations: #99, #102, #116.
• Removing the Montgomery functions #188.

Multiscalar Multiplication

The results of multiple elliptic curve multiplications are added up in Groth16 verification. Elliptic curve operations are not trivial, yet alone their combination. That is why efficient methods are important in this multiscalar multiplication operation.

Citrea’s contribution to MSM constant base points optimization: #88.

Refactor and Reorganization

Many enthusiastic developers have been contributing to BitVM2 along with Citrea developers. Occasional refactors and reorganizations to the codebase are beneficial to achieve a smooth development experience for everyone involved.

Citrea’s contributions: #176, #201, #217, #177, #206, #281.

Bug Fixes

In a software project about cryptologic protocols, bugs are inevitable. They might be evident after a failing test or might be in obscure functions and reveal their face only when an overlooked edge case is present.

Citrea’s contributions to bug fixes:

• Field multiplication bug: #86.
• Hamming weight & verifier improvement: #852, #124.
• Additional bug fixes: #196, #139, #141, #147.

Conclusion

Thanks to the collaborative efforts of the BitVM Alliance, BitVM2 development finished and it's now in the auditing phase. While BitVM's core technology is what paves the way for trust-minimized Bitcoin bridges, how it is implemented into a secondary layer is critical to achieving a secure and scalable two-peg mechanism.

Citrea's BitVM-based bridge, Clementine, addresses three critical problems in implementing a Bitcoin bridge:

• Bitcoin-light client (provably reasoning with canonical chain)
• Collateral-efficiency (having to source a lot of operator collateral)
• Scalability (ability to do withdrawals in parallel that can be disproven with a single disprove tx)

Clementine bridge and its whitepaper is currently the only documentation of how to use BitVM in a bridge design with clear solutions toward a secure and efficient bridge implementation.

Written by Hakan Karakuş.