Implement Merkle proof verification (existence & non-existence) for Comet Cairo contract

[Farhad-Shabani]

Summary

Implement the verification of existence (verify_membership) and non-existence (verify_non_membership) Merkle proofs for the CometBFT Cairo contract. These proofs typically accompany various IBC packets sent to a counterparty chain and are validated by the light client representing the source chain.
The task involves:

• 1. Implementation of the ICS-23 vector commitment in Cairo, as a general-purpose library
• 2. And, integrating that into the CometBFT client contract

[Farhad-Shabani]

Protobuf Decoding: On-Chain vs. Off-Chain Approaches?

When we retrieve commitment proofs from Cosmos chains, they’re protobuf-encoded as a u8 array. For Cairo contracts to verify these proofs, they need to be deserialized into Cairo-specific types. To make this happen, the data has to go through several conversions. Depending on whether Protobuf decoding happens on-chain or off-chain, there are two ways to handle it. Here’s how it breaks down, with roles split between the contract and the relayer:

1. Decoding On-Chain

1. Relayer: Fetch the proof as Protobuf-encoded u8 bytes from the Cosmos chain.
2. Relayer: Pack the proof bytes into an IBC message and serialize it into a felt252 array.
3. Relayer: Submit the message.
4. Contract: Deserialize the message and pull out the proof as u8 bytes.
5. Contract: Protobuf decode the proof bytes into a Cairo type.

2. Decoding Off-Chain

1. Relayer: Fetch the proof as Protobuf-encoded u8 bytes from the Cosmos chain.
2. Relayer: Protobuf decode the proof bytes into a domain Rust structure that mirrors its Cairo type.
3. Relayer: Pack the decoded proof into an IBC message and serialize it into a felt252 array.
4. Relayer: Submit the message.
5. Contract: Deserialize the message and directly obtain the proof as a Cairo type.

Proposal

(1) is the standard approach for IBC integrations, especially in Cosmos chains. But (2) is more cost-efficient since the heavy lifting (decoding) is done off-chain. That said, (2) does add a bit of extra work for the relayer. On the flip side, it keeps the contract logic simple, which makes it easier to maintain and boosts security.