proposervm

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.
• OChainHeight the height of the last accepted block on the O-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 O-Chain. Let a block have a height H and O-Chain height O 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 O are retrieved from O-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 O, O's inner block must be C's inner block's parent.
• A block must have a OChainHeight is larger or equal to its parent's OChainHeight (OChainHeight is monotonic).
• A block must have a OChainHeight that is less or equal to current O-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
• type Block
• type MockPostForkBlock
  • func NewMockPostForkBlock(ctrl *gomock.Controller) *MockPostForkBlock
  • func (m *MockPostForkBlock) Accept(arg0 context.Context) error
  • func (m *MockPostForkBlock) Bytes() []byte
  • func (m *MockPostForkBlock) EXPECT() *MockPostForkBlockMockRecorder
  • func (m *MockPostForkBlock) Height() uint64
  • func (m *MockPostForkBlock) ID() ids.ID
  • func (m *MockPostForkBlock) Parent() ids.ID
  • func (m *MockPostForkBlock) Reject(arg0 context.Context) error
  • func (m *MockPostForkBlock) Status() choices.Status
  • func (m *MockPostForkBlock) Timestamp() time.Time
  • func (m *MockPostForkBlock) Verify(arg0 context.Context) error
• type MockPostForkBlockMockRecorder
  • func (mr *MockPostForkBlockMockRecorder) Accept(arg0 interface{}) *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Bytes() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Height() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) ID() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Parent() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Reject(arg0 interface{}) *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Status() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Timestamp() *gomock.Call
  • func (mr *MockPostForkBlockMockRecorder) Verify(arg0 interface{}) *gomock.Call
• type PostForkBlock
• type VM
  • func New(vm block.ChainVM, activationTime time.Time, minimumOChainHeight uint64, ...) *VM
  • func (vm *VM) BatchedParseBlock(ctx context.Context, blks [][]byte) ([]snowman.Block, error)
  • func (vm *VM) BuildBlock(ctx context.Context) (snowman.Block, error)
  • func (vm *VM) Commit() error
  • func (vm *VM) GetAncestors(ctx context.Context, blkID ids.ID, maxBlocksNum int, maxBlocksSize int, ...) ([][]byte, error)
  • func (vm *VM) GetBlock(ctx context.Context, id ids.ID) (snowman.Block, error)
  • func (vm *VM) GetBlockIDAtHeight(ctx context.Context, height uint64) (ids.ID, error)
  • func (vm *VM) GetFullPostForkBlock(ctx context.Context, blkID ids.ID) (snowman.Block, error)
  • func (vm *VM) GetLastStateSummary(ctx context.Context) (block.StateSummary, error)
  • func (vm *VM) GetOngoingSyncStateSummary(ctx context.Context) (block.StateSummary, error)
  • func (vm *VM) GetStateSummary(ctx context.Context, height uint64) (block.StateSummary, error)
  • func (vm *VM) Initialize(ctx context.Context, chainCtx *snow.Context, dbManager manager.Manager, ...) error
  • func (vm *VM) LastAccepted(ctx context.Context) (ids.ID, error)
  • func (vm *VM) ParseBlock(ctx context.Context, b []byte) (snowman.Block, error)
  • func (vm *VM) ParseStateSummary(ctx context.Context, summaryBytes []byte) (block.StateSummary, error)
  • func (vm *VM) SetPreference(ctx context.Context, preferred ids.ID) error
  • func (vm *VM) SetState(ctx context.Context, newState snow.State) error
  • func (vm *VM) Shutdown(ctx context.Context) error
  • func (vm *VM) StateSyncEnabled(ctx context.Context) (bool, error)
  • func (vm *VM) VerifyHeightIndex(context.Context) error

Constants

const (
	// DefaultMinBlockDelay should be kept as whole seconds because block
	// timestamps are only specific to the second.
	DefaultMinBlockDelay = time.Second
	// DefaultNumHistoricalBlocks as 0 results in never deleting any historical
	// blocks.
	DefaultNumHistoricalBlocks uint64 = 0
)

Types

type Block

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

type MockPostForkBlock

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

MockPostForkBlock is a mock of PostForkBlock interface.

func NewMockPostForkBlock

func NewMockPostForkBlock(ctrl *gomock.Controller) *MockPostForkBlock

NewMockPostForkBlock creates a new mock instance.

func (*MockPostForkBlock) Accept

func (m *MockPostForkBlock) Accept(arg0 context.Context) error

Accept mocks base method.

func (*MockPostForkBlock) Bytes

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

Bytes mocks base method.

func (*MockPostForkBlock) EXPECT

func (m *MockPostForkBlock) EXPECT() *MockPostForkBlockMockRecorder

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

func (*MockPostForkBlock) Height

func (m *MockPostForkBlock) Height() uint64

Height mocks base method.

func (*MockPostForkBlock) ID

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

ID mocks base method.

func (*MockPostForkBlock) Parent

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

Parent mocks base method.

func (*MockPostForkBlock) Reject

func (m *MockPostForkBlock) Reject(arg0 context.Context) error

Reject mocks base method.

func (*MockPostForkBlock) Status

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

Status mocks base method.

func (*MockPostForkBlock) Timestamp

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

Timestamp mocks base method.

func (*MockPostForkBlock) Verify

func (m *MockPostForkBlock) Verify(arg0 context.Context) error

Verify mocks base method.

type MockPostForkBlockMockRecorder

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

MockPostForkBlockMockRecorder is the mock recorder for MockPostForkBlock.

func (*MockPostForkBlockMockRecorder) Accept

func (mr *MockPostForkBlockMockRecorder) Accept(arg0 interface{}) *gomock.Call

Accept indicates an expected call of Accept.

func (*MockPostForkBlockMockRecorder) Bytes

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

Bytes indicates an expected call of Bytes.

func (*MockPostForkBlockMockRecorder) Height

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

Height indicates an expected call of Height.

func (*MockPostForkBlockMockRecorder) ID

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

ID indicates an expected call of ID.

func (*MockPostForkBlockMockRecorder) Parent

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

Parent indicates an expected call of Parent.

func (*MockPostForkBlockMockRecorder) Reject

func (mr *MockPostForkBlockMockRecorder) Reject(arg0 interface{}) *gomock.Call

Reject indicates an expected call of Reject.

func (*MockPostForkBlockMockRecorder) Status

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

Status indicates an expected call of Status.

func (*MockPostForkBlockMockRecorder) Timestamp

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

Timestamp indicates an expected call of Timestamp.

func (*MockPostForkBlockMockRecorder) Verify

func (mr *MockPostForkBlockMockRecorder) Verify(arg0 interface{}) *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,
	minimumOChainHeight uint64,
	minBlkDelay time.Duration,
	numHistoricalBlocks uint64,
	stakingLeafSigner crypto.Signer,
	stakingCertLeaf *staking.Certificate,
) *VM

New performs best when [minBlkDelay] is whole seconds. This is because block timestamps are only specific to the second.

func (*VM) BatchedParseBlock

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

func (*VM) BuildBlock

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

func (*VM) Commit

func (vm *VM) Commit() error

func (*VM) GetAncestors

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

func (*VM) GetBlock

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

func (*VM) GetBlockIDAtHeight

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

vm.ctx.Lock should be held

func (*VM) GetFullPostForkBlock

func (vm *VM) GetFullPostForkBlock(ctx context.Context, 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

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

func (*VM) GetOngoingSyncStateSummary

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

func (*VM) GetStateSummary

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

func (*VM) Initialize

func (vm *VM) Initialize(
	ctx context.Context,
	chainCtx *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(ctx context.Context) (ids.ID, error)

func (*VM) ParseBlock

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

func (*VM) ParseStateSummary

func (vm *VM) ParseStateSummary(ctx context.Context, 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(ctx context.Context, preferred ids.ID) error

func (*VM) SetState

func (vm *VM) SetState(ctx context.Context, newState snow.State) error

func (*VM) Shutdown

func (vm *VM) Shutdown(ctx context.Context) error

shutdown ops then propagate shutdown to innerVM

func (*VM) StateSyncEnabled

func (vm *VM) StateSyncEnabled(ctx context.Context) (bool, error)

func (*VM) VerifyHeightIndex

func (vm *VM) VerifyHeightIndex(context.Context) error

vm.ctx.Lock should be held