Bootstrapping algorithm

Overview

The general idea for the bootstrapping algorithm is as follows:

query every peer's current branch
attempt to find a short sequence, call it a segment, of blocks which are supported by a quorum of peers with which to extend the node's chain
- the segment starts at the block above the node's current head and ends at the latest, earliest peer block (see notes for step 3)
- first, get all the headers in this sequence
- then, get the operations only for the blocks with a quorum of support
continue extending the node's chain by short segments until our current head has a timestamp within the threshold to be considered Synced
the only caveat is that the node's header retention strategy may have to change once we've gotten within 8 cycles of our peer's current heads to hedge against reorgs

General remarks

This algorithm is not optimized. We may be sending more (or less) messages than is actually necessary. The current focus is safety and correctness. Once this is achieved, we can shift our focus to performance. I don't claim to have even made all "obvious" optimizations in this doc.

All messages sent by the node should have a timer associated with them in order to have a clearly defined notion of when the node has not received a response. Not receiving a response, unfortunately, cannot always be penalized (see more notes). However, receiving a valid response to a request should always increase the peer's score, if not already at the max value (here, valid simply means the response has the correct type and if we requested a header or operation, it has the expected hash, it isn't a duplicate, etc).

Quorum always means > 2/3 of the node's current peers

Initial conditions

The node begins the bootstrapping process with:

a current head (block), either genesis or a block provided by a snapshot
a set of connections/peers
an Unsynced synchronization status
all peers with maximum peer_score
all peers having the genesis block as their current head
a global earliest_hashes variable instantiated by an empty set
a global pending_headers variable instantiated by an empty map
a global pending_operations variable instantiated by an empty map

The earliest_hashes variable is used as a kind of temporary target to meet before applying blocks. This variable has a type like:

pub type Hashes = HashSet<BlockHashes>

The pending_headers and pending_operations variables are used to temporarily aggregate (the short segments mentioned above) headers and corresponding operations, respectively.

pending_headers has a type like:

pub type PendingHeaders = HashMap<BlockLevel, HashSet<HeaderData>>

where

pub struct HeaderData {
  header : Header,
  hash : BlockHash,
  supporters : HashSet<PeerId>
}

and pending_operations has a type like:

pub type PendingOperations = HashMap<Level, HashSet<Vec<Operation>>>

(these types are not meant to be taken literally, just to give an idea)

Steps

Request GetCurrentBranch from each peer

if the peer has already advertised its current branch, we don't need to request it

For each received CurrentBranchMessage (see notes):

determine the earliest (lowest level) hash above the node's current head and add this hash to a global, mutable set earliest_hashes
validate all hashes that correspond to a block with level at or below the node's current head's level
- disconnect from each peer which does not pass this validation step (their branch deviates from what the node takes as a given)
adjust the peer's current head if the supplied header has a higher level or fitness
- this is all the node does when handling CurrentHeadMessages while Unsynced

Request all headers corresponding to the hashes in earliest_hashes from each responsive peer by sending a GetBlockHeaders message

as the node receives more and more CurrentBranchMessages, the collection of earliest_hashes grows
- the node just uses whatever value it reads from earliest_hashes to make the list of headers it requests from each peer, initially
- the node keeps track of which hashes have been requested from each peer and as we receive more earliest hashes, we make the corresponding block header requests from all peers whom we have not requested it
  - when new hashes are added to earliest_hashes, the node requests all these headers from the sender and the not-yet-requested ones from all other peers
- ultimately, the node should request all received headers from each peer (well, not quite, see notes)

For each received BlockHeaderMessage:

check hash of received header was actually requested from this peer
- if the header wasn't requested, then we should penalize the peer
add header data to pending_headers and update
- this requires calculating implied support for any known (i.e. pending) ancestors and support from children (see notes)
check if any headers have a quorum of support
- if not, the node continues requesting and handling block headers
- else, prune the pending_headers
  - for each level, if there is a header with a quorum of support, remove the rest at that level
    - if there is a quorum of support for a header, then all ancestors also have a quorum of support
  - any peer supporting a header other than the one with quorum support at any level should be penalized
if it's not the case that all remaining headers in pending_headers have quorum support, then the node continues requesting and handling headers as before
- effectively, the node goes back to step 3
- else, continue to step 5

The node requests all operations for each block with a header in pending_headers from any peer it still has a connection with

start with the operations for the earliest block and move to the latest, adding the operations to pending_operations upon receipt
once the node has all operations for the earliest block, they apply it
update current head accordingly
repeat for all remaining pending blocks

After applying all blocks in the segment, clear the earliest_hashes, pending_headers, and pending_operations variables

populate earliest_hashes with each peer's next earliest hash, if any exist
go back to requesting headers (step 3)

Notes on algorithm steps

These requests are made concurrently, order is irrelevant as long as the node makes a request to all peers

the node only needs to check if they already have a CurrentBranchMessage from the peer before sending a request
all messages carry a chain_id parameter, this spec assumes all messages are for the same chain_id

All CurrentBranchMessages can be handled concurrently

the individual steps in 2. are performed sequentially for a given message/peer
CurrentBranchMessages have two fields: chain_id and current_branch
- current_branch has two fields: current_head and history
  - current_head is the header of the sender's current head
  - history is a vector of BlockHashes which are determined by Steps
    - these Steps are deterministically generated from a Seed which depends only on the CryptoBoxPublicKeyHashes of the sender and receiver
    - the Steps basically tell us the "distance" between blocks in the history
    - starting from the supplied head's level, we can successively subtract the Step values from this number to produce the levels of each of the hashes in the history

// for example
// since we want to reconstruct the levels of the hashes sent to us, we generate the seed the same way the peer did
// current_head refers to the header provided by the peer in the CurrentBranchMessage
// hist_len is the length of the history vector
fn reconstruct_history_levels(node_id: &CryptoBoxPublicKeyHash, peer_id: &CryptoBoxPublicKeyHash, current_head: &BlockHeader, hist_len: i32) -> Vec<Level> {
    // peer is the sender, node is the receiver
    let seed = Seed::new(peer_id, node_id);
    let mut step = Step::init(&seed, current_head.message_hash()?.try_into()?.as_ref()); // we want a ref to the hash of current_head
    let mut l = current_head.level;
    let mut ls: Vec<Level> = Vec::new();
    let mut i: i32 = 0;
    // compute a vector of all the levels corresponding to the hashes in history
    while (i < hist_len) {
        step.next();
        ls.push(l - step);
        l -= step;
        i += 1;
    }
    ls
}

whether earliest_hashes is implemented as a set or list without duplicates is irrelevant
obviously, we will need to have a locking mechanism for earliest_hashes since it will be read and written to by several threads
the node disregards the mempool portion of CurrentHeadMessages while Unsynced

The order in which the node requests block headers from the responsive peers (those who have sent a CurrentBranchMessage) is not important as long as the node eventually sees a quorum of support for some of the requested block headers

these initial requests can be made concurrently
upon handling a CurrentBranchMessage, the node can immediately add the earliest hash from that peer to earliest_hashes
the later requests can also be made concurrently
- it probably makes the most sense to have one worker per peer/connection which runs every so often, checks for new earliest hashes, and makes the corresponding requests
- the frequency at which this worker performs these tasks should be proportional to the peer's score
we only need to request all earliest hashes from each peer if we don't have sufficient support for a single branch prior to this point
- the goal here is to find a quorum of peers supporting one segment
  - the segment being from the block above the node's current head to the latest, earliest block
  - it is probably confusing to read a phase like "latest, earliest block"... all we mean here, is the latest (highest level) out of the earliest blocks

The node can handle BlockHeaderMessages concurrently

a penalty can either be a decrease to the peer's score or {grey, black}listing them
updating support for a header:
- pending_headers is really a directed acyclic graph and in general, it is not connected
- daggy may be useful in implementing this
  - it's not necessarily connected because headers can arrive in any order
  - edges are directed from higher-level (child) to lower-level (parent) headers
  - edges only exist between a parent and a child
- for example, if a peer p sends the node a header hd, they support this header explicitly
  - if hd has already been included in pending_headers, we add p to the set of supporters
  - else, we add hd to pending_headers with p as the only supporter
  - now update the support for all headers in pending_headers:
    - starting at the tip (header with no child) of each branch, traverse the branch down to the base (header with no parent)
    - the supporters of the tip is unchanged
    - for each non-tip header in the branch, add the child's supporters to its set of of supporters
at the moment, headers can only be requested by GetBlockHeadersMessage
- once Octez supports GetPredecessorHeaderMessages, the header acquisition process can be sped up
  - this will enable us to request blocks based on level instead of hashes

The operation requests should be spread out among as many reliable peers as possible to parallelize the task

we do not need redundancy here since we've already established consensus on the headers in the segment and we can check hashes to verify the operations

Navigation Menu

Uh oh!

Bootstrapping algorithm

Overview

General remarks

Initial conditions

Steps

Notes on algorithm steps

More notes and questions

Requesting blocks headers

Handling disconnects

Handling timeouts

Reorgs

Questions

Uh oh!

FilesExpand file tree

bootstrapping_algorithm.md

Latest commit

History

bootstrapping_algorithm.md

File metadata and controls

Bootstrapping algorithm

Overview

General remarks

Initial conditions

Steps

Notes on algorithm steps

More notes and questions

Requesting blocks headers

Handling disconnects

Handling timeouts

Reorgs

Questions