ICS ?: Merkle Operators

[mossid]

Merkle operators are [][]byte -> [][]byte functions, which act as generalized proofs. It is annoying to implement each of the implementation-specific Merkle proof for each of the chains, so we can reduce the existing/future implementation specific Merkle proofs into the Merkle operator format and then prove it on the other chains.

The proposed set of Merkle operators(cosmos/iavl#136):

• ConcatOp{prefix, suffix []byte}: concats prefix + input + suffix
• SHA256Op{}: sha256 hashes the input
• PrependLengthOp{}: prepend the input with its length
• ApplyOp{index []int, ops []Operator}: apply ops to the inputs parallelly

IAVLValueOp, IAVLAbsentOp, SimpleValueOp can be reduced into the first three operators with a preprocessing. IAVLRangeOp is not proven to be able to reduce yet, but I'm pretty sure it is possible with ApplyOp(key checking will be a bit tricky).

When a new chain using a new Merkle tree implementation comes into the network, they can simply register how does the new Merkle proof look like. It can be described as a simple regular expression, for example, IAVLValueOps have the format of SHA256 PrependLength Concat SHA256 (PrependLength Concat SHA256)*. So even a chain does not understand IAVLValueOp from its code, the knowledge can be provided from an external actor as a regular expression of Merkle operators, which makes the chain able to learn new proof formats on runtime.

[ebuchman]

For reference there is some documentation on this scheme in the Tendermint repo since it's been added to the ABCI.Query method:

• ADR-026
• ABCI Query Proofs

See also the

• proto file
• verification code
• Notes on key path
• SimpleValueOp

[mossid]

The proposed set of Merkle operators:

(Even the mechanism looks like a stack machine but it is not. I think it is better to make the operations can perform the operation on any position of the input values. Please consider this while reading the proposal, the term "the input" may refer to the specific argument that the operator is willing to process(the first input by default, but can be altered))

• AppendOp: prepends/appends bytestrings to the input. Defined as (prefix bytes, suffix bytes), either can be nil.
• SHA256Op: SHA256 hashes the input.
• PrependLengthOp: prepend the varint encoded length of the input to the input.
• ConcatOp: joins the inputs forming a single bytestring as its result.
• LiftKeyOp: provides key checkpoint and push the key to the values
• AssertValuesOp: checks the input values, used to abort the proving process early if invalid.

Examples:

Run = func(Op, []bytes) Maybe<[]bytes>
Run(AppendOp{Position: 0, Prefix: 0x00, Suffix: 0x0102}, [0xAB]}) = [0x00AB0102]
Run(SHA256Op{Position: 1}, [0xAB, 0xCD]) = [0xAB, 0x90EC58...]
Run(PrependLengthOp{Position: 1}, [0xAB, 0xCD]) = [0xAB, 0x01CD]
Run(ConcatOp{Positions: [2, 0]}, [0xAB, 0xCD, 0xEF]) = [0xCD, 0xEFAB]
Run(LiftKeyOp{Key: 0x0011}, [0xAB]) = [0x0011, 0xAB]
Run(AssertValuesOp{Values: [0xAB, 0xCDEF]}, [0xAB, 0xCDEF]) = [0xAB, 0xCDEF]
Run(AssertValuesOp{Values: [0xAB, 0xCDEF]}, [0x77]) = nil

TODO: check if the operators above are resistant from attacks. The attackers should not be able to generate false proof combining the operators. This is achieved if the operators are dependent on the input(append, sha256, prependlength, concat) or it is independent but checked by the verifier(liftkey).

TODO: where should we insert the result if the operator processes multiple inputs like concat?

TODO: the set of operators will be fixed and consistent across the chains, it is better to write it as a proto file?

[cwgoes]

I believe @ethanfrey intends to work on this (and more!)

[ethanfrey]

Yes, I have started a draft of a format along with js and go validation logic in https://github.com/confio/proofs I plan to work quite a bit more on that in the coming two months

[cwgoes]

I believe this is superseded by #282.