Committee-Based Adjudication of Athena Challenges

[talm]

Here’s an idea for how to construct the Athena challenge protocol such that the only L1 miners that have to execute the Athena VM code are the block proposers and Hare participants for the layer in which the challenge is adjudicated.

It also allows the auxiliary challenge data to be pruned after Hare execution is complete.

High-level overview

TL;DR: L1 full nodes don’t verify challenges at all – they “blindly” trust the Hare committee to put only correct challenges in the block, and slash any L1 security deposits that need to be punished according to the block.

However, the rewards for successful challenges are given in Athena funds. So L1 miners never allocate rewards — only Athena executors do. The (honest) Athena executors know the correct Athena state, so they don’t have to trust the Hare participants to decide which challenges are correct Thus, they can refund deposits that were erroneously slashed at L1.

In a bit more detail

Executor state commitment

Eligible executors publish a state commitment for the layer they are executing. The commitment is conditional, and has the form:

“if the cumulative layer hash at layer i is L then the correct state hash after executing all blocks up to (including) layer i is h.”

In addition, the state commitment can include a list of “Athena→L1” messages. These affect L1 state, and are parsed by L1 miners with a delay (e.g., 50 layers after the block in which they appear),

(This assumes the previous layer’s block, that is included in the layer hash L, has a correct state; if not, the executor must issue a challenge instead).

Challenge format

If an executor state commitment in the previous layer is incorrect, the challenger sends a transaction that includes:

• The correct state hash (in the same format as the executor state commitment)

• Auxiliary data: The data from Athena state that is required to execute the block and recompute the state hash after all modified data is written. This data is included along with Merkle paths to the previous (correct) state hash.

  For example, if the block contains a transfer from account A to account B, the data would include the balances of A and B.

(We’re assuming here the challenge is for the latest state, to simplify the exposition)

Challenge protocol

• Every challenger and every executor must have an L1 security deposit in order to be eligible.
• We call a challenge “valid” if it is signed by a challenger that has a valid L1 deposit.
• L1 miners will not gossip invalid challenges. Note that checking validity does not require execution of the Athena VM.
• We call a challenge “good” if it is valid and when executed gives the correct state.
  A proposal and a block has only a single “slot” for a “good” challenge.

Constructing proposals

• Every L1 miner that is eligible to generate a proposal is responsible for executing all valid challenges (actually, it’s enough to execute a single “good” challenge — once the correct state is known, every challenge with a different state is clearly bad). The miner will choose at most one good challenge to include in the proposal (it will include all valid bad challenges.)

Constructing the block

• Hare participants must also execute all valid challenges included in proposals.
• If a proposal has a bad challenge in its good challenge slot, the miner will vote against that proposal.
• When constructing the unified content block, a single good challenge from the selected proposals will be chosen for the block’s good challenge slot. All the bad challenges will also be included in the block.
• The only data that needs to be stored for each challenge is the challenger’s ID (to allow reward/punishment) and the claimed correct state.

Executing a block with challenges

Challenges in the block have effects both on L1 and Athena state.

• In L1:
  • if a challenge appeared in the “good” slot of a block, then the L1 security deposit of every conflicting executor is burned.
  • if a challenge appeared in one of the bad challenge slots, then the L1 security deposit of the corresponding challenger is burned.
• In Athena:
  • Executors behave differently depending on whether a challenge is actually correct. Note that executors don’t need extra data to verify a challenge – they have the entire Athena state and know the correct state hash for every layer.
  • Correct challenge:
    • If the challenge appears in the “good challenge” slot of a block, some part of the burned executor security deposits are transferred to the Athena account of the challenger.
    • If the challenge appears in on of the bad slots of the block, some part of the burned challenger security deposit is transferred to the Athena accounts of the block proposers and Hare participants that validated the challenge (maybe also to the executors executing this block).
  • Incorrect challenge:
    • An “Incorrect challenge” message is added to the Athena→L1 message list. L1 miners that process this message slash the corresponding deposits.
    • If the challenge appears in the “good challenge” slot of a block (i.e., some honest executors were incorrectly slashed), the value of the burned executor security deposits is transferred (refunded) in full to the Athena accounts of the executors that were harmed. (alternatively, an Athena→L1 transfer message can be output, as if the executors have just transferred the funds from Athena back to their L1 accounts)
    • If a challenge appeared in one of the bad challenge slots of the block (i.e., the challenger was incorrectly slashed), the value of the burned challenger deposit is refunded to the challenger’s Athena account (or directly to the L1 account via an Athena→L1 message).

Analysis

If the honest-majority holds for the Hare, then only good challenges will be accepted, the malicious executors’/challengers’ L1 deposits burned, and the rewards for good challengers deposited in their Athena accounts.

If there is a temporary dishonest majority in the Hare, then the block may contain incorrect challenges. In that case, once honest majority is restored, the honest executors will refund any incorrectly burned deposits. A dishonest majority can still cause some damage to honest executors (there will be at least a few layers in which they do not have their security deposit, so they won’t be eligible to execute), but not too much. In particular, they can’t steal the deposit funds from honest executors or challengers.

The “incorrect challenge” Athena→L1 messages are a little tricky, because a malicious executor can generate bad messages (along with bad state). However, this will only have an effect if there are no honest challenges during the entire delay period (the time from when the messages are published to when the L1 miners process them). So this should only happen extremely rarely.

If it does happen, the same mechanism can be used recover — slashed L1 deposits will be refunded to Athena accounts by honest executors.

[Amira]

1. You say " We call a challenge “good” if it is valid and when executed gives the correct state.
   A proposal and a block has only a single “slot” for a “good” challenge."
   I guess same goes for executors, “we call a state commitment valid if it signed by an executor which has a valid L1 deposit.”

2. In your example, you’re assuming the challenge is for the latest state. What happens if it’s a really old state (let’s say 100 layers back)?

3. You say "However, the rewards for successful challenges are given in Athena funds. So L1 miners never allocate rewards - only Athena executors do".
   Why give rewards in Athena and not in L1 funds? I also don’t understand the logic behind saying L1 miners never allocate reward, only Athena executors do. Why even worry about such a scenario?

4. You say " The honest Athena executors know the correct Athena state, so they don’t have to trust the Hare participants to decide which challenges are correct. Thus, they can refund deposits that were erroneously slashed at L1."

   • Since not all deposit is burnt and some of that deposit will go as a reward for challengers and L1 miners, how can it be refund back to executors in this scenario?
   • Same thing for a challenger who was incorrectly slashed. Is the part of the deposit that was transferred to the Athena accounts of the block proposers and Hare participants that validated the challenge is given back to challenger?
   • Do hare participants that incorrectly slashed a challenger or executor get punished? If yes, how? Since we don’t demand L1 miners to have a deposit?

[talm]

@Amira

You say " We call a challenge “good” if it is valid and when executed gives the correct state.
A proposal and a block has only a single “slot” for a “good” challenge."
I guess same goes for executors, “we call a state commitment valid if it signed by an executor which has a valid L1 deposit.”

No, the rule for executors also requires eligibility and/or payment, which we haven’t completely agreed on yet. But in any case it’s not relevant for this discussion.

@Amira

• In your example, you’re assuming the challenge is for the latest state. What happens if it’s a really old state (let’s say 100 layers back)?

Again, not the focus of this discussion. But for completeness: if the challenger is challenging an older state (regardless of how old), it must act as both a challenger and an executor: the challenge will contain the information necessary to verify the first state on which it differs from the executors it is challenging, and the entire sequence of state hashes for the succeeding blocks, up to the present.

@Amira

Why give rewards in Athena and not in L1 funds? I also don’t understand the logic behind saying L1 miners never allocate reward, only Athena executors do. Why even worry about such a scenario?

The model I have in mind is that executors can’t “claw back” L1 balances, since those are tracked by L1 miners. The advantage of this model is that regardless of bugs in Athena code or the behavior of executors, the L1 balances are guaranteed to be ok as long as there’s an honest majority at L1.

However, the executors are free to do whatever they want with Athena balances (by “whatever they want”, I mean, of course, whatever the protocol specifies). So only L1 miners, in their adjudicator role, can slash the security deposits. But if the executors are the ones who handle reward allocation at the Athena level — the correct reward allocation is the one that matches the correct state, and can be done by the executors even if an incorrect state hash is written in the block. Moreover, they can “fix” mistakes made by a dishonest majority putting in the wrong state hash (and thus slashing accounts incorrectly) by reimbursing the Athena accounts of the damaged parties.

An alternative executor-centric model

Let’s consider the things that L1 miners (and full nodes) need to know about the state (both L1 and Athena):

• They need to know lower bounds on the L1 balances of relays (or L1 accounts that act as their own relay) to make sure they can pay storage fees
• They need to know lower bounds on the deposit amounts for executors/challengers so they can check eligibility

The idea behind this alternative model is to let the executors have control over the entire state: both L1 and Athena. In this model, the L1 miners are a kind of “light client”.

• L1 miners still track L1 state. However, the “canonical” state is maintained by executors.

• Executors track both L1 and Athena state. They also track the L1 miners’ view of L1 state, by executing the L1 miner code.

• Whenever the actual L1 state differs from the miners’ view, executors publish, in addition to the state hash, a set of “state updates” .

  • How exactly these updates are encoded doesn’t matter for this description, but it should be an efficient encoding of the “delta” between the miners’ (incorrect or outdated) view of the L1 state and the correct state.
  • This includes transfers from Athena to L1, as well as the effects of challenges.

• When a challenge occurs, just as described above:

  • A special “challenge tx” is added to the block. This tx includes only the challenging account and the claimed correct state (in this model, it will also include the claimed correct state updates). The challenge is accompanied by auxiliary information as described above.
  • A committee of L1 miners still plays the adjudicator role (the block proposers and Hare participants for the next layer execute the entire block). They generate a “resolution transaction” that contains the correct state for that block, or – in case they can’t do this because the challenges do not have sufficient auxiliary data – they just state that the challenges are invalid.

• When executing a block that contains a challenge transaction, executors slash the guilty parties’ security deposits and transfer rewards according to the correct state – they ignore challenge-resolution transactions (in fact, they resolve the challenges in parallel to the L1 adjudicators, so they do this before seeing a challenge resolution transaction).

• Executors do use the resolution transaction to determine the current view of L1 miners. Thus, the resolution transactions affect which state update messages will be output. (e.g., if the resolution transaction was correct, no state updates need to be output, while if it was incorrect, the state updates will include the “unslashing” of some security deposits and slashing of others.)

• Light clients use the latest unchallenged state hash as their accepted state; if the state hash is challenged, they use the corresponding resolution transaction. Depending on their personal risk profile, they can decide how long they should wait before accepting a state as unchallenged.

• L1 miners keep both a “latest” and a “conservative” view of L1 balances. They track pure L1 transactions (as they do in the current model), but in the conservative view, they treat differently L1→Athena state updates and Athena→L1 updates:

  • An L1→Athena update is accepted immediately.
  • An Athena→L1 update is accepted slowly: e.g., only if it is not challenged within 1 epoch.

• The exception to this is an Athena→L1 update that appeared in a challenge resolution: in this case, the result of the challenge resolution becomes both the latest and the conservative view.

• L1 miners use the conservative view to decide whether L1 transactions can pay storage fees and to decide eligibility of executors and challengers.

Analysis

• While the L1 honest-majority assumption holds, then challenge-resolution txs are always correct. As long as at least one executor is honest and can generate challenges, L1 miners (and light clients) will have an incorrect “latest state” only during the period between bad state being committed by executors and the first good challenge (optimally, this should be within 2 layers of the bad executor state being included in a block)

• Since L1 miners use the conservative approach to determine storage fee availability (and executor eligibility), a bad L1 state can cause some valid transactions to be delayed, and some otherwise eligible executors to be ignored, but I think that’s it.

• If there is a dishonest majority in an L1 Hare committee, the committee can issue a bad challenge resolution. In this case, executors will still slash only the malicious challenger’s security deposit, but will also issue a state update “fixing” the view of L1 miners. Of course, while the dishonest majority continues to hold, Hare participants can ignore the correct executor states. However, once honest majority holds again, the miner view of L1 state will also be fixed.

  • There is an edge case where this can’t happen: if the malicious L1 state ensures that no honest executors have valid security deposits. In this case, no challenger can contest the state. This can also potentially happen even in the previous model, where L1 miners control L1 state. I think the solution to this is to allow a challenger to stake a large amount of spacetime instead of a security deposit (i.e., the challenger’s identity will be canceled if the challenge fails). To disincentivize this kind of challenge when there is an alternative, we can reduce (or eliminate) the reward for a successful challenge.
  • Also, a dishonest majority can cause L1 miners to believe many executor deposits were slashed. However, once a valid challenge is issued (which should be very quickly after honest majority is restored), the deposits will be “unslashed” (in their view) – and because it is the result of a challenge resolution, it will update the conservative view quickly as well.

• Finally, note that even when the conservative view of L1 miners is wrong (which can only happen in the dishonest majority case), as far as I can see the worst that can happen is that blocks contain transactions that can’t pay their storage fees, and/or state commitments from executors that don’t have a security deposit (which a dishonest majority can do without having to create bad state). The latter is a little worse, since it reduces the incentive to challenge, but again it doesn’t require state manipulation if there’s a dishonest majority, so this can happen regardless of the model.