Skip to content

mubarak23/raito

 
 

Repository files navigation

raito-logo

Bitcoin ZK client written in Cairo.

GitHub Workflow Status Bitcoin Cairo Exploration Team

Overview

Shinigami is a zero-knowledge Bitcoin client implemented in Cairo. It aims to provide trustless validation of the Bitcoin blockchain through STARK proof verification. It 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.

flowchart TB
Pnm1(STARK proof of the chain state up to the block <i>n - 1</i>, including utxo accumulator) --> Vp(zk verifier)
Bn(blocks <i>n..m</i>) ----> Vb

subgraph Cairo
    Vp{{STARK verifier}}-->ChS(verified chain state)
    ChS --> Vb{{validate block<br>against the chain state}}
    Vb --> ChS
end

Vb --> Pn(STARK proof of the chain state up to the block <i>m</i>,<br> including utxo accumulator)

style Bn fill:pink
style Pn fill:lightgreen
style Pnm1 fill:lightgreen
style ChS fill:greenyellow
style Vp fill:gold
style Vb fill:gold
Loading

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

Although this is a highly experimental project without immediate plans for deployment, there are many potential applications:

  • light clients
  • IBD speedup
  • non custodial bridges
  • layer 2s

Roadmap

components

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

Milestone 5 - Full consensus validation

Validate full block execution, including the Bitcoin scripts checks and Utreexo.

Milestone 6 - Optimizations

  • identify Cairo code botlenecks
  • consider using garaga msm to batch signature verifications

Milestone 7 - Proving the validation

Recursively verify STARK proofs of chain state updates. Still largely tbd.

  • use garaga to implement signature verifications

Contact

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

Contributors ✨

Thanks goes to these wonderful people (emoji key):

A₿del ∞/21M 🐺 - 🐱
A₿del ∞/21M 🐺 - 🐱

💻
Maciej Kamiński @ StarkWare
Maciej Kamiński @ StarkWare

💻
Brandon R
Brandon R

💻
Tristan
Tristan

💻
Jean-Michel
Jean-Michel

💻
lomasson
lomasson

💻
Michael Zaikin
Michael Zaikin

💻
Harsh Pratap Singh
Harsh Pratap Singh

💻
Xavek
Xavek

💻
Olufemi Olumaiyegun
Olufemi Olumaiyegun

💻
MSG
MSG

💻
Mubarak Muhammad Aminu
Mubarak Muhammad Aminu

💻
oluwapeski
oluwapeski

💻
Steven
Steven

💻
Yusuf Habib
Yusuf Habib

💻
Gerson
Gerson

💻
PavitraAgarwal21
PavitraAgarwal21

💻
bloomingpeach
Nguyen Dao

💻
od-hunter
Hunter001

💻
feltroidprime
feltroid Prime

💻
mexes20
Mexes

💻
BlockyJ
BlockyJ

💻
Maksim Strebkov
Maksim Strebkov

💻
Herbie Wildwood
Herbie Wildwood

💻

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

About

Bitcoin ZK client written in Cairo.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Cairo 82.3%
  • Python 13.9%
  • Shell 1.9%
  • TypeScript 1.5%
  • Other 0.4%