ethereum-optimism / ethereum-optimism/optimism
interop: Cycle detection invalidates acyclic prerequisite chains
- 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
Assessment
This issue has not been assessed yet.