cmt_log

package
v0.7.0-alpha.5 Latest Latest
Warning

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

 Go to latest Published: Jul 4, 2023 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.

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,
	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.
	NextBaseAO   *isc.AliasOutputWithID // Using this AO as a base.
	PleaseRepeat bool                   // If true, the receiver should resend its latest message back to the sender.
}

func NewMsgNextLogIndex 

func NewMsgNextLogIndex(recipient gpa.NodeID, nextLogIndex LogIndex, nextBaseAO *isc.AliasOutputWithID, 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 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 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.
	AliasOutputConfirmed(confirmed *isc.AliasOutputWithID) (*isc.AliasOutputWithID, bool)
	//
	// 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, log *logger.Logger) VarLocalView

type VarLogIndex 

type VarLogIndex interface {
	// Returns the latest agreed LI/AO.
	// There is no output value, if LogIndex=⊥.
	Value() (LogIndex, *isc.AliasOutputWithID)
	// Consensus terminated with either with DONE or SKIP.
	// NextAO is the same as before for the SKIP case.
	// NextAO = nil means we don't know the latest AO from L1 (either startup or reject of a chain is happening).
	ConsensusOutputReceived(consensusLI LogIndex, consensusStatus cons.OutputStatus, nextBaseAO *isc.AliasOutputWithID) 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 might get a nil alias output in the case when a TX gets rejected and it was not the latest TX in the active chain.
	// NextAO = nil means we don't know the latest AO from L1 (either startup or reject of a chain is happening).
	L1ReplacedBaseAliasOutput(nextBaseAO *isc.AliasOutputWithID) gpa.OutMessages
	// Messages are exchanged, so this function handles them.
	MsgNextLogIndexReceived(msg *MsgNextLogIndex) gpa.OutMessages
	// Summary of the internal state.
	StatusString() string
}

func NewVarLogIndex 

func NewVarLogIndex(
	nodeIDs []gpa.NodeID,
	n int,
	f int,
	persistedLI LogIndex,
	outputCB func(li LogIndex, ao *isc.AliasOutputWithID),
	deriveAOByQuorum bool,
	log *logger.Logger,
) VarLogIndex

> ON Init(persistedLI): > latestAO ← ⊥ > proposedLI, agreedLI ← 0 > minLI ← persistedLI + 1 > maxPeerLIs ← ∅

type VarRunning 

type VarRunning interface {
	IsLatest(li LogIndex) bool
	ConsensusProposed(li LogIndex)
	ConsensusRecover(li LogIndex) bool
	ConsensusOutputDone(li LogIndex) bool
	ConsensusOutputSkip(li LogIndex) bool
	ConsensusOutputConfirmed(li LogIndex) bool
	ConsensusOutputRejected(li LogIndex) bool
	StatusString() string
}

All functions returns true, if the latest LI become completed.

func NewVarRunning 

func NewVarRunning(log *logger.Logger) VarRunning

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.