Lachesis
Lachesis is an open-source software library intended for developers who want to build peer-to-peer (p2p) applications, mobile or other, without having to implement their own consensus algorithm from scratch.
Lachesis is designed to easily plug into any blockchain node written in Golang, or in any other language if provided with a wrapper. Developers can focus on building the application logic and simply integrate with Lachesis to handle the replication aspect. Basically, Lachesis process consensus messages from other nodes and guarantee that everyone processes the same commands in the same order. To do this, it uses a DAG aBFT consensus algorithm.
Lachesis is:
- Asynchronous: Participants have the freedom to process commands at different times.
- Leaderless: No participant plays a 'special' role.
- Byzantine Fault-Tolerant: Supports one third of faulty nodes, including malicious behavior.
- Final: Lachesis's output can be used immediately, no need for block confirmations, etc.
Lachesis is a DAG-based aBFT consensus protocol with guaranteed finality. The Lachesis protocol is leaderless achieving complete asynchrony, no round robin and no proof-of-work. Every confirmed transaction is final, unless more than 1/3W of validators are Byzantine.
Each Lachesis node stores a local acyclic directed graph (DAG) composed of event blocks, each of which contains transactions. In this wiki, the terms 'event' and 'event block' are sometimes used interchangebly. The DAG capturing the happens-before relationship between the events is used to calculate an exact final order of events (and hence transactions) independently on each node.
Events are divided into confirmed and unconfirmed events. New events are unconfirmed, whilst usually events from past 2-3+ frames are all confirmed. For confirmed events, honest nodes can compute their exact order. Uconfirmed events can only be partially ordered.
Consensus results into batches of confirmed events, where each batch of events is called a block. Blocks (or finalized blocks) forming the final chain are calculated from event blocks independently on each node. Unlike PoW, round-robin PoS, coinage PoS and sync BFT, nodes don't send blocks to each other. Only events are being synced between nodes. Validators of the network do not vote on a concrete state of the network, but instead they periodically exchange transactions and events they observe with peers.
Unlike sync BFT (like pBFT), Lachesis do not use new events in current election, but instead they are used to vote for the events in 2-3+ previous virtual elections simultaneously. This leads to a smaller number of created consensus messages, as the same event is reused in different elections. Hence, Lachesis achieves a lower TTF and a smaller consensus overhead comparing to sync BFT.
validator - node which has a right to create new events
Atropos - root which was elected as a block head
decided frame - frame, which has decided its Atropos. In other words, it’s a frame which was translated into a block of final blockchain.
subgraph of event A - graph which contains events which A observes.
In other words, it's a graph which contains only event A and A's ancestors.
Quorum - the quorum is defined as 2/3W+1, where W is the total weight of validators.
QUORUM=TotalStake*2/3 + 1event A is forkless caused by event B means:
In subgraph of event A, A didn’t observe any forks from B’s creator and
at least QUORUM non-cheater validators have observed event B.
A note for experienced readers:
forklessCause is a stricter version of "happened-before" relation, i.e. if B forkless causes A, then B is happened before A.
Yet, unlike "happened-before" relation, forklessCause isn't transitive because it returns false if fork is observed. So if A forkless causes B, and B forkless causes C, it doesn't mean that A forkless causes C. However, if there's no forks in the graph, then forklessCause is always transitive.
Let forklessHappenedBefore(B,A) denote "B is forkless happened before A".
That is, B is happened before A, and event A's subgraph contains no fork from B's creator and at least QUORUM honest validators observed event B.
Thus, forklessCause(A,B) is equivalent to forklessHappenedBefore(B,A).
An event is called a root, if it is forkless caused by QUORUM roots of previous frame.
The root starts new frame. For every event, its frame number is no smaller than self-parent's frame number.
The lowest possible frame number is 1.
A validator can decide new root and frame on an event, based on the following requirements:
// calculate frame number
function calcFrameNumber(e Event)
// e.selfParent.Frame is 1 if no self-parent
for f = e.selfParent.Frame; e is forklessCaused by {QUORUM} roots on frame f; f++ {}
return fA note for experienced readers:
The definition of roots is originally drawn from a multi-round election. Their intuition may be described as below:
Similar to separation of an election into rounds, the graph gets separated into frames. Roots on a frame participate in election of all the roots on prior frames. If X(r1, r2) is a relation between roots, then roots could be seen as virtual voters on a frame, where each root r may vote for either roots on previous frame (1), or for roots on frames prior to previous frame (2). For case (1), r votes FOR/AGAINST according to the relation X(r, rootToVoteFor). For case (2), r votes AS MAJORITY OF votes from related roots on previous frame.
The following example shows a DAG of a network, which consists of 4 validators (Alice, Bob, Carol and Dave).
The label of each vertex is in the form [validator ID][frame number].[event sequence number]. The first letter represents validator's ID. An upper case letter shows the event is a root. First number is frame number, and second number is event's sequence number. For example, vertex 'A1.01' is an root event block (upper-case A), of validator Alice (A), at frame 1 and the event's sequence number is 01.
Examples of the roots logic:
- A1.01 is a root, because it is Alice's first event.
- a1.03 isn't a root, because although it observes 3 roots at frame 1 (A1.01, C1.01, D1.01), it's forkless caused only by 1 root at frame 1 (A1.01).
- A2.04 is a root, because it's forkless caused by at least 3 roots at frame 1 (A1.01, B1.01, D1.01). It receives new frame 2.
During connection of every root y, one iteration of the inner loop is executed.
The procedure computes a coloring of the graph such that each root is assigned with one of the colors {decided as candidate, decided as not a candidate}, or a special temporary state {not decided}.
Once a root is decided with one of the colors by a node, the same color is assigned to the root by
all other nodes, unless more than 1/3W are Byzantine.
This is the core property of Lachesis consensus algorithm.
function decideRoots
for x range roots from lastDecidedFrame + 1
for y range roots from all frames greater than x.frame
// y is a root which votes, x is a voting subject root
round = y.frame - x.frame
if round == 1
// y votes positively if x forkless causes y
y.vote[x] = forklessCause(x, y)
else
prevRoots = getRoots(y.frame-1) // contains at least {QUORUM} events, according to the root definition
yesVotes = 0
noVotes = 0
for prevRoot range prevRoots
if forklessCause(prevRoot, y) == TRUE
// count number of positive and negative votes
// for x from roots which forkless cause y
if prevRoot.vote[x] == TRUE
yesVotes = yesVotes + prevRoot.creator.weight
else
noVotes = noVotes + revRoot.creator.weight
// y votes like a majority of roots from previous frame which forkless cause y
y.vote[x] = (yesVotes - noVotes) >= 0
if yesVotes >= QUORUM
x.candidate = TRUE // decided as a candidate
decidedRoots[x.validator] = x
break
if noVotes >= QUORUM
x.candidate = FALSE // decided as a non-candidate
decidedRoots[x.validator] = x
breakIn the above algorithm, voters are validators. Validators are sorted by their weight first, and by their ID second. This sorting doesn't influence validators' rewards, nor give any other advantage.
Atropos is chosen as a first {decided as candidate} root, where "first" is defined according to the order above. It is worth noting that Atropos may be decided when not all the roots on a frame are decided - it allows to decide frames much earlier when there's a lot of validators, and hence reduce TTF (time to finality).
function chooseAtropos
for validator range sorted validators
root = decidedRoots[validator]
if root == NULL // not decided
return nil // frame isn't decided yet
if root.candidate == TRUE
return root // found Atropos
if root.candidate == FALSE
continueHere, a brief explanation of the algorithm and the coloring is shown as follows:
- If a root has received V>=
QUORUMvotes for a color, then for any other root on next frame, itsprevRoots(contains at leastQUORUMevents, according to the root definition) will overlap with V, and resulting overlapping will contain more than 1/2 of theprevRoots. It's crucial thatQUORUMis 2/3W+1, not just 2/3W. The condition implies that ALL the roots on next frame will vote for the same color unanimously. - A malicious validator may have multiple roots on the same frame (due to forks).
But due to the
forklessCauserelation and that no more than 1/3W are Byzantine, no more than one of the roots may be voted YES. The algorithm assigns a color only in round >= 2, soprevRootswill be "filtered" byforklessCauserelation, to prevent deciding differently due to forks. - If a root has received at least one YES vote, then it exists in the graph. Non-existing events (from an offline validator) will be decided NO unanimously. Thus, non-existing event cannot be assigned a {decided as candidate} color, and hence it cannot become Atropos.
- Technically, the election may take forever. Practically, however, the elections end mostly in 2nd or 3rd round.
- It would be possible to add a round with pseudo-random votes every C's round, though it may bring unnecessary complexity.
The following example can be launched by the command go test ./abft -run TestLachesisRandomRoots -v in lachesis-base repo.
Network parameters of the example: 4 validators with equal weights, and maximum number of parents is 2.
Below is a DAG example written in ASCII format. Each event has a name starting with a letter, which stands for validator's ID. The letter is in upper case if the event is root. Following the first letter is a frame number and then event's sequence number.
If there is a problem while reading the ASCII scheme, you can refer to the "Steps" section below, to determine the parents list of an event.
A1.01
║ ║
╠════════ B1.01
║ ║ ║
╠════════─╫─═══════ C1.01
║ ║ ║ ║
╠════════─╫─═══════─╫─═══════ D1.01
║ ║ ║ ║
a1.02════─╫─═══════─╫─════════╣
║ ║ ║ ║
║ b1.02════─╫─════════╣
║ ║ ║ ║
║ ║ c1.02═════╣
║ ║ ║ ║
a1.03════─╫─════════╣ ║
║ ║ ║ ║
╠════════ B2.03 ║ ║
║ ║║ ║ ║
║ ║╚═══════─╫─═══════ d1.02
║ ║ ║ ║
║ ║ C2.03═════╣
║ ║ ║ ║
A2.04════─╫─════════╣ ║
║ ║ ║ ║
║ b2.04═════╣ ║
║ ║║ ║ ║
║ ║╚═══════─╫─═══════ D2.03
║ ║ ║ ║
║ ║ c2.04═════╣
║ ║ ║ ║
║ ║ ╠════════ d2.04
║ ║ ║ ║
A3.05════─╫─═══════─╫─════════╣
║ ║ ║ ║
╠════════ B3.05 ║ ║
║ ║ ║ ║
║ ╠════════ C3.05 ║
║ ║ ║ ║
║ ╠════════─╫─═══════ D3.05
║ ║ ║ ║
a3.06════─╫─═══════─╫─════════╣
║ ║ ║ ║
║ b3.06════─╫─════════╣
║ ║ ║ ║
║ ║ c3.06═════╣
║ ║ ║ ║
║ B4.07═════╣ ║
║ ║ ║ ║
║ ║ ╠════════ d3.06
║ ║ ║ ║
A4.07════─╫─═══════─╫─════════╣
║ ║ ║ ║
a4.08═════╣ ║ ║
║║ ║ ║ ║
║╚═══════─╫─═══════ C4.07 ║
║ ║ ║ ║
║ b4.08═════╣ ║
║ ║ ║ ║
a4.09═════╣ ║ ║
║3 ║ ║ ║
║╚═══════─╫─═══════─╫─═══════ D4.07
║ ║ ║ ║
║ ║ c4.08═════╣
║ ║ ║ ║
║ b4.09═════╣ ║
║ ║ ║ ║
║ ╠════════ c4.09 ║
║ ║ ║ ║
A5.10════─╫─════════╣ ║
║ ║ ║ ║
╠════════ B5.10 ║ ║
║ ║3 ║ ║
║ ║╚═══════─╫─═══════ d4.08
║║ ║ ║ ║
║╚═══════─╫─═══════─╫─═══════ D5.09
║ ║ ║ ║
║ ║ C5.10═════╣
║ ║ ║ ║
╠════════─╫─═══════─╫─═══════ d5.10
║ ║ ║ ║
a5.11════─╫─═══════─╫─════════╣
║ ║ ║ ║
╠════════ b5.11 ║ ║
║ ║ ║ ║
║ ╠════════ c5.11 ║
║ ║ ║ ║
A6.12════─╫─════════╣ ║
║ ║ ║ ║
║ ╠════════─╫─═══════ d5.11
║ ║ ║ ║
║ b5.12════─╫─════════╣
║ ║ ║ ║
║ ╠════════ C6.12 ║
║ ║ ║ ║
╠════════─╫─═══════─╫─═══════ D6.12
║ ║ ║ ║
a6.13════─╫─═══════─╫─════════╣
║ ║ ║ ║
║ B6.13════─╫─════════╣
║ ║ ║ ║
a6.14═════╣ ║ ║
║║ ║ ║ ║
║╚═══════─╫─═══════ c6.13 ║
║ ║ ║ ║
╠════════─╫─═══════ C7.14 ║
║║ ║ ║ ║
║╚═══════─╫─═══════─╫─═══════ d6.13
║ ║ ║ ║
║ b6.14════─╫─════════╣
║ ║ ║ ║
a6.15═════╣ ║ ║
║ ║ ║ ║
║ B7.15═════╣ ║
║ ║║ ║ ║
║ ║╚═══════─╫─═══════ d6.14
║ ║ ║ ║
║ ║ c7.15═════╣
║ ║ ║ ║
╠════════─╫─═══════─╫─═══════ D7.15
║ ║ ║ ║
A7.16════─╫─═══════─╫─════════╣
║ ║ ║ ║
║ b7.16════─╫─════════╣
║ ║ ║ ║
║ ║ c7.16═════╣
║ ║ ║ ║
a7.17════─╫─════════╣ ║
║ ║ ║ ║
║ ║ ╠════════ d7.16
║ ║ ║ ║
║ b7.17════─╫─════════╣
║ ║ ║ ║
║ ║ c7.17═════╣
║ ║ ║ ║
a7.18════─╫─════════╣ ║
║ ║ ║ ║
╠════════─╫─═══════ c7.18 ║
║║ ║ ║ ║
║╚═══════─╫─═══════─╫─═══════ d7.17
║ ║ ║ ║
║ B8.18════─╫─════════╣
║ ║ ║ ║
║ b8.19═════╣ ║
║ ║║ ║ ║
║ ║╚═══════─╫─═══════ D8.18
║ ║ ║ ║
A8.19════─╫─═══════─╫─════════╣
║ ║ ║ ║
╠════════─╫─═══════ C8.19 ║
║ ║ ║ ║
╠════════─╫─═══════─╫─═══════ d8.19
║ ║ ║ ║
a8.20════─╫─═══════─╫─════════╣
║ ║ ║ ║
║ B9.20════─╫─════════╣
║ ║ ║ ║
║ ║ C9.20═════╣
║ ║ ║ ║
║ ║ ╠════════ D9.20
Example of the log produced by the consensus is given as follows. From the log, one may see the event connections, and which events were decided as Atroposes.
Connected event {name=A1.01, parents=[], frame=1, root}
Connected event {name=B1.01, parents=[A1.01], frame=1, root}
Connected event {name=C1.01, parents=[A1.01], frame=1, root}
Connected event {name=D1.01, parents=[A1.01], frame=1, root}
Connected event {name=a1.02, parents=[A1.01, D1.01], frame=1}
Connected event {name=b1.02, parents=[B1.01, D1.01], frame=1}
Connected event {name=c1.02, parents=[C1.01, D1.01], frame=1}
Connected event {name=a1.03, parents=[a1.02, c1.02], frame=1}
Connected event {name=B2.03, parents=[b1.02, a1.03], frame=2, root}
Connected event {name=d1.02, parents=[D1.01, b1.02], frame=1}
Connected event {name=C2.03, parents=[c1.02, d1.02], frame=2, root}
Connected event {name=A2.04, parents=[a1.03, C2.03], frame=2, root}
Connected event {name=b2.04, parents=[B2.03, C2.03], frame=2}
Connected event {name=D2.03, parents=[d1.02, B2.03], frame=2, root}
Connected event {name=c2.04, parents=[C2.03, D2.03], frame=2}
Connected event {name=d2.04, parents=[D2.03, c2.04], frame=2}
Connected event {name=A3.05, parents=[A2.04, d2.04], frame=3, root}
Connected event {name=B3.05, parents=[b2.04, A3.05], frame=3, root}
Connected event {name=C3.05, parents=[c2.04, B3.05], frame=3, root}
Connected event {name=D3.05, parents=[d2.04, B3.05], frame=3, root}
Connected event {name=a3.06, parents=[A3.05, D3.05], frame=3}
Connected event {name=b3.06, parents=[B3.05, D3.05], frame=3}
Connected event {name=c3.06, parents=[C3.05, D3.05], frame=3}
Connected event {name=B4.07, parents=[b3.06, c3.06], frame=4, root}
Connected event {name=d3.06, parents=[D3.05, c3.06], frame=3}
Connected event {name=A4.07, parents=[a3.06, d3.06], frame=4, root}
Connected event {name=a4.08, parents=[A4.07, B4.07], frame=4}
Connected event {name=C4.07, parents=[c3.06, A4.07], frame=4, root}
Connected event {name=b4.08, parents=[B4.07, C4.07], frame=4}
Connected event {name=a4.09, parents=[a4.08, b4.08], frame=4}
Connected event {name=D4.07, parents=[d3.06, A4.07], frame=4, root}
Connected event {name=c4.08, parents=[C4.07, D4.07], frame=4}
Connected event {name=b4.09, parents=[b4.08, c4.08], frame=4}
Connected event {name=c4.09, parents=[c4.08, b4.09], frame=4}
Connected event {name=A5.10, parents=[a4.09, c4.09], frame=5, root}
Frame 1 is decided: Atropos is D1.01. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
B2.03: ynyy
C2.03: yyyn
A2.04: yyyn
D2.03: ynyy
A3.05: YnYy
B3.05: -n-y
C3.05: -y-y
D3.05: -y-y
B4.07: -n-Y
A4.07: -y--
C4.07: -y--
D4.07: -y--
A5.10: -Y--
Frame 2 is decided: Atropos is A2.04. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
A3.05: nyyy
B3.05: nyyy
D3.05: yyyy
C3.05: yyyy
A4.07: yYYY
B4.07: n---
D4.07: y---
C4.07: y---
A5.10: Y---
Frame 3 is decided: Atropos is D3.05. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
A4.07: yyyy
B4.07: yyyn
D4.07: yyyy
C4.07: yyyy
A5.10: YYYY
Connected event {name=B5.10, parents=[b4.09, A5.10], frame=5, root}
Connected event {name=d4.08, parents=[D4.07, b4.08], frame=4}
Connected event {name=D5.09, parents=[d4.08, a4.09], frame=5, root}
Connected event {name=C5.10, parents=[c4.09, D5.09], frame=5, root}
Connected event {name=d5.10, parents=[D5.09, A5.10], frame=5}
Connected event {name=a5.11, parents=[A5.10, d5.10], frame=5}
Connected event {name=b5.11, parents=[B5.10, a5.11], frame=5}
Connected event {name=c5.11, parents=[C5.10, b5.11], frame=5}
Connected event {name=A6.12, parents=[a5.11, c5.11], frame=6, root}
Connected event {name=d5.11, parents=[d5.10, b5.11], frame=5}
Connected event {name=b5.12, parents=[b5.11, d5.11], frame=5}
Connected event {name=C6.12, parents=[c5.11, b5.12], frame=6, root}
Connected event {name=D6.12, parents=[d5.11, A6.12], frame=6, root}
Frame 4 is decided: Atropos is D4.07. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
A5.10: yyyy
B5.10: yyyy
D5.09: yyny
C5.10: yyyy
A6.12: YYyY
C6.12: --y-
D6.12: --Y-
Connected event {name=a6.13, parents=[A6.12, D6.12], frame=6}
Connected event {name=B6.13, parents=[b5.12, D6.12], frame=6, root}
Connected event {name=a6.14, parents=[a6.13, B6.13], frame=6}
Connected event {name=c6.13, parents=[C6.12, a6.13], frame=6}
Connected event {name=C7.14, parents=[c6.13, a6.14], frame=7, root}
Connected event {name=d6.13, parents=[D6.12, a6.13], frame=6}
Connected event {name=b6.14, parents=[B6.13, d6.13], frame=6}
Connected event {name=a6.15, parents=[a6.14, b6.14], frame=6}
Connected event {name=B7.15, parents=[b6.14, C7.14], frame=7, root}
Connected event {name=d6.14, parents=[d6.13, b6.14], frame=6}
Connected event {name=c7.15, parents=[C7.14, d6.14], frame=7}
Connected event {name=D7.15, parents=[d6.14, a6.15], frame=7, root}
Connected event {name=A7.16, parents=[a6.15, D7.15], frame=7, root}
Connected event {name=b7.16, parents=[B7.15, D7.15], frame=7}
Connected event {name=c7.16, parents=[c7.15, D7.15], frame=7}
Connected event {name=a7.17, parents=[A7.16, c7.16], frame=7}
Connected event {name=d7.16, parents=[D7.15, c7.16], frame=7}
Connected event {name=b7.17, parents=[b7.16, d7.16], frame=7}
Connected event {name=c7.17, parents=[c7.16, d7.16], frame=7}
Connected event {name=a7.18, parents=[a7.17, c7.17], frame=7}
Connected event {name=c7.18, parents=[c7.17, a7.18], frame=7}
Connected event {name=d7.17, parents=[d7.16, a7.17], frame=7}
Connected event {name=B8.18, parents=[b7.17, d7.17], frame=8, root}
Frame 5 is decided: Atropos is B5.10. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
A6.12: yyyn
D6.12: yyyy
C6.12: yyyn
B6.13: yyyy
C7.14: YYYy
B7.15: ---y
D7.15: ---y
A7.16: ---y
B8.18: ---Y
Frame 6 is decided: Atropos is B6.13. Election votes:
Every line contains votes from a root, for each subject. y is yes, n is no. Upper case means 'decided'. '-' means that subject was already decided when root was processed.
A7.16: yyyn
B7.15: yyyn
D7.15: yyyn
C7.14: yyyn
B8.18: YYYN
Connected event {name=b8.19, parents=[B8.18, c7.18], frame=8}
Connected event {name=D8.18, parents=[d7.17, B8.18], frame=8, root}
Connected event {name=A8.19, parents=[a7.18, D8.18], frame=8, root}
Connected event {name=C8.19, parents=[c7.18, A8.19], frame=8, root}
Connected event {name=d8.19, parents=[D8.18, A8.19], frame=8}
Connected event {name=a8.20, parents=[A8.19, d8.19], frame=8}
Connected event {name=B9.20, parents=[b8.19, d8.19], frame=9, root}
Connected event {name=C9.20, parents=[C8.19, d8.19], frame=9, root}
Connected event {name=D9.20, parents=[d8.19, C9.20], frame=9, root}
Root's votes don't depend on events connection order, because votes are built upon root's subgraph.
With a different events connection order, the election may be decided by partially different events. But the decided colors will be the same (unless more than 1/3W are Byzantine).
Once a new Atropos is decided, the new block will contain all the events in the subgraph of the Atropos, which were not included in the subgraphs of any previous Atroposes.
The events in a block are ordered by Lamport time, then by event's hash. Ordering by Lamport time ensures that parents are ordered before their children.
