Generic Merkle Operators

[mossid]

The Merkle proof operator is a generic proof format that can be implemented on any platform easily, without depending on specific libraries or language features. When a Merkle proof is needed to be wire encoded and verified on another machine, platform dependant parts can be converted into the generic merkle format.

We are now using IAVLValueOp, IAVLAbsentOp which are wrappers on golang struct RangeProof, which cannot be easily decoded and verified on other machines(e.g. solidity).

Turns out IAVLValueOp can be decomposed into few primitive operators, and I think the other proof types(absent and range) can be too.

// For a single input, prepends lengthprefixed Key, prepends Prefix, appends Suffix. 
type HashConcatOp struct {
  Key []byte
  Prefix []byte
  Suffix []byte
}

// Apply SHA256 hash on the inputs
type HashValueOp struct{}

// Prepend their length on the inputs
type PrependLengthOp struct {}

With them, we can define IAVL existence proof as the following:

[]merkle.ProofOperator{
  // LEAFNODE
  HashValueOp{},
  PrependLengthOp{},
  HashConcatOp{Key: key, Prefix: 0 + 1 + Version, Suffix: nil},
  // INNERNODES(repeat)
  for node := range nodes {
    PrependLengthOp{},
    if len(Left) == 0
      HashConcatOp{Key: nil, Prefix: Height + Size + Version, Suffix: Right},  
    } else {
      HashConcatOp{Key: nil, Prefix: Height + Size + Version + Left, Suffix: nil}
    },
  }
}

Local test passing: mossid#1

[ethanfrey]

Yes, this is very close to what I had in mind (and what I sketched in an earlier IBC paper). Much more generic (given those golang structs are translated to protobuf).

The PrependLengthOp is not needed. As you see there is already a prefix such as or Height + Size + Version which can be processed by the client. You can just add the length there.

So, we have eg. Prefix: Height + Size + Version + Length, Key, Suffix: Right

And the HashConcatOp should be able to handle any inner node.

---

We would need another type for leaf nodes that takes Key, Value as well-defined fields (so we know what is being proven) and then performs some ops on it. I don't have that function in mind, but probably could be formed with one other generic operator in addition to HashConcatOp.

---

The main problem with this currently is that such a proof seems incompatible with the ProofOp as defined in the tendermint api.

Unless we can figure a way to map your above constructs onto that, it will be a breaking change in tendermint and the rpc api.

[mossid]

I think it is better to have PrependLengthOp, even that the length of the input value is fixed in our case(SHA256 hashed), in general case the length may vary so we cannot determine which length bytes we have to prepend at the proof generation time. I'm also in favor of splitting HashConcatOp into SHA256Op(which is the same thing with HashValueOp above) and ConcatOp, so we can add other hash functions later too(for other merkle tree types)

ProofOp.data is just a dynamically serialized operator struct which the receiver will decode with ProofOpDecoder function. The only thing we need to implement is the encoder/decoder function for each of the operator types, which does not break the current api.