Ledger consensus engine

Ledger consensus engine

Part of Ledger implementation. This page covers Consensus, the voting side of one validator, the sign state that keeps it from signing twice, and LedgerNode, which ties both to a ledger. How a block is agreed, in words, is on the Ledger page.

The engine

Consensus is the voting side of one validator for one height, after Tendermint (Algorithm 1 of arXiv 1807.04938) with its rounds called views, so that round stays the word for the rounds of the validator set. It owns no clock, network or thread and is not thread-safe. It is told an event, a message, a timeout or news of work, and returns Actions: Broadcast(message), Schedule(timeout, delay) and Decide(block). It never looks inside a block; it asks ConsensusApp.

Method of ConsensusApp	What it does
propose(height, view, proposer, time)	The block for this height and view, with the proposer's endorsement still to come. Empty when it is not this key's turn, the height is not the next, or there is no work
validate(block)	Empty when the block is valid as it stands, but with no certificate required. Also refuses a block dated more than 30,000 ms ahead of the node's clock
validateCertified(block)	Empty when the block is valid with its certificate
hasWork(time)	Whether a transaction waits, a mint is due, or fees wait to be paid out

The messages. A proposal carries a block, its view and a valid view: -1 for a new block, or the earlier view in which the block gathered a quorum of prevotes, in which case the proposal carries those prevotes as proof and the signature covers a digest of them. A ballot is a prevote or precommit for a block hash, or for nil, the all-zero hash. A decision is a block with its certificate, which is how a node that missed the vote catches up. A precommit's signature is exactly an endorsement. The bytes are on Ledger encoding.

The rules, tried after every event until none applies:

Rule	What it does
Start a view	The proposer of the view asks the ledger to propose, or offers its valid block again. Every node sets a propose timer
Prevote	With the proposal of this view, the node prevotes the block if the ledger validates it and the node is not locked on another block, or its lock is from a view no later than the proposal's valid view. A re-proposal needs a quorum of prevotes as proof. Otherwise it prevotes nil
Lock and precommit	More than two thirds of prevotes for the proposal's block, in the prevote step: remember it as valid, lock on it, and precommit it
Precommit nil	More than two thirds of nil prevotes in the prevote step: precommit nil
Decide	More than two thirds of precommits for a block of a proposal the node holds, in that proposal's view, in any view: build the certificate and ask validateCertified. If that refuses, the node remembers it and does not retry within the view
Timers	Once more than two thirds of the prevotes of the view are in, a prevote timer starts, and on expiry the node precommits nil. Once more than two thirds of the precommits are in, a precommit timer starts, and on expiry the node starts the next view. On a propose timeout the node prevotes nil
Skip	If more than one third of the validators are heard in a higher view, go to the highest such view

The steps of one view, as one validator sees them:

stateDiagram-v2
    [*] --> Propose: start the view, set the propose timer
    Propose --> Prevote: proposal arrives, prevote the block or nil
    Propose --> Prevote: propose timer, prevote nil
    Prevote --> Precommit: more than 2/3 prevotes for the block, lock and precommit it
    Prevote --> Precommit: more than 2/3 nil prevotes, precommit nil
    Prevote --> Precommit: prevote timer, precommit nil
    Precommit --> Decided: more than 2/3 precommits for the block
    Precommit --> NextView: precommit timer
    NextView --> [*]: view + 1, the next key proposes
    Decided --> [*]: commit, start the next height

Loading

A decision can come in any step: more than two thirds of precommits for a block of a proposal the node holds decide it at once, which is how a node that missed a view catches up. Below, four validators decide a height in its second view after the first proposer went offline.

A ballot or proposal more than 32 views ahead is not stored, only noted as proof that its sender has reached that view. A proposal is accepted only for this height, as the first of its view, from the proposer of that view, with a valid signature and a block whose view agrees. The ballot box counts the first word of a validator per type and view, and records a contradicting second one as Equivocation evidence. Nothing consumes the evidence yet.

Waiting times (Timeouts.DEFAULT) are the base plus a step for each view, in milliseconds:

Timer	Base	Step
Propose	3000	500
Prevote	1000	500
Precommit	1000	500

A quiet chain rests. When a precommit timer fires and the node has no work, no lock, no valid block, no refused decision and has seen no proposal of this view or ballot of a later one, it stops its timers instead of starting a new view. It resumes when work arrives, or at the first message of the height. While it rests it re-sends what it signed for a while, between 5 and 60 seconds depending on the view, and then goes silent.

The sign state

SignState holds only what this validator has signed for the height it is working on, and its position: the view and step, the next view it may sign in, the block it is locked on and the valid block with their views, and its proposals and ballots. Received messages are not stored; peers send them again. It holds at most one proposal and two ballots per view, and none in a view above its own.

SignStateFile keeps it in a file that is written atomically, checksummed and locked, see Ledger storage. Observers neither read nor write a sign state.

The node

LedgerNode is one ledger, one engine and one sign state: new LedgerNode(ledger, seed, timeouts, signStore, clock), where a null seed makes an observer that follows and decides but never votes.

Save before send. The node calls persist() after every event and before the actions go back to the driver, so nothing leaves the node that is not on disk. A write is skipped if the state equals what is on disk.

sequenceDiagram
    participant D as LedgerDriver
    participant N as LedgerNode
    participant C as Consensus
    participant F as SignStateFile
    D->>N: an event: a message, a timeout or work
    N->>C: hand on the event
    C-->>N: actions: broadcast, schedule, decide
    N->>N: commit what is decided
    N->>F: save the sign state, forced to disk
    N-->>D: the actions
    D->>D: send the messages, set the timers

Loading

Commit is done by the node, not the engine. For each Decide it calls ledger.commit(block), starts the engine at the next height, loops while that height decides at once (a network of one validator), and saves the sign state. The driver then cancels the timers of the height and sends a status.

Start. The node compares the saved sign state with the height of its ledger:

• a state at a height below the next is ignored, because that height is decided;
• a state at the next height is restored, and the engine re-sends what it holds;
• a state above the next means the block log lost its tail, and start throws BlockLogBehindException: restore the tail from a peer and never delete the sign state.

A state that Consensus.restore refuses, such as foreign signatures or a precommit with no lock behind it, stops the node. If an event or a save throws, the node stops and refuses further events; the driver builds a replacement from the same files, which restores the last saved state.

In the source

• ledger/src/main/java/org/unigrid/hedgehog/ledger/Consensus.java: the voting engine, with BallotBox.java, Proposal.java, Ballot.java, Decision.java and Timeouts.java
• ledger/src/main/java/org/unigrid/hedgehog/ledger/ConsensusApp.java: the interface the engine asks the ledger through
• ledger/src/main/java/org/unigrid/hedgehog/ledger/SignState.java: what a validator has signed
• ledger/src/main/java/org/unigrid/hedgehog/ledger/LedgerNode.java: one ledger, one engine and one sign state together