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 xoringH
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 to6
.- 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'sPChainHeight
(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'sTimestamp
(Timestamp
is monotonic) - A block received by a node at time
t_local
must have aTimestamp
such thatTimestamp < t_local + maxSkew
(a block too far in the future is invalid).maxSkew
is currently set to10 seconds
. - A block issued by a proposer
p
which has a positioni
in the current proposer list must have its timestamp at leasti × WindowDuration
seconds after its parent block'sTimestamp
. A block issued by a validator not contained in the firstmaxWindows
positions in the proposal list must have its timestamp at leastmaxWindows × WindowDuration
seconds after its parent block'sTimestamp
. - A block issued within a time window must have a valid
Signature
, i.e. the signature must be verified to have been by the proposerCertificate
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 differentproposervm.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. ApreForkBlock
does not change the ID or serialization of an inner block; it's simply an in-memory object allowing correct verification ofpreForkBlocks
(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 theproposerVM
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 topostForkBlocks
, 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 theproposervm.Blocks
additional verification must have already passed. This maintains the invariant that whenVerify
passes, eitherAccept
orReject
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 apostForkBlock
that implementsOptions
and do not require signatures.
Fork Transition Execution
- Each
proposervm.Block
whose timestamp follows the activation time, must have its children made up ofpostForkBlocks
orpostForkOptions
.
Documentation ¶
Overview ¶
Package proposervm is a generated GoMock package.
Index ¶
- Constants
- type Block
- type 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 (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, db database.Database, ...) 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 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
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(arg0 context.Context) 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(arg0 context.Context) 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.
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(arg0 interface{}) *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(arg0 interface{}) *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(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, minimumPChainHeight 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 ¶ added in v1.6.4
func (*VM) GetAncestors ¶ added in v1.6.4
func (*VM) GetBlockIDAtHeight ¶ added in v1.7.5
vm.ctx.Lock should be held
func (*VM) GetFullPostForkBlock ¶ added in v1.7.5
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) GetOngoingSyncStateSummary ¶ added in v1.7.11
func (*VM) GetStateSummary ¶ added in v1.7.11
func (*VM) Initialize ¶
func (*VM) ParseBlock ¶
func (*VM) ParseStateSummary ¶ added in v1.7.11
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.