keep-starknet-strange / raito

Bitcoin ZK client written in Cairo.
https://raito.wtf
MIT License
48 stars 37 forks source link

[feat] Implement adding new leaves to the stump #267

Closed m-kus closed 1 month ago

m-kus commented 1 month ago

Context

The Bitcoin UTXO (unspent transaction output) set is very large (hundreds of millions) and it's not feasible to maintain it in the client, especially given that we operate in a zkVM with strict memory constaints. Instead, we only store a commitment to this set, in particular the Utreexo accumulator. Given this commitment + UTXO subset (required to validate given block) + inclusion proof it's possible to verify that particular UTXOs do belong to the set.

We aim to be compliant with the production implementation of Utreexo which is a bit different from the original version proposed in the paper https://eprint.iacr.org/2019/611.pdf.

Reference implementations include:

Task

Implement the algorithm for adding new items to the accumulator. Do this in utreexo::stump::accumulator::add. Add unit tests (use rustreexo/utreexo to generate test data).

Related code:

Implementation notes

Unlike the vanilla algorithm there are several things you need to take into account:

Some things to consider when porting code from Rust to Cairo:

baitcode commented 1 month ago

I'd love to work on the issue.