[feat] Add script that extends program arguments with Utreexo state and inclusion proofs

[m-kus]

Context

Currently we have several scripts for preparing program arguments:

• generate_data.py produces JSON files containing chain states (initial + expected result) and blocks with all transactions and referenced UTXOs;
• format_args.py takes JSON file produced by the previous script and encodes in accordance with the Cairo Serde rules.

Currently UTXOs are not constrained, so we want to leverage Utreexo accumulator to fix that.
It would require a fully-fledged backend that handles the large Utreexo forest containing millions of nodes.
But until then we still want to test the integration at least on a small subset of blocks.

Task

Create a new script that:

• imports utreexo.py as a dependency
• accepts path to the JSON file (produced by generate_data.py) as an argument
• accepts path to the output file as another argument
• accepts
• begins with an empty Utreexo state
• processes all blocks and outputs a new file that contains data from the source + Utreexo specific

For every block in the source file the script has to:

• remove all spent TXOs from the accumulator
• add all new UTXOs to the accumulator
• note that TXOs spent within the block are skipped

The output would look like:

{
  "state": {
     "chain_state": {},
     "utreexo_state": {},
  },
  "updates": [{
     "block": {},
     "utreexo_proofs": [{}]
  }],
  "expected": {
    "chain_state": {},
    "utreexo_state": {},
  }
}

Implementation hints

Since Utreexo accumulator operates on hashes (leaves) you'll have to reimplement Outpoint hashing. Some hints:

• derive hash impl https://github.com/starkware-libs/cairo/blob/883047edb4d1623302f8bb5d50fcd4b2e4566828/crates/cairo-lang-plugins/src/plugins/derive/hash.rs
• hash impl for felt based types https://github.com/starkware-libs/cairo/blob/883047edb4d1623302f8bb5d50fcd4b2e4566828/corelib/src/hash.cairo#L62

Materials

• community call https://www.youtube.com/watch?v=jq6cx6LowkA
• Utreexo paper https://eprint.iacr.org/2019/611.pdf

[Jeanmichel7]

Interested

[onlydustapp[bot]]

Hey @Jeanmichel7! Thanks for showing interest. We've created an application for you to contribute to Raito - Bitcoin ZK Client. Go check it out on OnlyDust!