process

package
v0.4.8 Latest Latest
Warning

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

 Go to latest Published: Jun 15, 2021 License: GPL-3.0 Imports: 4 Imported by: 0

Documentation

Overview

Package process implements the Byzantine fault tolerant consensus algorithm described by "The latest gossip of BFT consensus" (Buchman et al.), which can be found at https://arxiv.org/pdf/1807.04938.pdf. It makes extensive use of dependency injection, and concrete implementations must be careful to meet all of the requirements specified by the interface, otherwise the correctness of the consensus algorithm can be broken.

Index

Constants

View Source 
const (
	OnceFlagTimeoutPrecommitUponSufficientPrecommits = OnceFlag(1)
	OnceFlagTimeoutPrevoteUponSufficientPrevotes     = OnceFlag(2)
	OnceFlagPrecommitUponSufficientPrevotes          = OnceFlag(4)
)

Enumerate all OnceFlag values.

View Source 
const (
	Proposing     = Step(0)
	Prevoting     = Step(1)
	Precommitting = Step(2)
)

Enumerate step values.

View Source 
const (
	// InvalidRound is a reserved int64 that represents an invalid Round. It is
	// used when a Process is trying to represent that it does have have a
	// LockedRound or ValidRound.
	InvalidRound = Round(-1)
)

Variables

View Source 
var (
	// DefaulHeight is set to 1, because the genesis block is assumed to exist
	// at Height 0.
	DefaultHeight = Height(1)
	DefaultRound  = Round(0)
)
View Source 
var (
	// NilValue is a reserved hash that represents when a Process is
	// prevoting/precommitting to nothing (i.e. the Process wants to progress to
	// the next Round).
	NilValue = Value(id.Hash{})
)

Functions

func NewPrecommitHash added in v0.4.0 

func NewPrecommitHash(height Height, round Round, value Value) (id.Hash, error)

NewPrecommitHash receives fields of a precommit message and hashes the message

func NewPrecommitHashWithBuffer added in v0.4.0 

func NewPrecommitHashWithBuffer(height Height, round Round, value Value, data []byte) (id.Hash, error)

NewPrecommitHashWithBuffer receives fields of a precommit message, with a bytes buffer and hashes the message

func NewPrevoteHash added in v0.4.0 

func NewPrevoteHash(height Height, round Round, value Value) (id.Hash, error)

NewPrevoteHash receives fields of a prevote message and hashes the message

func NewPrevoteHashWithBuffer added in v0.4.0 

func NewPrevoteHashWithBuffer(height Height, round Round, value Value, data []byte) (id.Hash, error)

NewPrevoteHashWithBuffer receives fields of a prevote message, with a bytes buffer and hashes the message

func NewProposeHash added in v0.4.0 

func NewProposeHash(height Height, round Round, validRound Round, value Value) (id.Hash, error)

NewProposeHash receives fields of a propose message and hashes the message

func NewProposeHashWithBuffer added in v0.4.0 

func NewProposeHashWithBuffer(height Height, round Round, validRound Round, value Value, data []byte) (id.Hash, error)

NewProposeHashWithBuffer receives fields of a propose message, with a bytes buffer and hashes the message

Types

type Broadcaster 

type Broadcaster interface {
	BroadcastPropose(Propose)
	BroadcastPrevote(Prevote)
	BroadcastPrecommit(Precommit)
}

A Broadcaster is used to broadcast Propose, Prevote, and Precommit messages to all Processes in the consensus algorithm, including the Process that initiated the broadcast. It is assumed that all messages between correct Processes are eventually delivered, although no specific order is assumed.

Once a Value has been broadcast as part of a Propose, Prevote, or Precommit message, different Values must not be broadcast for that same message type with the same Height and Round. The same restriction applies to valid Rounds broadcast with a Propose message.

type Catcher added in v0.4.0 

type Catcher interface {
	CatchDoublePropose(Propose, Propose)
	CatchDoublePrevote(Prevote, Prevote)
	CatchDoublePrecommit(Precommit, Precommit)
	CatchOutOfTurnPropose(Propose)
}

A Catcher is used to catch bad behaviour in other Processes. For example, when the same Process sends two different Proposes at the same Height and Round. Not all instances of bad behaviour are caught by the Process. For example, when a Process moves to a new height, it will stop processing messages from previous heights, and so malicious behaviour that occurs in those dropped messages will not be caught. If it is required that all bad behaviour is caught, then additional checks must be made — outside the context of Hyperdrive — before passing messages to the Process.

type Committer added in v0.4.0 

type Committer interface {
	Commit(Height, Value)
}

A Committer is used to emit Values that are committed. The commitment of a new Value implies that all correct Processes agree on this Value at this Height, and will never revert.

type Height added in v0.4.0 

type Height int64

Height defines a typedef for int64 values that represent the height of a Value at which the consensus algorithm is attempting to reach consensus.

type MessageType 

type MessageType int8

MessageType enumerates the various types of Hyperdrive messages. 

const (
	// MessageTypePropose is the message type for a propose message.
	MessageTypePropose MessageType = 1
	// MessageTypePrevote is the message type for a prevote message.
	MessageTypePrevote MessageType = 2
	// MessageTypePrecommit is the message type for a precommit message.
	MessageTypePrecommit MessageType = 3
	// MessageTypeTimeout is the message type for a timeout message.
	MessageTypeTimeout MessageType = 4
)

func (MessageType) String added in v0.4.3 

func (ty MessageType) String() string

String implements the Stringer interface.

type OnceFlag added in v0.4.0 

type OnceFlag uint16

A OnceFlag is used to guarantee that events only happen once in any given Round.

type Precommit 

type Precommit struct {
	Height Height `json:"height"`
	Round  Round  `json:"round"`
	Value  Value  `json:"value"`

	From id.Signatory `json:"from"`
}

A Precommit is sent by every correct Process at most once per Round. It is the second step of reaching consensus. Informally, if a correct Process receives 2F+1 Precommits for a Value, then it will commit to that Value and progress to the next Height. However, there are many other conditions which can cause a Process to Precommit. See the Process for more information.

func (Precommit) Equal added in v0.4.0 

func (precommit Precommit) Equal(other *Precommit) bool

Equal compares two Precommits. If they are equal, then it return true, otherwise it returns false. The signatures are not checked for equality, because signatures include randomness.

func (Precommit) Marshal added in v0.4.0 

func (precommit Precommit) Marshal(buf []byte, rem int) ([]byte, int, error)

Marshal this message into binary.

func (Precommit) SizeHint added in v0.4.0 

func (precommit Precommit) SizeHint() int

SizeHint returns the number of bytes required to represent this message in binary.

func (*Precommit) Unmarshal added in v0.4.0 

func (precommit *Precommit) Unmarshal(buf []byte, rem int) ([]byte, int, error)

Unmarshal binary into this message.

type Prevote 

type Prevote struct {
	Height Height `json:"height"`
	Round  Round  `json:"round"`
	Value  Value  `json:"value"`

	From id.Signatory `json:"from"`
}

A Prevote is sent by every correct Process at most once per Round. It is the first step of reaching consensus. Informally, if a correct Process receives 2F+1 Precommits for a Value, then it will Precommit to that Value. However, there are many other conditions which can cause a Process to Prevote. See the Process for more information.

func (Prevote) Equal added in v0.4.0 

func (prevote Prevote) Equal(other *Prevote) bool

Equal compares two Prevotes. If they are equal, then it return true, otherwise it returns false. The signatures are not checked for equality, because signatures include randomness.

func (Prevote) Marshal added in v0.4.0 

func (prevote Prevote) Marshal(buf []byte, rem int) ([]byte, int, error)

Marshal this message into binary.

func (Prevote) SizeHint added in v0.4.0 

func (prevote Prevote) SizeHint() int

SizeHint returns the number of bytes required to represent this message in binary.

func (*Prevote) Unmarshal added in v0.4.0 

func (prevote *Prevote) Unmarshal(buf []byte, rem int) ([]byte, int, error)

Unmarshal binary into this message.

type Process 

type Process struct {

	// State of the Process.
	State `json:"state"`
	// contains filtered or unexported fields
}

A Process is a deterministic finite state automaton that communicates with other Processes to implement a Byzantine fault tolerant consensus algorithm. It is intended to be used as part of a larger component that implements a Byzantine fault tolerant replicated state machine.

All messages from previous and future Heights will be ignored. The component using the Process should buffer all messages from future Heights so that they are not lost. It is assumed that this component will also handle the authentication and rate-limiting of messages.

Processes are not safe for concurrent use. All methods must be called by the same goroutine that allocates and starts the Process.

func New 

func New(
	whoami id.Signatory,
	f int,
	timer Timer,
	scheduler Scheduler,
	proposer Proposer,
	validator Validator,
	broadcaster Broadcaster,
	committer Committer,
	catcher Catcher,
) Process

New returns a new Process that is in the default State with empty message logs.

func NewWithCurrentHeight added in v0.4.8 

func NewWithCurrentHeight(
	whoami id.Signatory,
	height Height,
	f int,
	timer Timer,
	scheduler Scheduler,
	proposer Proposer,
	validator Validator,
	broadcaster Broadcaster,
	committer Committer,
	catcher Catcher,
) Process

NewWithCurrentHeight returns a new Process that starts at the given height with empty message logs.

func (Process) Marshal added in v0.4.0 

func (p Process) Marshal(buf []byte, rem int) ([]byte, int, error)

Marshal this Process into binary.

func (*Process) OnTimeoutPrecommit added in v0.4.0 

func (p *Process) OnTimeoutPrecommit(height Height, round Round)

OnTimeoutPrecommit is used to notify the Process that a timeout has been activated. It must only be called after the TimeoutPrecommit method in the Timer has been called.

L65: 

Function OnTimeoutPrecommit(height, round)
	if height = currentHeight ∧ round = currentRound then
		StartRound(currentRound + 1)

func (*Process) OnTimeoutPrevote added in v0.4.0 

func (p *Process) OnTimeoutPrevote(height Height, round Round)

OnTimeoutPrevote is used to notify the Process that a timeout has been activated. It must only be called after the TimeoutPrevote method in the Timer has been called.

L61: 

Function OnTimeoutPrevote(height, round)
	if height = currentHeight ∧ round = currentRound ∧ currentStep = prevote then
		broadcast〈PRECOMMIT, currentHeight, currentRound, nil
		currentStep ← precommitting

func (*Process) OnTimeoutPropose added in v0.4.0 

func (p *Process) OnTimeoutPropose(height Height, round Round)

OnTimeoutPropose is used to notify the Process that a timeout has been activated. It must only be called after the TimeoutPropose method in the Timer has been called.

L57: 

Function OnTimeoutPropose(height, round)
	if height = currentHeight ∧ round = currentRound ∧ currentStep = propose then
		broadcast〈PREVOTE, currentHeight, currentRound, nil
		currentStep ← prevote

func (*Process) Precommit added in v0.4.0 

func (p *Process) Precommit(precommit Precommit)

Precommit is used to notify the Process that a Precommit message has been received (this includes Precommit messages that the Process itself has broadcast). All conditions that could be opened by the receipt of a Precommit message will be tried.

func (*Process) Prevote added in v0.4.0 

func (p *Process) Prevote(prevote Prevote)

Prevote is used to notify the Process that a Prevote message has been received (this includes Prevote messages that the Process itself has broadcast). All conditions that could be opened by the receipt of a Prevote message will be tried.

func (*Process) Propose added in v0.4.0 

func (p *Process) Propose(propose Propose)

Propose is used to notify the Process that a Propose message has been received (this includes Propose messages that the Process itself has broadcast). All conditions that could be opened by the receipt of a Propose message will be tried.

func (Process) SizeHint added in v0.4.0 

func (p Process) SizeHint() int

SizeHint returns the number of bytes required to represent this Process in binary.

func (*Process) Start 

func (p *Process) Start()

Start the Process.

L10: 

upon start do
	StartRound(0)

func (*Process) StartRound 

func (p *Process) StartRound(round Round)

StartRound will progress the Process to a new Round. It does not assume that the Height has changed. Since this changes the current Round and the current Step, most of the condition methods will be retried at the end (by way of defer).

L11: 

Function StartRound(round)
	currentRound ← round
	currentStep ← propose
	if proposer(currentHeight, currentRound) = p then
		if validValue != nil then
			proposal ← validValue
		else
			proposal ← getValue()
		broadcast〈PROPOSAL, currentHeight, currentRound, proposal, validRound〉
	else
		schedule OnTimeoutPropose(currentHeight, currentRound) to be executed after timeoutPropose(currentRound)

func (*Process) Unmarshal added in v0.4.0 

func (p *Process) Unmarshal(buf []byte, rem int) ([]byte, int, error)

Unmarshal from binary into this Process.

type Propose 

type Propose struct {
	Height     Height `json:"height"`
	Round      Round  `json:"round"`
	ValidRound Round  `json:"validRound"`
	Value      Value  `json:"value"`

	From id.Signatory `json:"from"`
}

A Propose message is sent by the proposer Process at most once per Round. The Scheduler interfaces determines which Process is the proposer at any given Height and Round.

func (Propose) Equal added in v0.4.0 

func (propose Propose) Equal(other *Propose) bool

Equal compares two Proposes. If they are equal, then it return true, otherwise it returns false. The signatures are not checked for equality, because signatures include randomness.

func (Propose) Marshal added in v0.4.0 

func (propose Propose) Marshal(buf []byte, rem int) ([]byte, int, error)

Marshal this message into binary.

func (Propose) SizeHint added in v0.4.0 

func (propose Propose) SizeHint() int

SizeHint returns the number of bytes required to represent this message in binary.

func (*Propose) Unmarshal added in v0.4.0 

func (propose *Propose) Unmarshal(buf []byte, rem int) ([]byte, int, error)

Unmarshal binary into this message.

type Proposer 

type Proposer interface {
	Propose(Height, Round) Value
}

A Proposer is used to propose new Values for consensus. A Proposer must only ever return a valid Value, and once it returns a Value, it must never return a different Value for the same Height and Round.

type Round added in v0.4.0 

type Round int64

Round defines a typedef for int64 values that represent the round of a Value at which the consensus algorithm is attempting to reach consensus.

type Scheduler 

type Scheduler interface {
	Schedule(height Height, round Round) id.Signatory
}

A Scheduler is used to determine which Process should be proposing a Value at the given Height and Round. A Scheduler must be derived solely from the Height, Round, and Values on which all correct Processes have already achieved consensus.

type State 

type State struct {
	CurrentHeight Height `json:"currentHeight"`
	CurrentRound  Round  `json:"currentRound"`
	CurrentStep   Step   `json:"currentStep"`
	LockedValue   Value  `json:"lockedValue"` // The most recent value for which a precommit message has been sent.
	LockedRound   Round  `json:"lockedRound"` // The last round in which the process sent a precommit message that is not nil.
	ValidValue    Value  `json:"validValue"`  // The most recent possible decision value.
	ValidRound    Round  `json:"validRound"`  // The last round in which valid value is updated.

	// ProposeLogs store the Proposes for all Rounds.
	ProposeLogs map[Round]Propose `json:"proposeLogs"`
	// ProposeIsValid is a map that stores whether the received proposal for the
	// consensus round is valid or not
	ProposeIsValid map[Round]bool
	// PrevoteLogs store the Prevotes for all Processes in all Rounds.
	PrevoteLogs map[Round]map[id.Signatory]Prevote `json:"prevoteLogs"`
	// PrecommitLogs store the Precommits for all Processes in all Rounds.
	PrecommitLogs map[Round]map[id.Signatory]Precommit `json:"precommitLogs"`
	// OnceFlags prevents events from happening more than once.
	OnceFlags map[Round]OnceFlag `json:"onceFlags"`
	// TraceLogs store the unique signatories from which we have received a msg
	// (propose/prevote/precommit) in a specific round for the current height
	TraceLogs map[Round]map[id.Signatory]bool
}

The State of a Process. It should be saved after every method call on the Process, but should not be saved during method calls (interacting with the State concurrently is unsafe). It is worth noting that the State does not contain a decision array, because it delegates this responsibility to the Committer interface.

L1: 

Initialization:
    currentHeight := 0 /* current height, or consensus instance we are currently executing */
    currentRound  := 0 /* current round number */
    currentStep ∈ {propose, prevote, precommit}
    decision[]  := nil
    lockedValue := nil
    lockedRound := −1
    validValue  := nil
    validRound  := −1

func DefaultState 

func DefaultState() State

DefaultState returns a State with all fields set to their default values.

func (State) Clone added in v0.4.0 

func (state State) Clone() State

Clone the State into another copy that can be modified without affecting the original.

func (State) Equal 

func (state State) Equal(other *State) bool

Equal compares two States. If they are equal, then it returns true, otherwise it returns false. Message logs and once-flags are ignored for the purpose of equality.

func (State) Marshal added in v0.4.0 

func (state State) Marshal(buf []byte, rem int) ([]byte, int, error)

Marshal implements the Surge Marshaler interface

func (State) SizeHint added in v0.4.0 

func (state State) SizeHint() int

SizeHint implements the Surge SizeHinter interface, and returns the byte size of the state instance

func (*State) Unmarshal added in v0.4.0 

func (state *State) Unmarshal(buf []byte, rem int) ([]byte, int, error)

Unmarshal implements the Surge Unmarshaler interface

func (State) WithCurrentHeight added in v0.4.1 

func (state State) WithCurrentHeight(height Height) State

WithCurrentHeight returns a process state having modified its current height with the given height

type Step 

type Step uint8

Step defines a typedef for uint8 values that represent the step of the state of a Process partaking in the consensus algorithm.

type Timer 

type Timer interface {
	// TimeoutPropose is called when the Process needs its OnTimeoutPropose
	// method called after a timeout. The timeout should be proportional to the
	// Round.
	TimeoutPropose(Height, Round)
	// TimeoutPrevote is called when the Process needs its OnTimeoutPrevote
	// method called after a timeout. The timeout should be proportional to the
	// Round.
	TimeoutPrevote(Height, Round)
	// TimeoutPrecommit is called when the Process needs its OnTimeoutPrecommit
	// method called after a timeout. The timeout should be proportional to the
	// Round.
	TimeoutPrecommit(Height, Round)
}

A Timer is used to schedule timeout events.

type Validator 

type Validator interface {
	Valid(Height, Round, Value) bool
}

A Validator is used to validate a proposed Value. Processes are not required to agree on the validity of a Value.

type Value added in v0.4.0 

type Value id.Hash

Value defines a typedef for hashes that represent the hashes of proposed values in the consensus algorithm. In the context of a blockchain, a Value would be a block.

func (*Value) Equal added in v0.4.0 

func (v *Value) Equal(other *Value) bool

Equal compares two Values. If they are equal, then it returns true, otherwise it returns false.

func (Value) MarshalJSON added in v0.4.1 

func (v Value) MarshalJSON() ([]byte, error)

MarshalJSON serialises a process value to JSON format

func (Value) String added in v0.4.1 

func (v Value) String() string

String implements the Stringer interface for process value

func (*Value) UnmarshalJSON added in v0.4.1 

func (v *Value) UnmarshalJSON(data []byte) error

UnmarshalJSON deserialises a JSON format to process value

Source Files

View all Source files

Directories

Path Synopsis

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.