3 of 80

Local Epoch

Each proposer and voter has its local epoch (a natural number)
Each epoch has a single eligible proposer, and the other proposers are standby proposer for this epoch
When a voter sees no liveness (new notarized blocks) for a designated time, the voter broadcasts a clock message to request to advance the next epoch
When a proposer/voter receives 2/3 clock messages which request to advance to epoch e, the proposer/voter updates its local epoch to e

4 of 80

More Definitions

The block’s sequence number (e, s)

e is the epoch
s is a monotonic increasing integer; s begins from 1

Pala defines two types of blocks

Normal block: chain[i].e == chain[i-1].e and chain[i].s == chain[i-1].s + 1
Timeout block: chain[i].e > chain[i-1].e and chain[i].s == 1

5 of 80

More Definitions (cont.)

"Fresher than" relation: we say (e1, s1) is "fresher than" (e2, s2) if e1 > e2 or e1 = e2 and s1 > s2.

A block is fresher than another block if its sequence number is fresher
A chain is fresher than another chain if its last block is fresher

Liveness: we say our consensus protocol has liveness if it is able to make progress (notarize new blocks)

6 of 80

More Definitions (cont.)

Freshest notarized chain

All blocks in the chain are notarized
The last block has the largest block sequence number compared to the other notarized chains

Finalized chain

When the freshest notarized chain ends with at least k consecutive normal blocks, chop off k trailing blocks to obtain the finalized chain (k is the outstanding window)
More on this later

7 of 80

Freshest Notarized Chain

Assume K = 2
The standby proposer P3 has such blockchain
(0,1) is the genesis block
The green blocks are notarized
The green blocks with orange borders are finalized
The green block with blue border is the last block in the freshest notarized chain

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(2,1)

8 of 80

Freshest Notarized Chain (cont.)

Assume P3’s local epoch becomes 3 and P3 is the primary proposer for epoch 3
P3 proposes (3,1) from (1,3)
Any voter with the same freshest notarized chain who also has local epoch 3 will vote on (3,1)

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(2,1)

(3,1)

9 of 80

Freshest Notarized Chain (cont.)

Assume V1 has different freshest notarized chain
V1 will not vote on (3,1)

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(2,1)

(3,1)

10 of 80

Freshest Notarized Chain (cont.)

If (3,1) becomes notarized and V1 receives the notarization
V1’s freshest notarized cain is updated to (3,1) because (3,1) is fresher than (2,1)

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(2,1)

(3,1)

11 of 80

Freshest Notarized Chain (cont.)

When V1 receives the proposal (3,2), V1 will vote on (3,2) this time

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(2,1)

(3,1)

(3,2)

12 of 80

Discussion about Local Epoch

When the primary proposer is offline or dishonest

No liveness → voters broadcast clock messages → update local epoch → switch the primary proposer
As long as there is at least one honest and online proposer, there is liveness with at least 2/3 honest and online voters

When there is any hiccup and nodes cannot make any progress

E.g., the primary proposer restarts and loses some votes and cannot create the notarization
Voters will broadcast clock messages and all nodes will start a new round in the next epoch

When there are network partitions and each partition has <2/3 voters

No liveness
No node in any partition can advance their local epoch

13 of 80

Strong Period of Synchrony Assumption

The partially synchronous network model used by Pala assumes there will be at some point a "strong period of synchrony"
During a strong period of synchrony all messages are guaranteed to arrive within a fixed amount of time
We are guaranteed liveness during a strong period of synchrony

14 of 80

Strong Period of Synchrony Assumption (Practical Version)

Only require that the assumption holds for clock messages
Proposers inform every proposer of every clock message they have heard
When an proposer becomes the primary proposer, it first performs reconciliation with all nodes, to make sure that it obtains the freshest notarized chain among all
See paper 8.2 for more details
More on this later

15 of 80

How to Distribute Data?

We can store all data in blocks and only need to distribute blocks
Store consensus data such as notarizations in blocks
The consensus data in blocks maintain the chain of the trust
Do the primary proposer need to broadcast notarizations before making new proposals?

Yes. Otherwise, the next proposer cannot make the first proposal from the last K blocks for the next epoch

16 of 80

Finalization

Finalized chain (paper version)

When the freshest notarized chain ends with at least k consecutive normal blocks, chop off k trailing blocks

Finalize chain (implementation version)

When the freshest notarized chain ends with at least 2*k consecutive normal blocks, chop off 2*k trailing blocks

Why?

We store chain[i]’s notarization in chain[i-k], where k is the outstanding window
Let chain[i:j] be the slice of i th block to j th block (included)
chain[-k:-1] stores notarizations of chain[-2k:-k-1]

17 of 80

Store Notarizations in Blocks

Assume K = 2
(e,s+K) stores the notarization of (e, s)

Represented by the red dot lines

The green blocks are notarized
The blocks with orange border are finalized

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

18 of 80

Store Notarizations in Blocks (cont.)

Assume K = 2
(e,1) stores the notarization of last K blocks with the old epoch
The finalized chain requires 2K consecutive normal blocks in the last
(5,1) is a timeout block, so the finalized chain is not updated

NOTE: We can finalize (1,2) using notarizations in (5,1). We chose a simpler finalization definition for a cleaner implementation.

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(5,1)

(5,2)

19 of 80

Store Notarizations in Blocks (cont.)

K = 2
After having more consecutive notarized normal blocks, the finalized chain extends

(0,1)

(1,1)

(1,2)

(1,3)

(1,4)

(5,1)

(5,2)

(5,3)

(5,4)

(5,5)

(5,6)

20 of 80

Proposer/Voter Reconfiguration

21 of 80

Proposer/Voter Reconfiguration

For each session of proposers and voters, calculate the election results based on the bid transactions in the 1 ~ N blocks after the Nth block is created
There is no transaction after the Nth block in this session
Pala considers the Nth block as the “stop block”

Aka “reconfiguration block” or “election block”

Once the stop block is finalized, the original proposers/voters will not finalize any new block

But some blocks might be finalized after the stop block at the same time
More on this later

22 of 80

Proposer/Voter Reconfiguration (cont.)

To keep the finalized chain finalized, the new proposers/voters must start the new proposal from the stop block

NOTE: we may have different finalized chains which finalize the stop block, so we’ll drop blocks after the stop block after the reconfiguration is done

Old proposers/voters can be offline after the first finalized block is created by the new proposers/voters

23 of 80

Proposer/Voter Reconfiguration - Case 1

K = 2
(5,4) is the stop block which records the new proposers and voters

(5,4)

(5,5)

24 of 80

Proposer/Voter Reconfiguration - Case 1 (cont.)

(5,4) becomes finalized
No more finalized block
The reconfiguration starts
Note that all nodes should have the blocks (5,4) ~ (5,8)
Some of them may have seen the notarization of (5,7) or (5,8) in memory

(5,4)

(5,5)

(5,6)

(5,7)

(5,8)

25 of 80

Proposer/Voter Reconfiguration - Case 1 (cont.)

To keep the finality of (5,4), the new proposer in the next configuration must make the new proposal from (5,4)
The notarizations in (6,1) are the same as the ones in (5,5) and (5,6)
We’re safe to lose blocks after (5,4) since there is no transaction

New Session

(5,3)

(5,4)

(5,5)

(5,6)

(5,7)

(6,1)

26 of 80

Proposer/Voter Reconfiguration - Case 2

Consider the case that the proposer is offline after (5,4) is notarized
Voters send clock(6) to switch the proposer

(5,4)

(5,5)

(5,6)

27 of 80

Proposer/Voter Reconfiguration - Case 2 (cont.)

Assume the next proposer’s freshest notarized chain ends at (5,5), but it doesn’t have (5,6)
The proposer keeps creating blocks until (5,4) is finalized and starts the reconfiguration at (6,5)
Note that (5,5) and (6,1) are also finalized by the “old” proposers and voters

(5,4)

(5,5)

(6,1)

(6,2)

(6,3)

(6,4)

(6,5)

28 of 80

Discussion about Timeout Blocks

It is possible to create many timeout blocks after the stop block is created
Say every proposer proposes and notarizes one block and becomes offline
We’ll have many timeout blocks and the stop block is not finalized
The proposer/voter reconfiguration starts after one proposer successfully proposes 1+2K blocks

(5,4)

(6,1)

(7,1)

(8,1)

(9,1)

(9,2)

(9,3)

(9,4)

(9,5)

29 of 80

Finalized Chain Branch during Reconfiguration

Assume the new session can extend from a notarized block after the stop block
We use (session, epoch, S) as the block sequence number here and the epoch is reset in each new session
Assume the nodes in session 2 receive nota (1,5,5) and (1,5,6)

New Session

(1,5,3)

(1,5,4)

(1,5,5)

(1,5,6)

(1,5,7)

(2,1,1)

(1,5,8)

30 of 80

Finalized Chain Branch during Reconfiguration (cont.)

Assume voters in the old session doesn’t receive nota (1,5,5) and (1,5,6), so they send clock(6)
Consensus nodes in the session 1 extends the chain to finalize the stop block and have a different finalized chain

… -> (1,5,6)
… -> (1,6,1)

Session 2’s view

(1,5,3)

(1,5,4)

(1,5,5)

(1,5,6)

(2,1,1)

(1,6,1)

(1,6,2)

(1,6,3)

(1,6,4)

(1,6,5)

31 of 80

Finalized Chain Branch during Reconfiguration (cont.)

Solution 1: Blocks after the stop block contain no transaction

It’s okay to extend the first block of session 2 from the stop block
Easy to implement
Clear to users

Solution 2: consensus nodes in session 2 finalize blocks after the stop block, but consensus nodes in session 1 can’t

The throughput is larger but the finality latency is still longer during the reconfiguration
Need to revise Geth’s code to avoid confusing users

Use solution 1 to simplify the code and use solution 2 when needed

32 of 80

Proofs of Epoch Advance

The clock notarization

2/3 Clock(e)
The proof is created when timeout happens

The notarization(e, s) of a block(e,s)

In case the node loses the clock notarization
To make the logic consistent, we put the clock notarization in (e, 1) and disallow using notarization (e, s) as the proof

Blocks and notarizations to finalize the stop block

33 of 80

High-Level Data Flow

34 of 80

Terminology

P1, P2: proposers
V1 ~ V3: voters
Hub-and-spoke topology
seq = (epoch, s): the sequence number of the last block of freshest notarized chain

(0, 1) is the genesis block

e: the local epoch
2 - (e % 2) → The primary proposer

e=1,3,5,... → P1
e=2,4,6,... → P2

seq = (0,1)�e=1

35 of 80

No Partition

P1 sends proposal(1,1) to Vi and P2

seq = (0,1)�e=1

36 of 80

No Partition (cont.)

Vi responds vote(1,1) to P1
P1 creates notarization(1,1)
P1 updates its freshest notarized chain

seq = (0,1)�e=1

seq = (1,1)�e=1

seq = (0,1)�e=1

37 of 80

No Partition (cont.)

P1 sends notarization(1,1) to Vi and P2
Vi and P2 updates its freshest notarized chain

seq = (1,1)�e=1

38 of 80

P1 is offline (Proposer Switch)

No progress in 6 seconds

the duration of the timeout is a protocol configuration

seq = (1,1)�e=1

39 of 80

Voters Request to Advance Epoch

Vi sends clock(2) to all proposers, but only P2 receives
P2 updates e=2
P2 becomes the primary proposer

seq = (1,1)�e=1

seq = (1,1)�e=2

40 of 80

Voters Request to Advance Epoch (cont.)

P2 sends the aggregation of clock(2) to Vi
Vi updates e=2

seq = (1,1)�e=2

seq = (1,1)�e=1

seq = (1,1)�e=2

41 of 80

Liveness is Back

P2 sends proposal(2,1) to Vi

seq = (1,1)�e=2

seq = (1,1)�e=1

seq = (1,1)�e=2

42 of 80

Liveness is Back (cont.)

Vi responds vote(2,1) to P2
P2 updates its freshest notarized chain
P2 sends notarization(2,1) to Vi
Vi updates freshest notarized chain

seq = (2,1)�e=2

seq = (1,1)�e=1

seq = (2,1)�e=2

43 of 80

Network Partition

Assume there are two partitions [P1, V1, V2] and [P2, V3]

seq = (2,1)�e=2

seq = (1,1)�e=1

seq = (2,1)�e=2

44 of 80

Network Partition

P2 sends proposal(2,2)
Only V3 is able to respond, so there is no liveness

seq = (2,1)�e=2

seq = (1,1)�e=1

seq = (2,1)�e=2

45 of 80

Network Partition (cont.)

P1 performs reconciliation with V1 and V2 after they just set up the connection
In the reconciliation, each end notifies the other of its seq and e

seq = (2,1)�e=2

seq = (1,1)�e=1

seq = (2,1)�e=2

46 of 80

Network Partition (cont.)

P1 finds out that its seq and e are behind, so it requests the following data from V1 (or V2)

The aggregation of clock(2)
block(2,1)
notarization(2,1)

seq = (2,1)�e=2

seq = (1,1)�e=1

seq = (2,1)�e=2

47 of 80

Network Partition (cont.)

V1 responds those data
P1 updates its state
P1 is not primary proposer, so still no liveness

seq = (2,1)�e=2

48 of 80

Network Partition (cont.)

After the timeout, Vi sends clock(3)
P1 has enough clock(3), so it updates e=3
P1 becomes the primary proposer
P2 has not enough clock(3), so it updates nothing

seq = (2,1)�e=2

seq = (2,1)�e=3

49 of 80

Network Partition (cont.)

P1 sends proposal(3,1)

seq = (2,1)�e=3

seq = (2,1)�e=2

seq = (2,1)�e=3

50 of 80

Network Partition (cont.)

After sending votes and notarization among P1, V1 and V2, the liveness is back

seq = (3,1)�e=3

seq = (2,1)�e=2

seq = (3,1)�e=3

51 of 80

Network Partition (cont.)

Note that P2 still waits for vote(2,2) to finish the proposal
P2 and V3 still wait for clock(3) to advance the local epoch
To be more precisely, P2 keeps sending proposals (2,2), (2,3), … until it reaches the maximum of outstanding window

seq = (3,1)�e=3

seq = (2,1)�e=2

seq = (3,1)�e=3

52 of 80

Network Partition (cont.)

Assume V2 finally connected to P2
Assume (P1, P2), (P1, V3), (P2,V1) are still disconnected
After P2 and V2 perform reconciliation, P2 updates its state

seq = (3,1)�e=3

seq = (2,1)�e=2

seq = (3,1)�e=3

53 of 80

Network Partition (cont.)

V3 learns the new update via the regular heartbeat messages to P2
V3 requests the new data and updates its state

seq = (3,1)�e=3

54 of 80

Network Partition (cont.)

In the meanwhile, P1, V1 and V2 keep building new notarized blocks

seq = (3,2)�e=3

seq = (3,1)�e=3

seq = (3,2)�e=3

55 of 80

Network Partition (cont.)

P2 and V3 will know the update later via heartbeat messages
P2 and V3 request new data and update their states

seq = (3,2)�e=3

56 of 80

Network Layer and�Strong Period of Synchrony

57 of 80

Network Layer Requirements for Strong Period of Synchrony�(Paper Version)

All proposers are hubs
Voters inform every proposer of every clock message they have heard and all proposers relay clock messages among all nodes

Once proposers and voters advance the epoch, the missing proposals/votes/notarizations from the old epoch don’t matter

The primary proposer performs reconciliation with all nodes to obtain the freshest notarized chain among all

58 of 80

“Voters inform every proposer of every clock message they have heard“� +�“All proposers relay clock messages among all nodes”

Assume only the following connections are established

Pi and Vi
Pi and Vi+1

59 of 80

“Voters inform every proposer of every clock message they have heard“� +�“All proposers relay clock messages among all nodes” (cont.)

Take the clock message from V1 to P1 as an example
The message will eventually arrive V6

V1 → P1
P1 → V2
V2 → P2
…
P5 → V6

The local epoch keeps growing, but there is no liveness

60 of 80

Discussion: Do We Really Need to Propagate �Clock Messages?

If every proposer connects to less than 2/3 voters, there is still no liveness after advancing the epoch because proposers won’t receive enough votes

It is impractical to propagate proposals, votes and notarizations

Can we just follow the same flow as the votes and notarizations to send clock messages and clock notarizations?

61 of 80

Network Layer Requirements for Strong Period of Synchrony�(Idea of Implementation Version)

Ensure connected ends have the same state

Freshest notarized chain
Epoch
Clock messages which are not enough to advance the epoch

Ensure new connected ends have the same state

Same as above
But check these immediately

62 of 80

Network Layer Requirements for Strong Period of Synchrony�(Implementation Version)

All proposers are hubs
For every connection, regularly check each end’s states via heartbeat messages

The sequence number of the last block of freshest notarized chain
Epoch e
The clock message clock(e+1) (this may not exist)

Fetch the proofs if one’s epoch or freshest notarized chain is behind

The proofs are blocks, notarizations of votes, the notarization of the latest clock message and the new clock message

63 of 80

Network Layer Requirements for Strong Period of Synchrony�(Implementation Version) (cont.)

Perform reconciliation after the connection is just set up

Just an immediate heartbeat message

The primary proposer performs “strong” reconciliation with all nodes right after it becomes the primary one

Start proposing after the primary proposer is not behind all connected voters

64 of 80

Why Fetching Clock Message during Reconciliation?

Assume e=1 for all nodes
3 - (e % 3) → The primary proposer

65 of 80