cmt_log

package
v1.0.2-alpha.2 Latest Latest
Warning

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

 Go to latest Published: Jan 24, 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 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,
	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)
	CanPropose()
	Suspended(suspended bool)
}

func NewVarOutput 

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

Source Files

View all Source files

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.