Signing LERs vs Exits

[bpfarmer]

Had a conversation with @hadjiszs and @HarryTmetic on how to authenticate BridgeExits and ImportedBridgeExits in the PP.

We agreed that instead of signing a linear hash of BridgeExits the chain could sign its own LocalExitRoot.

There was some disagreement about whether chains need to sign the ImportedBridgeExits. Theo and Monir made a good point that if the chain doesn't sign the ImportedBridgeExits, then the prover actually has some degree of freedom in choosing which claims to process, and the LBT is non-deterministic.

The proposal that I had in mind was the following. We define a set called IncomingLocalExitRoots consisting of LocalExitRoot from other chains. This set must be authenticated in some way, either by being included as a public input in a validity proof or proof of consensus, or via a signature from the chain operator.

Therefore, the payload from the chain operator to the prover is the following:

• (signed) commitment to IncomingLocalExitRoots
• IncomingLocalExitRoots: Vec<LocalExitRoot>
• Claims: Vec<Claim> where claim includes a NetworkID, InclusionProof, TokenAddress, Amount, etc - described fully elsewhere. Meant to represent an incoming deposit from another chain.
• (signed) LocalExitRoot for the current chain
• Exits: Vec<Exit> the set of exits from the chain (not sure if Exit is the proper type)

This assumes for the moment that the prover is storing/tracking the LocalBalanceTree and NullifierSet but in the future, they will likely be stored by the chain.

There are two benefits to this approach.

• First, it standardizes and simplifies the interface, because we already will need to commit to the set of IncomingLocalExitRoots for the interop proof.

• Second, it avoids potential bugs where a chain might mistakenly attempt to double-claim an exit. If the chain operator had to sign the actual incoming exits, then the prover would need the chain to resubmit. In this case, the prover can simply ignore double claims.

There is a potential drawback: a misbehaving prover could take the Vec<Claim> data structure and either exclude part of it, or include valid exits from other chains that have not been claimed yet. There is no downside to this from a validity perspective - we don't care when claims are credited to a chain's LocalBalanceTree as long as balances are non-negative.

However, it does create a potential data availability issue, if the prover includes extra Claims that result in an unrecoverable LocalBalanceTree and NullifierSet. I do think that there is an attack here: a validium never publishes its LER and a malicious prover includes claim(s) from this LER that makes it difficult to recover the LBT and Nullifier Set. However, this attack still exists in the case that a malicious sequencer includes a claim from a validium and signs a commitment to the incoming exit roots.

I think that we should decide whether the chain operator will sign the pessimistic proof, LBR, or NullifierSetRoot, in which case it doesn't matter whether the operator signs the set of claims.

For the rollup case, it's important that the PP takes a commitment to the set of claims as a public input that can be eventually verified against a public input in the validity proof, so that we can guarantee that the LBT and NullifierSet can be recoverable via L1 DA.

[krlosMata]

I think the most straightforward approach (and better aligned with medium-long term) is to sign both BridgeExits and ImportedBridgeExits.
This approach has the following trade-offs (maybe there are more that I'm missing):

cons

• PP will need to do a linear hash (Most probably keccak256 to be aligned with EVM)
  • first iteration could a linear poseidon to save PP resources
  • medium-long term: keccak for the chains that wants to post entire DA in L1, poseidon to the ones that just commits to a certain hash on L1
• PP could not be provable if the hash committed on L1 does not exits
  • this could happen only if there is two-step process, commit & verify on L1, to allow recursion on chain's individual PP

pros

• prover forced to process the data that the chain signed. No freedom degree.
• Medium term to allow chains to put all DA to compute full LBT and nullifierTree on-chain
• Chain to select which importedBridgeExits to import and how
  • include here the IncomingLocalExitRoots to be used for each importedBridgeExits
  • data to sign: usedLER_0 # LER_Leaf_0 (networkID, amount, ...) # ... # usedLER_N # LER_Leaf_N (networkID, amount, ...)
  • we may also exclude the usedLER_0 and let the prover to choose it

---

We agreed that instead of signing a linear hash of BridgeExits the chain could sign its own LocalExitRoot.
yes, signing the newLER defines deterministically BridgeExits. My only concern here is at some point, we will want to give flexibility on the chain regarding DA. I imagine a chain choosing between two approaches: pp chain - validium or pp chain - rollup.
pp chain - rollup has the ability to reconstruct LET, LBT & nulliferTree from DA on L1. So I think signing the full set of bridgeExits aligns better on the medium-long term

I think that we should decide whether the chain operator will sign the pessimistic proof, LBR, or NullifierSetRoot, in which case it doesn't matter whether the operator signs the set of claims.

I think the trade-off here is that the chain should be able to compute the LBR and the NullifierSetRoot prior sending the data to the aggLayer since it needs to be signed. This adds complexity on the chain side at this first stage. However just signing bridgeExits & importedBirdgeExits, the chain does not need to do any computation of the LBT or NullifierSetRoot.
Said that, I think this is valid approach to do as well and if it done, the code needed to compute the LBT & NullifierSetRoot will be used in medium-long term stages where the chain computes its own PP locally

[bpfarmer]

I think the most straightforward approach (and better aligned with medium-long term) is to sign both BridgeExits and ImportedBridgeExits.

No need to sign BridgeExits right, as the data is already committed to in the LER.

I think signing ImportedBridgeExits could make sense, but I worry that we're handling a case that doesn't really exist.

For rollups, we need a stronger guarantee than simply signing ImportedBridgeExits - we need to know that the claims in ImportedBridgeExits match what was actually claimed in the zkEVM. Otherwise, there's the possibility that a malicious sequencer will include claims from a Validium and launch a data-withholding attack to make it impossible to reconstruct the right LBT / NullifierSet. Just signing ImportedBridgeExits doesn't guarantee this.

On the other hand, for sidechains like Polygon PoS, we can't just check a single signature on ImportedBridgeExits because the entire validator set needs to approve ImportedBridgeExits - so we need it included in a consensus proof.

For single-sequencer validiums, we could check a signature, but if we already need to handle verifying ImportedBridgeExits for rollups in the execution proof, then it doesn't really make sense.

So if we exclude any setup that requires a proof of consensus or an execution proof, we're left with single-sequencer sidechains, which IMO is not a case that we should be handling.

It's a separate question whether we should have the PP check a signature for now as an interim step. IMO, since we'll be running the prover, I don't think that we need to worry about a misbehaving prover.

Medium term to allow chains to put all DA to compute full LBT and nullifierTree on-chain

I might just be misunderstanding something here @krlosMata - but I'm unclear on the DA question. I agree that we have to be really careful with rollups, but as long as we enforce consistency of ImportedBridgeExits between the execution proof and the PP, there's no additional data required to be posted to L1.

For validiums, we could post data required to reconstruct the LBT/NullifierSet, but imo if a validium operator wanted to launch a data-withholding attack, he could always just withhold data to make it impossible to reconstruct the state root.

[krlosMata]

So if we exclude any setup that requires a proof of consensus or an execution proof, we're left with single-sequencer sidechains, which IMO is not a case that we should be handling.

ok, I was always thinking on this scenario xD
I was assuming two different single-sequencer sidechains: ones with no DA and ones with DA.

• DA: provides ability from a third-party/special-role to force bridgeExits and continue LBT-NullifierTree (this could not happen if there is no DA)
  Agree that we do not have to take into account this scenario right now.

Therefore, it makes sense to sign just the LER.

---

From rollup perspective, the state-transition proof already enforces/commits a newLER, so it can enforce/commit also a ImportedBridgeExit_Tree, where all the claims are stored. So there will not be any discrepancy.

From sidechains like PoS, the consensus-proof will just provide guarantee on the ImportedBirdgeExits and newLER. This is where I think we can introduce the consensusType - consensusPayload as an inputs of the PP to be more generic. The first one that we will use will be consensusType: 0 and the PP takes the consensusPayload = publicKey and checks the signature. Later on, we can think about other consensus, such as the PoS one and how to handle it in the PP

[bpfarmer]

ok, I was always thinking on this scenario xD

:D maybe others would disagree but to me it's tough to see this as being super important.

Therefore, it makes sense to sign just the LER.

✅

I think we can introduce the consensusType - consensusPayload as an inputs of the PP to be more generic.

I agree in principle - I think that introducing consensusType and consensusPayload makes sense. However, should the PP check consensus? For example, there's no state root parameter in the PP, so we may not be able to fully verify the updated state of the chain. I wonder if it makes sense to have separate verification pipelines for:

• Execution Proof
• Consensus Proof
• Pessimistic Proof

We can obviously combine things in the short term to simplify, but maybe a clean separation of these components makes sense?

[krlosMata]

I was always thinking that the consensus is embedded into execution proof & pessimistic proof, differently.
So you have a consensus for each one:

• transactions ordering (state-transition at the end) in the execution
• bridgeExits & importedBridgeExits in the PP

An example that I can imagine: Polygon PoS

• on one hand, you verify consensus + state-transistion --> newStateRoot
• on the other hand, you verify consensus + PP --> newStatePP

This gives certain flexibility in the protocol since one is not dependent on the other one.