trie
trie copied to clipboard
fix: in-place nodes ignored in proof verification
Fixes #26.
Kinda relates to #7 and #9, but on the verification side only.
The current behavior of jumping to the next proof node does not work with in-place encoded child nodes, as when such nodes are encountered, it's always the last item of the proof, causing a mismatch of key and walked_path, and a verification failure.
This patch fixes the issue by checking whether the branch child is encoded in-place, and if so "recursively" walk the child (in reality this cannot be more than 1 level deep as otherwise it wouldn't be in-place to begin with).
The test case added is manually crafted, without using the hash builder for proof collection. This is because currently the issue of handling small nodes exist across the whole library, meaning the hash builder is faulty too. Unfortunately I only have time to fix the verification side, and hence the manual test case.
Technically this part is also prone to the issue:
https://github.com/alloy-rs/trie/blob/dc779547daca640d710916d5345cbe11560701d0/src/proof/verify.rs#L69-L72
as you can't just assume the extension's child is a hash. It's an easy fix by just applying the same check as in this patch, but I didn't have time to build the test case for this code path, and I don't want to submit untested code.
Sorry for pushing but would be nice if we can get this in :) Thanks!