Bitcoin ZK client written in Cairo.

Overview

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.

Applications

Bootstrapping full nodes

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 assumevalid that 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[https://bitcoinops.org/en/topics/assumeutxo/]).

First option takes a lot of time but it is trustless, while the second one is super fast but at the cost of extra trust assumption. With STARKs we can enjoy both fast and trust-minimized synchronization!

Indexer for meta protocols

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.

Light clients

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.

L2 solutions

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

Roadmap

Milestone 1 - Block header validation

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

Milestone 2 - Partial transaction validation

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

Milestone 3 - Bitcoin script validation

Try to run script validation with external Cairo crate.

Tasks:

• Integrate Shinigami-script

Milestone 4 - UTXO set verification

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

Milestone 5 - Full consensus validation

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

Milestone 6 - Proving

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

Contact

• Telegram
• OnlyDust

Usage

This will compile all the packages:

scarb build

This will run tests for all the packages:

scarb test

Build dependencies

Install necessary packages required by Python scripts:

pip install -r scripts/data/requirements.txt

References

• Data processing notes
• Utreexo implementation notes
• ZeroSync
• Bitcoin VM in Cairo
• STWO
• Cairo
• Circle STARK paper

Contributors ✨

Thanks goes to these wonderful people (emoji key):

A₿del ∞/21M 🐺 - 🐱 💻	Maciej Kamiński @ StarkWare 💻	Brandon R 💻	Tristan 💻	Jean-Michel 💻	lomasson 💻	Michael Zaikin 💻
Harsh Pratap Singh 💻	Xavek 💻	Olufemi Olumaiyegun 💻	MSG 💻	Mubarak Muhammad Aminu 💻	oluwapeski 💻	Steven 💻
Yusuf Habib 💻	Gerson 💻	PavitraAgarwal21 💻	Nguyen Dao 💻	Hunter001 💻	feltroid Prime 💻	Mexes 💻
BlockyJ 💻	Maksim Strebkov 💻	Herbie Wildwood 💻	Fishon Amos 💻	Wolf 💻	Ilia Batii 💻	Thomas Marchand 💻

This project follows the all-contributors specification. Contributions of any kind welcome!