search

turbofish-org / merk

High-performance Merkle key/value store
Apache License 2.0
226 stars 36 forks source link

Seemingly incorrect proof #10

Closed ethanfrey closed 5 years ago

ethanfrey commented 5 years ago

I stored a bunch of data and when querying on one key, get results for a different key back.

Please see https://github.com/confio/proofs-merk#issues-found

Code to reproduce https://github.com/confio/proofs-merk/blob/master/index.js#L45-L82

Am I mis-using the merkle tree?

mappum commented 5 years ago

Your queried key should be relative to the root object, so it should be ibc.chain_a.out.0 rather than state.ibc.chain_a.out.0. (To query the root object, you would use an empty string or no key at all).

You might note that the proof contains more data than you asked for. The reason it's a range proof with multiple keys is to prove that there was no omitted data about child objects (otherwise an attacker might send you valid proof for a, but leave out the nodes that describe a.b, giving you an incorrect value of a). I'm not sure how these semantics translate for IBC or general merkle proofs.

And also, you're actually getting back the value for ibc.chain_a.out rather than ibc.chain_a.out.0 since we don't merklize every key but only at the object level.

mappum commented 5 years ago

BTW, seems like it would have been nice if merk had thrown an error when you queried for the missing key, but really it was giving you a proof to prove that the state key did not exist, so a client verifying the proof would have errored here.

ethanfrey commented 5 years ago

:man_facepalming:

Thanks for the quick response. I updated the query and it does work as expected.