The Hitchhiker's Guide to Scaling Bitcoin with STARKs
Examining the potential implementation and implications of Scalable Transparent ARguments of Knowledge for Bitcoin's future
Contents
Introduction: The Big Picture
What are STARKs?
Why STARKs for Bitcoin?
The Technical Details: How STARKs Work on Bitcoin
OP_CAT: The Unsung Hero of Bitcoin Scaling
Covenants: Smart Contracts on Bitcoin
STARK Verification in Bitcoin Script
Implementation Considerations
The Bigger Implications: What This Means for Bitcoin and Beyond
Increasing Throughput
Fractal Scaling with Rollups
Horizontal Scaling with Recursive Proofs
Scaling the Lightning Network
Costs and Risks of Validity Rollups
STARKs: The Bridge Between Bitcoin and Ethereum
Conclusion: The Road Ahead
Bibliography
1. Introduction: The Big Picture
Imagine a world where Bitcoin, the pioneer of cryptocurrencies, can handle thousands of transactions per second, support complex smart contracts, and still maintain its core principles of decentralization and security. We can achieve this with STARKs (Scalable Transparent ARguments of Knowledge).
This article stands on the shoulders of giants, drawing from the research and insights of numerous experts in the blockchain and cryptography fields. Much of the detailed technical information in this article draws from the comprehensive research paper "Validity Rollups on Bitcoin" by John Light (Light, 2023). Light's work provides an in-depth exploration of how validity rollups could be implemented on Bitcoin and the potential impacts of such an implementation. Additionally, this article references work by other researchers and industry leaders mentioned in the bibliography, including Eli Ben-Sasson, Victor Kolobov, Avihu Levi, Andrew Poelstra, and others. Their contributions have been instrumental in shaping our understanding of Bitcoin scaling and the potential of STARKs.
Why do we need to scale Bitcoin in the first place? What are STARKs, and how can they help? And what are the broader implications of implementing STARKs on Bitcoin?
Bitcoin, in its current form, is like a reliable old car. It gets you where you need to go, but it's not exactly built for high-speed races or carrying heavy loads. As Eli Ben-Sasson, co-founder and president of StarkWare, puts it:
"Bitcoin's Whitepaper foresaw a network that was used practically for payments, large and small, and operated by all, rich and poor. Today, there are 1.5 billion people in the world who don't even have a bank account. Bitcoin payments would not just be an alternative for these people but actually their first access to financial infrastructure." (Ben-Sasson, 2024)
However, Bitcoin's current capacity is like a narrow road that can only handle a few cars at a time. It's too limited and expensive for these 1.5 billion people. STARKs could widen this road, allowing more "traffic" (transactions) without compromising the security of the journey.
This guide will cover:
The fundamentals of STARKs and their relevance to Bitcoin
The technical details of implementing STARKs on Bitcoin, including the crucial role of OP_CAT and covenants
The broader implications of this technology for Bitcoin and the entire blockchain ecosystem
The potential risks and challenges associated with this scaling solution
How STARKs could bridge the gap between Bitcoin and Ethereum
Any mistakes or misinterpretations are solely the responsibility of the author. For questions, comments, or corrections, please contact the author:
Telegram: @espejelomar
X (Twitter): @espejelomar
Signal: starknet_01
2. What are STARKs?
STARKs, or Scalable Transparent ARguments of Knowledge, are a type of cryptographic proof system.
Imagine you're playing a game of Sudoku with a friend. You've solved the puzzle, but your friend doesn't want to spend an hour checking every single number. STARKs are like a magical way of proving to your friend that you've solved the Sudoku correctly, without them having to check every number. Even more important, this proof is much quicker to verify than solving the puzzle from scratch.
In the context of Bitcoin, STARKs allow us to prove that a large number of transactions or complex computations are valid, without requiring every node on the network to re-execute all those transactions or computations. This is the key to scaling: we can do more work off-chain and provide a succinct proof that it was done correctly.
As Avihu Levi from StarkWare explains:
"STARKs offer a promising solution to alleviate these limitations, as they can efficiently verify the execution of computations offchain. By leveraging STARKs, it is possible to perform more complex computations within Bitcoin smart contracts and minimize their onchain footprint." (Levi, 2024)
3. Why STARKs for Bitcoin?
"Why STARKs? Aren't there other scaling solutions out there?" Indeed there are, but STARKs have some unique properties that make them particularly well-suited for Bitcoin:
1. Post-quantum security: Unlike some other cryptographic systems, STARKs are believed to be secure even against quantum computers.
2. No trusted setup: Some other proof systems require a complex setup phase that, if compromised, could undermine the entire system. STARKs don't have this weakness.
3. Bitcoin-friendly: The STARK verification process aligns well with Bitcoin's existing cryptographic operations, making implementation more straightforward.
4. Scalability: STARKs can verify extremely large computations with relatively small proofs, offering significant scaling potential.
5. Battle-tested: As Eli Ben-Sasson notes, STARKs have been "trusted with over $1T settled" in other contexts, demonstrating their reliability (Ben-Sasson, 2024).
4. The Technical Details: How STARKs Work on Bitcoin
Now that we understand the why, let's delve deeper into the how. Implementing STARKs on Bitcoin involves several key components and technical considerations. John Light's research provides valuable insights into these technical aspects (Light, 2023).
4.1. OP_CAT: The Unsung Hero of Bitcoin Scaling
At the heart of enabling STARKs on Bitcoin is a simple but powerful operation called OP_CAT. This opcode, which was originally part of Bitcoin but later removed, is now poised to make a comeback and revolutionize Bitcoin's capabilities.
OP_CAT is a Bitcoin script opcode that concatenates (joins together) elements. As Victor Kolobov explains:
"OP_CAT is a Bitcoin script opcode that concatenates elements. It plays a crucial role in implementing covenants and STARKs on Bitcoin, which, in turn, brings powerful general computation to Bitcoin." (Kolobov, 2024)
While this might seem trivial at first glance, OP_CAT is a crucial building block for more complex operations, including STARK verification.
4.1.1. The Importance of OP_CAT for STARKs
For STARKs, OP_CAT is essential because STARKs primarily consist of concatenating data together and hashing it. This leads to great savings as hashing is a native Bitcoin script operation, unlike more complex algebraic operations. The main hashing operations in STARKs are Merkle path verification and the Fiat-Shamir transform.
As CryptoRank notes in their article "Bitcoin Scaling Is Near: Prepare Yourself for OP_CAT (BIP-420)":
"The re-enablement of OP_CAT would actualize covenants on Bitcoin, which, once again, are spending conditions that restrict how funds can be spent in future transactions. This capability is crucial for Bitcoin Layer 2 solutions since it enhances the scripting capabilities needed for more complex and trustless Bitcoin infrastructure." (CryptoRank, 2024)
4.1.2. The History of OP_CAT
Interestingly, Bitcoin's creator, Satoshi Nakamoto, initially included OP_CAT but later removed it. Eli Ben-Sasson explains the reasoning behind this decision:
"You could see that the big danger with it is that suddenly, well, you could just keep on doubling strings, and within a very small number of operations, you could have this immense string that you just can't hold on your computer, and it would crash."
It's like giving someone the ability to infinitely expand a balloon - eventually, it would pop. However, there's a simple solution to this problem:
"But of course, there is a very simple way to stop that, which is basically to say, well, you can keep on the, you know, concatenating strings, but there's a limit, whatever, 1 kb or 1 mb or whatever it is, that you can't go beyond that."
In other words, we can add a safety valve to the balloon so it can't overinflate.
4.1.3. The Return of OP_CAT
Now, with the proposed BIP-420, there's a push to reintroduce OP_CAT through a soft fork. This reintroduction would enable the creation of covenants on Bitcoin, which are crucial for enhancing Bitcoin's scripting capabilities and leveraging the BitVM framework.
CryptoRank's article highlights the significance of this development:
"The new BIP-420 proposal aims to reintroduce the OP_CAT operation code through a soft fork to enable the creation of covenants, which are crucial for enhancing Bitcoin's scripting capabilities and leveraging the BitVM framework." (CryptoRank, 2024)
4.1.4. Implications of OP_CAT's Return
The reactivation of OP_CAT could have far-reaching implications for Bitcoin:
1. Enhanced Programmability: OP_CAT would allow for more complex and flexible Bitcoin scripts, enabling advanced smart contract functionality.
2. Covenants: With OP_CAT, it becomes possible to implement covenants, which are rules dictating how BTC can be spent in future transactions.
3. STARK Implementation: OP_CAT is a key component in implementing STARK verification on Bitcoin, which could dramatically increase its scalability.
4. Layer 2 Solutions: The enhanced scripting capabilities could pave the way for more efficient and secure Layer 2 solutions on Bitcoin.
4.1.5. Timeline for OP_CAT Implementation
While the exact timeline for OP_CAT's reintroduction is not set, there's growing momentum in the Bitcoin community to implement this change. As Eli Ben-Sasson notes:
"Starknet can become a single layer that settles on both Bitcoin and Ethereum... This will happen within six months after the potential Bitcoin upgrade, OP_CAT." (Ben-Sasson, 2024)
This suggests that once OP_CAT is implemented, we could see rapid development in Bitcoin scaling solutions, including STARK-based approaches.
In conclusion, OP_CAT, despite its simplicity, could be the key that unlocks Bitcoin's next evolution. By enabling more complex scripts, covenants, and STARK verification, OP_CAT could help Bitcoin scale to meet global needs while maintaining its core principles of security and decentralization. As CryptoRank advises, it's time for Bitcoin enthusiasts to "Prepare Yourself for OP_CAT (BIP-420)" as we stand on the brink of this exciting development in Bitcoin's scaling journey.
4.2. Covenants: Smart Contracts on Bitcoin
With OP_CAT in place, we can implement covenants on Bitcoin. Covenants are a way to create persistent logic and state on Bitcoin, essentially allowing for smart contracts. Avihu Levi describes a structure for this:
"You have remember that we said that with OpCAT we can build covenants, which means we can be aware of the transaction data. Somebody is providing this to us. So in particular, we can say, okay, this witness program can be now receive the information, the data of all the other white boxes in the transaction." (Levi, 2024)
This structure allows us to create smart contracts on Bitcoin that can maintain state and enforce complex rules, all while preserving Bitcoin's UTXO model. The general approach would be to encode the state in the transaction data itself and check the validity of its transitions to new values. To this end, our transaction will have two outputs:
The first output holds the logic of the contract (via a locking script), as well as the funds locked in the contract.
The second output holds the current state of the smart contract. This UTXO's locking script only holds state and will never be spent (it locks practically 0 bitcoins).
The locking script logic will enforce the following rules:
The spender transaction must have the same exact form (two outputs only, and all funds locked in the first output)
The first output must have the same locking script logic
The second output must be a valid state
The input provided to the current locking script must convince it the transition from the current state to the new state is valid (the validity is defined by the logic designer)
This construction, sometimes referred to as a "state caboose," ensures that the smart contract logic remains immutable and that state transitions follow the predefined rules.
4.3. STARK Verification in Bitcoin Script
The final piece of the puzzle is implementing a STARK verifier in Bitcoin script. This is where things get really interesting. Instead of writing complex contract logic directly in Bitcoin script, we can use a STARK verifier to check proofs of off-chain computation.
Levi proposes a structure where:
"The logic of the witness program of the smart contract is now, I define it to be a stack verifier. What does it mean? It means that the logic now says here is a way to verify a computation. And I also specify particularly which computation I intend to have here." (Levi, 2024)
This approach allows for complex computations to be performed off-chain, with only the verification happening on-chain. This dramatically increases the potential complexity and scale of operations that can be performed "on Bitcoin", while keeping the actual Bitcoin blockchain lean and efficient.
The STARK verifier in Bitcoin script would need to be able to verify validity proofs that prove data availability and that the new rollup state root is a valid update to the last valid rollup state root confirmed on the parent chain. Only state update transactions that are accompanied by a valid proof will successfully advance the rollup state when confirmed.
4.4. Implementation Considerations
To implement STARKs on Bitcoin, several changes to the Bitcoin protocol would be necessary. According to research by Trey Del Bonis, cited in Light's paper, the main changes needed are:
Support for validity proof verification
Implementation of recursive covenants
Increasing or removing the stack element size limit
Optional: OP_EVAL and PUSHSCRIPT opcodes for optimization
The validity proof verification is an obvious necessity for STARKs. The type of proofs supported will determine the capabilities of the rollups that can be built on Bitcoin.
Recursive covenants are needed to propagate the rollup construction forward with each state update, ensuring that BTC locked in a rollup script and not yet withdrawn remains in the script from one rollup state update to the next.
Increasing or removing the stack element size limit would make validity rollup data easier for the rollup script to work with and could potentially increase the number of transactions that can fit into each rollup state update.
The OP_EVAL and PUSHSCRIPT opcodes are suggested optimizations that could reduce the size of the rollup script in some areas, potentially reducing the amount of blockspace used and making rollups cheaper to use.
5. The Bigger Implications: What This Means for Bitcoin and Beyond
5.1. Increasing Throughput
STARKs can significantly increase the transaction throughput on Bitcoin. Let's look at some concrete numbers, based on Light's analysis (Light, 2023):
Account model validity rollup: Up to about 250,000 transactions per block
UTXO model validity rollup: Up to about 26,432 transactions per block
Shielded UTXO model validity rollup: Up to about 4,552 transactions per block
Compare these to the current Bitcoin mainchain capacity of about 7,130 transactions per block for 1-input-2-output P2WPKH transactions.
The exact throughput increase depends on the implementation details, but even in the most conservative case (shielded transactions), we're looking at a significant improvement in transaction capacity.
5.2. Fractal Scaling with Rollups
The scaling gains provided by validity rollups do not stop at L2. Validity rollups can be layered on top of validity rollups to provide "fractal scaling" to virtually unlimited levels of scale. Once bitcoin L1 blocks fill up with L2 validity rollup transactions, a Layer 3 (L3) validity rollup could be built on top of the L2 validity rollup, and so on.
5.3. Horizontal Scaling with Recursive Proofs
As more transactions need to be proven valid at each rollup layer, the difficulty of creating the necessary validity proofs increases. This computation can be parallelized using recursive proof composition. Recursion allows many computers to work on proving the validity of different transactions, and then these proofs can be combined into a single proof, allowing horizontal scaling.
5.4. Scaling the Lightning Network
The additional transaction capacity enabled by validity rollups could be used to support more Lightning transactions, increasing the potential number of users who can onboard and use Lightning in a self-custodial manner. For 2-P2WPKH-input-1-P2WSH-output-2-P2WPKH-output dual-funded channels, rollups can create room for up to 3.8x more Lightning channel open transactions.
6. Costs and Risks of Validity Rollups
While the benefits of validity rollups are significant, they come with their own set of costs and risks. John Light's research provides a comprehensive overview of these potential drawbacks (Light, 2023):
Increased bandwidth and storage costs
Managing full node verification costs
Miner extractable value (MEV)
Algorithmic incentive manipulation contracts
Novel cryptography risks
Compromised "toxic waste" in some implementations
Bandwidth and Storage Costs
If block space is increased to allow for more rollup transactions, this would increase bandwidth and storage costs for L1 full nodes. Light notes that more data will need to be relayed around the bitcoin network when broadcasting transactions and blocks, and more data will need to be stored on disk (Light, 2023).
Full Node Verification Costs
Validity rollups impose a new cost on L1 full nodes: the cost to verify the validity proof of the rollup state update. This verification cost can vary widely depending on the complexity of the proof and performance optimizations implemented. Recent benchmarks suggest verification times ranging from 2ms to 5ms for modern proofs.
Miner Extractable Value (MEV)
If sufficiently expressive smart contracts are enabled through validity rollups, it could create new opportunities for MEV on Bitcoin. While MEV would mainly be captured by rollup block producers on L2, it's an area that requires further research to understand its potential impact on L1 incentives and security.
Algorithmic Incentive Manipulation Contracts
Adding support for validity rollups on Bitcoin could enable "algorithmic incentive manipulation" (AIM) attacks. These use smart contracts to incentivize miners to attack each other or specific users, potentially disrupting the normal incentives of Nakamoto consensus.
Novel Cryptography Risks
The novelty of some cryptographic proof systems used in validity rollups introduces potential risks. While some implementations have been in production for several years, vulnerabilities have been discovered in both designs and implementations of cryptographic proof systems. This underscores the need for extensive review and testing before deployment on Bitcoin.
Compromised "Toxic Waste"
Some cryptographic proof protocols rely on a "parameter generation ceremony" to instantiate the protocol. If the random numbers generated during this ceremony (often called "toxic waste") are compromised, it could allow an attacker to produce counterfeit proofs. It's worth noting that STARK-based proof protocols do not require such a ceremony and thus do not generate toxic waste.
7. STARKs: The Bridge Between Bitcoin and Ethereum
"What is Starknet's vision? Starknet's vision is that we want to move to a world where integrity is never assumed, but rather upheld by all and is publicly verified. Which means that basically when you're doing financial interactions, when you're interacting with your bank or with your state, it's not that they make promises and you're supposed to trust them. The promises they make are baked into smart contracts or into protocols, and those protocols are actually run by others and they don't have a say on, you know, barring or censoring you or blocking you." - excerpt from Eli Ben-Sasson's presentation on The Rollup (2024).
It's like moving from a world where we have to trust referees to make the right calls, to a world where every player and spectator can instantly and accurately verify every call themselves.
As we explore the potential of STARKs to scale Bitcoin, it's crucial to understand how this development relates to Ethereum, the second-largest cryptocurrency by market capitalization and the leading platform for smart contracts and decentralized applications (dApps). The relationship between Bitcoin, Ethereum, and STARKs is complex and multifaceted, with implications that could reshape the entire blockchain ecosystem.
Unifying the Blockchain Space
One of the most exciting prospects of implementing STARKs on Bitcoin is the potential to create a unified layer that can interact with both Bitcoin and Ethereum. As Eli Ben-Sasson envisions:
"Starknet can become a single layer that settles on both Bitcoin and Ethereum... This will happen within six months after the potential Bitcoin upgrade, OP_CAT." (Ben-Sasson, 2024)
This unified layer could serve as a bridge between the two largest blockchain ecosystems, potentially resolving the long-standing divide between Bitcoin maximalists and Ethereum enthusiasts. It would allow for unprecedented interoperability, where assets and data could flow seamlessly between the two networks.
Complementary Strengths
Bitcoin and Ethereum have traditionally been seen as competitors, each with its own strengths and weaknesses. Bitcoin excels as a store of value and a secure, decentralized network, while Ethereum's strength lies in its flexibility and support for complex smart contracts. STARKs could potentially allow Bitcoin to incorporate some of Ethereum's strengths without compromising its core principles.
As Victor Kolobov notes:
"Making Starknet a Layer 2 on Bitcoin provides the best of both worlds: tremendous financial innovation backed by the security of Bitcoin serving as digital gold." (Kolobov, 2024)
This doesn't mean that Bitcoin would replace Ethereum or vice versa. Instead, it could lead to a more complementary relationship between the two, with each network focusing on its core strengths while benefiting from the capabilities of the other through the Starknet layer.
Cross-Chain Development and Innovation
The implementation of STARKs on Bitcoin could also lead to exciting new possibilities for cross-chain development and innovation. Developers who have been working primarily on Ethereum could bring their expertise to Bitcoin, and vice versa. This cross-pollination of ideas and technologies could accelerate innovation across the entire blockchain space.
For instance, the Cairo programming language, which is designed for efficient proving and verification using STARKs, could become a powerful tool for both Bitcoin and Ethereum developers. As Avihu Levi suggests:
"Cairo is a programming language specifically designed for efficient proving and verification using STARKs, making it well-suited for use in Bitcoin smart contracts. It enables the creation of more sophisticated smart contracts with increased ergonomics, functionality, and safety." (Levi, 2024)
Competition and Collaboration
While the potential for collaboration is exciting, it's important to note that the implementation of STARKs on Bitcoin could also increase competition between Bitcoin and Ethereum. If Bitcoin can support complex smart contracts and high transaction throughput, it might compete more directly with Ethereum for certain use cases.
However, this competition could be healthy for the ecosystem as a whole, driving both networks to innovate and improve. As Ben-Sasson points out:
"We firmly believe in Ethereum and are committed to its long term success. Bringing ZK-STARKs to Bitcoin would not be a deviation from our path, but rather coming full circle." (Ben-Sasson, 2024)
Challenges in Cross-Chain Integration
While the potential for integration between Bitcoin and Ethereum through STARKs is exciting, it's not without challenges. The two networks have different architectures, consensus mechanisms, and development cultures. Bridging these differences will require careful design and likely some compromises.
"This sort of trade off between not moving too fast but allowing for change and then allowing for the right kind of change that is in the benefit of the public, as opposed to being in the benefit of some corporation or some nation state. It's a problem that I don't think blockchain has solved."
It's like trying to steer a massive ship - you need to move forward, but not so fast that you lose control, and you need to make sure you're heading in a direction that benefits everyone on board, not just the captain or a few passengers.
Moreover, there might be resistance from purists in both communities who prefer to keep the networks separate. Overcoming these cultural and technical barriers will be crucial for realizing the full potential of STARKs as a unifying technology.
The Future: A More Interconnected Blockchain Ecosystem
Ultimately, the implementation of STARKs on Bitcoin and its relationship to Ethereum points towards a future where blockchain networks are more interconnected and interoperable. Instead of isolated silos, we might see a web of blockchain networks, each with its own strengths, but all able to communicate and interact through layers like Starknet.
This could lead to a more robust, flexible, and powerful blockchain ecosystem that can better serve the needs of users around the world. As we move forward, the relationship between Bitcoin, Ethereum, and STARKs will likely be a key factor in shaping the future of blockchain technology and its impact on the world.
8. Conclusion: The Road Ahead
The integration of STARKs into Bitcoin represents a potential quantum leap in the capabilities and reach of the world's first cryptocurrency. It offers a path to scale Bitcoin to meet global needs while preserving its core attributes of decentralization and security. As John Light's research demonstrates, they can potentially increase transaction throughput by orders of magnitude, enable new smart contract capabilities, and improve privacy (Light, 2023).
As we stand on the brink of this new frontier, it's clear that the work is just beginning. Implementing STARKs on Bitcoin will require not just technical innovation, but also community consensus and careful consideration of the broader implications. Implementing validity rollups on Bitcoin is not without challenges. It requires careful consideration of the technical changes needed, the potential impacts on the network, and the new risks introduced. The Bitcoin community will need to weigh these factors carefully as it considers the potential adoption of this technology.
Yet, the potential rewards are immense. As Ben-Sasson eloquently puts it:
"Crypto can clean up the digital and financial worlds. It can deliver integrity to money and rebalance power in our society, taking it away from big tech and restoring it to sovereign individuals. It's a tool to empower humans and grassroots communities. In short, it's a source of good." (Ben-Sasson, 2024)
By scaling Bitcoin with STARKs, we may be taking a significant step towards realizing this vision of a more open, accessible, and empowering financial system for all.
9. Bibliography
Ben-Sasson, E. (2024). Scaling Bitcoin for mass use: A realistic vision. StarkWare. https://starkware.co/blog/scaling-bitcoin-for-mass-use/
Kolobov, V. (2024). The path to general computation on Bitcoin. StarkWare. https://starkware.co/blog/general-computation-on-bitcoin/
Levi, A. (2024). Scaling Bitcoin Together, Brussels. Citra Conference.
Light, J. (2023). Validity Rollups on Bitcoin. https://github.com/john-light/validity-rollups/blob/main/validity_rollups_on_bitcoin.md
Poelstra, A. (2021). Covenants in Bitcoin Script. Blockstream.
Chen, W., & Yuan, P. (2024). Bitcoin Wildlife Sanctuary project. L2 Iterative Ventures.
The Rollup. (2024). The New Era of Bitcoin Powered By Starknet [Interview with Eli Ben-Sasson]. YouTube.
CryptoRank. (2024). Bitcoin Scaling Is Near: Prepare Yourself for OP_CAT (BIP-420). CryptoRank.