Define proofs for query

[ethanfrey]

• format for proofs as protobuf
• Iavl adapter converts to this format
• test proof verification

we want to use a format compatible with tendermint, and ideally cosmos-sdk, to make it easier to support ibc.

Starting from tendermint rpc... let's track down the proof format...

Rpc call returns the abciQuery object (as json)
func ABCIQuery(ctx *rpctypes.Context, path string, data cmn.HexBytes, height int64, prove bool) (*ctypes.ResultABCIQuery, error)

Abci definition

message ResponseQuery {
...
  merkle.Proof proof = 8;
  int64 height = 9;
  string codespace = 10;
}

merkle.Proof format

message ProofOp {
  string type = 1;
  bytes key = 2;
  bytes data = 3;
}

message Proof {
  repeated ProofOp ops = 1 [(gogoproto.nullable)=false];
}

Unclear is what exactly these ProofOp types are and what they mean.
Digging in deeper, we can see the iavl_value_proof defines one operation to represent the entire range proof for one value:

type IAVLValueOp struct {
	// Encoded in ProofOp.Key.
	key []byte
	// To encode in ProofOp.Data.
	Proof *RangeProof `json:"proof"`
}
...
func (op IAVLValueOp) ProofOp() merkle.ProofOp {
	bz := cdc.MustMarshalBinaryLengthPrefixed(op)
	return merkle.ProofOp{
		Type: ProofOpIAVLValue,
		Key:  op.key,
		Data: bz,
	}
}

With the actual range proof, being an iavl-specific internal structure, encoded with go-amino. I cannot see this code actually called, however.

---

In an attempt to see this in practice, I will look at the canonical abci app, cosmos-sdk.

Look at their BaseApp.Query entry point.

Which will route the query to the data store if the prefix is "/store"

func handleQueryStore(app *BaseApp, path []string, req abci.RequestQuery) (res abci.ResponseQuery) {
	// "/store" prefix for store queries
	queryable, ok := app.cms.(sdk.Queryable)
	if !ok {
		msg := "multistore doesn't support queries"
		return sdk.ErrUnknownRequest(msg).QueryResult()
	}

	req.Path = "/" + strings.Join(path[1:], "/")
	return queryable.Query(req)
}

It seems that rootmulti.Store is the default app.cms implementation, with the actual Query function

Which takes the QueryResult of a substore, and appends a special "multistore proof op":

	store := rs.getStoreByName(storeName)
	queryable, ok := store.(types.Queryable)
	res := queryable.Query(req)
        // ...
	res.Proof.Ops = append(res.Proof.Ops, NewMultiStoreProofOp(
		[]byte(storeName),
		NewMultiStoreProof(commitInfo.StoreInfos),
	).ProofOp())

And finally, we dig into the Query method of the Iavl sub-store, and see the proof formation:

	value, proof, err := tree.GetVersionedWithProof(key, res.Height)
	// ...
	if value != nil {
		// value was found
		res.Value = value
		res.Proof = &merkle.Proof{Ops: []merkle.ProofOp{iavl.NewIAVLValueOp(key, proof).ProofOp()}}
	} else {
		// value wasn't found
		res.Value = nil
		res.Proof = &merkle.Proof{Ops: []merkle.ProofOp{iavl.NewIAVLAbsenceOp(key, proof).ProofOp()}}
	}

So, basically, we just call MutableTree.GetVersionedWithProof and then serialize the returned RangeProof into a custom format.

This may work fine if both client and server are golang and importing the iavl codebase, but I see trouble with handling these not-well-defined proofs in eg. a javascript client.

---

Final conclusion from this deep-dive in cosmos code:

1. Raw proof structures are available in tendermint/iavl
2. There is a "standard format" to encode them
3. This "standard format" currently stores enormous opaque blobs that cannot be parse in another language
4. We should define a simpler RangeProof -> merkle.ProofOp[] mapping that can be defined in terms of simpler primitives (concat, sha256, etc)
5. The case of one item is collapsed into a subset of range proof. Let us define a simple-to-parse struct for the one-key-present case, then the one-key-missing case, then the larger range proof, then secondary index proofs.... Each one can be it's own issue and should be well defined to be able to validate from non-go code without access to any custom libraries

[ethanfrey]

Older links I had posted above... may be interesting, but too much noise for the description:

Some relevant links to current state in tendermint/cosmos:

• https://github.com/tendermint/tendermint/blob/master/docs/architecture/adr-026-general-merkle-proof.md
• [WIP] General Merkle Proof tendermint/tendermint#2298
• General Merkle Follow Up tendermint/tendermint#2510
• General Merkle Clarifications tendermint/tendermint#2527
• R4R: Add general merkle absence proof (also for empty substores) cosmos/cosmos-sdk#2685

I also seems that some of this is updated in tendermint 0.26, so we need to decide if we update before implementing this:

• [WIP] Update to TM v0.26.0 - Part II cosmos/cosmos-sdk#2681

Implementation in iavl:

• General Merkle Proof cosmos/iavl#105
• https://github.com/tendermint/iavl/blob/master/proof.go
• https://github.com/tendermint/iavl/blob/master/proof_range.go
• https://github.com/tendermint/iavl/blob/master/proof_path.go

We should aim for as much compatibility with cosmos-sdk/tendermint as possible in the proof format, as it would allow us to one day also implement a compatible ibc module. It seems like there is some progress recently on defining a canonical merkle proof format that we can adopt internally (or maybe get for "free" from iavl implementation).

• [WIP] General Merkle Proof tendermint/tendermint#2298 (merged)
• General Merkle Follow Up tendermint/tendermint#2509
• General Merkle Proof cosmos/iavl#105