Mina to Ethereum Bridge

Carlos Lira

20 Oct 2024 — 7 min read

Mina is a layer 1 (L1) blockchain that uses zero-knowledge proofs (ZKP) to maintain its size at 22 kB.

Its vibrant community and technology make it unique and developers and users from other ecosystems could benefit from their interaction with Mina. To this end, Aligned will support the technology needed for Mina to build a bridge to Ethereum.

Allow cross-chain transactions seamlessly.
Allow applications to leverage Mina's zero-knowledge capabilities and expand their capabilities across multiple chains.

In particular, the second one lets users compute and prove things off-chain and verify them on-chain in Ethereum.

While Lambda's bridge is operational, its cost is too expensive for most applications. You can check a description of the bridge and implementation here. The main challenges for a bridge between Mina and Ethereum are the following:

Verify a Mina state proof in Ethereum.
Perform consensus checks to ensure that it corresponds to the canonical chain.
Show the state of your account.

Each of these three steps offers challenges, as we will see:

Mina's proofs use Kimchi with an inner product argument (IPA), using cycle of curves formed by the Pallas and Vesta elliptic curves (better known as the Pasta curves). There are no precompiles in Ethereum for operations using the Pasta curves and verifying one of these proofs is prohibitely expensive!
Mina uses the Poseidon hash function, which is faster to prove using Kimchi-IPA than the Keccak or Blake2 hash functions. Unfortunately, there are no precompiles in Ethereum for Poseidon, making even a single call to the hash function very expensive.

We could solve these problems by generating zero-knowledge proofs that can be verified efficiently in Ethereum, such as Groth16 or Plonk-KZG, using the BN254 elliptic curve. The main drawback is that we have to perform recursive proving over different fields (because we have to move from the native fields of the Pasta curves to the native fields of BN254), which is computationally intensive. We can do much simpler using Aligned, reducing both computational effort and costs.

When we want to update the state of Mina in Ethereum, we have to check the latest proof and the consensus. We are developing a verifier that will output true if and only if:

The proof is valid.
The consensus checks pass.

This prevents sending valid proofs for previous states or not belonging to the current chain. This way, for the cost of one proof in Aligned, we check the validity of the state proof and the consensus. This avoids all the difficulties of handling the consensus separately in the bridge contract and recursive proving.

Showing account inclusion can be simplified by avoiding zero-knowledge proofs. Since an inclusion proof is already logarithmic in size, we can include a specialized verifier that checks it in Aligned.

Components of the Bridge

The architectural diagram for the bridge is given in the following figure:

Mina Polling Service

mina_bridge repo: core/mina_polling_service.rs

This module queries a Mina node (defined by the user) GraphQL DB for the latest state data (called the candidate state) and proof.

It also queries the Bridge’s smart contract for the last verified Mina state hash, called the Bridge’s tip state or just tip state (if there’s no tip state in the smart contract then it defaults to the hardcoded genesis hash instead) and queries the state corresponding to that hash to the Mina node.

Then it serializes:

both states (which are an OCaml structure encoded in base64, standard vocabulary) as bytes, representing the underlying UTF-8.
both state hashes (field element) as bytes (arkworks serialization).
the candidate state proof (an OCaml structure encoded in base64, URL vocabulary) as bytes, representing the underlying UTF-8.

This data composes what we call a Mina Proof of State.

Mina Proof of State

We understand a Mina Proof of State to be composed of:

public inputs (vector of bytes): [candidate_state_hash, candidate_state_length, candidate_state, tip_state_hash, tip_state_length, tip_state]. We include the lengths of the states in bytes because these can vary, unlike the hashes which are a fixed 32 bytes.
proof: Kimchi proof of the candidate state (specifically a Wrap proof in the context of the Pickles recursive system). We like to call it “Pickles proof” for simplicity.

This is the proof that the Mina verifier in Aligned (also called a Mina operator) expects.

Aligned Polling Service

mina_bridge repo: core/aligned_polling_service.rs

This module sends the Mina Proof of State (retrieved by the Mina Polling Service) to the Aligned batcher for verification using the Aligned SDK. The batcher executes pre-verification checks that validate the integrity of the proof and discards it if one of these checks is unsuccessful. After pre-verification, the batcher includes the Mina Proof of State in the current proof batch and then sends it to Aligned’s operators.

The Aligned Polling Service waits until the batch that includes the Mina Proof of State is verified, polling Aligned every 10 seconds (the Aligned SDK does this).

Finally, the service returns the verification data sent by Aligned after proof submission. This data is used to update the Bridge’s tip state by sending a transaction to the Bridge’s smart contract.

Smart Contract Utility

mina_bridge repo: core/smart_contract_utility.rs

This module sends a transaction to the Bridge’s smart contract that calls the “update tip” (see the Smart Contract section) function by sending the incomplete verification data retrieved by the Aligned Polling Service, aside from the Mina Proof of State public inputs. By “incomplete,” we mean we’re sending all the verification data except for the public input commitment, a keccak256 hash of the public inputs. So, by sending the public inputs to the contract, we can cheaply calculate on-chain the public input commitment for completing the verification data. We do this instead of directly sending the commitment so the contract can:

check that the tip_state_hash is indeed the tip state hash stored in the contract
retrieve the candidate_state_hash and store it if the candidate was verified on-chain.

Smart Contract

mina_bridge repo: contract/

The contract stores the Bridge’s tip state hash and exposes functions to read (getTipStateHash()) or update it (updateTipStateHash()). Generally it’s the Smart Contract Utility that will send a transaction to update the tip state hash.

The Bridge’s contract update function calls the Aligned Service Manager smart contract to check that the Mina Proof of State was verified in Aligned. The parameters that the Aligned Service Manager needs to check are the complete verification data.

If the Aligned Service Manager calls returns true, a Mina Proof of State of some candidate state (whose hash is known by the contract) was verified against the Bridge’s tip state (consensus checking). Then this candidate state is now the tip state, so its hash is stored in the contract.

Currently, the “update tip” transaction costs between 100k and 150k gas, a big part of it being the call data cost of sending both state's data in the public inputs of the Mina Proof of State. The cost could be decreased to <100k by modifying the definition of a Mina Proof of State, sending the state data as proof data instead of public inputs. This is not a priority at the project's current phase, so this change hasn’t been made yet.

Aligned’s Mina Proof of State verifier

aligned_layer repo: operator/mina/

Aligned Layer integrated a verifier in its operator code for verifying Mina Proofs of State.

Consensus checking

The verifier's first step is to execute consensus checks specific to the Ouroboros Samasika consensus mechanism that the Mina Protocol uses. The checks compare state data between the candidate state and the tip state.

Currently, the only check implemented is the one corresponding to short-range forks. The check just compares whether the candidate state’s height is greater than the tip’s. If equal, tiebreak logic is implemented. Tiebreak consists of lexicographically comparing the VRF hashes of both states and if these are equal, then comparing the consensus state hashes.

So the total logic can be summed up by:

if candidate_block_height > tip_block_height {
    return candidate;
}

// tiebreak logic
else if candidate_block_height == tip_block_height {
    // compare last VRF digests lexicographically
    if hash_last_vrf(candidate) > hash_last_vrf(tip) {
        return candidate;
    } else if hash_last_vrf(candidate) == hash_last_vrf(tip) {
        // compare consensus state hashes lexicographically
        if hash_state(candidate) > hash_state(tip) {
            return candidate;
        }
    }
}

return tip;

If the candidate wins the comparisons, then verification continues. If not, verification fails.

State hash check

We check that both the candidate and tip state hashes are correct by hashing the corresponding state data using OpenMina’s hasher. This way, we can be certain that the hashes are valid if the Mina Proof of State was verified in Aligned, which is useful for the Bridge’s smart contract to check that the tip state is indeed the state corresponding to the tip and for storing the candidate hash if its proof is valid.

Pickles verification

This is the last step of the Mina Proof of State verifier. We are leveraging OpenMina’s “block verifier” to verify the Pickles proof of the candidate state. The verifier takes the hash of the state as public input. OpenMina’s block verifier has yet to be audited.

Roadmap

Mina Proof of State verification in Mina Aligned Operator ✅
Short range fork rule check in Mina Aligned Operator ✅
- We are using the transition frontier root as initial state to perform consensus check and assuming for now that it's valid.
Mina Bridge Smart Contract ✅
Integration with Aligned Layer fork using Holešky Testnet ✅
Account inclusion verification 🚧
Consensus check and Mina Proof of State verification in Aligned Batcher
Complete consensus algorithm

Blockers

We are researching the consensus algorithm we need to implement in the Mina verifier. We are waiting for confirmation of several design decisions related to relative finalization and the rest of the consensus rules. We are in constant communication with the people involved and once we are confirmed we can start implementing the complete consensus algorithm.

Costs

The verification costs in Aligned depend on the number of proofs in a batch: the more proofs we have, the lower the costs! The worst case scenario for the bridge would be when there is only one proof to verify, since the cost is not amortized with other proofs. We should also bear in mind that the current estimation could change due to additional costs associated with the consensus. While there is still room for further improvements, the worst case scenario for the bridge has the following cost breakdown:

Batcher: 125k gas.
Aggregator/Verifier: 250k gas.
Bridge contract: 110k gas.

The total gas cost is 485k for this scenario, which is significantly lower than current solutions and avoids additional proving. The cost in USD varies on the value of ETH and gas. For an ETH value of 3000 USD and a gas cost of 15 gwei/gas, the cost would be around 20 USD.

Summary

The Mina to Ethereum bridge will allow developers and users from two vibrant ecosystems to work closer together and benefit from each other. The construction of such piece of infrastructure, operating in a fast and affordable way, is not straightforward, due to the abscence of precompiles in Ethereum and the need for expensive proof recursion. However, using Aligned, the verification of Mina's state proofs and consensus can be simplified by providing one specialized verifier that passes if and only if the consensus checks and proof verification pass. Moreover, we avoid the need of ZKP to show inclusion of an account by performing the necessary Poseidon hashing natively. This construction should lead to lower bridging costs as well as lower latency.