Balanced binary Merkle tree proof merging panics on arbitrary hash sizes #5220
Comments
|
There are additional places in the merged proof code where a panic can occur. These should be addressed as well. |
stringhandler
pushed a commit
that referenced
this issue
Mar 7, 2023
Description --- Removes panics from [merged balanced binary Merkle tree](#5193) proofs. Changes proof format to avoid a hash output size assumption. Minor renaming and typo fixes for clarity. Closes [issue 5220](#5220). Motivation and Context --- Recent work implements merged balanced binary Merkle tree proofs. However, the verifier depended on a specific hash output length (32 bytes) to differentiate node hashes from proof indexes. This would lead to a panic if this size restriction was not met; it was not enforced because of how hashers are used in the design. Separately, proof semantics were not checked by the verifier, which could lead to other panics. This PR addresses both of these points. Instead of relying on hash output size, merged path data now includes a flag to indicate if each step references a proof index or a node hash. The verifier now returns a `Result`, producing an error if the proof semantics are incorrect. If they are correct, its return value can be unwrapped as a `bool` to assert the verification passes. It also fixes a few typos and does some minor renaming for clarity. Note that the design still retains an original assumption of a universal `usize` that may be problematic. Non-merged proofs contain a `usize` index to the node in question, and merged proofs additionally contain `usize` vectors to indicate path lengths and proof indexes. This may lead to unexpected and inconsistent behavior, and should be carefully examined separately. How Has This Been Tested? --- Existing unit tests pass.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Recent work implements merged balanced binary Merkle proofs. The proof format relies in part on the size of vector elements to reconstruct paths used in such a proof. Elements are assumed to be either an index or a hash output; indexes are used for hash output lookups.
However, the size of hash outputs is assumed to be exactly 32 bytes, which is not guaranteed to be the case. The caller is allowed to supply a hash function of its choice for use in computing non-leaf node hashes, and which may not produce 32-byte output. Further, the caller is assumed to hash leaf nodes itself and pass them to the library, and no checks are performed on the lengths of these values. If there is a mismatch, the verifier panics.
The library should account for the possibility of such a mismatch, either by allowing hash functions that don't have 32-byte outputs, or by restricting values to exactly 32 bytes during proof creation and verification.
Separately, the library probably shouldn't panic on a size mismatch, since the caller would need to check this. It should return a proof error or a failed verification.
The text was updated successfully, but these errors were encountered: