Agglayer: handling bridge in `CLAIM` note nullifiers

[partylikeits1983]

As per #2416 we must keep track of spent CLAIM note via nullifier tracking.

There are two methods of achieving this, both with slight tradeoffs:

1. Simple way: Use PROOF_DATA_KEY as nullifier for the CLAIM note. The PROOF_DATA_KEY is the RPO hash (will be posiedon2 hash) of the underlying proof data required by the solidity bridgeIn() method. Since the proof data will always be unique, a hash of the proof data, PROOF_DATA_KEY, should be sufficient to use as a nullifier value to track spent CLAIM notes. However this would mean that the only way to check if a given CLAIM note has been spent, is to know its corresponding PROOF_DATA_KEY.

2. More complex: Use bitmap to track leafIndex values as is done in Agglayer solidity contract. This would mean implementing _setAndCheckClaimed() and isClaimed() logic in MASM. It is likely that aggkit needs a getClaimed() function equivalent on Miden agglayer contracts, which takes leafIndex & sourceBridgeNetwork as parameters.

---

Pros and Cons of each approach:

Downsides of approach 1:
Requires computing hash of proof data PROOF_DATA_KEY to check if it exists in the nullifier mapping. Each nullifier is a single Word. The isClaimed() procedure doesn't match agglayer Solidity contracts.

Benefits of approach 1:
Super easy to do, can have a PR up and merged in 1-2 days.

Downsides of approach 2:
More time to implement bitmap tracking in MASM similar to how its done in Solidity. Minimum 2 days to implement, and 1-2 days on review.

Benefits of approach 2:
Matches Agglayer Solidity contracts. MASM isClaimed() procedure matches Solidity logic.

Conclusion:

I think that approach 1 is the way to go, unless it is absolutely necessary for Aggkit to have access to a isClaimed() procedure which matches 1:1 the Solidity implementation.

[bobbinth]

Downsides of approach 1:
Requires computing hash of proof data PROOF_DATA_KEY to check if it exists in the nullifier mapping. Each nullifier is a single Word. The isClaimed() procedure doesn't match agglayer Solidity contracts.

Don't we compute this anyway? Or do you mean we need to compute it in some other context?

Also, what exactly is the "nullifier mapping"? Is this the chain's nullifier tree or a specific storage slot in the bridge account?

Overall, I'd probably go with approach 1 too - though, would like to understand the downsides more.

[partylikeits1983]

Don't we compute this anyway? Or do you mean we need to compute it in some other context?

Yes we compute PROOF_DATA_KEY once, then it is stored in global memory, where we can access it for various purposes.

what exactly is the "nullifier mapping"?

The nullifier mapping would be a mapping in a storage slot in the bridge account. We need to add this regardless of which approach we go with, 1 or 2.

---

Response from Agglayer team in slack:

You do not need to mimic is isClaimed() functionality. As long as you store the nullfifer correctly, it is OK.
From the protocol perspective, the nullifier is the combination of the uint32 leafIndex & uint32 sourceBridgeNetwork which identifies uniquely a claim in the GER.

From the design, anyone can do an implemention.
We choose the bitmap implementation because of GAS savings in Solidity. Very first approach was in fact just a double mapping mapping(uint32 => mapping(uint32 => bool)) public nullifier; (internally solidity does a hash basically). Same would be:

uint256 nullifierHash = keccak256(leafIndex, sourceBridgeNetwork);
mapping(uint256 nullifierHash => bool) public nullifier;

Therefore, the isClaimed() function can be implemented in different ways as long as the nullifier is the correct one. In Miden, just doing a poseidon with leafIndex & sourceBridgeNetwork looks like the most straightforward approach.

As a side note, I've checked our core components (aggkit, agglayer-node), and none of them is using the isClaimed() function. It may be used from UI components, bridge UI or auto-claim service though.

---

Summary:

According to the Agglayer team, it is not critical how the nullifier is computed, as long as it is a valid nullifier, meaning no two CLAIM notes produce the same nullifier. Although the approach outlined by Agglayer team is to do a "poseidon with leafIndex & sourceBridgeNetwork" we already have to do a RPO (will be poseidon after VM upgrade) of PROOF_DATA which results in PROOF_DATA_KEY, I think using PROOF_DATA_KEY is the most straight forward approach.

[bobbinth]

Although the approach outlined by Agglayer team is to do a "poseidon with leafIndex & sourceBridgeNetwork" we already have to do a RPO (will be poseidon after VM upgrade) of PROOF_DATA which results in PROOF_DATA_KEY, I think using PROOF_DATA_KEY is the most straight forward approach.

I would consider doing this as Poseidon2(leaf_index, source_bridge_network) - if it doesn't add too much complexity (maybe as a follow-up). The main reasoning is that while we PROOF_DATA_KEY readily available in MASM, computing nullifier in other context from proof data would be more expensive (I don't have specific contexts in mind though).

So, I'd probably do:

• Let's use PROOF_DATA_KEY for now - as this is the most straight-forward approach.
• Once the above is implemented, let's create an issue to consider transitioning to Poseidon2(leaf_index, source_bridge_network).

[krlosMata]

The PROOF_DATA_KEY is the RPO hash (will be posiedon2 hash) of the underlying proof data required by the solidity bridgeIn()

Is this data the hash of both smtProof when an asset is claimed ?

[partylikeits1983]

Is this data the hash of both smtProof when an asset is claimed ?

Yes, it is the hash of both.

[krlosMata]

I'm not sure about the details on the claimAsset functionality in the Miden side, but an attack of double-spending (infinite in fact) can be done if the nullifier are the smt-proofs.

Two scenario attacks

Non-constrained smtProofRollupExitRoot

There are two trees structures in the GER: L1_LER (left side of the GER) and RER (right side of the GER).
RER contains all LER for every rollup. More details here.

If a bridge goes from L1 to L2, the L2 claimAsset call does not need to use the smtProofRollupExitRoot since it is not needed given that the L1 LER is only the left side of the GER. Therefore, smtProofRollupExitRoot is not constrained. One can set any value to smtProofRollupExitRoot, which will turn out in a different nullififer allowing infinite claiming.

Same leaf claimable from different GERs

GER is an incremental tree that contains all bridges. One bridge can be claimed from different GERs.
Example:

• GER_A: tree with just one bridge, bridge_A
• GER_B: tree with two bridges, bridge_A & bridge_B

Both GER_A and GER_B are injected in Miden to be able to claim.

• User claims bridge_A from GER_A --> smtProof = [A, B, C] --> it generates nullifier N_A
• User claims bridge_A from GER_B --> smtProof = [D, B, C] --> it generates nullifier N_B

Therefore, bridge_A has been claimed twice and it is repeatable for every GER that is injected.

---

---

I strongly recommend to use a unique nullififer Poseidon2(leaf_index, source_bridge_network) to avoid any potential issues and double-spending attacks

[bobbinth]

Same leaf claimable from different GERs

ah - very good point! Yes, let's use Poseidon2(leaf_index, source_bridge_network) for the nullifier.

[mmagician]

closed in #2610