Recursive utreexo proofs

[JoseSK999]

Utreexo nodes need an inclusion proof for every block, which I think are about 250kb each. But my understanding of this project is that we can instead use STARKs to prove that an UTXO being spent is part of the UTXO set in its compact form.

Is it possible then to have a single recursive proof that each block is spending UTXOs included in the utreexo accumulator? The zerosync project aims to verify everything, including this, but my question is if it's possible to have a proof that covers only Utreexo.

I would like to know if this can be done, and how. It makes sense to have a single proof for each block because each one spends from a unique UTXO set. The drawback is increased bandwidth costs, and storage for bridge nodes. Perhaps STARKs can help here with recursive proofs?

[lucidLuckylee]

The single recursive proof to ensure that every block only uses utxos stored in the utreexo accumulator is already in zerosync and one of course could remove the other validation parts and postpone them to the verifier (the syncing node) again. The recursive proof would have to contain a list/accumulator that contains all blocks/transactions for which the proof holds, but that is no problem.

Since a STARK has about the same size as the 250kb you mention you hardly gain anything by sending a STARK that proves that the utxos were present in the utreexo accumulator for each block.

[JoseSK999]

But if we can use a single recursive STARK proof, instead of many 250kb utreexo proofs for each block, aren't we gaining a lot? Proving inclusion for all the blockchain would be in the order of GB with utreexo, while a STARK proof doing the same thing could be less than a MB. Probably I miss something.

[lucidLuckylee]

No you are correct: My second paragraph was referring to the approach where a bridge node would peovide a STARK instead of all the Merkle proofs for a block. Sorry; I should have made that more clear.

[JoseSK999]

Okay! Reducing the bridge node storage requirement that much seems like a big deal. What I don't understand is that, if the proof only verifies against a set of utreexo states (one for each block), then the verifier will need to process all blocks, store the state for each one and then verify the STARK proof?

[lucidLuckylee]

I guess so

[cryptskii]

Have the bridge node also provide the utreexo states for each block along with the STARK proof. The verifier can store these states and use them to verify the STARK proof, without needing to process all blocks. This does increase the data provided by the bridge node but still saves a lot of storage/bandwidth over utreexo proofs for each block.

Have the STARK proof commit to a "compressed" version of the utreexo states, like a hash or accumulator of each state. The verifier would only need to store these compressed utreexo state representations to verify the STARK, without storing the full states. The STARK would need to prove the transitions between these compressed states are valid. This saves the verifier storage at the cost of a more complex STARK proof.

Use "checkpoints" where the STARK proof only goes back to the last checkpoint, and the verifier is given the full utreexo state at each checkpoint. The verifier needs to fully process blocks and build the utreexo state up to each checkpoint in order to verify the STARK segments in between, but does not need to do this for the entire chain. This balances the storage/computation needs between the bridge node and verifier.

[cryptskii]

some ideas