Validating

This chapter is the normative specification of Kailua's validation protocol: how disputes between contradictory sequencing proposals are settled by proofs, and how proposals are proven valid ahead of their challenge timeout. As in the previous chapter, the key words must, must not, should, and may denote requirements on any conforming implementation, and the rules below define the protocol in the abstract — with the KailuaTournament and KailuaVerifier contracts as the current implementation instance and the validator agent as the reference implementation of the validator role.

Proof submission is permissionless and non-interactive: any party may settle any dispute with a single submission, and proofs attach to a proposal's identity rather than to any individual proposal instance.

Transition Proofs

The foundation of validation is the transition proof: a succinct, verifiable attestation of one application of the rollup's state transition function. A transition proof establishes a claim tuple:

A conforming verification procedure must accept a claim tuple only if starting from the agreed output, deriving the rollup using only data reachable from the derivation anchor yields the computed output at the computed height, under the committed configuration and program.

---
title: The Statement Established by a Transition Proof
---
graph LR;
  DA[derivation anchor] --> STF[state transition program];
  AO((agreed output)) --> STF;
  CFG[configuration] --> STF;
  STF --> CO((computed output at computed height));

The protocol imposes two constraints on how claim tuples may be formed:

1. The derivation anchor must be one committed by a proposal registered in the protocol. Provers cannot introduce an arbitrary L1 context; they may only derive from a view that some proposal has staked on.
2. The computed height must equal the parent proposal's height plus a whole number of output-span (S) steps, so proofs always align with the commitment schedule of the proposals they judge.

Proof Classes

Three classes of proof can be recorded against a child identity in a tournament:

For every proof class, a conforming implementation must enforce:

1. Proofs may be accepted for or against a child only until its parent's tournament produces a finalized successor.
2. At most one proof outcome is ever recorded per identity; the outcome, the prover, and the proving time are recorded permanently.
3. Proof submission must remain open to any party for as long as rule 1 permits.

Validity Proofs

A validity proof vouches for a child's entire commitment set in one step. It must consist of a transition proof whose agreed output is the parent's claim and whose computed output is the child's claim, at the child's full height — covering all N × S blocks.

---
title: Validity Proof Coverage (N = 4)
---
graph LR;
  P((parent claim)) ==4 × S blocks proven==> c((claim));
  P -.-> o0((o₀)) -.-> o1((o₁)) -.-> o2((o₂)) -.-> c;

When a proposal publishes more than one output commitment (N > 1), the transition proof must additionally commit — through its precondition — to the equivalence of the derived intermediate outputs and the proposal's published intermediate commitments. A validity proof thereby vouches for the published data, not merely the final claim.

Recording a validity proof makes the proven identity the tournament's unique valid identity, with these effects:

• Every other child identity in the tournament immediately becomes unviable; contradictory siblings are disqualified by the tournament rules — their proposers eliminated — without individual fault proofs.
• No proposal contradicting the valid identity may be created from that point on (creation rule 10).
• Children bearing the valid identity no longer wait out the challenge timeout: they finalize as soon as their parent is finalized — the finality fast-forward of resolution rule 2.

Output Fault Proofs

An output fault proof convicts a child by exhibiting a single divergent output commitment. For a disputed commitment at position i (where the proposal's commitments occupy positions 0 through N − 1, the claim being the last), a conforming implementation must require:

1. i addresses one of the proposal's N output commitments.
2. Agreed output. For i = 0, the transition proof's agreed output must be the parent's claim. For i > 0, the submitter must demonstrate — via the data availability layer's read-back mechanism — that the proposal itself published the agreed output as its commitment at position i − 1.
3. Divergence. The proven computed output must contradict the proposal's commitment at position i: for the final position, it must differ from the proposal's claim; for intermediate positions, the submitter must demonstrate what the proposal published at position i and that it differs from the computed output. Proofs exhibiting agreement must be rejected.
4. The transition proof must cover exactly the S blocks from position i − 1 (or the parent claim) to position i, with no precondition.

---
title: Output Fault Proof Against Position 2 (N = 4)
---
graph LR;
  P((parent claim)) -.S.-> o0((o₀)) -.S.-> o1((o₁ agreed)) ==S blocks proven==> x((computed ≠ o₂)) -.S.-> c((claim));

Rule 2 is what makes disputes cheap: because the agreed output is read from the faulty proposal's own publication, a fault proof only ever derives the S blocks between two adjacent commitments — never the whole proposal. The choice of N and S thus bounds the worst-case proving work for any single dispute, as illustrated in the design overview. Note that the agreed output need not be correct — position i − 1 may itself be faulty. The proof only establishes that the proposal is inconsistent with its own published data at position i, which suffices: whatever the truth, an identity that diverges from the derivable state at any position is not the correct one.

A recorded fault makes the identity permanently unviable: the proposal and all duplicates can never finalize, and the tournament rules disqualify them, eliminating their proposers.

Trail Fault Proofs

A trail fault proof convicts a child of violating the publication format, and requires no transition proof: the submitter demonstrates, via the read-back mechanism, that the proposal published a non-zero value in its trailing (zero-padding) region. Implementations must reject trail fault claims that address the commitment region or exhibit a zero value. A recorded trail fault has the same effect as an output fault.

Payouts and Permits

When a proposer is eliminated, the prover's share of the slashed bond is paid to a beneficiary resolved in this order of precedence:

1. The holder of the sole fault proving permit for the convicted identity — if exactly one permit was ever acquired for it, and that permit was active when the convicting fault proof was recorded.
2. The recorded prover of the convicted identity.
3. The recorded prover of the tournament's valid identity, when elimination resulted from a validity proof.

---
title: Prover Share Beneficiary
---
graph TD;
  F[proposer eliminated] --> Q{sole permit, active at fault proof time?};
  Q -- yes --> H[permit holder];
  Q -- no --> R{fault proof recorded for the convicted identity?};
  R -- yes --> V[its recorded prover];
  R -- no --> W[prover of the valid identity];

Permits give provers an exclusive reward window in exchange for locked collateral. A conforming permit mechanism must enforce:

1. Permits may only be acquired for identities that are still viable.
2. The permit collateral must cover at least twice the prover's elimination share, so that abandoning a permit costs more than the reward it protects.
3. Permit issuance capacity must be bounded by expiry: at most one more permit than twice the number of already-expired permits may exist for an identity at any time.
4. A permit becomes active only after its activation delay, expires after its total duration, and its collateral is returned when released after a proof recorded within its lifetime. Holders whose permits expired before the proof forfeit their collateral to the holders active at proving time.

The Validator Role

Any party may act as a validator. The protocol's safety argument requires that every dispute eventually receives a deciding proof; for this, at least one honest validator must exist and behave as follows:

• Prove only provable statements. A validator must confirm that the deployment's committed program and configuration are ones it can execute and vouch for, before dedicating any resources to the deployment.
• Judge from a trusted view. A validator must assess every observed proposal — claim, each intermediate commitment, and trailing data — against its own trusted view of the rollup, and must defer judgement on any proposal whose height its view has not yet settled. It must never derive a fault verdict from unverifiable data.
• Target the first divergence. For an incorrect proposal, the validator should convict at the cheapest sufficient point: a format violation (trail fault) needs no transition proof and takes precedence; otherwise the earliest divergent commitment, so the transition proof spans a single S-block step whose agreed output is still shared with the canonical chain.
• Avoid redundant work. A validator should prove each identity at most once across all duplicates, skip disputes already settled (re-checking immediately before submission, since other validators race for the same disputes), decline to fault-prove when a validity proof already settles the tournament, and de-correlate its proving schedule from other validators (e.g., by randomized delay) where redundancy is not desired.
• Use registered derivation anchors. A validator must construct claim tuples only over registered derivation anchors (constraint 1): beginning with the disputed proposal's own, and — if its L1 view proves insufficient to derive the disputed span — retrying with successively later ones.
• Verify before submitting. A validator should verify its own proofs and cross-check every claim-tuple component and read-back opening against the settlement layer before submission, and re-buffer rather than discard proofs whose submission fails.
• Fast-forward when appropriate. A validator may prove the validity of correct proposals to accelerate finality. On deployments where N = 1, it should respond to any conflict with a validity proof of the correct sibling: a single such proof both accelerates the honest proposal and eliminates every contradiction, and there is no cheaper intermediate fault to exhibit.
• Honor the permit protocol. A validator using permits must acquire them only when capacity is available, wait for activation before submitting the associated proof so the exclusive window applies, and release them after the proof is recorded to reclaim collateral.