proposervm

package
v1.9.1-rc.7 Latest Latest
Warning

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

 Go to latest Published: Oct 24, 2022 License: BSD-3-Clause Imports: 32 Imported by: 5

README

Snowman++: congestion control for Snowman VMs

Snowman++ is a congestion control mechanism available for snowman VMs. Snowman++ can be activated on any snowman VM with no modifications to the VM internals. It is sufficient to wrap the target VM with a wrapper VM called proposerVM and to specify an activation time for the congestion-control mechanism. In this document we describe the high level features of Snowman++ and the implementation details of the proposerVM.

Congestion control mechanism description

Snowman++ introduces a soft proposer mechanism which attempts to select a single proposer with the power to issue a block, but opens up block production to every validator if sufficient time has passed without blocks being generated.

At a high level, Snowman++ works as follows: for each block a small list of validators is randomly sampled, which will act as "proposers" for the next block. Each proposer is assigned a submission window: a proposer cannot submit its block before its submission window starts (the block would be deemed invalid), but it can submit its block after its submission window expires, competing with next proposers. If no block is produced by the proposers in their submission windows, any validator will be free to propose a block, as happens for ordinary snowman VMs.

In the following we detail the block extensions, the proposers selection, and the validations introduced for Snowman++.

Snowman++ block extension

Snowman++ does not modify the blocks produced by the VM it is applied to. It extends these blocks with a header carrying the information needed to control block congestion.

A standard block header contains the following fields:

  • ParentID, the ID of the parent's enriched block (Note: this is different from the inner block ID).
  • Timestamp, the local time at block production.
  • PChainHeight the height of the last accepted block on the P-chain at the time the block is produced.
  • Certificate the TLS certificate of the block producer, to verify the block signature.
  • Signature the signature attesting this block was proposed by the correct block producer.

An Option block header contains the field:

  • ParentID the ID of the Oracle block to which the Option block is associated.

Option blocks are not signed, as they are deterministically generated from their Oracle block.

Snowman++ proposers selection mechanism

For a given block, Snowman++ randomly selects a list of proposers. Block proposers are selected from the subnet's validators. Snowman++ extracts the list of a given subnet's validators from the P-Chain. Let a block have a height H and P-Chain height P recorded in its header. The proposers list for next block is generated independently but reproducibly by each node as follows:

  • Subnet validators active at block P are retrieved from P-chain.
  • Validators are canonically sorted by their nodeID.
  • A seed S is generated by xoring H and the chainID. The chainID inclusion makes sure that different seeds sequences are generated for different chains.
  • Validators are pseudo-randomly sampled without replacement by weight, seeded by S.
  • maxWindows number of subnet validators are retrieved in order from the sampled set. maxWindows is currently set to 6.
  • The maxWindows validators are the next block's proposer list.

Each proposer gets assigned a submission window of length WindowDuration. currently set at 5 seconds. A proposer in position i in the proposers list has its submission windows starting i × WindowDuration after the parent block's timestamp. Any node can issue a block maxWindows × WindowDuration after the parent block's timestamp.

Snowman++ validations

The following validation rules are enforced:

  • Given a proposervm.Block C and its parent block P, P's inner block must be C's inner block's parent.
  • A block must have a PChainHeight is larger or equal to its parent's PChainHeight (PChainHeight is monotonic).
  • A block must have a PChainHeight that is less or equal to current P-Chain height.
  • A block must have a Timestamp larger or equal to its parent's Timestamp (Timestamp is monotonic)
  • A block received by a node at time t_local must have a Timestamp such that Timestamp < t_local + maxSkew (a block too far in the future is invalid). maxSkew is currently set to 10 seconds.
  • A block issued by a proposer p which has a position i in the current proposer list must have its timestamp at least i × WindowDuration seconds after its parent block's Timestamp. A block issued by a validator not contained in the first maxWindows positions in the proposal list must have its timestamp at least maxWindows × WindowDuration seconds after its parent block's Timestamp.
  • A block issued within a time window must have a valid Signature, i.e. the signature must be verified to have been by the proposer Certificate included in block header.
  • A proposervm.Block's inner block must be valid.

A proposervm.Block violating any of these rules will be marked as invalid. Note, however, that a proposervm.Block invalidity does not imply its inner block invalidity. Notably the validation rules above enforce the following invariants:

  • Only one verification attempt will be issued to a valid inner block. On the contrary multiple verification calls can be issued to invalid inner blocks.
  • Rejection of a proposervm.Block does not entail rejection of inner block it wraps. This is necessary since different proposervm.Blocks can wrap the same inner block. Without proper handling this could result in an inner block being accepted after being rejected. Therefore, an inner block is only rejected when a sibling block is being accepted.

ProposerVM Implementation Details

Snowman++ must have an activation time, following which the congestion control mechanism will be enforced.

Block Structure

Generally speaking the proposerVM wraps an inner block generated by the inner VM into a proposervm.Block. Once the activation time has past, the proposervm.Block will attach a header to inner block, carrying all the fields necessary to implement the congestion mechanism. No changes are performed on the inner block, but the inclusion of the header does change the block ID and the serialized version of the block.

There are three kinds of proposervm.Blocks:

  • preForkBlock is a simple wrapper of an inner block. A preForkBlock does not change the ID or serialization of an inner block; it's simply an in-memory object allowing correct verification of preForkBlocks (see Execution modes section below for further details of why this is required).
  • postForkBlock adds congestion-control related fields to an inner block, resulting in a different ID and serialization than the inner block. Note that for such blocks, serialization is a two step process: the header is serialized at the proposerVM level, while the inner block serialization is deferred to the inner VM.
  • postForkOption wraps inner blocks that are associated with an Oracle Block. This enables oracle blocks to be issued without enforcing the congestion control mechanism. Similarly to postForkBlocks, this changes the block's ID and serialization.
Execution modes

When creating a proposerVM, one must specify an activation time following which the congestion control mechanism will be enforced. Therefore, the proposerVM must be able to execute before the mechanism is enforced, after the mechanism is enforced, and during the enabling of the mechanism.

Pre-fork Execution

Before the congestion control mechanism is enforced, it must hold that the chain's rules are unchanged.

  • preForkBlocks are the only blocks that are able to be verified successfully.
Post-fork Execution

After the congestion control mechanism is enforced, it must hold that the inner VM's rules are still enforced, and that blocks will only be verified if they are signed by the correct validator.

  • If an inner block's Verify is called, then it is enforced that the proposervm.Blocks additional verification must have already passed. This maintains the invariant that when Verify passes, either Accept or Reject will eventually be called on the block.
  • Given a parent block, there must be one deterministic proposer window for every child block. This ensures that modifying the child block doesn't allow conflicting proposal windows.
  • The proposal windows should rotate after each block, to avoid a single proposer from dominating the block production.
  • postForkBlocks are issued only when the local node's ID is currently in their proposal window.
  • postForkOptions are only allowed after a postForkBlock that implements Options and do not require signatures.
Fork Transition Execution
  • Each proposervm.Block whose timestamp follows the activation time, must have its children made up of postForkBlocks or postForkOptions.

Documentation

Overview

Package proposervm is a generated GoMock package.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Block 

type Block interface {
	snowman.Block
	// contains filtered or unexported methods
}

type MockPostForkBlock added in v1.9.1 

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

MockPostForkBlock is a mock of PostForkBlock interface.

func NewMockPostForkBlock added in v1.9.1 

func NewMockPostForkBlock(ctrl *gomock.Controller) *MockPostForkBlock

NewMockPostForkBlock creates a new mock instance.

func (*MockPostForkBlock) Accept added in v1.9.1 

func (m *MockPostForkBlock) Accept() error

Accept mocks base method.

func (*MockPostForkBlock) Bytes added in v1.9.1 

func (m *MockPostForkBlock) Bytes() []byte

Bytes mocks base method.

func (*MockPostForkBlock) EXPECT added in v1.9.1 

func (m *MockPostForkBlock) EXPECT() *MockPostForkBlockMockRecorder

EXPECT returns an object that allows the caller to indicate expected use.

func (*MockPostForkBlock) Height added in v1.9.1 

func (m *MockPostForkBlock) Height() uint64

Height mocks base method.

func (*MockPostForkBlock) ID added in v1.9.1 

func (m *MockPostForkBlock) ID() ids.ID

ID mocks base method.

func (*MockPostForkBlock) Parent added in v1.9.1 

func (m *MockPostForkBlock) Parent() ids.ID

Parent mocks base method.

func (*MockPostForkBlock) Reject added in v1.9.1 

func (m *MockPostForkBlock) Reject() error

Reject mocks base method.

func (*MockPostForkBlock) Status added in v1.9.1 

func (m *MockPostForkBlock) Status() choices.Status

Status mocks base method.

func (*MockPostForkBlock) Timestamp added in v1.9.1 

func (m *MockPostForkBlock) Timestamp() time.Time

Timestamp mocks base method.

func (*MockPostForkBlock) Verify added in v1.9.1 

func (m *MockPostForkBlock) Verify() error

Verify mocks base method.

type MockPostForkBlockMockRecorder added in v1.9.1 

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

MockPostForkBlockMockRecorder is the mock recorder for MockPostForkBlock.

func (*MockPostForkBlockMockRecorder) Accept added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Accept() *gomock.Call

Accept indicates an expected call of Accept.

func (*MockPostForkBlockMockRecorder) Bytes added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Bytes() *gomock.Call

Bytes indicates an expected call of Bytes.

func (*MockPostForkBlockMockRecorder) Height added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Height() *gomock.Call

Height indicates an expected call of Height.

func (*MockPostForkBlockMockRecorder) ID added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) ID() *gomock.Call

ID indicates an expected call of ID.

func (*MockPostForkBlockMockRecorder) Parent added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Parent() *gomock.Call

Parent indicates an expected call of Parent.

func (*MockPostForkBlockMockRecorder) Reject added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Reject() *gomock.Call

Reject indicates an expected call of Reject.

func (*MockPostForkBlockMockRecorder) Status added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Status() *gomock.Call

Status indicates an expected call of Status.

func (*MockPostForkBlockMockRecorder) Timestamp added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Timestamp() *gomock.Call

Timestamp indicates an expected call of Timestamp.

func (*MockPostForkBlockMockRecorder) Verify added in v1.9.1 

func (mr *MockPostForkBlockMockRecorder) Verify() *gomock.Call

Verify indicates an expected call of Verify.

type PostForkBlock 

type PostForkBlock interface {
	Block
	// contains filtered or unexported methods
}

type VM 

type VM struct {
	block.ChainVM

	state.State

	proposer.Windower
	tree.Tree
	scheduler.Scheduler
	mockable.Clock
	// contains filtered or unexported fields
}

func New 

func New(
	vm block.ChainVM,
	activationTime time.Time,
	minimumPChainHeight uint64,
) *VM

func (*VM) BatchedParseBlock added in v1.6.4 

func (vm *VM) BatchedParseBlock(blks [][]byte) ([]snowman.Block, error)

func (*VM) BuildBlock 

func (vm *VM) BuildBlock() (snowman.Block, error)

func (*VM) Commit added in v1.7.5 

func (vm *VM) Commit() error

func (*VM) GetAncestors added in v1.6.4 

func (vm *VM) GetAncestors(
	blkID ids.ID,
	maxBlocksNum int,
	maxBlocksSize int,
	maxBlocksRetrivalTime time.Duration,
) ([][]byte, error)

func (*VM) GetBlock 

func (vm *VM) GetBlock(id ids.ID) (snowman.Block, error)

func (*VM) GetBlockIDAtHeight added in v1.7.5 

func (vm *VM) GetBlockIDAtHeight(height uint64) (ids.ID, error)

vm.ctx.Lock should be held

func (*VM) GetFullPostForkBlock added in v1.7.5 

func (vm *VM) GetFullPostForkBlock(blkID ids.ID) (snowman.Block, error)

Note: this is a contention heavy call that should be avoided for frequent/repeated indexer ops

func (*VM) GetLastStateSummary added in v1.7.11 

func (vm *VM) GetLastStateSummary() (block.StateSummary, error)

func (*VM) GetOngoingSyncStateSummary added in v1.7.11 

func (vm *VM) GetOngoingSyncStateSummary() (block.StateSummary, error)

func (*VM) GetStateSummary added in v1.7.11 

func (vm *VM) GetStateSummary(height uint64) (block.StateSummary, error)

func (*VM) Initialize 

func (vm *VM) Initialize(
	ctx *snow.Context,
	dbManager manager.Manager,
	genesisBytes []byte,
	upgradeBytes []byte,
	configBytes []byte,
	toEngine chan<- common.Message,
	fxs []*common.Fx,
	appSender common.AppSender,
) error

func (*VM) LastAccepted 

func (vm *VM) LastAccepted() (ids.ID, error)

func (*VM) ParseBlock 

func (vm *VM) ParseBlock(b []byte) (snowman.Block, error)

func (*VM) ParseStateSummary added in v1.7.11 

func (vm *VM) ParseStateSummary(summaryBytes []byte) (block.StateSummary, error)

Note: it's important that ParseStateSummary do not use any index or state to allow summaries being parsed also by freshly started node with no previous state.

func (*VM) SetPreference 

func (vm *VM) SetPreference(preferred ids.ID) error

func (*VM) SetState added in v1.7.5 

func (vm *VM) SetState(newState snow.State) error

func (*VM) Shutdown added in v1.7.5 

func (vm *VM) Shutdown() error

shutdown ops then propagate shutdown to innerVM

func (*VM) StateSyncEnabled added in v1.7.11 

func (vm *VM) StateSyncEnabled() (bool, error)

func (*VM) VerifyHeightIndex added in v1.7.5 

func (vm *VM) VerifyHeightIndex() error

vm.ctx.Lock should be held

Source Files

View all Source files

Directories

Path Synopsis
Package state is a generated GoMock package.
 Package state is a generated GoMock package.
Package tree is a generated GoMock package.
 Package tree is a generated GoMock package.

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.