agreement

package
v0.0.0-...-adf39d2 Latest Latest
Warning

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

 Go to latest Published: Apr 26, 2024 License: AGPL-3.0 Imports: 30 Imported by: 1

README

Agreement

           ^_^        :o)
            o          o
    :-O                      ಠ_ಠ
     o [B]->                  o
:-)     |                        >:(
 o      V                         o
    x_x                      uwu
     o                        o
           :-)        :-3
            o          o

The Algorand Byzantine Agreement protocol enables all nodes to consistently update the state of the system.

The agreement.Service establishes a consensus on the ordering of Blocks. This ordering is defined by a Round number, which indexes into the ordered log of Blocks.

Clients instantiate an agreement.Service by providing it several parameters:

  • Ledger represents a data store which supports the reading and writing of data stored within Blocks.
  • BlockFactory produces Blocks for a given round.
  • BlockValidator validates Blocks for a given round.
  • KeyManager holds the participation keys necessary to participate in the protocol.
  • Network provides an abstraction over the underlying network.
  • timers.Clock provides timekeeping services for timeouts.
  • db.Accessor provides persistent storage for internal state.

Blocks for which consensus is completed are written using Ledger.EnsureBlock alongside Certificate objects, which are cryptographic proofs that a Block was confirmed for a given round.

If Ledger and db.Accessor provide crash-safe storage, agreement will also recover safely after crashes.

Specification

The specification for the protocol implemented by this package is located here.

Optimizations from and other deviations from the spec will be noted throughout this file.

Terminology

Certain terms in this implementation are used as shorthands for specific concepts:

  • "Threshold" and "quorum" both refer to the total weight of votes needed to form a bundle for a given value.
  • A "proposal-vote" refers to a vote whose step is "propose"=0.
  • A "payload" refers to the body of a proposal which contains, among other fields, a Block.
  • "Freshness" generally refers to the relevance of some message or event. Message relay rules which refer to a round, period, or step may be referred to as freshness rules. Freshness may also be used to describe the relevance of bundles.
  • The "frozen" value in a period p refers to the proposal-value in the proposal-vote which was observed by the state machine to have the lowest credential (i.e., mu(S, r, p)).
  • The "staging" value in a period p refers to the proposal-value which received a quorum of soft votes (i.e., sigma(S, r, p)).
  • Additional terminology is described in the agreement service doc.

Design

At the top level, an agreement.Service encapsulates the parameters and the goroutines which execute the protocol.

Our implementation divides its tasks into two components: a concurrent component, which communicates with the network, disk, and timeouts, and performs expensive CPU operations, and a serialized state machine, which executes protocol logic and makes decisions on what abstract actions to take.

These two components communicate with each other using the abstractions of events and actions. event objects describe communication from the concurrent component to the state machine, encapsulating external input to the machine. For each input event, the state machine emits an output []action, which lists a sequence of control operations and operations which are potentially observable by the outside universe. Communication occurs between these components through a pair of Go channels in service.demuxLoop and service.mainLoop.

events are also used for internal communication between components of the state machine.

The concurrent and serialized components share a variety of static data structures, such as vote, bundle, and proposal. These data types have distinct unauthenticated versions, which allows routines to specify that they accept untrusted input.

Concurrent Component

The demux object demultiplexes over a variety of channels which all represent inputs to the system. Inputs include:

  • Receiving a message from the Network
  • Receiving a timeout from the Clock
  • Notification to stop waiting for a block in the current Round (Ledger.Wait)
  • Authenticated messages from the cryptoVerifier

The cryptoVerifier parallelizes expensive cryptographic operations such as authentication of votes, bundles, and proposal payloads so as to maximize CPU core utilization.

A special case of the node behavior is encapsulated in the pseudonode: to increase ease of testing and to minimize code duplication, the state machine produces votes and proposals by directing the pseudonode to create them from participation key data. The pseudonode then directs the votes and proposals back to the state machine, as if they arrived from some external source. The state machine validates these messages in the same way it validates real network messages and relays them back into the network as appropriate.

Spec Notes: Additional Events

Because signature verification is expected to be a computational bottleneck in the agreement code, it executes concurrently with respect to the state machine. As a result, the relay rules described in the specification of the protocol are altered slightly: for instance, properties of messages are checked twice when determining whether to ignore them: once before cryptographic verification, and once after cryptographic verification. Checking before cryptographic verification is not strictly necessary but is an optimization that reduces CPU costs in non-adversarial cases; e.g., duplicate votes are discarded before signature verification is attempted.

In the specification, each participant in the agreement protocol is associated with a single set of keys. In practice, nodes may wish to participate on behalf of many keys simultaneously. These keys are encapsulated in the KeyManager, and the pseudonode allows the agreement protocol to multiplex across these keys. For all intents and purposes, these keys may be modelled as distinct participants which all exhibit identical behavior, and whose messages are all serialized through a single participant. For instance, if two keys are both selected to propose a block, then this node may or may not transmit the block belonging to the key with the lower-priority credential.

This implementation thus extends the set of "external" events handled by the state machine. In addition to handling timeouts and network events, the state machine thus also handles concurrent writes to the Ledger via Wait, and it handles the output of cryptographic verification concurrently. Moreover, the implementation abstracts over multiple keys by generating synthetic network events from the pseudonode.

Serialized State Machine

The logic of the agreement protocol is implemented as a state machine. This state machine is composed of many smaller state machines, which represent different subtasks required by the protocol. All state machines communicate with each other by sending events to each other and by receiving events as replies (except for player, which is at the root of the state machine tree). This communication takes place through the router, which relays messages between machines. After it receives a message, a state machine will handle it, producing an event in response and possibly updating its own state.

For the router to route information correctly, all instances of all state machines must be uniquely identified for the router. Every type of state machine corresponds to a unique stateMachineTag (<machine>.T()). Certain state machines have many instances; for instance, there is one machine which tracks votes for each step, and there is one machine which tracks proposals for each period. These instances are distinguished from each other by a (round, period, step)-triplet. For a given type of state machine, the less specific fields in the triplet are ignored: for example, to send a message to the state machine handling proposals in round 100, period 2, both (100, 2, 0) and (100, 2, 6) identify this instance, since it handles messages for any step in period 2.

State machines are arranged hierarchically in the state machine tree. At the top of the tree is the player, which has two children: the root vote machine and the root proposal machine. The vote machines and the proposal machines are both hierarchically arranged first by round, then by period, and finally by step. Thus the hierarchy is as follows:

  • player
    • vote
      • vote round 0
        • vote (round, period) (0, 0)
          • vote (round, period, step) (0, 0, 0)
          • vote (round, period, step) (0, 0, 1)
          • ...
        • vote (round, period) (0, 1)
        • ...
      • vote round 1
      • ...
    • proposal
      • proposal round 0
        • proposal (round, period) (0, 0)
          • proposal (round, period, step) (0, 0, 0)
          • proposal (round, period, step) (0, 0, 1)
          • ...
        • proposal (round, period) (0, 1)
        • ...
      • proposal round 1
      • ... A state machine in the hierarchy can deliver events and queries to any of its children but not its parents. All state machines also receive a read-only copy of the player state when receiving any event.

State machines may be wrapped in Contracts which specify pre- and post-conditions for events received and emitted by a state machine. These contracts may be checked at runtime to find violations and possible bugs.

The tracer records the path of messages as they travel through the state machine for debugging, inspection, and post-mortem functionality.

The player machine

The root of the state machine tree is the player machine. This machine holds the current round, period, and step of the node, as well as some metadata to ensure correct propagation of received messages. All events are first routed to the player, which may forward them to other state machines. player is special in two ways: first of all, it is an event actor, which means that its handle method emits []action, and second, it is passed (by value) to all children state machines so that they are aware of the current state of the node.

The player consumes messageEvents which it forwards to the appropriate state machines. bundles and non-proposal-votes (i.e., votes with step =/= 0) are forwarded to the vote threshold machines, while proposalPayloads and proposal-votes (i.e. votes with step = 0) are forwarded to the proposal machines. Based on their outputs, the player chooses to relay or ignore these messages.

The player consumes timeouts events. The player communicates its next timeout by setting its Deadline and Napping fields.

The player produces actions which transmit messages to the pseudonode (e.g., attest to votes, assemble Blocks, repropose proposals) when appropriate. The player may issue queries to determine how to vote; for instance, the player will ask the proposal machine whether a Block is "committable" i.e., whether the entire Block has arrived along with a soft-threshold for that digest.

The player changes the round and period of the node according to thresholdEvents it receives from the vote threshold machine (and also potentially upon receiving a roundInterruptionEvent). It changes step according to timeout events it has received. On conclusion of a round, the player queries the Block from the proposal machine and then writes them along with the Certificate to the Ledger.

The remaining state machines are subordinate to player and handle two broad kinds of functonality: detecting when a threshold of votes has been reached, and managing Block proposals. The voteMachines create thresholdEvents and gives them to the player machine, while the proposalMachines track proposals and reconstruct them from network messages.

Spec Notes: Reordering

In the spec of the agreement protocol, messages are delivered on an ordered but best-effort basis. This means that the agreement protocol is resilient to message reordering in the network layer. However, good ordering improves the liveness of the agreement protocol and improves the rate at which the protocol converges.

One ordering constraint which impacts performance and also test reliability is the ordering of proposal-votes with respect to their matching proposal payloads. If the proposal payload is received before its corresponding proposal-vote, the agreement protocol will drop the payload and must recover into a new period.

The introduction of a concurrent cryptographic verification pool exacerbates this problem: a received proposal-vote will enter cryptographic verification before any state changes. If the corresponding payload arrives before cryptographic verification finishes, which is likely on a fast network or on a machine with a loaded CPU, the node will drop the payload and must again recover into a new period.

As a result, the implementation bundles together matching proposal-votes and proposal payloads into a compoundMessage. Nodes process a compoundMessage by first processing the proposal-vote (if it exists) and then following by processing the payload afterwards. To retain a handle on the proposal payload associated with a proposal-vote which is sent into the cryptoVerifier, the player maintains a proposalTable which associates outstanding proposal-vote verification requests with their corresponding payload.

The vote threshold machines

The vote threshold machines convert votes and bundles into events which signal that a quorum of valid votes has formed for some step and for some value.

At the root level, the voteAggregator receives raw and authenticated network messages that hold votes and bundles. It performs basic duplicate filtering and then forwards these messages to voteTrackerRound machines.

In addition to forwarding these messages to voteTrackerPeriod machines, voteTrackerRound machines also hold the freshest threshold event which they have seen. This serves two purposes: on arriving in a new period, the player must process any threshold event which has been pipelined, and during partitions, these events hold bundles which the node must propagate to neighbors.

voteTrackerPeriod machines respond to queries for the thresholds which have been observed by the node in some period.

voteTracker machines implement the core vote counting logic for a given step. Whenever the number of votes passes the threshold required for that step, the machine generates the threshold event exactly once and then returns the event up the state machine tree. It also records duplicate votes received in a given period, up to sender equivocation.

The proposal management machines

The proposal management machines track and store Block proposals across periods as the node executes the Byzantine Agreement protocol.

The proposalManager receives raw and authenticated proposalPayload messages. It also receives raw and authenticated votes for which step = 0 (= propose). These special "proposal-votes" represent the proposal messages Block proposers send at the beginning of a round and propagate in the network independently from the Blocks themselves, which are contained in proposalPayload messages.

The proposalManager performs duplicate filtering and then forwards messages as appropriate. It also issues the control messages required to change round and period.

The proposalStore tracks the set of proposal-values and payloads which are relevant to a given round. It also maintains the correct setting of the pinned proposal-value. When a new period arrives, it garbage-collects old proposals and updates the pinned value as necessary. When a new round arrives, it returns any enqueued payload events as necessary.

The proposalTracker maintains two proposal-values: one corresponding to the lowest proposal-credential seen in a period (the frozen proposal-value), and one corresponding to the sole value for which a quorum of soft-votes has been observed in the period (the staging proposal-value). It also records duplicate proposal-votes received in a given period.

The staging slot for a given period is important because its state is the precursor to cert and next votes. Once both a soft threshold for a value and the Block corresponding to this value has been observed by the node, a proposal committableEvent is emitted, which indicates that the node may cert or next-vote for the proposal.

Documentation

Overview

Package agreement implements Algorand's agreement protocol, which enables all nodes to consistently update the state of the system.

The Service establishes a consensus on the ordering of Blocks. This ordering is defined by a Round number, which indexes into the ordered log of Blocks.

Clients instantiate an Service by providing it several parameters:

  • Ledger represents a data store which supports the reading and writing of data stored within Blocks.

  • BlockFactory produces Blocks for a given round.

  • BlockValidator validates Blocks for a given round.

  • KeyManager holds the participation keys necessary to participate in the protocol.

  • Network provides an abstraction over the underlying network.

  • timers.Clock provides timekeeping services for timeouts.

  • db.Accessor provides persistent storage for internal state.

    Blocks for which consensus is completed are written using Ledger.EnsureBlock alongside Certificate objects, which are cryptographic proofs that a Block was confirmed for a given round.

If Ledger and db.Accessor provide crash-safe storage, agreement will also recover safely after crashes.

Index

Constants

This section is empty.

Variables

View Source 
var ErrAssembleBlockRoundStale = errors.New("requested round for AssembleBlock is stale")

ErrAssembleBlockRoundStale is returned by AssembleBlock when the requested round number is not the one that matches the ledger last committed round + 1.

Functions

func ActionTypeMaxSize 

func ActionTypeMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func BlockAssemblerMaxSize 

func BlockAssemblerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func BundleMaxSize 

func BundleMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func CertificateMaxSize 

func CertificateMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func CompoundMessageMaxSize 

func CompoundMessageMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ConsensusVersionViewMaxSize 

func ConsensusVersionViewMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func DeadlineMaxSize 

func DeadlineMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func DeadlineTimeout 

func DeadlineTimeout(p period, v protocol.ConsensusVersion) time.Duration

DeadlineTimeout is the duration of the second agreement step, varying based on period and consensus version.

func DefaultDeadlineTimeout 

func DefaultDeadlineTimeout() time.Duration

DefaultDeadlineTimeout is the default duration of the second agreement step.

func DiskStateMaxSize 

func DiskStateMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func EquivocationVoteAuthenticatorMaxSize 

func EquivocationVoteAuthenticatorMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func EquivocationVoteMaxSize 

func EquivocationVoteMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func EventTypeMaxSize 

func EventTypeMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func FilterTimeout 

func FilterTimeout(p period, v protocol.ConsensusVersion) time.Duration

FilterTimeout is the duration of the first agreement step.

func FreshnessDataMaxSize 

func FreshnessDataMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func LateCredentialTrackingEffectMaxSize 

func LateCredentialTrackingEffectMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func MessageEventMaxSize 

func MessageEventMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func MessageMaxSize 

func MessageMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func NextThresholdStatusEventMaxSize 

func NextThresholdStatusEventMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ParamsRound 

func ParamsRound(rnd basics.Round) basics.Round

ParamsRound returns the round from which consensus parameters should be used for agreement on round rnd.

func PeriodMaxSize 

func PeriodMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func PeriodRouterMaxSize 

func PeriodRouterMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func PlayerMaxSize 

func PlayerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalManagerMaxSize 

func ProposalManagerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalMaxSize 

func ProposalMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalSeekerMaxSize 

func ProposalSeekerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalStoreMaxSize 

func ProposalStoreMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalTableMaxSize 

func ProposalTableMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalTrackerContractMaxSize 

func ProposalTrackerContractMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalTrackerMaxSize 

func ProposalTrackerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalValueMaxSize 

func ProposalValueMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposalVoteCounterMaxSize 

func ProposalVoteCounterMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ProposerSeedMaxSize 

func ProposerSeedMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func RawVoteMaxSize 

func RawVoteMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func RootRouterMaxSize 

func RootRouterMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func RoundRouterMaxSize 

func RoundRouterMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func SeedInputMaxSize 

func SeedInputMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func SelectorMaxSize 

func SelectorMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func SerializableErrorMaxSize 

func SerializableErrorMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func StepMaxSize 

func StepMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func StepRouterMaxSize 

func StepRouterMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func ThresholdEventMaxSize 

func ThresholdEventMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func TimeoutTypeMaxSize 

func TimeoutTypeMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func TransmittedPayloadMaxSize 

func TransmittedPayloadMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func UnauthenticatedBundleMaxSize 

func UnauthenticatedBundleMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func UnauthenticatedEquivocationVoteMaxSize 

func UnauthenticatedEquivocationVoteMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func UnauthenticatedProposalMaxSize 

func UnauthenticatedProposalMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func UnauthenticatedVoteMaxSize 

func UnauthenticatedVoteMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteAggregatorMaxSize 

func VoteAggregatorMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteAuthenticatorMaxSize 

func VoteAuthenticatorMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteMaxSize 

func VoteMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteTrackerContractMaxSize 

func VoteTrackerContractMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteTrackerMaxSize 

func VoteTrackerMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteTrackerPeriodMaxSize 

func VoteTrackerPeriodMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

func VoteTrackerRoundMaxSize 

func VoteTrackerRoundMaxSize() (s int)

MaxSize returns a maximum valid message size for this message type

Types

type AsyncVoteVerifier 

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

AsyncVoteVerifier uses workers to verify agreement protocol votes and writes the results on an output channel specified by the user.

func MakeAsyncVoteVerifier 

func MakeAsyncVoteVerifier(verificationPool execpool.BacklogPool) *AsyncVoteVerifier

MakeAsyncVoteVerifier creates an AsyncVoteVerifier with workers as the number of CPUs

func (*AsyncVoteVerifier) Parallelism 

func (avv *AsyncVoteVerifier) Parallelism() int

Parallelism gives the maximum parallelism of the vote verifier.

func (*AsyncVoteVerifier) Quit 

func (avv *AsyncVoteVerifier) Quit()

Quit tells the AsyncVoteVerifier to shutdown and waits until all workers terminate.

type Autopsy 

type Autopsy struct {
	io.Reader
	io.Closer
	// contains filtered or unexported fields
}

An Autopsy is a trace of the ordered input events and output actions as seen by the agreement state machine.

Functions depending on autopsies are not guaranteed to be supported as the agreement protocol changes.

func PrepareAutopsy 

func PrepareAutopsy(cadaverBaseFilename string, nextBounds func(int, AutopsyBounds), done func(int, error)) (*Autopsy, error)

PrepareAutopsy prepares an autopsy from a cadaver filename.

nextBounds is called with a sequence number for each new invocation of a cadaver-generating process (a "run").

done is called with the total number of runs and any error encountered while performing the autopsy.

func PrepareAutopsyFromStream 

func PrepareAutopsyFromStream(stream io.ReadCloser, nextBounds func(int, AutopsyBounds), done func(int, error)) (*Autopsy, error)

PrepareAutopsyFromStream prepares an autopsy from a given ReadCloser.

nextBounds is called with a sequence number for each new invocation of a cadaver-generating process (a "run").

done is called with the total number of runs and any error encountered while performing the autopsy.

func (*Autopsy) DumpMessagePack 

func (a *Autopsy) DumpMessagePack(filter AutopsyFilter, w0 io.WriteCloser) (version string)

DumpMessagePack dumps a msgpack representation of the AutopsiedCdvs to the given io.Writer.

func (*Autopsy) DumpString 

func (a *Autopsy) DumpString(filter AutopsyFilter, w0 io.Writer) (version string)

DumpString dumps a textual representation of the AutopsyCdvs to the given io.Writer.

type AutopsyBounds 

type AutopsyBounds struct {
	// Start and End are inclusive here.
	StartRound  uint64
	StartPeriod uint64
	EndRound    uint64
	EndPeriod   uint64
}

AutopsyBounds defines the range of rounds and periods spanned by a single invocation of a cadaver-generating process.

type AutopsyFilter 

type AutopsyFilter struct {
	Enabled bool         // do not filter if this is false
	First   basics.Round // first round to emit output for; inclusive
	Last    basics.Round // last round to emit output for; inclusive
}

AutopsyFilter represents a window of rounds to be filtered from the autopsy output.

type Block 

type Block bookkeeping.Block

Block (in agreement) represents an UnfinishedBlock produced by a BlockFactory, that was later finalized by providing the seed and the proposer, and can now be proposed by agreement.

type BlockFactory 

type BlockFactory interface {
	// AssembleBlock produces a new UnfinishedBlock for a given Round.
	// It must be finalized before proposed by agreement. It is provided
	// a list of participating addresses that may propose this block.
	//
	// AssembleBlock should produce a block for which the corresponding
	// BlockValidator validates (i.e. for which BlockValidator.Validate
	// returns true). If an insufficient number of nodes can assemble valid
	// entries, the agreement protocol may lose liveness.
	//
	// AssembleBlock may return an error if the BlockFactory is unable to
	// produce an UnfinishedBlock for the given round. If an insufficient number of
	// nodes on the network can assemble entries, the agreement protocol may
	// lose liveness.
	AssembleBlock(rnd basics.Round, partAddresses []basics.Address) (UnfinishedBlock, error)
}

An BlockFactory produces an Block which is suitable for proposal for a given Round.

type BlockValidator 

type BlockValidator interface {
	// Validate must return an error if a given Block cannot be determined
	// to be valid as applied to the agreement state; otherwise, it returns
	// nil.
	//
	// The correctness of Validate is essential to the correctness of the
	// protocol. If Validate accepts an invalid Block (i.e., a false
	// positive), the agreement protocol may fork, or the system state may
	// even become undefined. If Validate rejects a valid Block (i.e., a
	// false negative), the agreement protocol may even lose
	// liveness. Validate should therefore be conservative in which Entries
	// it accepts.
	//
	// TODO There should probably be a second Round argument here.
	Validate(context.Context, bookkeeping.Block) (ValidatedBlock, error)
}

An BlockValidator validates that a given Block may correctly be appended to the sequence of Entries agreed upon by the protocol so far.

type CadaverMetadata 

type CadaverMetadata struct {
	NumOpened         int
	VersionCommitHash string
}

CadaverMetadata contains informational metadata written to the top of every cadaver file

type Certificate 

type Certificate unauthenticatedBundle

A Certificate contains a cryptographic proof that agreement was reached on a given block in a given round.

When a client first joins the network or has fallen behind and needs to catch up, certificates allow the client to verify that a block someone gives them is the real one.

func (Certificate) Authenticate 

func (c Certificate) Authenticate(e bookkeeping.Block, l LedgerReader, avv *AsyncVoteVerifier) (err error)

Authenticate returns nil if the Certificate authenticates the given Block; otherwise, it returns an error.

Callers may want to cache the result of this check, as it is relatively expensive.

func (*Certificate) CanMarshalMsg 

func (_ *Certificate) CanMarshalMsg(z interface{}) bool

func (*Certificate) CanUnmarshalMsg 

func (_ *Certificate) CanUnmarshalMsg(z interface{}) bool

func (*Certificate) MarshalMsg 

func (z *Certificate) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (*Certificate) MsgIsZero 

func (z *Certificate) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (*Certificate) Msgsize 

func (z *Certificate) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Certificate) UnmarshalMsg 

func (z *Certificate) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*Certificate) UnmarshalMsgWithState 

func (z *Certificate) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type ConsensusVersionView 

type ConsensusVersionView struct {
	Err     *serializableError
	Version protocol.ConsensusVersion
	// contains filtered or unexported fields
}

A ConsensusVersionView is a view of the consensus version as read from a LedgerReader, associated with some round.

func (*ConsensusVersionView) CanMarshalMsg 

func (_ *ConsensusVersionView) CanMarshalMsg(z interface{}) bool

func (*ConsensusVersionView) CanUnmarshalMsg 

func (_ *ConsensusVersionView) CanUnmarshalMsg(z interface{}) bool

func (*ConsensusVersionView) MarshalMsg 

func (z *ConsensusVersionView) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (*ConsensusVersionView) MsgIsZero 

func (z *ConsensusVersionView) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (*ConsensusVersionView) Msgsize 

func (z *ConsensusVersionView) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*ConsensusVersionView) UnmarshalMsg 

func (z *ConsensusVersionView) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*ConsensusVersionView) UnmarshalMsgWithState 

func (z *ConsensusVersionView) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type Deadline 

type Deadline struct {
	Duration time.Duration
	// Type is used to allow tests fire timeouts of specific types.
	Type TimeoutType
	// contains filtered or unexported fields
}

Deadline marks a timeout event of type Type that the player schedules to happen after Duration time.

func (*Deadline) CanMarshalMsg 

func (_ *Deadline) CanMarshalMsg(z interface{}) bool

func (*Deadline) CanUnmarshalMsg 

func (_ *Deadline) CanUnmarshalMsg(z interface{}) bool

func (*Deadline) MarshalMsg 

func (z *Deadline) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (*Deadline) MsgIsZero 

func (z *Deadline) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (*Deadline) Msgsize 

func (z *Deadline) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Deadline) UnmarshalMsg 

func (z *Deadline) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*Deadline) UnmarshalMsgWithState 

func (z *Deadline) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type EventsProcessingMonitor 

type EventsProcessingMonitor interface {
	UpdateEventsQueue(queueName string, queueLength int)
}

EventsProcessingMonitor is an abstraction over the inner queues of the agreement service. It allows an external client to monitor the activity of the various events queues.

type KeyManager 

type KeyManager interface {
	// VotingKeys returns an immutable array of voting keys that are
	// valid for the provided votingRound, and were available at
	// keysRound.
	VotingKeys(votingRound, keysRound basics.Round) []account.ParticipationRecordForRound

	// Record indicates that the given participation action has been taken.
	// The operation needs to be asynchronous to avoid impacting agreement.
	Record(account basics.Address, round basics.Round, participationType account.ParticipationAction)
}

A KeyManager stores and deletes participation keys.

type LateCredentialTrackingEffect 

type LateCredentialTrackingEffect uint8

LateCredentialTrackingEffect indicates the impact of a vote that was filtered (due to age) on the credential tracking system (in credentialArrivalHistory), for the purpose of tracking the time it took the best credential to arrive, even if it was late. 

const (
	// NoLateCredentialTrackingImpact indicates the filtered event would have no impact on
	// the credential tracking mechanism.
	NoLateCredentialTrackingImpact LateCredentialTrackingEffect = iota

	// UnverifiedLateCredentialForTracking indicates the filtered event could impact
	// the credential tracking mechanism and more processing (validation) may be required.
	// It may be set by proposalManager when handling votePresent events.
	UnverifiedLateCredentialForTracking

	// VerifiedBetterLateCredentialForTracking indicates that the filtered event provides a new best
	// credential for its round.
	// It may be set by proposalManager when handling voteVerified events.
	VerifiedBetterLateCredentialForTracking
)

func (LateCredentialTrackingEffect) CanMarshalMsg 

func (_ LateCredentialTrackingEffect) CanMarshalMsg(z interface{}) bool

func (*LateCredentialTrackingEffect) CanUnmarshalMsg 

func (_ *LateCredentialTrackingEffect) CanUnmarshalMsg(z interface{}) bool

func (LateCredentialTrackingEffect) MarshalMsg 

func (z LateCredentialTrackingEffect) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (LateCredentialTrackingEffect) MsgIsZero 

func (z LateCredentialTrackingEffect) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (LateCredentialTrackingEffect) Msgsize 

func (z LateCredentialTrackingEffect) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*LateCredentialTrackingEffect) UnmarshalMsg 

func (z *LateCredentialTrackingEffect) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*LateCredentialTrackingEffect) UnmarshalMsgWithState 

func (z *LateCredentialTrackingEffect) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type Ledger 

type Ledger interface {
	LedgerReader
	LedgerWriter
}

A Ledger represents the sequence of Entries agreed upon by the protocol. The Ledger consists of two parts: a LedgerReader and a LedgerWriter, which provide read and write access to the ledger, respectively.

Ledger must be safe for concurrent use.

Once a method of Ledger succeeds, it must always succeed and become idempotent. (That is, all future calls to that method must return the same result, and multiple calls to a method must produce the same state as a single call.)

type LedgerDroppedRoundError 

type LedgerDroppedRoundError struct {
	Err error
}

LedgerDroppedRoundError is a wrapper error for when the ledger cannot return a Lookup query because the entry is old and was dropped from the ledger. The purpose of this wrapper is to help the agreement differentiate between a malicious vote and a vote that it cannot verify

func (*LedgerDroppedRoundError) Error 

func (e *LedgerDroppedRoundError) Error() string

func (*LedgerDroppedRoundError) Unwrap 

func (e *LedgerDroppedRoundError) Unwrap() error

type LedgerReader 

type LedgerReader interface {
	// NextRound returns the first round for which no Block has been
	// confirmed.
	NextRound() basics.Round

	// Wait returns a channel which fires when the specified round
	// completes and is durably stored on disk.
	Wait(basics.Round) chan struct{}

	// Seed returns the VRF seed that was agreed upon in a given round.
	//
	// The Seed is a source of cryptographic entropy which has bounded
	// bias. It is used to select committees for participation in
	// sortition.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	Seed(basics.Round) (committee.Seed, error)

	// LookupAgreement returns the AccountData associated with some Address
	// needed by agreement at the conclusion of a given round.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	LookupAgreement(basics.Round, basics.Address) (basics.OnlineAccountData, error)

	// Circulation returns the total amount of online money in circulation at the
	// conclusion of a given round rnd that is eligible for voting at voteRnd.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	Circulation(rnd basics.Round, voteRnd basics.Round) (basics.MicroAlgos, error)

	// LookupDigest returns the Digest of the entry that was agreed on in a
	// given round.
	//
	// Recent Entry Digests are periodically used when computing the Seed.
	// This prevents some subtle attacks.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	//
	// A LedgerReader need only keep track of the digest from the most
	// recent multiple of (config.Protocol.BalLookback/2). All other
	// digests may be forgotten without hurting liveness.
	LookupDigest(basics.Round) (crypto.Digest, error)

	// ConsensusParams returns the consensus parameters that are correct
	// for the given round.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	//
	// TODO replace with ConsensusVersion
	ConsensusParams(basics.Round) (config.ConsensusParams, error)

	// ConsensusVersion returns the consensus version that is correct
	// for the given round.
	//
	// This method returns an error if the given Round has not yet been
	// confirmed. It may also return an error if the given Round is
	// unavailable by the storage device. In that case, the agreement
	// protocol may lose liveness.
	ConsensusVersion(basics.Round) (protocol.ConsensusVersion, error)
}

A LedgerReader provides read access to observe the state of the ledger.

type LedgerWriter 

type LedgerWriter interface {
	// EnsureBlock adds a Block, along with a Certificate authenticating
	// its contents, to the ledger.
	//
	// The Ledger must guarantee that after this method returns, any Seed,
	// Record, or Circulation call reflects the contents of this Block.
	//
	// EnsureBlock will never be called twice for two entries e1 and e2
	// where e1.Round() == e2.Round() but e1.Digest() != e2.Digest(). If
	// this is the case, the behavior of Ledger is undefined.
	// (Implementations are encouraged to panic or otherwise fail loudly in
	// this case, because it means that a fork has occurred.)
	//
	// EnsureBlock does not wait until the block is written to disk; use
	// Wait() for that.
	EnsureBlock(bookkeeping.Block, Certificate)

	// EnsureValidatedBlock is an optimized version of EnsureBlock that
	// works on a ValidatedBlock, but otherwise has the same semantics
	// as above.
	EnsureValidatedBlock(ValidatedBlock, Certificate)

	// EnsureDigest signals the Ledger to attempt to fetch a Block matching
	// the given Certificate.  EnsureDigest does not wait for the block to
	// be written to disk; use Wait() if needed.
	//
	// The Ledger must guarantee that after this method returns, any Seed,
	// Record, or Circulation call reflects the contents of the Block
	// authenticated by the given Certificate.
	//
	// EnsureDigest will never be called twice for two certificates c1 and
	// c2 where c1 authenticates the block e1 and c2 authenticates the block
	// e2, but e1.Round() == e2.Round() and e1.Digest() != e2.Digest(). If
	// this is the case, the behavior of Ledger is undefined.
	// (Implementations are encouraged to panic or otherwise fail loudly in
	// this case, because it means that a fork has occurred.)
	EnsureDigest(Certificate, *AsyncVoteVerifier)
}

A LedgerWriter allows writing entries to the ledger.

type Message 

type Message struct {
	MessageHandle
	Data []byte
}

Message encapsulates a MessageHandle and its payload.

type MessageHandle 

type MessageHandle interface{}

MessageHandle is an ID referring to a specific message.

A MessageHandle of nil denotes that a message is "sourceless".

type Network 

type Network interface {
	// Messages returns a channel of Messages which corresponds to a given
	// protocol.Tag.
	Messages(protocol.Tag) <-chan Message

	// Broadcast attempts to send a slice of bytes under some protocol.Tag
	// to all neighbors.
	//
	// Broadcast represents a best-effort, ordered delivery mechanism.  In
	// other words, sends to any given peer may fail due to disconnection or
	// network congestion.  However, the Network should try to transmit
	// messages in the order identical to the ordering of Broadcast calls.
	//
	// Calls to Broadcast by the agreement package are currently guaranteed
	// to be serialized.
	//
	// If the broadcasting of the message have failed or is not possible, the
	// method returns a non-nil error describing the underlaying error.
	// otherwise, a nil is returned.
	Broadcast(protocol.Tag, []byte) error

	// Relay attempts to send a slice of bytes under some protocol.Tag to
	// all neighbors, except for the neighbor associated with the given
	// MessageHandle.
	//
	// The behavior of Relay is otherwise identical to Broadcast.
	//
	// Passing a MessageHandle value of nil to Relay should produce behavior
	// identical to calling Broadcast.  In other words, the calls
	// Broadcast(tag, data) and Relay(nil, tag, data) should cause identical
	// behavior.
	//
	// If the relaying of the message have failed or is not possible, the
	// method returns a non-nil error describing the underlaying error.
	// otherwise, a nil is returned.
	Relay(MessageHandle, protocol.Tag, []byte) error

	// Disconnect sends the Network a hint to disconnect to the peer
	// associated with the given MessageHandle.
	Disconnect(MessageHandle)

	// Start notifies the network that the agreement service is ready
	// to start receiving messages.
	Start()
}

Network is an abstraction over the interface expected by the agreement protocol.

type Parameters 

type Parameters struct {
	Ledger
	Network
	KeyManager
	BlockValidator
	BlockFactory
	RandomSource
	EventsProcessingMonitor
	timers.Clock[TimeoutType]
	db.Accessor
	logging.Logger
	config.Local
	execpool.BacklogPool
}

Parameters holds the parameters necessary to run the agreement protocol.

type RandomSource 

type RandomSource interface {
	// Uint64 returns a pseudo-random 64-bit value as a uint64.
	Uint64() uint64
}

RandomSource is an abstraction over the random number generator. The agreement protocol use it to determine the duration of which different nodes would wait on steps 5 and above.

type Service 

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

Service represents an instance of an execution of Algorand's agreement protocol.

func MakeService 

func MakeService(p Parameters) (*Service, error)

MakeService creates a new Agreement Service instance given a set of Parameters.

Call Start to start execution and Shutdown to finish execution.

func (*Service) DumpDemuxQueues 

func (s *Service) DumpDemuxQueues(w io.Writer)

DumpDemuxQueues dumps the demux queues to the given writer.

func (*Service) SetTracerFilename 

func (s *Service) SetTracerFilename(filename string)

SetTracerFilename updates the tracer filename used.

func (*Service) Shutdown 

func (s *Service) Shutdown()

Shutdown the execution of the protocol.

This method returns after all resources have been cleaned up.

func (*Service) Start 

func (s *Service) Start()

Start executing the agreement protocol.

type SortAddress 

type SortAddress = basics.SortAddress

SortAddress is re-exported from basics.Address since the interface is already defined there

type SortPeriod 

type SortPeriod []period

SortPeriod defines SortInterface used by msgp to consistently sort maps with this type as key.

func (SortPeriod) Len 

func (a SortPeriod) Len() int

func (SortPeriod) Less 

func (a SortPeriod) Less(i, j int) bool

func (SortPeriod) Swap 

func (a SortPeriod) Swap(i, j int)

type SortProposalValue 

type SortProposalValue []proposalValue

SortProposalValue defines SortInterface used by msgp to consistently sort maps with this type as key.

func (SortProposalValue) Len 

func (a SortProposalValue) Len() int

func (SortProposalValue) Less 

func (a SortProposalValue) Less(i, j int) bool

func (SortProposalValue) Swap 

func (a SortProposalValue) Swap(i, j int)

type SortRound 

type SortRound []basics.Round

SortRound defines SortInterface used by msgp to consistently sort maps with this type as key. note, for type aliases the base type is used for the interface

func (SortRound) Len 

func (a SortRound) Len() int

func (SortRound) Less 

func (a SortRound) Less(i, j int) bool

func (SortRound) Swap 

func (a SortRound) Swap(i, j int)

type SortStep 

type SortStep []step

SortStep defines SortInterface used by msgp to consistently sort maps with this type as key.

func (SortStep) Len 

func (a SortStep) Len() int

func (SortStep) Less 

func (a SortStep) Less(i, j int) bool

func (SortStep) Swap 

func (a SortStep) Swap(i, j int)

type SortUint64 

type SortUint64 = basics.SortUint64

SortUint64 is re-exported from basics since the interface is already defined there canonical encoding of maps in msgpack format.

type TimeoutType 

type TimeoutType int8

TimeoutType defines the type of a Deadline, to distinguish between different timeouts set by agreement. 

const (
	// TimeoutDeadline annotates timeout events in the agreement protocol (e.g.,
	// for receiving a block).
	TimeoutDeadline TimeoutType = iota
	// TimeoutFastRecovery annotates the fast recovery timeout in the agreement
	// protocol.
	TimeoutFastRecovery
	// TimeoutFilter annotates the filter step timeout event in the agreement
	// protocol.
	TimeoutFilter
)

func (TimeoutType) CanMarshalMsg 

func (_ TimeoutType) CanMarshalMsg(z interface{}) bool

func (*TimeoutType) CanUnmarshalMsg 

func (_ *TimeoutType) CanUnmarshalMsg(z interface{}) bool

func (TimeoutType) MarshalMsg 

func (z TimeoutType) MarshalMsg(b []byte) (o []byte)

MarshalMsg implements msgp.Marshaler

func (TimeoutType) MsgIsZero 

func (z TimeoutType) MsgIsZero() bool

MsgIsZero returns whether this is a zero value

func (TimeoutType) Msgsize 

func (z TimeoutType) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*TimeoutType) UnmarshalMsg 

func (z *TimeoutType) UnmarshalMsg(bts []byte) (o []byte, err error)

func (*TimeoutType) UnmarshalMsgWithState 

func (z *TimeoutType) UnmarshalMsgWithState(bts []byte, st msgp.UnmarshalState) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

type TransmittedPayload 

type TransmittedPayload = transmittedPayload

TransmittedPayload exported for dumping textual versions of messages

type UnauthenticatedVote 

type UnauthenticatedVote = unauthenticatedVote

UnauthenticatedVote exported for dumping textual versions of messages

type UnfinishedBlock 

type UnfinishedBlock interface {
	// FinishBlock creates a proposable block, having set the cryptographically
	// random seed and payout related fields.
	//
	// Calls to Seed() or to Digest() on the copy's Block must
	// reflect the value of the new seed.
	FinishBlock(seed committee.Seed, proposer basics.Address, eligible bool) Block

	Round() basics.Round
}

An UnfinishedBlock represents a Block produced by a BlockFactory and must be finalized before being proposed by agreement.

type ValidatedBlock 

type ValidatedBlock interface {
	// Block returns the underlying block that has been validated.
	Block() bookkeeping.Block
}

A ValidatedBlock represents an Block that has been successfully validated and can now be recorded in the ledger. This is an optimized version of calling EnsureBlock() on the Ledger.

Source Files

View all Source files

Directories

Path Synopsis
Package agreementtest produces useful functions for testing code.
 Package agreementtest produces useful functions for testing code.
Package gossip adapts the interface of network.GossipNode to agreement.Network.
 Package gossip adapts the interface of network.GossipNode to agreement.Network.

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.