ZK ICS23

[aeryz]

The light client on chain B verifies the membership proofs that are generated by the chain A to verify that it took an action (eg. committing a packet). This proof is basically consists of two merkle inclusion proofs. It's two instead of one because Cosmos SDK modules are using an iavl tree at the module level and use a top-level merkle tree where the keys are the identifiers of the modules (eg. ibc) and values are the iavl root hashes.

The downside of the traditional method

The downside of this approach is if you want to batch the verification of multiple packets, the light client still needs to check each of the inclusion proofs individually. This makes the verification cost grow linearly (O(n)).

The ZK solution

Overview of the method

• In order to keep the circuit small, the hashing algorithm used for both merkle and iavl trees must be a zk-friendly hashing algorithm such as MiMC. This modification is not straighforward though since these algorithms expect the data to be in size of 32k where k is arbitrary integer. The downsides will be discussed later on.
• The projected circuit size will be around 500-800k constrains which will give us enough room to batch 10-15 proofs. This circuit will be merged into galois and this will result in voyager updating the client per 10-15 packets only once.

Downsides

1. ZK-friendly hashes are slow: Unfortunately, MiMC is way slower (~100x) than SHA256. There are more performant algorithms out there such as Poseidon and Poseidon2 but they still are around ~30x slower and they still need the input size to be a multiple of 32.
2. ZK-friendly hashes require data to be padded: In IAVL tree a prefix is stored with each data as a metadata which is encoded with proto varint. This encoding is variable and it's size is basically as small as possible (in terms of bit size). But the padding will require at least 16-32 bytes more per data saved.
3. Single packet relaying will be costly: Since union will use a zk-friendly hashing algorithm which is not practical for using in the EVM, we won't be able to run a non-zk verifier in EVM. We will need to deploy a separate single verification circuit which will make it costly to verify for a single packet.
4. Need to maintain two separate forks: We have to apply the changes to cosmos/iavl and cosmos-sdk/x/store and maintain them afterwards.

Advantages

1. Reduced cost per packet: This needs to be benchmarked but the cost of verifying(hence relaying) a single packet can be significantly reduced.

More ideas to make this better

1. Using a separate iavl tree for IBC: Currently there is only single iavl tree used for all modules. We could modify the sdk to use a separate one for ibc. This would mean that no other module will pay for zk-friendly hashing. During the verification we will need to do a merkle+iavl verification (no-zk) to verify the ibc root, and then verify the circuit execution once for verifying multiple packet commitments.

Related work

1. unionlabs/iavl modifications
2. unionlabs/cosmos-sdk modifications
3. unionlabs/union PoC branch including the ics23 circuit