Proof verification can be forged

[petscheit]

In the current proof verification implementation, it is never asserted, that the tree was traversed all the way down to the leaf nodes.
The tree is fully traversed, if the entire key/path has been processed, so all 251 bits. Not traversing all the way until the end of the key, allows an attacker to verify arbitrary edge nodes that are in the original path of the key.

This behaviour can be prevented, by ensuring the remaining_key parameter is 0 after all proof nodes have been processed. Otherwise it is possible to truncate the proof path, verifying an incorrect value as a result.

I have added a PoC of this behaviour here: a935126

[cchudant]

I believe this is fixed by #36, as I rewrote that entire part of the lib.
I will probably close this issue when that pr gets merged as this bug will not be relevant anymore. There may be other bugs lurking in my proof verification though - it has not been tested in depth, since we never need to verify any strorage proof in madara. It looks very correct though, it's just lacking a few tests.

[petscheit]

Hey, thanks for the response! This is great timing actually, as I have just finished my implementation of this in cairo0. I think I have a good understanding of this now. Maybe we can take a look at each others code and give some feedback? Probably doesnt hurt to have someone else look over it. Wdyt?

My implementation is here: https://github.com/HerodotusDev/hdp-cairo/blob/feat/starknet-memorizer/src/verifiers/starknet/storage_verifier.cairo#L156

Notes:

• Since its done in cairo, devision is bad. As a result, the proof is evaluated backwards. For non-inclusion proofs this forces us to do some shifting in the beginning.

[cchudant]

@petscheit
That's interesting! I don't know cairo0 though, sorry 😅
Also, the proofs I have implemented are multi-proofs. is that what you are implementing too?

[petscheit]

Ahh, I see. Well thats of the table then I guess!

I saw the multi proofs, wanted to take a look how you did that later. My implementation is compatible with pathfinder_getProof RPC call. This endpoint just gives you the raw proof for smart contract slot you request, so not super efficient for a lot of operations, but nice to verify.

For Madaras use case, the bonsai-trie proofs should eventually be verifiable on Starknet right? Is this currently the case with the Alexandria verifier?

[antiyro]

Hello hello @petscheit does Alexandria have a verifier impl? Or are you talking about the integrity verifier from Herodotus?

Our getProof endpoint will respect v0.8.0 official specs. I'm wondering what are you working on exactly??

[cchudant]

here is the link to the v0.8.0 specs starkware-libs/starknet-specs#232 if you want to look at it
it's still in flux and not standardized yet, but I believe it is intended to replace pathfinder_getProof, and we'll only implement that

[petscheit]

Hey @antiyro

alexandria has an implementation for verifying the storage proofs, but it turned out that its incomplete actually. So it can reject valid proofs as incompatible.

I am working on a cairo0 implementation of the starknet mpt verification algo. I played around with the "native" mpt verifier that is part of cairo-lang, but its quite inefficient if you just want to verify a single proof.