Bridging via AggLayer

[bobbinth]

In this post I'll describe the basics of how bridging via the AggLayer could work for Miden.

Unified bridge

Bridging on AggLayer works via the Unified Bridge (previously the LxLy bridge). The link has quite a bit of content, but the important concepts are:

Each L2 maintains a Local exit tree (LET) and the root of this tree is abbreviated as LER. LET is an append-only data structure represented by a Merkle tree. When we want to bridge something out of an L2, we need to append a node to the LET of that L2. The node we append needs to contain information about which asset we are bridging and where we bridging it to (destination network and address). There are several formats for doing so, the simplest of which is the BridgeAssetMessage format which looks like so:

pub struct BridgeAssetMessage {
    destination_network: u32,
    destination_address: Address, // 20 bytes
    amount: u256,
    token: Address, // unique identifier of the asset
}

On the L1, there is a global exit tree (GET) and the root of this tree is abbreviated as GER. GET is a tree of trees. Leaves in this tree are LERs of all networks connected to the AggLayer. Besides the LERs, GET also contains a commitment to the mainnet exit tree (MET and MER respectively). This tree works like LETs, but it tracks exits from the L1 to L2s.

Once a node has been appended to a LET, claiming of bridged assets can be done by proving the existence of the node against the GER on the L1. Similarly, to move funds from L1 to L2, a node fist needs to be appended to MET, and then its inclusion needs to be proven on the L2 against GER (which L2s also maintain).

How could it work on Miden

To make this structure work on Miden, we'll need a few new contracts and a few new note types. To explain how it will work, we'll go through two flows - bridging from Miden to L1 and then from L1 to Miden.

Bridging from Miden to AggLayer

The high-level diagram of how to bridge assets from Miden to Agglayer looks like this:

First, we'll need a bridge account (i.e., something like AggLayerBridge account component). This account will need to keep track of the LET and the faucet registry. Since LET is an append-only data structure, we actually only need to keep track of the "frontier" of the tree - i.e., a set of nodes needed to append the next node. This is helpful because LET uses Keccak as a hash function and so it would have been very difficult for us to represent it using our SMTs. But because it is append-only, we only need to keep track of 32 nodes. Each of these nodes is 32 bytes and so, we'll need 2 word per node, or 64 words total. This can easily fit into simple storage slots.

The faucet registry will maintain a list of faucets connected to the bridge. These could be stored in a storage map (or maybe storage array). Each connected faucet would need to satisfy a well-defined interface. For this we'll probably need to create something like AggLayerFungibleFaucet account component.

The exact interfaces of AggLayerBridge and AggLayerFungibleFaucet are TBD, but:

• AggLayerBridge would expose something like bridge_asset procedure. This procedure will take ASSET, destinations_network, and destination_address as parameters.
• AggLayerFungibleFaucet would expose something like convert_asset procedure. This procedure will take ASSET as a parameter and would return 256-bit amount and 20 byte token identifier for the asset. How exactly it'll do this is TBD.

The overall flow for bridging out is then:

1. The user creates a Bridge-to-AggLayer (B2AGG) note and sends it to the bridge account.
2. The bridge account verifies that the faucet for the asset in the note is in the faucet registry. It then,
   a. Makes an FPI call to the faucet to call its convert_asset procedure and get the amount/token address.
   b. Crates a BridgeAssetMessage and appends it to LET it maintains.
   c. Sends a burn note with the original asset to the faucet account.
3. The faucet will consume the note and burn the contained asset.

The transaction in step 1 would be a local transaction (i.e., executed by the user), but transactions in steps 2 and 3 would be network transactions. Although, transaction in step 3 could also be done locally - depending on how the faucet is defined. This also implies that the bridge account would need to be a network account, and the faucet account could be a network account or just public account.

Once the LET in the bridge account is updated, it will be propagated to the L1 and included into the L1s GET. We'll treat this process a black box for now. Once L1s GET is updated, the user will be able to claim their funds on the L1.

Bridging from AggLayer to Miden

The digram for bridging from AggLayer to Miden is a bit more complicated and looks like this:

Here we have 2 off-chain components that would do the following:

• AggOracle is responsible for updating GER maintained by the bridge with the latest value. The exact mechanics of how we store GERs in the bridge and how the are updated are TBD - but here are some options:
  • We could store all GERs from L1 in a storage map (or better in a storage array). This means that the storage of the bridge contract will continuously grow. Depending on how frequently new GERs are generated, this may or may not be a problem.
  • To update the bridge, the AggOracle could send a note or could execute a direct transaction. Each of these has their own tradeoffs which we'd need to evaluate separately. Moreover, how the bridge account authenticates updates from AggOracle is also TBD.
• Claim manager is responsible for sending claim notes to the faucet. These notes will contain the proof against one of the GERs proving that the user has bridge an asset to Miden.
  • Claim manager would be a "convenience component" as the user would also be able to send the claim messages to the faucet - though, this would require the user to know the proof (which would require following the L1) and be proactive.

The high-level flow is then like this:

1. The AggOracle updates the bridge with the latest GERs.
2. The claim manager sends claim notes to all relevant faucets.
3. The faucet makes an FPI call to the bridge to verify the proof contained in the claim note. The proof will need to contain at least 32 nodes, and since each node is 32 bytes, we'll need to include at least 256 elements in the note's inputs. This is currently higher than our MAX_INPUTS_PER_NOTE (which is 128) - so, we'll probably need to bump this up.
   a. As a part of this FPI call, the bridge verifies that the request is coming from a registered faucet. This will ensure that random faucets can't interact with the bridge.
   b. If the proof verifies, the faucet would issue our regular P2ID note with the newly minted asset. This P2ID note would need to be generated deterministically - i.e., if someone tries to claim it again the exact same note will be generated again. This will naturally prevent ability to "double-claim" the bridged asset (because all such duplicate notes would have the same nullifier and thus, only one of such notes could be consumed).
4. The user will consume the P2ID note to get the asset.

The transaction ins step 3 would need to be a network transaction. Transactions in steps 2 and 4 would be local transactions, and the type of transaction for step 1 is TBD.

New contracts

To summarize new contracts we'll need to support all of the above functionality:

• AggLayerBridge - maintains LET and GERs to facilitate bridging. Also, has a registry of all registered faucets.
• AggLayerFungibleFaucet - maintains information about how to convert Miden assets into AggLayer assets, and provides functionality for claiming bridged assets.
• B2AGG (Bridge-to-AggLayer) note which is sent to the AggLayerBridge account when the user wants to bridge assets out of Miden.
• BURN note which can be sent to a faucet to burn the assets contained in this note (the faucet must be the issuer of the assets).
• AGGCLAIM note which is sent the the claim manager (or the user) to an AggLayerFungibleFaucet account to claim the funds sent into Miden.

Open questions:

1. How are AggLayer's asset IDs computed?
2. How would the bridge account maintain a list of GERs?
3. How would the AggOracle update the bridge account with new GERs?
4. Probably many more...

[Mirko-von-Leipzig]

b. If the proof verifies, the faucet would issue our regular P2ID note with the newly minted asset. This P2ID note would need to be generated deterministically - i.e., if someone tries to claim it again the exact same note will be generated again. This will naturally prevent ability to "double-claim" the bridged asset (because all such duplicate notes would have the same nullifier and thus, only one of such notes could be consumed).

Do we actually allow duplicate note creation? Are these not rejected outright - and is this safe across epochs? As in, what happens if I create a new note with a duplicate nullifier where the original was created several epochs ago. Can the user not construct a new valid nullifier proof without including the original now? Or do nullifier proofs always include non-membership proofs for all prior epochs?

[bobbinth]

We don't - the question is how do we prevent it.

[PhilippGackstatter]

I guess a naive solution is to let each faucet have a storage map hash(ger_proof) -> is_claimed where hash(ger_proof) is the sequential hash over the proof against the GER claiming that the asset is in it and the bool flag checks that it can only be claimed once. But this would be infinitely growing storage.

So using the nullifier tree may be the most efficient option for this.

[Mirko-von-Leipzig]

Would it be possible to verify the nullifier tree within the account? Essentially we replicate our current tx_inputs/block_inputs approach.

The account stores the recent history in a map as @PhilippGackstatter suggests, but we restrict it to N blocks. Claim must also supply the nullifier exclusion proof for history older than this. The account then checks recent history and the nullifier proof before emitting it. Claim is valid if N and the nullifier proof overlap.

[bobbinth]

This could work. Another option is to make the token supply of bridge faucet unlimited (since the limiting factor is located on another chain). This would require modifying how the faucets work a bit. Specifically, token issuance slot would no longer be managed by the kernel, but would be managed by the faucet code (this may be a desirable refactoring anyways).

[PhilippGackstatter]

Would it be possible to verify the nullifier tree within the account?

I considered that as well but thought it would be too complicated due to the epoch-based nullifier management. But I guess we could write this nullifier check in a library and then use it from both the block kernel and the bridge faucet eventually, which would make it fairly easy I guess.

I think if we can prevent it as early as possible, that is preferable, because minting unlimited amounts of a token may have undesirable side effects and seems like it could break an invariant somewhere in an external tool.

Specifically, token issuance slot would no longer be managed by the kernel, but would be managed by the faucet code (this may be a desirable refactoring anyways).

Agreed, that would be nice to do anyway :)

[PhilippGackstatter]

Looks good! I think this makes sense. Small questions/comments:

Each of these nodes is 32 bytes and so, we'll need 2 word per node, or 64 words total.

Just to double-check, to store 32 bytes we need 5 field elements, not necessarily two words, right? So we may be able to optimize this a bit more into 32 * 5 / 4 = 40 words? Not sure if it's easier to work with but it may reduce the cycle count of each transaction a bit - though not important to discuss now.

The bridge account verifies that the faucet for the asset in the note is in the faucet registry. It then,
a. Makes an FPI call to the faucet to call its convert_asset procedure and get the amount/token address.
b. Crates a BridgeAssetMessage and appends it to LET it maintains.
c. Sends a burn note with the original asset to the faucet account.

It would be nice if convert_asset could take care of c), i.e. create the note with the asset to burn. That would just be nice to encapsulate that converting an asset is only possible when a burn note is also created.

[bobbinth]

Just to double-check, to store 32 bytes we need 5 field elements, not necessarily two words, right? So we may be able to optimize this a bit more into 32 * 5 / 4 = 40 words? Not sure if it's easier to work with but it may reduce the cycle count of each transaction a bit - though not important to discuss now.

Yes, we could make them more compact. I was just thinking that for simplicity we'd use 32 bits per element.

It would be nice if convert_asset could take care of c), i.e. create the note with the asset to burn. That would just be nice to encapsulate that converting an asset is only possible when a burn note is also created.

We won't be able to do it in an FPI call then (since in an FPI call, account state cannot be updated).

[hexoscott]

2. How would the bridge account maintain a list of GERs?

As of now this is managed outside of the bridge by a separate GER contract on the L2 but no reason this couldn't be combined into the bridge contract so long as the Oracle knows how to interact with it. The contract stores a history of depositCount -> InfoRoot and GER -> L1BlockHash so storage will expand over time. Any bridge activity in the Agglayer will need to be reflected in the local state of each L2 by tracking the GER.

3. How would the AggOracle update the bridge account with new GERs?

On EVM chains the GER contract has some properties added when the contract is initialised containing the addresses of accounts allowed to add/remove GER entries from storage. The Oracle has the key for one of these accounts in it's keystore and will issue transactions to the contract to insert GERs to state.

The link here has the implementation for the GER contract https://github.com/agglayer/agglayer-contracts/blob/main/contracts/v2/PolygonZkEVMGlobalExitRootV2.sol

[hexoscott]

Correction, that is the GER contract on the L1. This is the contract deployed on the L2 https://github.com/agglayer/agglayer-contracts/blob/v12.1.1/contracts/sovereignChains/AgglayerGERL2.sol