KIP 334: Prepared Certificates Across Rounds

Abstract

When a proposer fails or messages are delayed and consensus does not complete, Kaia BFT starts a new round at the same block height. In the existing protocol, a validator that observes a quorum of votes for a block considers the block prepared and sets a local lock on it, which keeps it from voting for a conflicting block in later rounds. However, the round change that Kaia inherited from IBFT does not convey the lock or the votes behind it to the next proposer, so the proposer may propose a conflicting block and the height can stall.

This KIP defines a prepared certificate, a block with the signed PREPARE or COMMIT votes proving that it was prepared. A ROUND CHANGE carries a signed claim on its sender’s certificate together with the certificate itself. The proposer of the new round re-proposes the block prepared in the highest round with its certificate, and the other validators accept the proposal regardless of their own locks once they verify that certificate, which preserves any block that could have been decided.

Motivation

While preparing the transition to permissionless validator participation, Kaia re-examined the round-change procedure of its BFT consensus against the Istanbul-family protocols established since, and found that a lock in Kaia BFT is kept only locally. The issue is not new to the permissionless transition, but the transition is the occasion to address it with an explicit protocol rule.

A locked validator rejects any proposal at the same height that differs from its locked block. Honest validators can therefore end up locked on different blocks, and a single Byzantine validator can then stall the height. Consider four validators A, B, C, and D with a quorum of three, where D is Byzantine.

1. In round 0, all four vote for block X, but because of network delays only A observes the quorum and locks on X.
2. In round 1, an unlocked proposer proposes block Y. A rejects it, and B, C, and D vote for it. Only C observes the quorum and locks on Y.
3. From then on, A rejects every proposal other than X, and C every proposal other than Y. If D stops voting, no proposal gathers three votes, and the height is never decided.

PBFT solves this problem in its view change, and IBFT 2.0 and QBFT bring it to the Istanbul family as the round change: a prepared block travels with its proof, and the next proposer re-proposes the block prepared in the highest round. Rather than adopting any of these protocols as a whole, this KIP introduces their common recovery principle into Kaia BFT. In the example above, every round-change quorum then includes the claim of A or C, so an honest proposer re-proposes the claimed block with its certificate. Both locked validators accept it, and A, B, and C form a quorum.

Specification

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119.

Terminology

Message formats

Every consensus message is sent in a Message envelope. The envelope’s Code identifies the message type, and its Msg carries the payload of that type.

This KIP adds two proofs to these messages. A ROUND CHANGE proves which block its sender has prepared, and a PRE-PREPARE above round 0 proves that its proposal respects the blocks prepared in earlier rounds.

A prepared certificate is a block with the PREPARE or COMMIT envelopes proving that the block was prepared in a given round. A ROUND CHANGE sender signs only a compact claim on its certificate and attaches the certificate itself as the unsigned Evidence of the envelope.

A round-change certificate (RCC) is a set of signed ROUND CHANGE envelopes from at least a quorum, stripped of their Evidence, for the round of a PRE-PREPARE. Together with PreparedMessages, the votes behind the claim that the proposal re-proposes, it forms the justification of the PRE-PREPARE.

The following conventions apply to all formats in this section.

• All messages are RLP-encoded.
• An optional field is omitted from the encoding when it has no value.
• Following the existing Istanbul encoding, View is encoded as [Round, Sequence], with the round first.

Message envelope

Message {
    PrevHash    // parent block hash of the height being decided
    Code        // message type
    Msg         // RLP-encoded payload
    Address     // sender
    Signature   // signature of the sender
    Evidence    // optional, ROUND CHANGE only
}

Signature is the sender’s ECDSA signature over Keccak256(RLP([PrevHash, Code, Msg, Address])). Evidence is not part of the signed preimage, so removing Evidence from a signed envelope leaves the signature valid. Instead, Evidence MUST match the EvidenceHash inside the signed Msg, so a relay cannot replace the attached evidence with a different value.

The following rules apply to Evidence.

• Evidence MAY be present only in a ROUND CHANGE message. A message of any other code that carries Evidence is invalid.
• When there is no Evidence, the field MUST be omitted. A message that explicitly encodes a zero-length Evidence is invalid. Allowing it would give the same message two valid encodings, which could be used to bypass gossip deduplication.

PREPARE and COMMIT messages

PREPARE and COMMIT are the votes of a round. They are also the elements of a prepared certificate and of PreparedMessages.

Prepare {
    View
    Digest
}

Commit {
    View
    Digest
    CommittedSeal   // signature of the sender over Digest || 0x02 || byte(View.Round)
}

The envelope Signature and CommittedSeal are 65-byte secp256k1 ECDSA signatures encoded as R (32 bytes) || S (32 bytes) || V (1 byte), where V is either 0 or 1.

CommittedSeal is part of Msg and is therefore also authenticated by the envelope signature. It is copied as is into the header of the committed block. The header records the decided round in the last byte of the vanity area of Extra, which the block hash excludes, so the committed seal binds the round instead.

• CommittedSeal is a signature over Keccak256(Digest || 0x02 || byte(View.Round)), where 0x02 is the message code of COMMIT and byte(View.Round) is the low 8 bits of the round.
• On receiving a COMMIT, a validator recovers the signer of CommittedSeal over this preimage and rejects the message if the signer differs from the sender.
• When verifying a block header, a node recovers the signer of each committed seal with the header’s round byte in the preimage. If the round byte differs from the round in which the seals were made, the quorum check on the committed seals fails and the block is invalid.
• A validator that receives a PRE-PREPARE for an already decided height MAY respond with a COMMIT when the block is in its local chain and the sender is the proposer of that view, but only if the round of the PRE-PREPARE equals the round recorded in the stored header. Otherwise it would produce a committed seal for a round in which it never committed.

Prepared certificate

PreparedCertificate {
    View        // [Round, Sequence] in which Proposal was prepared
    Proposal    // prepared block
    Messages    // signed PREPARE or COMMIT envelopes from at least a quorum
}

A prepared certificate proves that Proposal reached the prepared state in View. A certificate is not a standalone consensus message; it is carried as RLP(PreparedCertificate) in the Evidence of a ROUND CHANGE. A valid prepared certificate satisfies all of the following conditions.

• The block number of Proposal equals View.Sequence, and the header of Proposal carries no committed seals.
• The body of Proposal passes the block body checks that precede execution: it matches the transactions root of the header, and its size, transaction gas prices, and blob sidecars satisfy the block rules. The votes bind only the digest, which does not cover every part of the body.
• Each element of Messages is a PREPARE or COMMIT envelope without Evidence. The View of each payload equals the View of the certificate, and its Digest equals the hash of Proposal. The PrevHash of each envelope equals the parent hash of Proposal.
• The signature of each envelope is a signature of its Address. For a COMMIT, CommittedSeal is also a signature of its Address.
• Every sender is a committee member and appears at most once, with either its PREPARE or its COMMIT. The number of Messages does not exceed the committee size, and the number of senders is at least the quorum.

ROUND CHANGE message

RoundChange {
    View
    Prepared {          // optional
        Round           // View.Round of the certificate
        Digest          // hash of the certificate's Proposal
        EvidenceHash    // Keccak256(Evidence)
    }
}

View is the round and sequence the sender is moving to. Prepared is a claim summarizing the prepared certificate the sender holds for the same sequence, and is omitted when the sender holds none. Its EvidenceHash binds the signed claim to the unsigned certificate.

A valid ROUND CHANGE message satisfies all of the following conditions.

• Prepared and Evidence are either both present or both absent. When Prepared is present, Keccak256(Evidence) equals Prepared.EvidenceHash.
• Prepared.Round is less than View.Round, and Prepared.Digest is not the zero hash.
• The certificate decoded from Evidence is a valid prepared certificate. Its View is [Prepared.Round, View.Sequence], and the hash of its Proposal equals Prepared.Digest.

PRE-PREPARE message

Preprepare {
    View
    Proposal
    RoundChangeCertificate   // optional, signed ROUND CHANGE envelopes
    PreparedMessages         // optional, signed PREPARE or COMMIT envelopes
}

The header of Proposal carries no committed seals. A round-0 PRE-PREPARE MUST carry neither RoundChangeCertificate nor PreparedMessages. A PRE-PREPARE for a round greater than 0 MUST carry RoundChangeCertificate, and justifies its Proposal with these two fields, which together are called the justification of the PRE-PREPARE.

RoundChangeCertificate is a list of at least a quorum of signed ROUND CHANGE envelopes for View. Evidence MUST be removed from each envelope, which leaves its signature valid. Every sender is a committee member and appears at most once, and the PrevHash of each envelope equals the parent hash of the current height. For each claim, Prepared.Round is less than View.Round and Prepared.Digest is not the zero hash, as in ROUND CHANGE message.

PreparedMessages is the list of votes proving the prepared claim in RoundChangeCertificate that Proposal re-proposes, and the proposer omits it when Proposal re-proposes no claim. In case 2 of PRE-PREPARE processing, a receiver reconstructs a prepared certificate from [Round of that claim, View.Sequence], Proposal, and PreparedMessages, and verifies it; in case 3, it ignores PreparedMessages. How a proposer selects a claim and how a receiver verifies the justification are defined in Proposal selection and PRE-PREPARE processing.

Consensus flow

Within a round, a validator is in one of the following states. The states and their transitions are those of the existing Istanbul BFT consensus; the last column lists what this KIP adds or changes.

The following subsections follow the life of a prepared certificate: a validator creates one when it enters the prepared state, carries it in a ROUND CHANGE, the proposer of the next round selects one from the round-change certificate, and the other validators verify that selection when they process the PRE-PREPARE.

Entering the prepared state

When a validator accepts the PRE-PREPARE of a proposal in its current view, it collects PREPARE and COMMIT messages for the same view and the hash of that proposal. A PREPARE and a COMMIT from the same sender count as one. When the votes reach a quorum, the validator:

1. considers the proposal prepared and locks on it in the current round;
2. stores the proposal and the votes it has received for it as its prepared certificate for the current view; and
3. sends a COMMIT if it has not already done so.

A locked validator that receives the PRE-PREPARE of its locked block in a later round sends a PREPARE and waits for a quorum in that round, as it would for any other proposal. This follows PBFT, in which replicas run the prepare phase again for every value re-proposed in a new view, and QBFT. Hence, whenever an honest validator sends a COMMIT in a round, it holds a prepared certificate for that round. The only exception is a COMMIT for an already decided block, described in PREPARE and COMMIT messages.

The lock and the prepared certificate change only in the following cases.

• When the validator observes a quorum in a later round, the lock and certificate of that round replace the earlier ones. Typically the later round re-proposes the locked block, and only the round of the lock advances.
• When a certificate verified in PRE-PREPARE processing has a higher round than the one it holds, the validator adopts that certificate.
• When the validator executes its locked block, either on importing it after a commit or in case 3 of PRE-PREPARE processing, and the execution fails, it records the block as invalid and releases both the lock and the certificate. Claims on that block are void for it from then on.
• When the validator moves to a new height, it releases both the lock and the certificate.

Round change

When its round timer expires or it rejects a PRE-PREPARE, a validator moves to the next round of the same height and sends a ROUND CHANGE for that round. If it holds a prepared certificate, the ROUND CHANGE claims it and carries it as Evidence.

A validator accepts a ROUND CHANGE that is valid as defined in ROUND CHANGE message and comes from a committee member. It keeps one ROUND CHANGE per sender for each round, replacing it only with one that has a strictly higher claim.

When a validator has ROUND CHANGE messages for the same round from a quorum of committee members, it starts that round and keeps those messages as the round-change certificate of that round. As before, ROUND CHANGE messages for a higher round from f + 1 committee members make a validator that is waiting for a round change move to that round and send its own ROUND CHANGE.

Proposal selection

A claim is void for a validator when it claims a block that the validator has executed and found invalid. The proposer of a round greater than 0 re-proposes the prepared block with the highest claim in the round-change certificate that started the round, as selected by SelectCertificate.

function SelectCertificate(sequence, round, RCC):
    claims ← prepared claims in RCC, except void claims
    if own lock is set and its round is higher than that of every claim in claims:
        replace own ROUND CHANGE in RCC, or add one if RCC has none, with a newly signed one that claims own prepared certificate
        return own prepared certificate
    if claims is not empty:
        return prepared certificate received with a claim of the highest round in claims
    return none

If no certificate is selected, the proposer proposes a new block. It broadcasts the PRE-PREPARE with its justification, and MUST NOT send a PRE-PREPARE for the round with any other proposal.

PRE-PREPARE processing

A validator processes a PRE-PREPARE from the proposer of its current view under the existing rules. In addition, the PRE-PREPARE MUST be valid as defined in PRE-PREPARE message, and for a round greater than 0 the validator accepts its proposal only in the cases below.

The cases depend on the claims in the round-change certificate. Void claims are ignored, but their senders still count toward the quorum.

1. No claim remains. A block decided in an earlier round would leave a claim in every round-change certificate, so no block can have been decided, and the proposal may be any block. PreparedMessages MUST be empty.
2. The proposal is a block claimed at the highest remaining round. The prepared certificate reconstructed from that round, the sequence, the proposal, and PreparedMessages MUST be valid. The justification then proves this certificate.

3. The proposal is any other block. Either the proposer treated the highest claim as void, which the validator may not know, or the highest claim is not backed by a valid prepared certificate. The validator decides as follows.

    if own lock is not set:
        accept                          // no block of its own to protect
    else:
        execute the locked block, unless it has already been executed at this height
        if the execution fails:         // the block is now known invalid and the lock is released
            check the justification again, with claims on that block now void, and decide again from case 1
        else:
            reject
   

If the PRE-PREPARE is invalid or its proposal is not accepted in any of these cases, the validator rejects it and sends a ROUND CHANGE for the next round. Otherwise the validator verifies the proposal as a block, as before, and accepts the PRE-PREPARE regardless of its own lock. If the justification proves a certificate with a higher round than the one the validator holds, the validator adopts that certificate and its block as its lock; otherwise it keeps its lock until a quorum in this round replaces it. The validator then sends a PREPARE and proceeds as in Entering the prepared state.

Activation

This KIP is activated by the Permissionless hard fork. Its rules apply from the Permissionless fork block onward, and the existing rules apply before it.

Rationale

The recovery mechanism of this KIP is the view change of PBFT, in the round-change form of QBFT. The first two subsections explain rules that this KIP takes from QBFT and that differ from the existing Kaia BFT; the remaining ones explain where this KIP differs from QBFT to fit Kaia.

Signed claim and unsigned certificate

As in QBFT, a ROUND CHANGE signs only a claim on its prepared certificate and carries the certificate outside the signature, so that a PRE-PREPARE can embed the same signed ROUND CHANGE without the certificate and carry the selected block and its votes only once. The justification of a PRE-PREPARE, in contrast, is placed inside Msg, because a PRE-PREPARE is never embedded in another message. Unlike QBFT, the signed claim includes EvidenceHash, which binds the attached certificate to the claim, so a relay cannot attach a different certificate to the same claim.

Accepting a justified proposal regardless of the lock

A locked validator accepts a justified PRE-PREPARE even if its proposal differs from its locked block, including a block claimed at a round lower than its own lock. This follows QBFT, and matches PBFT, which has no lock and in which a backup accepts a new view by checking its view-change messages alone. By the quorum-intersection argument of the PBFT view change, if a block has been decided, every round-change certificate contains a claim on it from an honest validator, and every valid prepared certificate of a higher round is also for that block. In case 2 of PRE-PREPARE processing, the validator verifies the prepared certificate of the highest claim, so a proposal accepted in that case keeps a decided block without a comparison with the local lock. Such a comparison would only stall the height when validators locked at a round higher than every claim in the certificate refuse the proposal.

The highest signed claim in a round-change certificate is not necessarily backed by a valid prepared certificate, because the embedded ROUND CHANGE messages carry no Evidence. A Byzantine proposer can sign a claim at a higher round without a certificate and include it in its own round-change certificate. Such a proposer cannot satisfy case 2 for that claim, and any other proposal falls into case 3, where the locks of honest validators keep a decided block, as explained in Void claims on invalid blocks.

COMMIT votes in a certificate

QBFT forms a prepared certificate from PREPARE messages only. Kaia enters the prepared state on a quorum of PREPARE and COMMIT messages combined, so a certificate contains the votes that formed that quorum, of either kind.

Void claims on invalid blocks

In Kaia, a block is executed only after it is committed, when it is inserted into the chain, so even a committed block can fail execution. When it does, the validator records the block as invalid and releases its lock on it, and treats any claim on it as void. Otherwise the highest-prepared-round rule would re-propose the block in every later round, and the height would never be decided. Since validators find a block invalid at different times, a validator without a lock accepts a proposal below a claim, and a locked validator accepts it only after its own locked block fails execution. This keeps a decided block: at least a quorum less f honest validators lock it and never find it invalid, so the remaining validators are fewer than a quorum and cannot form one for another block.

Round-bound committed seal

The safety arguments of PBFT and QBFT assume that a committed block had a COMMIT quorum in a single view or round. Without the round in the committed seal, seals for the same block from different rounds could be combined into a valid header, although no single round reached a COMMIT quorum.

Backwards Compatibility

This KIP is a hard fork and is not backward compatible. All nodes MUST upgrade to a client implementing this KIP before the Permissionless fork block, not only validators: the round-bound committed seal changes how every node verifies a block header, so a node running an older client rejects blocks from the fork block onward. Validators additionally exchange the consensus messages defined in this KIP. Blocks before the fork block are processed under the existing rules.

Security Considerations

Cost of verifying Evidence

Evidence is block-sized and expensive to verify. Implementations SHOULD check EvidenceHash and the sender before decoding Evidence, cache verified certificates, and bound the number of future rounds retained. A ROUND CHANGE for a round beyond this bound is discarded, so it counts neither toward starting that round nor toward the f + 1 messages that make a waiting validator catch up. The bound is implementation-specific and does not affect safety. Since the round timer doubles with each round, honest validators do not fall that many rounds apart in practice.

Executing the locked block

A Byzantine proposer can repeatedly propose a block below a claim to make locked validators execute their locked blocks. A validator executes each locked block at most once per height, so the cost is bounded by the number of distinct blocks it locks at the height. A failure unrelated to the block itself, such as unavailable parent state, gives no result, and the block is executed again on the next occasion.

Round byte in the committed seal

The committed seal includes only the low 8 bits of the round, so seals from rounds r and r + 256 share a preimage. A height does not reach 256 rounds in practice, nor even round 34. A round with a Byzantine proposer can end as soon as honest validators reject its PRE-PREPARE. In a round with an honest proposer, however, honest validators move on before the round timer expires only if they cannot accept the valid proposal, for example because their state is temporarily unavailable. The round timer doubles with each round and reaches 2³³ seconds, over 270 years, at round 33. The proposer of each round follows an order of the committee shuffled with the mix hash of the parent block, so long runs of consecutive rounds with Byzantine proposers are unlikely. Barring local failures, reaching round 34 would require a round with an honest proposer at round 33 − k or later to time out, where k is the longest such run, which takes more than 2^{33 − k} seconds, or over three months even for k = 10.

Proposals below a claim

In case 3 of PRE-PREPARE processing, a validator without a lock accepts a proposal below the highest claim without verifying the claim, so a Byzantine proposer can make unlocked validators vote for an arbitrary block. Safety does not depend on them, as explained in Void claims on invalid blocks; at worst the round fails, as with any faulty proposer.

Message size

A ROUND CHANGE with Evidence carries a whole block and up to n votes. A PRE-PREPARE above round 0 carries a block, up to n ROUND CHANGE envelopes, and up to n votes. Both must fit in a single consensus message of the P2P layer, which is limited to 12 MiB. The block size limit of 10 MiB, in force since the Osaka hard fork, leaves the remaining 2 MiB for the envelopes, each of which is a few hundred bytes.

Committed seals in a proposal

The block hash excludes committed seals, so copies of a proposal that differ only in committed seals share a digest and pass the same vote checks. Rejecting proposals and certificates that carry committed seals prevents such padded copies from being retained, re-proposed, or relayed.

Test Cases

See consensus/istanbul/core/consensus_test.go and the other tests added in the implementation.

Implementation

• kaiachain/kaia#1084: prepared certificates and the message format.
• kaiachain/kaia#985: round-bound committed seals.

References

• Practical Byzantine Fault Tolerance — M. Castro and B. Liskov, OSDI 1999. The origin of the view change that carries prepared certificates.
• IBFT 2.0: A Safe and Live Variation of the IBFT Blockchain Consensus Protocol for Eventually Synchronous Networks — R. Saltini and D. Hyland-Wood, 2019.
• The Istanbul BFT Consensus Algorithm — H. Moniz, 2020. The basis of QBFT.
• RFC 2119: Key words for use in RFCs to Indicate Requirement Levels — governs the MUST / SHOULD / MAY vocabulary used in the Specification.

Copyright

Copyright and related rights waived via CC0.