protocol_state

README

Dynamic Protocol State in a nutshell

• The Dynamic Protocol State is a framework for storing a snapshot of protocol-defined parameters and supplemental protocol-data into each block. Think about it as a key value store in each block.
• The Flow network uses its Dynamic Protocol State to orchestrate Epoch switchovers and more generally control participation privileges for the network (including ejection of misbehaving or compromised nodes).
• Furthermore, the Dynamic Protocol State makes it easily possible to update operational protocol parameters on the live network via a governance transaction. For example, we could update consensus timing parameters such as hotstuff-min-timeout.

These examples from above all use the same primitives provided by the Dynamic Protocol State:

• (i) a Key-value store, whose hash-commitment is included in the payload of every block,
• (ii) a set of rules (represented as a state machine) that updates the key-value-store from block to block, and
• (iii) dedicated Service Events originating from the System Smart Contracts (via verification and sealing) are the inputs to the state machines (ii).

This provides us with a very powerful set of primitives to orchestrate the low-level protocol on the fly with inputs from the System Smart Contracts. Engineers extending the protocol can add new entries to the Key-Value Store and provide custom state machines for updating their values. Correct application of this state machine (i.e. correct evolution of data in the store) is guaranteed by the Dynamic Protocol State framework through BFT consensus.

Core Concepts

Orthogonal State Machines

Orthogonality means that state machines can operate completely independently and work on disjoint sub-states. By convention, they all consume the same inputs (incl. the ordered sequence of Service Events sealed in one block). In other words, each state machine $S_0, S_1,\ldots$ has full visibility into the inputs, but each draws their own independent conclusions (maintaining their own exclusive state). There is no information exchange between the state machines; one state machine cannot read the current state of another.

We emphasize that this architecture choice does not prevent us from implementing sequential state machines for certain use-cases. For example: state machine $A$ provides its output as input to another state machine $B$. Here, the order of running the state machines matters. This order-dependency is not supported by the Protocol State, which executes the state machines in an arbitrary order. Therefore, if we need state machines to be executed in some specific order, we have to bundle them into one composite state machine (conceptually a processing pipeline) by hand. The composite state machine's execution as a whole can then be managed by the Protocol State, because the composite state machine is orthogonal to all other remaining state machines. Requiring all State Machines to be orthogonal is a deliberate design choice. Thereby the default is favouring modularity and strong logical independence. This is very beneficial for managing complexity in the long term.

Key-Value-Store

The Flow protocol defines the Key-Value-Store's state $\mathcal{P}$ as the composition of disjoint sub-states $P_0, P_1, \ldots, P_j$. Formally, we write $\mathcal{P} = P0 \otimes P1 \otimes \ldots \otimes Pj$, where $'\otimes'$ denotes the product state. We loosely associate each $P_0, P_1,\ldots$ with one specific key-value entry in the store. Correspondingly, we have conceptually independent state machines $S_0, S_1,\ldots$ operating each on their own respective sub-state $P_0, P_1, \ldots$ A one-to-one correspondence between key-value-pair and state machine should be the default, but is not strictly required. However, the strong requirement is that no key-value-pair is operated on my more than one state machine.

Formally we write:

• The overall protocol state $\mathcal{P}$ is composed of disjoint substates $\mathcal{P} = P_0 \otimes P_1 \otimes\ldots\otimes P_j$
• For each state $P_i$, we have a dedicated state machine $S_i$ that exclusively operates on $P_i$
• The state machines can be formalized as orthogonal regions of the composite state machine $\mathcal{S} = S_0 \otimes S_1 \otimes \ldots \otimes S_j$. (Technically, we represent the state machine by its state-transition function. All other details of the state machine are implicit.)
• The state machine $\mathcal{S}$ being in state $\mathcal{P}$ and observing the input $\xi = x_0\cdot x_1 \cdot x_2 \cdot\ldots\cdot x_z$ will output state $\mathcal{P}'$. To emphasize that a certain state machine 𝒮 exclusively operates on state $\mathcal{P}$, we write $\mathcal{S}[\mathcal{P}] = S_0[P_0] \otimes S_1[P_1] \otimes\ldots\otimes S_j[P_j]$. Observing the events $\xi$, the output state is $\mathcal{P}' = \mathcal{S}[\mathcal{P}] (\xi) = S_0 [P_0] (\xi) \otimes S_1 [P_1] (\xi) \otimes\ldots\otimes S_j [P_j] (\xi) = P'_0 \otimes P'_1 \otimes\ldots\otimes P'_j$, where each state machine $S_i$ individually generated the output state $S_i [P_i] (\xi) = P'_i$.

Input ξ

Conceptually, the consensus leader first executes these state machines during their block building process. At this point, the ID of the final block is unknown. Nevertheless, some part of the payload construction already happened, because the sealed execution results are used as an input below. There is a large degree of freedom in which data fields of the partially-constructed block we permit as possible inputs to the state machines. At the moment, the primary purpose is for the execution environment (with results undergone verification and sealing) to send Service Events to the protocol layer. Therefore, the current convention is:

1. At time of state machine construction (for each block), the Protocol State framework provides:
   • candidateView: view of the block currently under construction (or being currently validated)
   • parentID: parent block's ID (generally used by state machines to read their respective sub-state)
2. The Service Events sealed in the candidate block (under construction) are given to each state machine via the EvolveState(..) call.

New key-value pairs and corresponding state machines can easily be added by implementing the OrthogonalStoreStateMachine interface and adding a new entry to the Key-Value-Store's data model (file ./kvstore/models.go).

Documentation

Index

• type KVStoreAPI
• type KVStoreMutator
• type KeyValueStoreStateMachine
• type KeyValueStoreStateMachineFactory
• type OrthogonalStoreStateMachine
• type ProtocolKVStore

Types

type KVStoreAPI

type KVStoreAPI interface {
	protocol.KVStoreReader

	// Replicate instantiates a Protocol State Snapshot of the given `protocolVersion`.
	// We reference to the Protocol State Snapshot, whose `Replicate` method is called
	// as the 'Parent Snapshot'.
	// If the `protocolVersion` matches the version of the Parent Snapshot, `Replicate` behaves
	// exactly like a deep copy. If `protocolVersion` is newer, the data model corresponding
	// to the newer version is used and values from the Parent Snapshot are replicated into
	// the new data model. In all cases, the new Snapshot can be mutated without changing the
	// Parent Snapshot.
	//
	// Caution:
	// Implementors of this function decide on their own how to perform the migration from parent protocol version
	// to the given `protocolVersion`. It is required that outcome of `Replicate` is a valid KV store model which can be
	// incorporated in the protocol state without extra operations.
	// Expected errors during normal operations:
	//  - kvstore.ErrIncompatibleVersionChange if replicating the Parent Snapshot into a Snapshot
	//    with the specified `protocolVersion` is not supported.
	Replicate(protocolVersion uint64) (KVStoreMutator, error)
}

KVStoreAPI is the latest interface to the Protocol State key-value store which implements 'Prototype' pattern for replicating protocol state between versions.

Caution: Engineers evolving this interface must ensure that it is backwards-compatible with all versions of Protocol State Snapshots that can be retrieved from the local database, which should exactly correspond to the versioned model types defined in ./kvstore/models.go

type KVStoreMutator

type KVStoreMutator interface {
	protocol.KVStoreReader

	// SetVersionUpgrade sets the protocol upgrade version. This method is used
	// to update the Protocol State version when a flow.ProtocolStateVersionUpgrade is processed.
	// It contains the new version and the view at which it has to be applied.
	SetVersionUpgrade(version *protocol.ViewBasedActivator[uint64])

	// SetEpochStateID sets the state ID of the epoch state.
	// This method is used to commit the epoch state to the KV store when the state of the epoch is updated.
	SetEpochStateID(stateID flow.Identifier)
}

KVStoreMutator is the latest read-writer interface to the Protocol State key-value store.

Caution: Engineers evolving this interface must ensure that it is backwards-compatible with all versions of Protocol State Snapshots that can be retrieved from the local database, which should exactly correspond to the versioned model types defined in ./kvstore/models.go

type KeyValueStoreStateMachine

type KeyValueStoreStateMachine = OrthogonalStoreStateMachine[protocol.KVStoreReader]

KeyValueStoreStateMachine is a type alias for a state machine that operates on an instance of KVStoreReader. StateMutator uses this type to store and perform operations on orthogonal state machines.

type KeyValueStoreStateMachineFactory

type KeyValueStoreStateMachineFactory interface {
	// Create creates a new instance of an underlying type that operates on KV Store and is created for a specific candidate block.
	// No errors are expected during normal operations.
	Create(candidateView uint64, parentID flow.Identifier, parentState protocol.KVStoreReader, mutator KVStoreMutator) (KeyValueStoreStateMachine, error)
}

KeyValueStoreStateMachineFactory is an abstract factory interface for creating KeyValueStoreStateMachine instances. It is used separate creation of state machines from their usage, which allows less coupling and superior testability. For each concrete type injected in State Mutator a dedicated abstract factory has to be created.

type OrthogonalStoreStateMachine

type OrthogonalStoreStateMachine[P any] interface {

	// Build returns:
	//   - database updates necessary for persisting the updated protocol sub-state and its *dependencies*.
	//     It may contain updates for the sub-state itself and for any dependency that is affected by the update.
	//     Deferred updates must be applied in a transaction to ensure atomicity.
	//
	// No errors are expected during normal operations.
	Build() (*transaction.DeferredBlockPersist, error)

	// EvolveState applies the state change(s) on sub-state P for the candidate block (under construction).
	// Information that potentially changes the Epoch state (compared to the parent block's state):
	//   - Service Events sealed in the candidate block
	//   - the candidate block's view (already provided at construction time)
	//
	// SAFETY REQUIREMENTS:
	//   - The seals for the execution results, from which the `sealedServiceEvents` originate,
	//     must be protocol compliant.
	//   - `sealedServiceEvents` must list the service Events in chronological order. This can be
	//      achieved by arranging the sealed execution results in order of increasing block height.
	//      Within each execution result, the service events are in chronological order.
	//
	// CAUTION:
	// Per convention, the input seals from the block payload have already been confirmed to be protocol compliant.
	// Hence, the service events in the sealed execution results represent the *honest* execution path. Therefore,
	// the sealed service events should encode a valid evolution of the protocol state -- provided the system smart
	// contracts are correct. As we can rule out byzantine attacks as the source of failures, the only remaining
	// sources of problems can be (a) bugs in the system smart contracts or (b) bugs in the node implementation.
	//   - A service event not representing a valid state transition despite all consistency checks passing is
	//     indicative of case (a) and _should be handled_ internally by the respective state machine. Otherwise,
	//     any bug or unforeseen edge cases in the system smart contracts would in consensus halt, due to errors
	//     while evolving the protocol state.
	//   - Consistency or sanity checks failing within the OrthogonalStoreStateMachine is likely the symptom of an
	//     internal bug in the node software or state corruption, i.e. case (b). This is the only scenario where the
	//     error return of this function is not nil. If such an exception is returned, continuing is not an option.
	//
	// No errors are expected during normal operations.
	EvolveState(sealedServiceEvents []flow.ServiceEvent) error

	// View returns the view associated with this state machine.
	// The view of the state machine equals the view of the block carrying the respective updates.
	View() uint64

	// ParentState returns parent state associated with this state machine.
	ParentState() P
}

OrthogonalStoreStateMachine represents a state machine that exclusively evolves its state P. The state's specific type P is kept as a generic. Generally, P is the type corresponding to one specific key in the Key-Value store.

Orthogonal State Machines: Orthogonality means that state machines can operate completely independently and work on disjoint sub-states. By convention, they all consume the same inputs (incl. the ordered sequence of Service Events sealed in one block). In other words, each state machine has full visibility into the inputs, but each draws their on independent conclusions (maintain their own exclusive state).

The Dynamic Protocol State comprises a Key-Value-Store. We loosely associate each key-value-pair with a dedicated state machine operating exclusively on this key-value pair. A one-to-one correspondence between key-value-pair and state machine should be the default, but is not strictly required. However, we strictly require that no key-value-pair is being operated on by *more* than one state machine.

The Protocol State is the framework, which orchestrates the orthogonal state machines, feeds them with inputs, post-processes the outputs and overall manages state machines' life-cycle from block to block. New key-value pairs and corresponding state machines can easily be added by

• adding a new entry to the Key-Value-Store's data model (file `./kvstore/models.go`)
• implementing the `OrthogonalStoreStateMachine` interface

For more details see `./Readme.md`

NOT CONCURRENCY SAFE

type ProtocolKVStore

type ProtocolKVStore interface {
	// StoreTx returns an anonymous function (intended to be executed as part of a database transaction),
	// which persists the given KV-store snapshot as part of a DB tx. Per convention, all implementations
	// of `protocol.KVStoreReader` should be able to successfully encode their state into a data blob.
	// If the encoding fails, the anonymous function returns an error upon call.
	//
	// Expected errors of the returned anonymous function:
	//   - storage.ErrAlreadyExists if a KV-store snapshot with the given id is already stored.
	StoreTx(stateID flow.Identifier, kvStore protocol.KVStoreReader) func(*transaction.Tx) error

	// IndexTx returns an anonymous function intended to be executed as part of a database transaction.
	// In a nutshell, we want to maintain a map from `blockID` to `stateID`, where `blockID` references the
	// block that _proposes_ the updated key-value store.
	// Upon call, the anonymous function persists the specific map entry in the node's database.
	// Protocol convention:
	//   - Consider block B, whose ingestion might potentially lead to an updated KV store. For example,
	//     the KV store changes if we seal some execution results emitting specific service events.
	//   - For the key `blockID`, we use the identity of block B which _proposes_ this updated KV store.
	//   - CAUTION: The updated state requires confirmation by a QC and will only become active at the
	//     child block, _after_ validating the QC.
	//
	// Expected errors of the returned anonymous function:
	//   - storage.ErrAlreadyExists if a KV store for the given blockID has already been indexed.
	IndexTx(blockID flow.Identifier, stateID flow.Identifier) func(*transaction.Tx) error

	// ByID retrieves the KV store snapshot with the given ID.
	// Expected errors during normal operations:
	//   - storage.ErrNotFound if no snapshot with the given Identifier is known.
	//   - kvstore.ErrUnsupportedVersion if the version of the stored snapshot not supported by this implementation
	ByID(id flow.Identifier) (KVStoreAPI, error)

	// ByBlockID retrieves the kv-store snapshot that the block with the given ID proposes.
	// CAUTION: this store snapshot requires confirmation by a QC and will only become active at the child block,
	// _after_ validating the QC. Protocol convention:
	//   - Consider block B, whose ingestion might potentially lead to an updated KV store state.
	//     For example, the state changes if we seal some execution results emitting specific service events.
	//   - For the key `blockID`, we use the identity of block B which _proposes_ this updated KV store. As value,
	//     the hash of the resulting state at the end of processing B is to be used.
	//   - CAUTION: The updated state requires confirmation by a QC and will only become active at the child block,
	//     _after_ validating the QC.
	//
	// Expected errors during normal operations:
	//   - storage.ErrNotFound if no snapshot has been indexed for the given block.
	//   - kvstore.ErrUnsupportedVersion if the version of the stored snapshot not supported by this implementation
	ByBlockID(blockID flow.Identifier) (KVStoreAPI, error)
}

ProtocolKVStore persists different snapshots of the Protocol State's Key-Calue stores [KV-stores]. Here, we augment the low-level primitives provided by `storage.ProtocolKVStore` with logic for encoding and decoding the state snapshots into abstract representation `protocol_state.KVStoreAPI`.

At the abstraction level here, we can only handle protocol state snapshots, whose data models are supported by the current software version. There might be serialized snapshots with legacy versions in the database that are not supported anymore by this software version.