cmt_log

package
v1.3.0-alpha.2 Latest Latest
Warning

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

Go to latest
Published: Jun 3, 2024 License: Apache-2.0 Imports: 16 Imported by: 0

Documentation

Overview

package cmtLog is responsible for producing a log of chain's block decisions for a particular committee. The main tasks for this module are:

  • Track the head of the chain log for a committee.
  • Track which blocks are approved, pending or reverted.
  • Handle startup and recovery scenarios.

Main principles of the algorithm: > - Propose to go to the next log index when > - a) consensus for the latest known LogIndex has terminated (confirmed | rejected | skip | recover). > All the previous can be left uncompleted. > - b) confirmed alias output is received from L1, that we haven't posted in this node. > - and we have a tip AO (from the local view). > - If there is a single clean chain, we can use pipelining (consider consDone event > instead of waiting for confirmed | rejected). > - We start a consensus instance whenever VLI reports a quorum and we have not started it yet. > Even if we provided no proposal for that LI.

The algorithm at a high level:

> ON Startup: > Let prevLI <- TRY restoring the last started LogIndex ELSE 0 > MinLI <- prevLI + 1 > LogIndex.Start(prevLI) > UPON AliasOutput (AO) {Confirmed | Rejected} by L1: > LocalView.Update(AO) > IF LocalView changed THEN > LogIndex.L1ReplacedBaseAliasOutput() > TryProposeConsensus()

> ON Startup: > Let prevLI <- TRY restoring the last started LogIndex ELSE 0 > MinLI <- prevLI + 1 > LogIndex.Start(prevLI) > TryProposeConsensus() > UPON AliasOutput (AO) {Confirmed | Rejected} by L1: > LocalView.Update(AO) > IF LocalView changed THEN > LogIndex.L1ReplacedBaseAliasOutput() > TryProposeConsensus() > ON ConsensusOutput/DONE (CD) > LocalView.Update(CD) > IF LocalView changed THEN > LogIndex.ConsensusOutput(CD.LogIndex) > TryProposeConsensus() > ON ConsensusOutput/SKIP (CS) > LogIndex.ConsensusOutput(CS.LogIndex) > TryProposeConsensus() > ON ConsensusTimeout (CT) > LogIndex.ConsensusTimeout(CT.LogIndex) > TryProposeConsensus() > ON Suspend: > Suspended <- TRUE > TryProposeConsensus() > ON Reception of ⟨NextLI, •⟩ message: > LogIndex.Receive(⟨NextLI, •⟩ message). > TryProposeConsensus() > PROCEDURE TryProposeConsensus: > IF ∧ LocalView.BaseAO ≠ NIL > ∧ LogIndex > ConsensusLI > ∧ LogIndex ≥ MinLI // ⇒ LogIndex ≠ NIL > ∧ ¬ Suspended > THEN > Persist LogIndex > ConsensusLI <- LogIndex > Propose LocalView.BaseAO for LogIndex > ELSE > Don't propose any consensus.

See `WaspChainRecovery.tla` for more precise specification.

Notes and invariants:

  • Here only a single consensus instance will be considered needed for this node at a time. Other instances may continue running, but their results will be ignored. That's because a consensus takes an input from the previous consensus output (the base alias ID and other parts that depend on it).
  • A consensus is started when we have new log index greater than that we have crashed with, and there is an alias output received.

## Summary.

Inputs expected:

  • Consensus: Start -> Done | Timeout.
  • AliasOutput: Confirmed | Rejected -> {}.
  • Suspend.

Messages exchanged:

  • NextLogIndex (private, between cmtLog instances).

Here we implement the local view of a chain, maintained by a committee to decide which alias output to propose to the ACS. The alias output decided by the ACS will be used as an input for TX we build.

The LocalView maintains a list of Alias Outputs (AOs). The are chained based on consumed/produced AOs in a transaction we publish. The goal here is to tract the unconfirmed alias outputs, update the list based on confirmations/rejections from the L1.

In overall, the LocalView acts as a filter between the L1 and LogIndex assignment in varLogIndex. It has to distinguish between AOs that are confirming a prefix of the posted transaction (pipelining), from other changes in L1 (rotations, rollbacks, rejections, etc.).

We have several inputs:

  • **Alias Output Confirmed**. It can be AO posted by this committee, as well as by other committee (e.g. chain was rotated to other committee and then back) or a user (e.g. external rotation TX).

  • **Alias Output Rejected**. These events are always for TXes posted by this committee. We assume for each TX we will get either Confirmation or Rejection.

  • **Consensus Done**. Consensus produced a TX, and will post it to the L1.

  • **Consensus Skip**. Consensus completed without producing a TX and a block. So the previous AO is left unspent.

  • **Consensus Recover**. Consensus is still running, but it takes long time, so maybe something is wrong and we should consider spawning another consensus for the same base AO.

On the pipelining:

  • During the normal operation, if consensus produces a TX, it can use the produced AO to build next TX on it. That's pipelining. It allows to produce multiple blocks per L1 milestone. This component tracks the AOs build in this way and not confirmed yet.

  • If AO produced by the consensus is rejected, then all the AOs build on top of it will be rejected eventually as well, because they use the rejected AO as an input. On the other hand, it is unclear if unconfirmed AOs before the rejected one will be confirmed or rejected, we will wait until L1 decides on all of them.

  • If we get a confirmed AO, that is not one of the AOs we have posted (and still waiting for a decision), then someone from the outside of a committee transitioned the chain. In this case all our produced/pending transactions are not meaningful anymore and we have to start building all the chain from the newly received AO.

  • Recovery notice is received from a consensus (with SI/LI...) a new consensus will be started after agreeing on the next LI. The new consensus will take the same AO as an input and therefore will race with the existing one (maybe it has stuck for some reason, that's a fallback). In this case we stop building an unconfirmed chain for the future state indexes and will wait for some AO to be confirmed or all the concurrent consensus TX'es to be rejected.

Note on the AO as an input for a consensus. The provided AO is just a proposal. After ACS is completed, the participants will select the actual AO, which can differ from the one proposed by this node.

NOTE: On the rejections. When we get a rejection of an AO, we cannot mark all the subsequent StateIndexes as rejected, because it is possible that the rejected AO was started to publish before a reorg/reject. Thus, only that single AO has to be marked as rejected. Nevertheless, the AOs explicitly (via consumed AO) depending on the rejected AO can be cleaned up.

Index

Constants

This section is empty.

Variables

View Source
var ErrCmtLogStateNotFound = errors.New("errCmtLogStateNotFound")

Functions

func NewInputAliasOutputConfirmed

func NewInputAliasOutputConfirmed(aliasOutput *isc.AliasOutputWithID) gpa.Input

func NewInputCanPropose

func NewInputCanPropose() gpa.Input

func NewInputConsensusOutputConfirmed

func NewInputConsensusOutputConfirmed(aliasOutput *isc.AliasOutputWithID, logIndex LogIndex) gpa.Input

func NewInputConsensusOutputDone

func NewInputConsensusOutputDone(
	logIndex LogIndex,
	proposedBaseAO iotago.OutputID,
	baseAliasOutputID iotago.OutputID,
	nextAliasOutput *isc.AliasOutputWithID,
) gpa.Input

This message is internal one, but should be sent by other components (e.g. consensus or the chain).

func NewInputConsensusOutputRejected

func NewInputConsensusOutputRejected(aliasOutput *isc.AliasOutputWithID, logIndex LogIndex) gpa.Input

func NewInputConsensusOutputSkip

func NewInputConsensusOutputSkip(
	logIndex LogIndex,
	proposedBaseAO iotago.OutputID,
) gpa.Input

This message is internal one, but should be sent by other components (e.g. consensus or the chain).

func NewInputConsensusTimeout

func NewInputConsensusTimeout(logIndex LogIndex) gpa.Input

This message is internal one, but should be sent by other components (e.g. consensus or the chain).

func NewInputMilestoneReceived added in v1.1.0

func NewInputMilestoneReceived() gpa.Input

func NewInputSuspend

func NewInputSuspend() gpa.Input

func UnmarshalMessage

func UnmarshalMessage(data []byte) (gpa.Message, error)

Types

type CmtLog

type CmtLog interface {
	AsGPA() gpa.GPA
}

Public interface for this algorithm.

func New

func New(
	me gpa.NodeID,
	chainID isc.ChainID,
	dkShare tcrypto.DKShare,
	consensusStateRegistry ConsensusStateRegistry,
	nodeIDFromPubKey func(pubKey *cryptolib.PublicKey) gpa.NodeID,
	deriveAOByQuorum bool,
	pipeliningLimit int,
	postponeRecoveryMilestones int,
	cclMetrics *metrics.ChainCmtLogMetrics,
	log *logger.Logger,
) (CmtLog, error)

Construct new node instance for this protocol.

> ON Startup: > Let prevLI <- TRY restoring the last started LogIndex ELSE 0 > MinLI <- prevLI + 1 > ...

type ConsensusStateRegistry

type ConsensusStateRegistry interface {
	Get(chainID isc.ChainID, committeeAddress iotago.Address) (*State, error) // Can return ErrCmtLogStateNotFound.
	Set(chainID isc.ChainID, committeeAddress iotago.Address, state *State) error
}

Interface used to store and recover the existing persistent state. To be implemented by the registry.

type LogIndex

type LogIndex uint32

LogIndex starts from 1. 0 is used as a nil value.

func MaxLogIndex

func MaxLogIndex(lis ...LogIndex) LogIndex

func NilLogIndex

func NilLogIndex() LogIndex

func (LogIndex) AsUint32

func (li LogIndex) AsUint32() uint32

func (LogIndex) Bytes

func (li LogIndex) Bytes() []byte

func (LogIndex) IsNil

func (li LogIndex) IsNil() bool

func (LogIndex) Next

func (li LogIndex) Next() LogIndex

type MsgNextLogIndex

type MsgNextLogIndex struct {
	gpa.BasicMessage
	NextLogIndex LogIndex             // Proposal is to go to this LI without waiting for a consensus.
	Cause        MsgNextLogIndexCause // Reason for the proposal.
	PleaseRepeat bool                 // If true, the receiver should resend its latest message back to the sender.
}

func NewMsgNextLogIndex

func NewMsgNextLogIndex(recipient gpa.NodeID, nextLogIndex LogIndex, cause MsgNextLogIndexCause, pleaseRepeat bool) *MsgNextLogIndex

func (*MsgNextLogIndex) AsResent

func (msg *MsgNextLogIndex) AsResent() *MsgNextLogIndex

Make a copy for re-sending the message. We set pleaseResend to false to avoid accidental loops.

func (*MsgNextLogIndex) Read

func (msg *MsgNextLogIndex) Read(r io.Reader) error

func (*MsgNextLogIndex) String

func (msg *MsgNextLogIndex) String() string

func (*MsgNextLogIndex) Write

func (msg *MsgNextLogIndex) Write(w io.Writer) error

type MsgNextLogIndexCause

type MsgNextLogIndexCause byte
const (
	MsgNextLogIndexCauseConsOut MsgNextLogIndexCause = iota // Consensus output received, we can go to the next log index.
	MsgNextLogIndexCauseL1RepAO                             // L1 replaced an alias output, probably have to start new log index.
	MsgNextLogIndexCauseRecover                             // Either node is booted or consensus asks for a recovery, try to proceed to next li.
	MsgNextLogIndexCauseStarted                             // Consensus is started, maybe we have to catch up with it.
)

func (MsgNextLogIndexCause) String

func (c MsgNextLogIndexCause) String() string

type Output

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

Output for this protocol indicates, what instance of a consensus is currently required to be run. The unique identifier here is the logIndex (there will be no different baseAliasOutputs for the same logIndex).

func (*Output) GetBaseAliasOutput

func (o *Output) GetBaseAliasOutput() *isc.AliasOutputWithID

func (*Output) GetLogIndex

func (o *Output) GetLogIndex() LogIndex

func (*Output) String

func (o *Output) String() string

type QuorumCounter

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

func NewQuorumCounter

func NewQuorumCounter(msgCause MsgNextLogIndexCause, nodeIDs []gpa.NodeID, log *logger.Logger) *QuorumCounter

func (*QuorumCounter) EnoughVotes

func (qc *QuorumCounter) EnoughVotes(quorum int) LogIndex

func (*QuorumCounter) HaveVoteFrom

func (qc *QuorumCounter) HaveVoteFrom(from gpa.NodeID) bool

func (*QuorumCounter) LastMessageForPeer

func (qc *QuorumCounter) LastMessageForPeer(peer gpa.NodeID, msgs gpa.OutMessages) gpa.OutMessages

func (*QuorumCounter) MaybeSendVote

func (qc *QuorumCounter) MaybeSendVote(li LogIndex) gpa.OutMessages

func (*QuorumCounter) MyLastVote

func (qc *QuorumCounter) MyLastVote() LogIndex

func (*QuorumCounter) VoteReceived

func (qc *QuorumCounter) VoteReceived(vote *MsgNextLogIndex)

type State

type State struct {
	LogIndex LogIndex
}

type VarLocalView

type VarLocalView interface {
	//
	// Returns alias output to produce next transaction on, or nil if we should wait.
	// In the case of nil, we either wait for the first AO to receive, or we are
	// still recovering from a TX rejection.
	Value() *isc.AliasOutputWithID
	//
	// Corresponds to the `tx_posted` event in the specification.
	// Returns true, if the proposed BaseAliasOutput has changed.
	ConsensusOutputDone(logIndex LogIndex, consumed iotago.OutputID, published *isc.AliasOutputWithID) (*isc.AliasOutputWithID, bool) // TODO: Recheck, if consumed AO is the decided one.
	//
	// Corresponds to the `ao_received` event in the specification.
	// Returns true, if the proposed BaseAliasOutput has changed.
	// Also it returns confirmed log index, if a received AO confirms it, or NIL otherwise.
	AliasOutputConfirmed(confirmed *isc.AliasOutputWithID) (*isc.AliasOutputWithID, bool, LogIndex)
	//
	// Corresponds to the `tx_rejected` event in the specification.
	// Returns true, if the proposed BaseAliasOutput has changed.
	AliasOutputRejected(rejected *isc.AliasOutputWithID) (*isc.AliasOutputWithID, bool)
	//
	// Support functions.
	StatusString() string
}

func NewVarLocalView

func NewVarLocalView(pipeliningLimit int, tipUpdatedCB func(ao *isc.AliasOutputWithID), log *logger.Logger) VarLocalView

type VarLogIndex

type VarLogIndex interface {
	// Summary of the internal state.
	StatusString() string

	// Returns the latest agreed LI.
	// There is no output value, if LogIndex=⊥.
	Value() LogIndex

	// Mark the log index as used (consensus initiated for it already) so
	// that it would not be proposed anymore in future.
	LogIndexUsed(li LogIndex)

	// Consensus terminated with either with DONE or SKIP.
	// The logIndex is of the consensus that has been completed.
	ConsensusOutputReceived(consensusLI LogIndex) gpa.OutMessages

	// Consensus decided, that its maybe time to attempt another run.
	// The timeout-ed consensus will be still running, so they will race for the result.
	ConsensusRecoverReceived(consensusLI LogIndex) gpa.OutMessages

	// This is called when we have to move to the next log index based on the AO received from L1.
	L1ReplacedBaseAliasOutput() gpa.OutMessages

	// This is called, if an AO is confirmed for which we know a log index (was pending).
	L1ConfirmedAliasOutput(li LogIndex) gpa.OutMessages

	// Messages are exchanged, so this function handles them.
	MsgNextLogIndexReceived(msg *MsgNextLogIndex) gpa.OutMessages
}

func NewVarLogIndex

func NewVarLogIndex(
	nodeIDs []gpa.NodeID,
	n int,
	f int,
	persistedLI LogIndex,
	outputCB func(li LogIndex),
	metrics *metrics.ChainCmtLogMetrics,
	log *logger.Logger,
) VarLogIndex

type VarOutput

type VarOutput interface {
	// Summary of the internal state.
	StatusString() string
	Value() *Output
	LogIndexAgreed(li LogIndex)
	TipAOChanged(ao *isc.AliasOutputWithID)
	HaveRejection()
	HaveMilestone()
	CanPropose()
	Suspended(suspended bool)
}

func NewVarOutput

func NewVarOutput(persistUsed func(li LogIndex), postponeRecoveryMilestones int, log *logger.Logger) VarOutput

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL