hotstuff

package
v0.18.2-canary Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 16, 2021 License: AGPL-3.0 Imports: 10 Imported by: 30

README

Flow's HotStuff

We use a BFT consensus algorithm with deterministic finality in Flow for

  • Consensus Nodes: deciding on the content of blocks
  • Cluster of Collector Nodes: batching transactions into collections.

Flow uses a derivative of HotStuff (see paper HotStuff: BFT Consensus in the Lens of Blockchain (version 6) for the original algorithm). Our implementation is a mixture of Chained HotStuff and Event-Driven HotStuff with a few additional, minor modifications:

  • We employ the rules for locking on blocks and block finalization from Event-Driven HotStuff. Specifically, we lock the newest block which has an (direct or indirect) 2-chain built on top. We finalize a block when it has a 3-chain built on top where with the first two chain links being direct.
  • The way we progress though views follows the Chained HotStuff algorithm. A replica only votes or proposes for its current view.
  • Flow's HotStuff does not implement ViewChange messages (akin to the approach taken in Streamlet: Textbook Streamlined Blockchains)
  • Flow uses a decentralized random beacon (based on Dfinity's proposal). The random beacon is run by Flow's consensus nodes and integrated into the consensus voting process.
Node weights

In Flow, there are multiple HotStuff instances running in parallel. Specifically, the consensus nodes form a HotStuff committee and each collector cluster is its own committee. In the following, we refer to an authorized set of nodes, who run a particular HotStuff instance as a (HotStuff) committee.

  • Flow allows nodes to have different weights, reflecting how much they are trusted by the protocol. The weight of a node can change over time due to stake changes or discovering protocol violations. A super-majority of nodes is defined as a subset of the consensus committee, where the nodes have more than 2/3 of the entire committee's accumulated weight.
  • The messages from zero-weighted nodes are ignored by all committee members.

Architecture

Determining block validity

In addition to HotStuff's requirements on block validity, the Flow protocol adds additional requirements. For example, it is illegal to repeatedly include the same payload entities (e.g. collections, challenges, etc) in the same fork. Generally, payload entities expire. However within the expiry horizon, all ancestors of a block need to be known to verify that payload entities are not repeated.

We exclude the entire logic for determining payload validity from the HotStuff core implementation. This functionality is encapsulated in the Chain Compliance Layer (CCL) which precedes HotStuff. The CCL forwards a block to the HotStuff core logic only if

  • the block's payload is valid,
  • the block is connected to the most recently finalized block, and
  • all ancestors have previously been processed by HotStuff.

If ancestors of a block are missing, the CCL caches the respective block and (iteratively) requests missing ancestors.

Payload generation

Payloads are generated outside of the HotStuff core logic. HotStuff only incorporates the payload root hash into the block header.

Structure of votes

In Flow's HotStuff implementation, votes are used for two purposes:

  1. Prove that a super-majority of committee nodes considers the respective block a valid extension of the chain. Therefore, nodes include a StakingSignature (BLS with curve BLS12-381) in their vote.
  2. Construct a Source of Randomness as described in Dfinity's Random Beacon. Therefore, consensus nodes include a RandomBeaconSignature (also BLS with curve BLS12-381, used in a threshold signature scheme) in their vote.

When the primary collects the votes, it verifies the StakingSignature and the RandomBeaconSignature. If either signature is invalid, the entire vote is discarded. From all valid votes, the StakingSignatures and the RandomBeaconSignatures are aggregated separately. (note: Only the aggregation of the RandomBeaconSignature into a threshold signature is currently implemented. Aggregation of the BLS StakingSignatures will be added later.)

  • Following version 6 of the HotStuff paper, replicas forward their votes for block b to the leader of the next view, i.e. the primary for view b.View + 1.
  • A proposer will attach its own vote for its proposal in the block proposal message (instead of signing the block proposal for authenticity and separately sending a vote).
Primary section

For primary section, we use a randomized, weight-proportional selection.

Component Overview

HotStuff's core logic is broken down into multiple components. The figure below illustrates the dependencies of the core components and information flow between these components.

  • HotStuffEngine and ChainComplianceLayer do not contain any core HotStuff logic. They are responsible for relaying HotStuff messages and validating block payloads respectively.
  • EventLoop buffers all incoming events, so EventHandler can process one event at a time in a single thread.
  • EventHandler orchestrates all HotStuff components and implements HotStuff's state machine. The event handler is designed to be executed single-threaded.
  • Communicator relays outgoing HotStuff messages (votes and block proposals)
  • Pacemaker is a basic PaceMaker to ensure liveness by keeping the majority of committee replicas in the same view
  • Forks maintains an in-memory representation of all blocks b, whose view is larger or equal to the view of the latest finalized block (known to this specific replica). As blocks with missing ancestors are cached outside of HotStuff (by the Chain Compliance Layer), all blocks stored in Forks are guaranteed to be connected to the genesis block (or the trusted checkpoint from which the replica started). Internally, Forks consists of multiple layers:
    • LevelledForest: A blockchain forms a Tree. When removing all blocks with views strictly smaller than the last finalized block, the chain decomposes into multiple disconnected trees. In graph theory, such structure is a forest. To separate general graph-theoretical concepts from the concrete block-chain application, LevelledForest refers to blocks as graph vertices and to a block's view number as level. The LevelledForest is an in-memory data structure to store and maintain a levelled forest. It provides functions to add vertices, query vertices by their ID (block's hash), query vertices by level, query the children of a vertex, and prune vertices by level (remove them from memory).
    • Finalizer: the finalizer uses the LevelledForest to store blocks. The Finalizer tracks the locked and finalized blocks. Furthermore, it evaluates whether a block is safe to vote for.
    • ForkChoice: implements the fork choice rule. Currently, NewestForkChoice always uses the quorum certificate (QC) with the largest view to build a new block (i.e. the fork a super-majority voted for most recently).
    • Forks is the highest level. It bundles the Finalizer and ForkChoice into one component.
  • Validator validates the HotStuff-relevant aspects of
    • QC: total weight of all signers is more than 2/3 of committee weight, validity of signatures, view number is strictly monotonously increasing
    • block proposal: from designated primary for the block's respective view, contains proposer's vote for its own block, QC in block is valid
    • vote: validity of signature, voter is has positive weight
  • VoteAggregator caches votes on a per-block basis and builds QC if enough votes have been accumulated.
  • Voter tracks the view of the latest vote and determines whether or not to vote for a block (by calling forks.IsSafeBlock)
  • Committee maintains the list of all authorized network members and their respective weight on a per-block basis. Furthermore, the committee contains the primary selection algorithm.
  • BlockProducer constructs the payload of a block, after the HotStuff core logic has decided which fork to extend

Implementation

We have translated the Chained HotStuff protocol into a state machine shown below. The state machine is implemented in EventHandler.

PaceMaker

The HotStuff state machine interacts with the PaceMaker, which triggers view changes. Conceptually, the PaceMaker interfaces with the EventHandler in two different modes:

  • [asynchronous] On timeouts, the PaceMaker will emit a timeout event, which is processed as any other event (such as incoming blocks or votes) through the EventLoop.
  • [synchronous] When progress is made following the happy-path business logic, the EventHandler will inform the PaceMaker about completing the respective processing step via a direct method call (see PaceMaker interface). If the PaceMaker changed the view in response, it returns a NewViewEvent which will be synchronously processed by the EventHandler.

Flow's PaceMaker is simple (compared to Libra's PaceMaker for instance). It solely relies on increasing the timeouts exponentially if no progress is made and exponentially decreasing timeouts on the happy path. The timeout values are limited by lower and upper-bounds to ensure that the PaceMaker can change from large to small timeouts in a reasonable number of views. The specific values for lower and upper timeout bounds are protocol-specified; we envision the bounds to be on the order of 1sec (lower bound) and multiple days (upper bound).

Progress, from the perspective of the PaceMaker is defined as entering view V for which the replica knows a QC with V = QC.view + 1. In other words, we transition into the next view due to reaching quorum in the last view.

A central, non-trivial functionality of the PaceMaker is to skip views. Specifically, given a QC with view qc.view, the Pacemaker will skip ahead to view qc.view + 1 if currentView ≤ qc.view.

Code structure

All relevant code implementing the core HotStuff business logic is contained in /consensus/hotstuff/ (folder containing this README). When starting to look into the code, we suggest starting with /consensus/hotstuff/event_loop.go and /consensus/hotstuff/event_handler.go.

Folder structure

All files in the /consensus/hotstuff/ folder, except for event_loop.go and follower_loop.go, are interfaces for HotStuff-related components. The concrete implementations for all HotStuff-relevant components are in corresponding sub-folders. For completeness, we list the component implemented in each subfolder below:

  • /consensus/hotstuff/blockproducer builds a block proposal for a specified QC, interfaces with the logic for assembling a block payload, combines all relevant fields into a new block proposal.
  • /consensus/hotstuff/committee maintains the list of all authorized network members and their respective weight on a per-block basis; contains the primary selection algorithm.
  • /consensus/hotstuff/eventhandler orchestrates all HotStuff components and implements the HotStuff state machine. The event handler is designed to be executed single-threaded.
  • /consensus/hotstuff/follower This component is only used by nodes that are not participating in the HotStuff committee. As Flow has dedicated node roles with specialized network functions, only a subset of nodes run the full HotStuff protocol. Nevertheless, all nodes need to be able to act on blocks being finalized. The approach we have taken for Flow is that block proposals are broadcast to all nodes (including non-committee nodes). Non-committee nodes locally determine block finality by applying HotStuff's finality rules. The HotStuff Follower contains the functionality to consume block proposals and trigger downstream processing of finalized blocks. The Follower does not actively participate in HotStuff.
  • /consensus/hotstuff/forks maintains an in-memory representation of all blocks b, whose view is larger or equal to the view of the latest finalized block (known to this specific HotStuff replica). It tracks the last finalized block, the currently locked block, evaluates whether it is safe to vote for a given block and provides a Fork-Choice when the replica is primary.
  • /consensus/hotstuff/helper contains broadly-used helper functions for testing
  • /consensus/hotstuff/integration integration tests for verifying correct interaction of multiple HotStuff replicas
  • /consensus/hotstuff/model contains the HotStuff data models, including block proposal, QC, etc. Many HotStuff data models are built on top of basic data models defined in /model/flow/.
  • /consensus/hotstuff/notifications: All relevant events within the HotStuff logic are exported though a notification system. While the notifications are not used HotStuff-internally, they notify other components within the same node of relevant progress and are used for collecting HotStuff metrics.
  • /consensus/hotstuff/pacemaker contains the implementation of Flow's basic PaceMaker, as described above.
  • /consensus/hotstuff/persister for performance reasons, the implementation maintains the consensus state largely in-memory. The persister stores the last entered view and the view of the latest voted block persistenlty on disk. This allows recovery after a crash without the risk of equivocation.
  • /consensus/hotstuff/runner helper code for starting and shutting down the HotStuff logic safely in a multithreaded environment.
  • /consensus/hotstuff/validator holds the logic for validating the HotStuff-relevant aspects of blocks, QCs, and votes
  • /consensus/hotstuff/verification contains integration of Flow's cryptographic primitives (signing and signature verification)
  • /consensus/hotstuff/voteaggregator caches votes on a per-block basis and builds a QC if enough votes have been accumulated.
  • /consensus/hotstuff/voter tracks the view of the latest vote and determines whether or not to vote for a block

Pending Extensions

  • BLS Aggregation of the StakingSignatures
  • include Epochs
  • upgrade PaceMaker to include Timeout Certificates
  • refactor crypto integration (code in verification and dependent modules) for better auditability

Telemetry

The HotStuff state machine exposes some details about its internal progress as notification through the hotstuff.Consumer. The following figure depicts at which points notifications are emitted.

We have implemented a telemetry system (hotstuff.notifications.TelemetryConsumer) which implements the Consumer interface. The TelemetryConsumer tracks all events as belonging together that were emitted during a path through the state machine. Each path through the state machine is identified by a unique id. Generally, the TelemetryConsumer could export the collected data to a variety of backends. For now, we export the data to a logger.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ComputeStakeThresholdForBuildingQC 

func ComputeStakeThresholdForBuildingQC(totalStake uint64) uint64

ComputeStakeThresholdForBuildingQC returns the stake that is minimally required for building a QC

Types

type BlockProducer 

type BlockProducer interface {

	// MakeBlockProposal builds a new HotStuff block proposal using the given view and
	// the given quorum certificate for its parent.
	MakeBlockProposal(qc *flow.QuorumCertificate, view uint64) (*model.Proposal, error)
}

BlockProducer is the component that is responsible for producing a new block proposal for HotStuff when we are the leader for a view.

type Committee 

type Committee interface {

	// Identities returns a IdentityList with legitimate HotStuff participants for the specified block.
	// The list of participants is filtered by the provided selector. The returned list of HotStuff participants
	//   * contains nodes that are allowed to sign the specified block (legitimate participants with NON-ZERO STAKE)
	//   * is ordered in the canonical order
	//   * contains no duplicates.
	// The list of all legitimate HotStuff participants for the specified block can be obtained by using `filter.Any`
	Identities(blockID flow.Identifier, selector flow.IdentityFilter) (flow.IdentityList, error)

	// Identity returns the full Identity for specified HotStuff participant.
	// The node must be a legitimate HotStuff participant with NON-ZERO STAKE at the specified block.
	// ERROR conditions:
	//    * ErrInvalidSigner if participantID does NOT correspond to a _staked_ HotStuff participant at the specified block.
	Identity(blockID flow.Identifier, participantID flow.Identifier) (*flow.Identity, error)

	// LeaderForView returns the identity of the leader for a given view.
	// CAUTION: per liveness requirement of HotStuff, the leader must be fork-independent.
	//          Therefore, a node retains its proposer view slots even if it is slashed.
	//          Its proposal is simply considered invalid, as it is not from a legitimate participant.
	// Returns the following expected errors for invalid inputs:
	//  * epoch containing the requested view has not been set up (protocol.ErrNextEpochNotSetup)
	//  * epoch is too far in the past (leader.InvalidViewError)
	LeaderForView(view uint64) (flow.Identifier, error)

	// Self returns our own node identifier.
	// TODO: ultimately, the own identity of the node is necessary for signing.
	//       Ideally, we would move the method for checking whether an Identifier refers to this node to the signer.
	//       This would require some refactoring of EventHandler (postponed to later)
	Self() flow.Identifier

	// DKG returns the DKG info for the given block.
	DKG(blockID flow.Identifier) (DKG, error)
}

Committee accounts for the fact that we might have multiple HotStuff instances (collector committees and main consensus committee). Each hostuff instance is supposed to have a dedicated Committee state. A Committee provides subset of the protocol.State, which is restricted to exactly those nodes that participate in the current HotStuff instance: the state of all legitimate HotStuff participants for the specified block. Legitimate HotStuff participants have NON-ZERO STAKE.

The intended use case is to support collectors running HotStuff within Flow. Specifically, the collectors produced their own blocks, independently of the Consensus Nodes (aka the main consensus). Given a collector block, some logic is required to find the main consensus block for determining the valid collector-HotStuff participants.

type Communicator 

type Communicator interface {

	// SendVote sends a vote for the given parameters to the specified recipient.
	SendVote(blockID flow.Identifier, view uint64, sigData []byte, recipientID flow.Identifier) error

	// BroadcastProposal broadcasts the given block proposal to all actors of
	// the consensus process.
	BroadcastProposal(proposal *flow.Header) error

	// BroadcastProposalWithDelay broadcasts the given block proposal to all actors of
	// the consensus process.
	// delay is to hold the proposal before broadcasting it. Useful to control the block production rate.
	BroadcastProposalWithDelay(proposal *flow.Header, delay time.Duration) error
}

Communicator is the component that allows the HotStuff core algorithm to communicate with the other actors of the consensus process.

type Consumer 

type Consumer interface {
	FinalizationConsumer

	// OnEventProcessed notifications are produced by the EventHandler when it is done processing
	// and hands control back to the EventLoop to wait for the next event.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnEventProcessed()

	// OnReceiveVote notifications are produced by the EventHandler when it starts processing a vote.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnReceiveVote(currentView uint64, vote *model.Vote)

	// OnReceiveProposal notifications are produced by the EventHandler when it starts processing a block.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnReceiveProposal(currentView uint64, proposal *model.Proposal)

	// OnEnteringView notifications are produced by the EventHandler when it enters a new view.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnEnteringView(viewNumber uint64, leader flow.Identifier)

	// OnQcTriggeredViewChange notifications are produced by PaceMaker when it moves to a new view
	// based on processing a QC. The arguments specify the qc (first argument), which triggered
	// the view change, and the newView to which the PaceMaker transitioned (second argument).
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnQcTriggeredViewChange(qc *flow.QuorumCertificate, newView uint64)

	// OnProposingBlock notifications are produced by the EventHandler when the replica, as
	// leader for the respective view, proposing a block.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnProposingBlock(proposal *model.Proposal)

	// OnVoting notifications are produced by the EventHandler when the replica votes for a block.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnVoting(vote *model.Vote)

	// OnQcConstructedFromVotes notifications are produced by the VoteAggregator
	// component, whenever it constructs a QC from votes.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnQcConstructedFromVotes(*flow.QuorumCertificate)

	// OnStartingTimeout notifications are produced by PaceMaker. Such a notification indicates that the
	// PaceMaker is now waiting for the system to (receive and) process blocks or votes.
	// The specific timeout type is contained in the TimerInfo.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnStartingTimeout(*model.TimerInfo)

	// OnReachedTimeout notifications are produced by PaceMaker. Such a notification indicates that the
	// PaceMaker's timeout was processed by the system. The specific timeout type is contained in the TimerInfo.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnReachedTimeout(timeout *model.TimerInfo)

	// OnQcIncorporated notifications are produced by ForkChoice
	// whenever a quorum certificate is incorporated into the consensus state.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnQcIncorporated(*flow.QuorumCertificate)

	// OnForkChoiceGenerated notifications are produced by ForkChoice whenever a fork choice is generated.
	// The arguments specify the view (first argument) of the block which is to be built and the
	// quorum certificate (second argument) that is supposed to be in the block.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnForkChoiceGenerated(uint64, *flow.QuorumCertificate)

	// OnDoubleVotingDetected notifications are produced by the Vote Aggregation logic
	// whenever a double voting (same voter voting for different blocks at the same view) was detected.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnDoubleVotingDetected(*model.Vote, *model.Vote)

	// OnInvalidVoteDetected notifications are produced by the Vote Aggregation logic
	// whenever an invalid vote was detected.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnInvalidVoteDetected(*model.Vote)
}

Consumer consumes outbound notifications produced by HotStuff and its components. Notifications are consensus-internal state changes which are potentially relevant to the larger node in which HotStuff is running. The notifications are emitted in the order in which the HotStuff algorithm makes the respective steps.

Implementations must:

  • be concurrency safe
  • be non-blocking
  • handle repetition of the same events (with some processing overhead).

type DKG 

type DKG interface {
	protocol.DKG
}

type EventHandler 

type EventHandler interface {

	// OnReceiveVote processes a vote received from another HotStuff consensus
	// participant.
	OnReceiveVote(vote *model.Vote) error

	// OnReceiveProposal processes a block proposal received fro another HotStuff
	// consensus participant.
	OnReceiveProposal(proposal *model.Proposal) error

	// OnLocalTimeout will check if there was a local timeout.
	OnLocalTimeout() error

	// TimeoutChannel returs a channel that sends a signal on timeout.
	TimeoutChannel() <-chan time.Time

	// Start will start the event handler.
	Start() error
}

EventHandler runs a state machine to process proposals, votes and local timeouts.

type EventLoop 

type EventLoop struct {
	// contains filtered or unexported fields
}

EventLoop buffers all incoming events to the hotstuff EventHandler, and feeds EventHandler one event at a time.

func NewEventLoop 

func NewEventLoop(log zerolog.Logger, metrics module.HotstuffMetrics, eventHandler EventHandler) (*EventLoop, error)

NewEventLoop creates an instance of EventLoop.

func (*EventLoop) Done 

func (el *EventLoop) Done() <-chan struct{}

Done implements interface module.ReadyDoneAware

func (*EventLoop) Ready 

func (el *EventLoop) Ready() <-chan struct{}

Ready implements interface module.ReadyDoneAware Method call will starts the EventLoop's internal processing loop. Multiple calls are handled gracefully and the event loop will only start once.

func (*EventLoop) SubmitProposal 

func (el *EventLoop) SubmitProposal(proposalHeader *flow.Header, parentView uint64)

SubmitProposal pushes the received block to the blockheader channel

func (*EventLoop) SubmitVote 

func (el *EventLoop) SubmitVote(originID flow.Identifier, blockID flow.Identifier, view uint64, sigData []byte)

SubmitVote pushes the received vote to the votes channel

type FinalizationConsumer 

type FinalizationConsumer interface {

	// OnBlockIncorporated notifications are produced by the Finalization Logic
	// whenever a block is incorporated into the consensus state.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnBlockIncorporated(*model.Block)

	// OnFinalizedBlock notifications are produced by the Finalization Logic whenever
	// a block has been finalized. They are emitted in the order the blocks are finalized.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnFinalizedBlock(*model.Block)

	// OnDoubleProposeDetected notifications are produced by the Finalization Logic
	// whenever a double block proposal (equivocation) was detected.
	// Prerequisites:
	// Implementation must be concurrency safe; Non-blocking;
	// and must handle repetition of the same events (with some processing overhead).
	OnDoubleProposeDetected(*model.Block, *model.Block)
}

FinalizationConsumer consumes outbound notifications produced by the finalization logic. Notifications represent finalization-specific state changes which are potentially relevant to the larger node. The notifications are emitted in the order in which the finalization algorithm makes the respective steps.

Implementations must:

  • be concurrency safe
  • be non-blocking
  • handle repetition of the same events (with some processing overhead).

type FollowerLogic 

type FollowerLogic interface {
	// FinalizedBlock returns the latest finalized block
	FinalizedBlock() *model.Block

	// AddBlock processes a block proposal
	AddBlock(proposal *model.Proposal) error
}

FollowerLogic runs a state machine to process proposals

type FollowerLoop 

type FollowerLoop struct {
	// contains filtered or unexported fields
}

FollowerLoop implements interface FollowerLoop

func NewFollowerLoop 

func NewFollowerLoop(log zerolog.Logger, followerLogic FollowerLogic) (*FollowerLoop, error)

NewFollowerLoop creates an instance of EventLoop

func (*FollowerLoop) Done 

func (fl *FollowerLoop) Done() <-chan struct{}

Done implements interface module.ReadyDoneAware

func (*FollowerLoop) Ready 

func (fl *FollowerLoop) Ready() <-chan struct{}

Ready implements interface module.ReadyDoneAware Method call will starts the FollowerLoop's internal processing loop. Multiple calls are handled gracefully and the follower will only start once.

func (*FollowerLoop) SubmitProposal 

func (fl *FollowerLoop) SubmitProposal(proposalHeader *flow.Header, parentView uint64)

SubmitProposal feeds a new block proposal (header) into the FollowerLoop. This method blocks until the proposal is accepted to the event queue.

Block proposals must be submitted in order, i.e. a proposal's parent must have been previously processed by the FollowerLoop.

type Forks 

type Forks interface {
	ForksReader

	// AddBlock adds the block to Forks. This might cause an update of the finalized block
	// and pruning of older blocks.
	// Handles duplicated addition of blocks (at the potential cost of additional computation time).
	// PREREQUISITE:
	// Forks must be able to connect `block` to its latest finalized block
	// (without missing interim ancestors). Otherwise, an error is raised.
	// When the new block causes the conflicting finalized blocks, it will return
	// Might error with ByzantineThresholdExceededError (e.g. if finalizing conflicting forks)
	AddBlock(block *model.Block) error

	// AddQC adds a quorum certificate to Forks.
	// Will error in case the block referenced by the qc is unknown.
	// Might error with ByzantineThresholdExceededError (e.g. if two conflicting QCs for the
	// same view are found)
	AddQC(qc *flow.QuorumCertificate) error

	// MakeForkChoice prompts the ForkChoice to generate a fork choice for the
	// current view `curView`. The fork choice is a qc that should be used for
	// building the primaries block.
	// It returns a qc and the block that the qc is pointing to.
	//
	// PREREQUISITE:
	// ForkChoice cannot generate ForkChoices retroactively for past views.
	// If used correctly, MakeForkChoice should only ever have processed QCs
	// whose view is smaller than curView, for the following reason:
	// Processing a QC with view v should result in the PaceMaker being in
	// view v+1 or larger. Hence, given that the current View is curView,
	// all QCs should have view < curView.
	// To prevent accidental misusage, ForkChoices will error if `curView`
	// is smaller than the view of any qc ForkChoice has seen.
	// Note that tracking the view of the newest qc is for safety purposes
	// and _independent_ of the fork-choice rule.
	MakeForkChoice(curView uint64) (*flow.QuorumCertificate, *model.Block, error)
}

Forks encapsulated Finalization Logic and ForkChoice rule in one component. Forks maintains an in-memory data-structure of all blocks whose view-number is larger or equal to the latest finalized block. The latest finalized block is defined as the finalized block with the largest view number. When adding blocks, Forks automatically updates its internal state (including finalized blocks). Furthermore, blocks whose view number is smaller than the latest finalized block are pruned automatically.

PREREQUISITES: Forks expects that only blocks are added that can be connected to its latest finalized block (without missing interim ancestors). If this condition is violated, Forks will raise an error and ignore the block.

type ForksReader 

type ForksReader interface {

	// IsSafeBlock returns true if block is safe to vote for
	// (according to the definition in https://arxiv.org/abs/1803.05069v6).
	//
	// In the current architecture, the block is stored _before_ evaluating its safety.
	// Consequently, IsSafeBlock accepts only known, valid blocks. Should a block be
	// unknown (not previously added to Forks) or violate some consistency requirements,
	// IsSafeBlock errors. All errors are fatal.
	IsSafeBlock(block *model.Block) bool

	// GetBlocksForView returns all BlockProposals at the given view number.
	GetBlocksForView(view uint64) []*model.Block

	// GetBlock returns (BlockProposal, true) if the block with the specified
	// id was found (nil, false) otherwise.
	GetBlock(id flow.Identifier) (*model.Block, bool)

	// FinalizedView returns the largest view number where a finalized block is known
	FinalizedView() uint64

	// FinalizedBlock returns the finalized block with the largest view number
	FinalizedBlock() *model.Block
}

ForksReader only reads the forks' state

type PaceMaker 

type PaceMaker interface {

	// CurView returns the current view.
	CurView() uint64

	// UpdateCurViewWithQC will check if the given QC will allow PaceMaker to fast
	// forward to QC.view+1. If PaceMaker incremented the current View, a NewViewEvent will be returned.
	UpdateCurViewWithQC(qc *flow.QuorumCertificate) (*model.NewViewEvent, bool)

	// UpdateCurViewWithBlock will check if the given block will allow PaceMaker to fast forward
	// to the BlockProposal's view. If yes, the PaceMaker will update it's internal value for
	// CurView and return a NewViewEvent.
	//
	// The parameter `nextPrimary` indicates to the PaceMaker whether or not this replica is the
	// primary for the NEXT view taking block.view as reference.
	// True corresponds to this replica being the next primary.
	UpdateCurViewWithBlock(block *model.Block, isLeaderForNextView bool) (*model.NewViewEvent, bool)

	// TimeoutChannel returns the timeout channel for the CURRENTLY ACTIVE timeout.
	// Each time the pace maker starts a new timeout, this channel is replaced.
	TimeoutChannel() <-chan time.Time

	// OnTimeout is called when a timeout, which was previously created by the PaceMaker, has
	// looped through the event loop. When used correctly, OnTimeout will always return
	// a NewViewEvent.
	// It is the responsibility of the calling code to ensure that NO STALE timeouts are
	// delivered to the PaceMaker.
	OnTimeout() *model.NewViewEvent

	// Start starts the PaceMaker (i.e. the timeout for the configured starting value for view).
	Start()

	// BlockRateDelay
	BlockRateDelay() time.Duration
}

PaceMaker for HotStuff. The component is passive in that it only reacts to method calls. The PaceMaker does not perform state transitions on its own. Timeouts are emitted through channels. Each timeout has its own dedicated channel, which is garbage collected after the respective state has been passed. It is the EventHandler's responsibility to pick up timeouts from the currently active TimeoutChannel process them first and subsequently inform the PaceMaker about processing the timeout. Specifically, the intended usage pattern for the TimeoutChannels is as follows:

• Each time the PaceMaker starts a new timeout, it created a new TimeoutChannel

• The channel for the CURRENTLY ACTIVE timeout is returned by PaceMaker.TimeoutChannel()

  • Each time the EventHandler processes an event, the EventHandler might call into PaceMaker potentially resulting in a state transition and the PaceMaker starting a new timeout
  • Hence, after processing any event, EventHandler should retrieve the current TimeoutChannel from the PaceMaker.

For Example: 

for {
		timeoutChannel := el.eventHandler.TimeoutChannel()
		select {
		   case <-timeoutChannel:
		    	el.eventHandler.OnLocalTimeout()
		   case <other events>
		}
}

type Persister 

type Persister interface {

	// GetStarted will retrieve the last started view.
	GetStarted() (uint64, error)

	// GetVoted will retrieve the last voted view.
	GetVoted() (uint64, error)

	// PutStarted persists the last started view.
	PutStarted(view uint64) error

	// PutVoted persists the last voted view.
	PutVoted(view uint64) error
}

Persister is responsible for persisting state we need to bootstrap after a restart or crash.

type Signer 

type Signer interface {
	// CreateProposal creates a proposal for the given block.
	CreateProposal(block *model.Block) (*model.Proposal, error)

	// CreateVote creates a vote for the given block.
	CreateVote(block *model.Block) (*model.Vote, error)

	// CreateQC creates a QC for the given block.
	CreateQC(votes []*model.Vote) (*flow.QuorumCertificate, error)
}

Signer is responsible for creating votes, proposals and QC's for a given block.

type SignerVerifier 

type SignerVerifier interface {
	Signer
	Verifier
}

SignerVerifier can sign and verify HotStuff entities.

type Validator 

type Validator interface {

	// ValidateQC checks the validity of a QC for a given block.
	ValidateQC(qc *flow.QuorumCertificate, block *model.Block) error

	// ValidateProposal checks the validity of a proposal.
	ValidateProposal(proposal *model.Proposal) error

	// ValidateVote checks the validity of a vote for a given block.
	ValidateVote(vote *model.Vote, block *model.Block) (*flow.Identity, error)
}

Validator provides functions to validate QC, proposals and votes.

type Verifier 

type Verifier interface {

	// VerifyVote checks the validity of a vote for the given block.
	// The first return value indicates whether `sigData` is a valid signature
	// from the provided voter identity. It is the responsibility of the
	// calling code to ensure that `voter` is authorized to vote.
	// The implementation returns the following sentinel errors:
	// * verification.ErrInvalidFormat if the signature has an incompatible format.
	// * unexpected errors should be treated as symptoms of bugs or uncovered
	//   edge cases in the logic (i.e. as fatal)
	VerifyVote(voter *flow.Identity, sigData []byte, block *model.Block) (bool, error)

	// VerifyQC checks the validity of a QC for the given block.
	// The first return value indicates whether `sigData` is a valid signature
	// from the provided voter identity. It is the responsibility of the
	// calling code to ensure that `voter` is authorized to vote.
	// It is the responsibility of the calling code to ensure that `voters`
	// only contains authorized nodes (without duplicates).
	// The implementation returns the following sentinel errors:
	// * verification.ErrInvalidFormat if the signature has an incompatible format.
	// * unexpected errors should be treated as symptoms of bugs or uncovered
	//   edge cases in the logic (i.e. as fatal)
	VerifyQC(voters flow.IdentityList, sigData []byte, block *model.Block) (bool, error)
}

Verifier is the component responsible for the cryptographic integrity of votes, proposals and QC's against w.r.t. the block they are signing. Overall, there are two criteria for the validity of a vote and QC: 

(1) the signer ID(s) must correspond to authorized consensus participants
(2) the signature must be cryptographically valid.

Note that Verifier only implements (2). This API design allows to decouple 

(i) the common logic for checking that a super-majority of the consensus
    committee voted

(ii) the handling of combined staking+RandomBeacon votes (consensus nodes) 

vs only staking votes (collector nodes)

On the one hand, this API design makes code less concise, as the two checks are now distributed over API boundaries. On the other hand, we can avoid repeated Identity lookups in the implementation, which increases performance.

type VoteAggregator 

type VoteAggregator interface {

	// StorePendingVote is used to store a vote for a block for which we don't
	// have a block yet.
	StorePendingVote(vote *model.Vote) (bool, error)

	// StoreVoteAndBuildQC will store a vote and build the QC related to the
	// voted upon block if enough votes can be accumulated.
	StoreVoteAndBuildQC(vote *model.Vote, block *model.Block) (*flow.QuorumCertificate, bool, error)

	// StoreProposerVote stores the vote of the proposer of the block and is
	// used to separate vote and block handling.
	StoreProposerVote(vote *model.Vote) bool

	// BuildQCOnReceivedBlock will try to build a QC for the received block in
	// case enough votes can be accumulated for it.
	BuildQCOnReceivedBlock(block *model.Block) (*flow.QuorumCertificate, bool, error)

	// PruneByView will remove any data held for the provided view.
	PruneByView(view uint64)
}

VoteAggregator aggregates votes and produces quorum certificates.

type Voter 

type Voter interface {

	// ProduceVoteIfVotable will produce a vote for the given block if voting on
	// the given block is a valid action.
	ProduceVoteIfVotable(block *model.Block, curView uint64) (*model.Vote, error)
}

Voter produces votes for the given block

Source Files

View all Source files

Directories

Path Synopsis
(c) 2020 Dapper Labs - ALL RIGHTS RESERVED
 (c) 2020 Dapper Labs - ALL RIGHTS RESERVED
leader
finalizer
forkchoice
test
pubsub
timeout

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.