Bitcoin ZK client written in Cairo.
Raito is a Bitcoin consensus client written in Cairo: it implements the same block validation logic as Bitcoin Core but in a provable language. What that means is after you run block validation you can present the result (e.g. chain state) and a succinct proof of execution correctness. The key is that the other party is no longer required to re-run the validation to ensure the chain state is correct, it is enough to just verify the proof.
Raito is heavily inspired by ZeroSync project.
Disclaimer: This project is in the early stages of development and should not be used in production. It will evolve rapidly, expect breaking changes.
At its core, consensus client accepts two inputs: a batch of consecutive blocks n to m and a STARK proof of the state of the chain up to block n−1. It ensures that the historical chain state is valid by verifying the STARK proof. Then, it produces a new chain state by applying the new blocks on top of the historical state. As a result, a proof of the new state is generated.
Raito essentially "compresses" the block validation and hence its primary application is enabling quick node synchronization (aka initial block download — IBD). Currently if you are bootstrapping a new full node from scratch there are two options:
- Fetch all the block headers and transaction from P2P and then apply them one by one, computing the state and accumulating the UTXO set (There is an optimization
assumevalidthat helps to speed up the process); - Download and import a snapshot of the chain state from some trusted source, run the usual sync in the background (see
assumeutxo).
First option takes a lot of time but it is trustless, while the second one is faster (importing snapshot and catching up with the head still takes time) but at the cost of extra trust assumption that assumeutxo hash is checked for correctness during code review (every time it changes!).
With STARKs we can enjoy both fast and trust-minimized synchronization:
- You still have to trust that Raito (Bitcoin client), Cairo (compiler toolchain), Stwo (prover toolchain), and STARKs are sound and flawless, i.e. that enough qualified specialists verified the code and math (and issued audit reports!);
- However these are "reusable" trust assumptions: you can produce proof for every new Bitcoin block without a need to review anything (unlike assumeutxo approach); this allows to minimize the gap between the head and the snapshot and that way speed up the IBD.
Non-interactive witness aggregation (also known as transaction compression) is a method for more efficient block size utilization. It becomes especially important in the context of migrating to post-quantum signing schemes, which typically involve large public keys and signatures. However, even with the current set of cryptographic primitives, witness aggregation can help address the issue of payment transactions competing with complex contracts and meta-protocols.
How it works: Miners execute blocks and produce a proof of correct execution. Once this proof is available, all transaction witnesses (that include signatures, Taproot scripts, etc) can be discarded, freeing up block space for additional transactions. This approach effectively increases the "effective" block size (i.e., the maximum amount of computation) without increasing bandwidth or storage requirements. It also helps mitigate the impact of large, complex transactions (rollup state settlements, refutations, or inscriptions) that might otherwise postpone the ordinary payment transactions.
Raito can be extended with additional validation logic and custom state tree for protocols like Runes and be used for bootstrapping meta indexers, similarly to how it is used for bootstrapping Bitcoin full nodes.
A trust-minimized bridge design requires "embedding" a Bitcoin client into the target chain for validating the block headers and verifying transaction inclusion proofs. It is typically a "light" version of the client that is efficient onchain but makes more trust assumptions.
Raito provides building blocks for creating light clients with different tradeoffs. However the job of determining the canonical chain remains outside of Raito's scope and should be implemented separately.
See UTU relay for an example how Raito primitives can be utilized to build a one-way bridge.
Since Raito compresses block validation and execution it can be leveraged to build Bitcoin scaling solutions aka L2s: aggregate multiple transactions, execute, generate a proof, settle on Bitcoin. It is basically a validity rollup or validium if you choose to post data not on Bitcoin but elsewhere. Same would also work for meta protocols effectively turning them from sovereign to validity rollups.
Such design is much more scalable and secure compared to sidechains and free of some of the limitations of Lightning. The settlement part however remains unsolved and we yet to see proof verification happening in Bitcoin mainnet.
Some interesting read on this problem:
- https://hackmd.io/@polyhedra/bitcoin
- https://l2ivresearch.substack.com/p/recent-progress-on-bitcoin-stark
Consider a problem of proving that you can spend a set of outputs O (that are not yet spent as of block B) with total amount >X without revealing which particular UTXOs these are. This requires several primitives:
- Utreexo accumulator: a hash commitment scheme tailored for UTXO set, allows to produce succinct inclusion proofs given the current roots
- Utreexo enabled ZK client: a provable Bitcoin consensus client which also maintains the UTXO set and updates Utreexo accumulator
Given these primitives we can prove the following statements:
- If you start with genesis and sequentially execute
Bblocks you'd end up with a certain state of Utreexo accumulatorR - A set of outputs
Obelongs to the UTXO set at that point - The total amount of outputs
Ois greater thanX - You are able to produce a valid witness to spend all the outputs
O
Aggregating all above would give us a proof of assets, which can be part of a more complex protocol such as proof of reserves (aka proof of solvency).
Proof of reserves protocol allows to show that the reserves a crypto exchange hold are actually held and that their clients’ funds are “safe“.
See also:
Implement a reduced light client that can verify a range of blocks starting at genesis.
It does not have to validate execution, just check that the block header fields follow the protocol.
Tasks:
- block hash computation
- proof-of-work validation/computation
- block time validation/computation
- block difficulty adjustment
- script for fetching arbitrary block data
- script for preparing program arguments
- script for running the program e2e for multiple blocks
Extend light client with partial transaction validation, but without UTXO checks.
Tasks:
- reassess validation check list (analyze Bitcoin core codebase)
- generate & run integration tests e2e instead of Cairo codegen
- transaction ID calculation
- transaction root computation
- validate transaction fee
- validate coinbase transaction
- validate that transaction can be mined (locktime, sequence, coinbase maturity)
- validate segwit specific data (wtxid commitment)
- validate block weight
- script that fetches blocks extended with references UTXOs
- script that runs the program e2e for a span of blocks
Try to run script validation with external Cairo crate.
Tasks:
- Integrate Shinigami-script
Add inclusion proofs for the UTXOs included in the block.
Tasks:
- isolate unspendable outputs (OP_RETURN, etc)
- implement cache for UTXOs spent in the same block they are created (*)
- implement transaction outpoint hashing
- implement Utreexo accumulator (addition)
- Utreexo backend that maintains utxo set and Utreexo roots
- implement Utreexo single inclusion proof verification
- implement Utreexo single output removal
- implement Utreexo bridge node that generates individual inclusion proofs
- implement script that runs the program e2e for a span of blocks
- implement Utreexo accumulator version compatible with rustreexo
Validate full block execution over large number of blocks, including the Bitcoin scripts checks and Utreexo proofs.
- consensus logic
- consensus logic + utreexo proofs
- consensus logic + utreexo proofs + scripts
Recursively verify STARK proofs of chain state updates. Still largely tbd. From initial observations it is clear that a series of optimizations will be necessary.
- sha256 optimization
- don't use ByteArray when serializing data
- blocklevel recursion
- consider using garaga msm to batch signature verifications
- identify other Cairo code botlenecks
This will compile all the packages:
scarb buildThis will run tests for all the packages:
scarb testInstall necessary packages required by Python scripts:
pip install -r scripts/data/requirements.txt- Data processing notes
- Utreexo implementation notes
- Resource usage (without sha2 steps!)
- ZeroSync
- Bitcoin VM in Cairo
- STWO
- Cairo
- Circle STARK paper
Raito is a reference to Light Yagami (夜神月, Yagami Raito) from the manga/anime Death Note.
- Raito in Japanese means "Light", which in turns can refer to Lightning ⚡ (and hence both a reference to speed of verification of the Bitcoin blockchain using a ZKP and a reference to the Lightning Network)
- Raito can work in tandem with Shinigami that enables verification of Bitcoin Script programs. Raito = Consensus and Raito = Execution. Since Shinigami was named after Ryuk (Shinigami in Death Note), Raito was named after Light (Raito in Death Note).
- What Raito writes in the Death Note always happen, so you can see it as a source of truth, similarly to how you use a Zero-Knowledge Proof to verify the integrity of a computation.
Thanks goes to these wonderful people (emoji key):
This project follows the all-contributors specification. Contributions of any kind welcome!