P2P protocol
The section describes a p2p protocol used in the current implementation to aim for:
- low-latency event propagation
- fast initial download of events
- tolerance to fork-events
Although this p2p protocol works in the same manner like existing p2p protocols for exchanging blocks in Blockchain-based ledgers, it is engineered to handle the graph structure of Lachesis.
The protocol's algorithm includes the following:
- Event pack: Each peer arranged event blocks into packs, which form as a "chain" of event packs. A node joining the network will download event packs from peers. Pack downloading is primarily active during initial event download.
- Event broadcast: when a node has already downloaded all the packs from its peers in the network, the node will then exchange events with peers through broadcasting. Broadcasting (and relaying) events among peers is primarily active when node has already synced up.
P2p protocol is a “transport” level in which events are delivered and exchanged by peers. This p2p doesn’t depend on consensus algorithm. It is not necessary for a node to know which peer delivers which event, as long as these events are valid and signed. Nodes of the network use the protocol to boost up event propagation and new nodes do not neccessarily connect to validator nodes to sync up.
We found that exchanging event blocks is not efficient if doing block by block. That is because it will generate lots of requests among peers.
On consensus, event blocks are packed into (finalized) blocks (of a final chain of blocks). Each Atropos confirms a set of events, orders them and these are packed into a block. Events in a block are written on disk in this order. The blocks are ordered by the ordering of Atroposes that confirmed them. These blocks are identical on all the nodes (thanks to our aBFT Lachesis).
Yet we don't use these final blocks for gossiping, because they include only events with transactions.
Instead, each node maintains a similar division of event blocks into packs. Similar to (final) block, every pack is a set of event blocks, observed by a set (not by a single event, unlike block) of head events. Each pack includes all the observed events, including cheater’s. Packs are built uniformly in size, so basically we create a new pack (by increasing packs counter and saving current global heads), when the size/length of current pack is greater than N.
Every pack may be connected if and only if all the previous packs are connected. We may run a binary search to find a lowest pack not downloaded from a peer, to avoid downloading already connected event blocks.
Each node has its owns packs division, not identical to packs of other peers.
New nodes download events pack-by-pack from peers in the network. Once synced up, nodes can then send/receive new events via events broadcasting. Synced up nodes don’t need to download packs normally.
input: event ID, peer
The function returns false if peer probably knows about event,
i.e. no need to broadcast the event hash (or full event, if propagation is aggressive)
to this peer.
if peer sent me this event ID?
return false
if I sent event ID to this peer?
return false
return (event's epoch == peer.progress.Epoch OR
event's epoch == peer.progress.Epoch+1)
input: packInfo, events DB
The function returns true if pack is already downloaded on this node.
if I have connected all the events from {packInfo.Heads}
return true
else
return falseEvent blocks in packs are partially ordered by Lamport time.
Events may be connected in the order, in which they are listed in pack.
Event ID starts with epoch:lamport time,
so the sorting is done on DB side, because DB sorts records lexicographically (by key).
input: e (event)
packInfos[Last pack height].numOfEvents += 1
for each parent in e.parents
if parent in {Global heads}
{Global heads}.erase(parent)
{Global heads}.insert(e)
packs[Last pack height].insert(e.ID)The routine marks non-pinned packs as pinned when they become big enough.
if packInfos[Last pack height].numOfEvent >= N
infos[Last pack height].heads = Global heads
Last pack height += 1Signals about the current synchronization status.
The current peer's status is used during packs downloading, and to estimate may peer be interested in the new event or not (based on peer's epoch).
type PeerProgress struct {
Epoch idx.Epoch
NumOfBlocks idx.Block
LastPackInfo PackInfo
LastBlock hash.Event
}Non-aggressive events propagation. Signals about newly-connected batch of events, sending only their IDs.
hash.EventsRequest the batch of events by IDs.
hash.EventsContains the batch of events. May be an answer to GetEventsMsg, or be sent during aggressive events propagation.
[]EventRequest pack infos by epoch:pack indexes
type getPackInfosData struct {
Epoch idx.Epoch
Indexes []idx.Pack
}Contains the requested pack infos. An answer to GetPackInfosMsg.
type PackInfo struct {
Index idx.Pack
Size uint32
NumOfEvents uint32
Heads hash.Events
}
type packInfosData struct {
Epoch idx.Epoch
TotalNumOfPacks idx.Pack // in specified epoch
Infos []PackInfo
}Request pack by epoch:pack index
type getPackData struct {
Epoch idx.Epoch
Index idx.Pack
}Contains the requested pack. An answer to GetPackMsg.
type packData struct {
Epoch idx.Epoch
Index idx.Pack
IDs hash.Events
}RLP is used for messages serialization.
Transactions exchanging is compatible with eth62 protocol.
Lachesis fully supports ETH discv4/discv5 discovery protocols - which are used to find connections in the network.