[feat] Utreexo: inclusion proof verification

[m-kus]

Context

How can we check that the outpoints we attach to the transaction inputs are legit? They are not part of the encoded transaction hence do not contribute to the merkle root. Currently all validations that use data from the outpoints are underconstrained.

The most straightforward way to address that is to maintain the so-called UTXO set:

• For every transaction output we add it to the set: if it already exists then it's an error
• For every transaction input we remove the referenced output from the set: if it does not exist then it's an error

But UTXO set can be pretty large and it is very expensive to do that in a Cairo program. Instead we can do the following:

• Keep only a succinct commitment to the set
• For every block provide only the necessary subset of UTXOs + inclusion proofs

So the workflow would look like the following:

• Prepare blocks extended with UTXOs (what we do already using our Python scripts)
• Generate inclusion proofs for every UTXO referenced in that block
• Program checks proofs, updates commitment

We will use the Utreexo accumulator to implement this scheme.

Task

In this task we are going to implement another primitive required for Utreexo integration: verifying inclusion proof for a particular UTXO.

Implementation hints

You'd need to implement UtreexoAccumulator::verify for UtreexoState.
Utreexo leaves are Poseidon hashes of outpoints.
There will likely to be some common Merkle hashing utils shared with #167

References

• https://eprint.iacr.org/2019/611.pdf
• https://github.com/ZeroSync/ZeroSync/blob/f1bd4736b0bac190ac48cbc8d5fcd92e2e1be7b9/src/utxo_set/utreexo.cairo#L90

[m-kus]

@bloomingpeach wanna give it a try?

[ShantelPeters]

@m-kus can I take this on ?

[onlydustapp[bot]]

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

[PavitraAgarwal21]

Hey @b-j-roberts want to take this up

[bloomingpeach]

yes @m-kus I'd like to work on this issue.

[onlydustapp[bot]]

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