ethereum-optimism / ethereum-optimism/optimism

interop: Cycle detection invalidates acyclic prerequisite chains

Closed
#22,825 0 comments 0 reactions 1 assignee Claimed by @ajsutton View on GitHub
H-interop proofs: interop
Dominant language
Go
Stars
6.5k
Forks
4k
Avg merge
2d 15h
Merged PRs (30d)
145

Description

**Claude:**

## Summary

Current Go and Kona cycle detection classify every unresolved graph node as a cycle participant.

Reverse Kahn pruning leaves acyclic prerequisites unresolved when they feed a cycle. Both implementations then replace a valid prerequisite chain.

I reproduced this behavior at `develop` commit `adb49c16082bdb82b60408097576fe393953594c`.

## Reproduction

Construct this same-timestamp dependency graph:

- `A0` depends on `B0`.
- `B0` depends on `A1`.
- `A1` depends on `A0` and `C0`.
- `C0` has no graph dependency.

Only `A0`, `B0`, and `A1` form a cycle. `C0` is an acyclic prerequisite.

This graph is reachable through valid message declarations. Chain D can supply `C0`'s initiating log without creating another graph node.

A focused Go test produced this result:

```text
expected cycle chains: {A, B}
actual cycle chains: {A, B, C}
```

## Root cause

`checkCycle` removes nodes that have no dependents. Cyclic `A1` depends on `C0`, so `C0` never becomes removable.

`collectCycleParticipants` then treats every unresolved node as cyclic.

Relevant Go locations:

- `op-supernode/supernode/activity/interop/cycle.go:52-87`
- `op-supernode/supernode/activity/interop/cycle.go:214-242`

Kona implements the same algorithm and result:

- `rust/kona/crates/protocol/interop/src/rules.rs:183-203`
- `rust/kona/crates/protocol/interop/src/rules.rs:225-302`
- `rust/kona/crates/proof/proof-interop/src/consolidation.rs:149-151`

## Impact

Go adds chain C to `InvalidHeads`. Kona re-executes chain C as deposit-only and commits the replacement output.

This can discard valid user transactions from a chain outside the cycle.

The behavior conflicts with these specifications:

- [Message graph](https://specs.optimism.io/interop/messaging.html#message-graph)
- [Replacing invalid blocks](https://specs.optimism.io/interop/derivation.html#replacing-invalid-blocks)

## Expected behavior

Cycle detection must report only nodes that belong to a directed cycle.

The implementation should exclude connected acyclic prerequisites. Tests should cover this graph in both Go and Kona.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.