Citrea’s Prover: Designed for Bitcoin
Citrea is the first rollup to leverage Bitcoin’s secure and decentralized blockspace to enable the most trust-minimized way to use BTC. By using Bitcoin as a data availability and settlement layer, Citrea ensures that any Bitcoin full-node can reconstruct Citrea’s latest state, and verify its integrity. This allows Citrea to increase BTC’s utility without compromising its security or decentralization.
At the core of this construction is Citrea's Prover, which is responsible for maintaining Citrea’s state on Bitcoin. This includes updating and ensuring its validity. However, this task is challenging due to Bitcoin’s limited and expensive blockspace. Citrea’s Prover is designed to work within these constraints, making it an efficient and scalable ZK rollup for Bitcoin.
In this piece, we’ll explore how Citrea’s Prover overcomes Bitcoin’s limitations.
Understanding the Prover’s Role
Prover is one of the most crucial components of Citrea as it is responsible for ensuring Citrea’s state on Bitcoin is available and valid, inheriting data availability and settlement guarantees of Bitcoin. The Prover collects Citrea blocks to form a batch and generates a zero-knowledge proof to assert the validity of that batch. Citrea also must inscribe the batch to inherit Bitcoins’ data availability guarantees. However, when building a ZK rollup on Bitcoin, a prover needs to be carefully designed considering Bitcoin’s limited and expensive blockspace.
The first optimization Citrea’s Prover makes is to inscribe state differences, rather than full transactional data, to inherit Bitcoins’ data availability. State difference is storage slot difference between the last finalized state and current state. By summing the state differences, any Bitcoin full node can reconstruct Citrea’s state.
While this approach is efficient, Citrea’s Prover also includes additional techniques to further optimize the use of Bitcoin’s blockspace. First one is called stateful compression and revolves around the storage slot keys and values. The second one revolves around the sequencer commitments and is applied when the compressed state difference does not fit into a Bitcoin block, i.e. size of state diff is > 4 MB.
Stateful Compression in Citrea’s Prover
Stateful compression is a data compression technique where the compressor (in Citreas’ case, the Citrea Prover) improves efficiency by keeping track of patterns in the data, using a memory of past inputs to make decisions about how to compress current data. This technique achieves higher compression rates than stateless compression techniques, where each chunk of data is compressed independently, without reference to previous data. While stateless compression is faster, it usually achieves lower compression rates. Stateful compression, though slower, allows for much better results by leveraging recurring patterns and relationships in the data.
In Citrea’s case, stateful compression reduces the size of the state difference, which consists of storage slot keys and values. Each storage slot consists of a key-value pair where value is accessed from the key. Both the key and value are each 32 bytes long when initialized. Since some storage slots will be frequently updated, consistently using 32 byte long keys for updates is inefficient. To address this, Citrea Prover indexes each key into an 8 byte long chunk, which is then used to update the corresponding value.
Compressing the value component is easier, as it often contains sequences of zeroes. Citrea’s Prover uses a 1-byte flag to indicate changes in the value, with four possible flags:
- NoCompression Flag: This indicates that 32 byte Value will be provided. It is mostly used for initializing storage slots during events like contract deployments.
- Add Flag: This indicates an increase in the value, accompanied by a 1-byte chunk specifying the amount of change.
- Sub Flag: This indicates a decrease in the value, also accompanied by a 1-byte chunk.
- Transform Flag: This states that the value has changed, neglecting any relation between the previous and current value. This is also accompanied by a 1-byte chunk.
After applying stateful compression, Citrea’s Prover further compresses the state difference using Brotli, a compression algorithm that reduces the size of the state difference by about 65%.
Citrea’s Prover and Sequencer Commitments
To protect the ordering finality until the batch proof is produced, Citrea’s sequencer commits the merkle root of Citrea’s soft blocks. To uphold this ordering, Citrea’s Prover is configured to scan Bitcoin blocks to include the blockhash of the Bitcoin block scanned in its outputs and inscribe this output along with ZK proof of the batch and state differences resulting from the batch. The Citrea Prover applies another compression technique around these sequencer commitments in addition to stateful compression technique and Brotli compression.
Citrea’s Prover scans Bitcoin blocks to extract sequencer commitments. For each extracted commitment, the Prover begins by computing the state difference for the first commitment in the sequence. It then iteratively adds following commitments (e.g., 1 → (N-1), 1 → N, and so on), calculating the cumulative state difference at each step to determine its size. If the size of state difference between 1 → N exceeds 4 MB—making it too large to fit into a Bitcoin block—the Prover ignores Nth commitment and generates a zero-knowledge proof that asserts the validity of transactions between 1 → (N-1)th sequencer commitment. Prover later generates a second zero-knowledge proof to assert the validity of the transition from the (N-1)th commitment to the Nth commitment.
This approach works even when the Nth commitment and (N-1)th commitment are in the same block.
Conclusion
Using Bitcoin as a data availability and settlement layer is challenging due to Bitcoin's limited and expensive blockspace. Citrea overcomes these limitations by using state differences and further advanced compression and aggregation techniques. This approach significantly reduces the space requirements, making Citrea more efficient and better suited to operate within Bitcoin's constraints.
By working within Bitcoin’s constraints, Citrea makes it possible to use Bitcoin’s security for new decentralized applications. As the first rollup being built on Bitcoin, we're constantly exploring the most efficient and scalable ways to build a rollup for Bitcoin, paving the way for further advancements and practical implementation.
Yusuf Ozmiş
Join the community and follow us on X to be an early adopter. You don’t want to miss any updates from Citrea!
- Follow Twitter | X
- Join Discord