Execution validity is not attributable: blame-set constraint for fraud proofs, and signed dissents

Writing the consensus correctness specification (#6674) surfaced two findings about execution validity that don't belong in a documentation PR. Both are recorded in the spec as limitations — justification::proof::AccountabilityScope, manager::proof::commit::CertifiedBlockWasExecuted and manager::proof::commit::IncomingBundlesAreSelfDerived — but neither is actionable there.

They are independent and can be split; they are filed together because they share a root cause.

Background: incorrect execution is not attributable

EquivocationProof covers only a validator contradicting its own signatures — two votes of the same kind in a round, validating past a lock, a contradicted first-round attestation, an invalid justification opening. Nothing in it relates a block's ProposedBlock to its BlockExecutionOutcome.

So a validator that votes for exactly one block per round, with a sound justification chain, but whose block carries a fabricated outcome, leaves no extractable proof at all. What we have instead is local detection in ChainWorkerState::execute_contiguous_block:

if outcome != verified {
    return Err(ChainError::CorruptedChainState(…).into());
}

That is unilateral — the detecting node holds nothing transferable, and any peer must redo the work to be convinced.

This matters more than it looks, because the outcome is eight separately committed components (BlockHeader carries state_hash, messages_hash, events_hash, blobs_hash, oracle_responses_hash, …) and they differ sharply in reach. A wrong state_hash stays on the chain. A wrong messages or events field leaves it — bundles are delivered into other chains' inboxes and consumed by their blocks, events are read across chains via OracleResponse::Event — and those downstream blocks are themselves properly certified, so they are evidence of nobody's fault. Only blobs are self-verifying, being content-addressed.

Part 1 — Design note: a fraud proof must blame the grounding link, not the confirmation quorum

This is a correctness constraint on any future execution-fraud-proof scheme, worth recording now because it is easy to get wrong and the enabling data already ships.

The obvious blame set — everyone who signed the confirmed certificate — is unsound. A validator handling an OriginalProposal::Regular retry does not re-execute: try_handle_block_proposal takes outcome.clone().with(block) and trusts the carried certificate, which check_invariants binds to exactly that block. So a correct validator can legitimately sign a block it never computed, and convicting the top quorum would frame it.

The right blame set is already in the certificate. CertifiedBlockWasExecuted establishes, by induction down the retry chain, that some correct validator executed the block — and the induction bottoms out precisely at the justification chain's grounding link, the bottom link cast with unlocking_round: None, i.e. the quorum that validated the block from a fresh (or fast-retry) proposal. Those are the validators that actually executed it.

Consequences worth noting:

• The blame set is a full quorum, so ≥ quorum_threshold weight — stronger than equivocation's validity_threshold, and it needs no intersection argument.
• The justification chain, which exists for equivocation attribution, turns out to carry exactly the right culprits for execution fraud too. No new evidence structure is needed.
• Two caveats bound the value of any such scheme. Oracles: oracle_responses are not reproducible functions of chain state, so a proof can only ever establish "the outcome does not follow from the proposal and these recorded answers", never that the answers were honest. Finality: we finalize on confirmation, not after a challenge window, and cross-chain messages have already been consumed by the time a proof could exist — so such proofs would be punitive only, and would leave a transitively corrupted subgraph standing.

No action requested beyond recording the constraint. Filing it because it currently exists only in a conversation.

Part 2 — Proposal: signed dissents on execution mismatch

Concrete and small. Today an execution mismatch is a silent local rejection. Instead, the detecting validator could emit a signed dissent: (block_hash, its own computed state_hash, signature).

Two attested, contradictory state_hashes for the same (proposal, oracle_responses) pair is transferable evidence that someone is wrong. It does not say who without adjudication — and so is not a fraud proof — but it converts a unilateral rejection into a network-visible alarm, and a validity_threshold of dissents is an actionable operational signal.

It also addresses an observability gap that is arguably the more urgent problem: we do not currently know how many nodes would even notice. Three paths skip the comparison entirely —

1. preprocess_certified_block does not execute at all, and takes messages and events from the certificate;
2. the execution_state_cache hit path in execute_contiguous_block reuses a cached state rather than re-executing;
3. oracle_responses are replayed into re-execution rather than re-derived, so a fabricated oracle answer reproduces the same state hash and is never caught by construction.

Dissents would make the effective re-execution coverage measurable.

Related, and possibly the first thing to check: IncomingBundlesAreSelfDerived shows that cross-chain integrity degrades with how much of the chain graph each validator executes. A correct validator refuses to vote on a block consuming a bundle it has not itself received (must_be_present = true in try_handle_block_proposal) and requires exact equality with its inbox — but whether that inbox content is self-derived depends on whether it executed the sending chain or only preprocessed it. That is a deployment property, not a protocol one, and it is not currently measured either.

Suggested sequencing

1. Measure effective re-execution coverage across the fleet (no protocol change).
2. Signed dissents — no cryptography, network-visible, immediate operational value.
3. Only then evaluate whether a proving path is worth it. If so, note that ZK fraud proofs (rather than interactive bisection) would let us keep the existing sequential-fold state commitment instead of Merkleizing linera-views, since the circuit can witness the state and recompute the commitment itself. The long pole there is a second, provable execution backend that is bit-identical to singlepass including fuel accounting — not the state commitment.

Links

• #6674 — the specification, including all three statements referenced above.
• linera_chain::spec and linera_core::spec — reading order and the "Known gaps" list.