search

hyperlane-xyz / hyperlane-monorepo

The home for Hyperlane core contracts, sdk packages, and other infrastructure
https://hyperlane.xyz
Other
338 stars 373 forks source link

Hyperlane Messages should be batch-verifiable with zk proofs #4548

Open nambrot opened 2 months ago

nambrot commented 2 months ago

Context

Hyperlane messages are currently verified individually, typically by verifying validator signatures on a specific message hash (message ID).

The validator signature also includes the root of a merkle tree on the origin chain that commits to all outbound messages. An alternative verification procedure could be

  1. verify quorum of signatures on merkle root at height J
  2. verify merkle proof (range proof?) of messages I...J where I < J

Without ZK, this would be more gas efficient at some sufficiently large batch size where the calldata costs of providing merkle proofs are offset by the savings from eliminating signature verification. Especially on L2s, where calldata costs are more expensive than on the L1, this is prohibitive.

With ZK, these merkle proofs (and/or signature verification) would have a ~constant gas cost that does not vary with the size of batch.

Options

This bounty suggests the usage of zkVMs like Succincts SP1 or RiscZero. There are 2 approaches to this:

  1. attempt to reuse the existing contract ISM implementations and a zkEVM proof of batch verification
  2. create a new offchain ISM program for batch verification

It probably requires figuring out the following problems:

  1. How to express signature verification and merkle proof inclusion inside the zkVMs 1.1. (you likely have to create a new ISM for this unless you modify the merkleTreeISM to allow writing the root into storage and only batch the merkle proving)
  2. How to support the metadata passing for each individual message in the Mailbox.process function 2.1 (maybe have to have this new ISM use transient storage)
  3. (Optional, but very nice to have) How to modify the relayer to fetch the proof

Leave any questions, it would be very cool to see Hyperlane's batching (currently with Multicall3) to enjoy even greater effectiveness!

Relevant links:

armanthepythonguy commented 1 month ago

@nambrot @yorhodes I would like to work on this bounty. I have been working with zkVMs for some time now and have good knowledge of the working. Also, I have worked on Hyperlane infrastructure previously so it would be easy for me to integrate both the tech.

armanthepythonguy commented 1 month ago

Also, I would like to extend a bit more on the ZK side of things, ZKVMs are great to start with but it would make sense if we could bench Plonky2 and Plonky3's performance for the required merkle tree circuits because it will much more optimized.

nambrot commented 1 month ago

Go for it @armanthepythonguy, would be very cool to see!

armanthepythonguy commented 1 month ago

hyperlane-zk @nambrot here's a basic workflow on what I am implementing. This is just the very first iteration to develop a small POC. Later as suggested I will be working on making the infra solid by attaching relayer as well. Lmk what you think

nambrot commented 1 month ago

I would not modify the hyperlane validator to call the prover. Figuring out what off-chain services/data has to be retrieved is the responsability of the relayer

armanthepythonguy commented 1 month ago

I would not modify the hyperlane validator to call the prover. Figuring out what off-chain services/data has to be retrieved is the responsability of the relayer

Okkk got it ser šŸ«”