提议者选择过程

本文档规定了 Tendermint 中使用的提议者选择过程。Tendermint 是 CometBFT 采用的共识算法，该过程用于选择某一轮的提议者。由于 Tendermint 是一种“基于领导者的共识协议”，提议者选择对于其正确运行至关重要。在给定的区块高度上，提议者选择算法会在每一轮使用同一个验证者集合运行。在不同高度之间，应用可以通过 ABCIResponses 的 EndBlock 指定更新后的验证者集合。

提议者选择的要求

本节介绍相关要求，其中 Rx 表示强制要求，Ox 表示可选要求。提议者选择过程必须满足以下要求：

R1：确定性

给定一个验证者集合 V，以及两个诚实验证者 p 和 q，对于每个高度 h 和每一轮 r，必须满足： proposer_p(h,r) = proposer_q(h,r) 其中，proposer_p(h,r) 表示在进程 p 上，于高度 h、轮次 r 由提议者选择过程返回的提议者。

R2：公平性

给定一个总投票权为 P 的验证者集合，以及一个选举序列 S。在 S 的任意长度为 C*P 的子序列中，验证者 v 必须被选为提议者 P/VP(v) 次，即其频率为： f(v) ~ VP(v) / P 其中，C 是用于容忍验证者集合变更的系数，取值如下：

如果没有验证者集合变更，则 C == 1
如果存在验证者变更，则 C ~ k

[这部分还需要进一步完善]

基本算法

提议者选择过程的核心是一个加权轮询算法。一个有助于理解该选择算法如何工作以及为何公平的模型，是优先队列模型。验证者会根据其投票权在该队列中向前移动（投票权越高，验证者越快向队列头部移动）。当算法运行时，会发生以下过程：

所有验证者都会根据各自的投票权向前移动：对每个验证者，将其优先级增加对应的投票权
队列中的第一位成为提议者：选择优先级最高的验证者
将提议者移回队列后部：将提议者的优先级减去总投票权

记号说明：

vset - 验证者集合
n - 验证者数量
VP(i) - 验证者 i 的投票权
A(i) - 验证者 i 的累积优先级
P - 集合的总投票权
avg - 所有验证者优先级的平均值
prop - 提议者

选择算法的简化视图：

    def ProposerSelection (vset):

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

稳定集合

考虑如下验证者集合：

验证者	p1	p2
VP	1	3

假设没有验证者变更，下表展示了若干次运行中的提议者优先级计算过程。表中展示了选择过程的四次运行，从第 5 次开始会重复计算出相同的值。每一行展示了优先队列及进程在队列中的位置。提议者最接近队列头部，即最右侧的验证者。随着优先级更新，验证者会在队列中向右移动。提议者在当选后由于其优先级被降低，会向左移动。

优先级运行	-2	-1	0	1	2	3	4	5	算法步骤
			p1,p2						初始化为 0
运行 1				p1		p2			A(i)+=VP(i)
		p2		p1					A(p2)-= P
运行 2					p1,p2				A(i)+=VP(i)
	p1				p2				A(p1)-= P
运行 3		p1						p2	A(i)+=VP(i)
		p1		p2					A(p2)-= P
运行 4			p1				p2		A(i)+=VP(i)
			p1,p2						A(p2)-= P

可以证明：

在每次第 k+1 轮运行结束时，优先级总和与第 k 轮结束时相同。如果新集合的优先级初始化为 0，那么在没有变更的情况下，每轮运行时优先级总和都将为 0。
优先级之间的最大距离为 (n-1) *P。[形式化证明尚未完成]

验证者集合变更

在提议者选择过程的两次运行之间，验证者集合可能发生变化。有些变化会对提议者选举产生影响。

投票权变更

再次考虑前面的例子，假设 p1 的投票权被改为 4：

验证者	p1	p2
VP	4	3

再假设在这次变更之前，提议者优先级如第一行所示（上一轮运行结束后的状态）。可以看到，即使发生了这次变更，选择过程仍然可以像之前一样继续运行。

优先级运行	-2	-1	1	2	注释
上一次运行		p2	p1		update VP(p1)
下一次运行				p2	A(i)+=VP(i)
	p1			p2	A(p1)-= P

然而，当某个验证者的投票权从较高值变为较低值时，其他某些验证者可能会在队列后方停留很长时间。这个场景会在“提议者优先级范围”一节再次讨论。与前面一样：

在每次第 k+1 轮运行结束时，优先级总和与第 k 轮相同。
优先级之间的最大距离为 (n-1) * P。

验证者移除

考虑一个新的示例，验证者集合为：

验证者	p1	p2	p3
VP	1	2	3

假设在上一轮运行结束后，提议者优先级如第一行所示，其总和为 0。在移除 p2 之后，到下一次提议者选择运行结束时（倒数第二行），优先级总和将变为 -2（即被移除进程的优先级的相反数）。该过程本可以在不做修改的情况下继续运行。然而，当验证者集合发生足够多次变更后，优先级值会逐渐逼近允许的最大值或最小值，并因溢出检测而被截断。因此，选择过程增加了另一个__新步骤__，对当前优先级进行居中处理，使得优先级总和保持接近 0。

优先级运行	-3	-2	-1	1	2	3	注释
上一次运行	p3			p1	p2		remove p2
下一次运行
新步骤		p3			p1		A(i) -= avg, avg = -1
				p3		p1	A(i)+=VP(i)
			p1	p3			A(p1)-= P

修改后的选择算法如下：

    def ProposerSelection (vset):

        // center priorities around zero
        avg = sum(A(i) for i in vset)/len(vset)
        for each validator i in vset:
            A(i) -= avg

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

说明：

现在优先级总和接近 0。由于使用整数除法，该总和是一个位于 (-n, n) 之间的整数，其中 n 为验证者数量。

新增验证者

当新增一个验证者时，会出现与移除验证者时相同的问题：新集合中的优先级总和不为 0。这个问题可通过前面引入的居中步骤解决。还需要处理另一个问题。刚刚当选的验证者 V 会被移到队列末尾。如果验证者集合很大，和/或其他验证者拥有显著更高的投票权，那么 V 需要等待很多轮之后才会再次当选。如果 V 先将自己移出集合再重新加入，它就能在队列中显著地（尽管并不公平）向前“跳跃”。为防止这种情况，在新增验证者时，其初始优先级会被设为：

    A(V) = -1.125 *  P

其中，P 是包含 V 在内的整个集合的总投票权。当前实现使用 1.125 作为惩罚系数，因为它带来的惩罚较小且计算高效。更多细节见这里。如果考虑这样一个验证者集合，其中 p3 刚刚被加入：

验证者	p1	p2	p3
VP	1	3	8

那么 p3 的提议者优先级初始值为：

    A(p3) = -1.125 * (1 + 3 + 8) ~ -13

注意，由于当前计算采用整数除法，当投票权总和小于 8 时会存在惩罚损失。在下一轮中，p3 仍会处于队列前方，被选为提议者，然后再被移回队列后部。

优先级运行	-13	-9	-5	-2	-1	2	5	6	7	算法步骤
上一次运行				p2		p1				add p3
	p3			p2		p1				A(p3) = -13
下一次运行		p3				p2		p1		A(i) -= avg, avg = -4
					p3		p2		p1	A(i)+=VP(i)
			p1		p3		p2			A(p1)-=P

提议者优先级范围

引入居中之后，会出现一些有意思的情况。在包含高投票权验证者的集合中，较早加入集合的低投票权验证者，会从后续加入集合的新验证者中受益。这是因为这些较早加入的验证者在居中过程中会经历更多次右移操作，而这些操作会提高它们的优先级。举例来说，考虑这样一个集合：p2 在 p1 之后加入，优先级为 -1.125 * 80k = -90k。当选择过程运行一次后：

验证者	p1	p2	说明
VP	80k	10
A	0	-90k	添加 p2
A	45k	-45k	运行选择

然后执行以下步骤：

添加一个新的验证者 p3：
验证者 p1 p2 p3
VP 80k 10 10
运行一次选择。记号 ..p / p.. 表示相对于该列优先级而言非常小的偏差。
优先级运行 -90k.. -60k -45k -15k 0 45k 75k 155k 说明
上一次运行 p3 p2 p1 添加 p3
下一次运行
right_shift p3 p2 p1 A(i) -= avg,avg=-30k
..p3 ..p2 p1 A(i)+=VP(i)
..p3 ..p2 p1.. A(p1)-=P, P=80k+20
移除 p1，再运行一次选择：
验证者 p3 p2 说明
VP 10 10
A -60k -15k
A -22.5k 22.5k 运行选择

验证者	p1	p2	p3
VP	80k	10	10

验证者	p3	p2	说明
VP	10	10
A	-60k	-15k
A	-22.5k	22.5k	运行选择

此时，尽管总投票权为 20，优先级之间的距离却达到了 45k。p3 需要运行 4500 次才能追上 p2。为了防止这类场景，选择算法会对优先级进行缩放，使最小值与最大值之间的差小于总投票权的两倍。修改后的选择算法如下：

    def ProposerSelection (vset):

        // scale the priority values
        diff = max(A)-min(A)
        threshold = 2 * P
     if  diff > threshold:
            scale = diff/threshold
            for each validator i in vset:
          A(i) = A(i)/scale

        // center priorities around zero
        avg = sum(A(i) for i in vset)/len(vset)
        for each validator i in vset:
            A(i) -= avg

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

观察：

经过这项修改后，优先级之间的最大距离变为 2 * P。

还要注意，即使在稳态下，优先级范围也可能增长到超过 2 * P。这里引入的缩放有助于将该范围保持在有界状态内。

细节问题

验证者投票权溢出条件

验证者投票权是一个以 int64 存储的正数。添加验证者时，1.125 * P 的计算不能溢出。因此，处理验证者更新（添加和更新）的代码会检查溢出条件，确保总投票权永远不会大于最大的 int64 值 MAX，并满足 1.125 * MAX 仍然位于 int64 的取值范围内。一旦检测到溢出条件，就会返回致命错误。

提议者优先级上溢/下溢处理

提议者优先级使用 int64 存储。选择算法会对这些值执行加法和减法；在发生上溢或下溢时，会将数值限制为：

    MaxInt64  =  1 << 63 - 1
    MinInt64  = -1 << 63

需求满足声明

[R1] 提议者算法是确定性的；在相同交易和相同验证者集合修改的情况下，它在多次执行中会给出一致结果。 [进行中 - 需要更多细节] [R2] 给定一组总投票权为 P 的进程，在长度为 P 的一段选举序列中，任一进程被选为提议者的次数都等于它的投票权。随后，这段由 P 个提议者组成的序列会重复。考虑如下验证者集合：

验证者	p1	p2
VP	1	3

在验证者集合没有其他变化的情况下，当前的提议者选择实现会生成如下序列： p2, p1, p2, p2, p2, p1, p2, p2,... 或 [p2, p1, p2, p2]* 如果一个序列从子序列 [p2, p1, p2, p2] 的任意循环排列开始，也能提供相同程度的公平性。实际上，在长度等于该子序列长度的滑动窗口中（作用于生成序列），可以观察到这些循环排列。根据投票权为每个验证者分配优先级，并在每次运行时更新这些优先级，可以确保提议者选择的公平性。此外，每当某个验证者当选为提议者时，它的优先级都会按总投票权降低。直观来看，一个进程 v 在到达队首并被选中之前，至多会在队列中向前跳跃 (max(A) - min(A))/VP(v) 次。于是其频率为：

    f(v) ~ VP(v)/(max(A)-min(A)) = 1/k * VP(v)/P

对于当前实现，这意味着在 k * P 次运行中，v 至少应当成为提议者 VP(v) 次，其中缩放因子 k=2。

Proposer Selection Procedure

This document specifies the Proposer Selection Procedure that is used in Tendermint, the consensus algorithm adopted in CometBFT, to choose a round proposer. As Tendermint is “leader-based consensus protocol”, the proposer selection is critical for its correct functioning. At a given block height, the proposer selection algorithm runs with the same validator set at each round . Between heights, an updated validator set may be specified by the application as part of the ABCIResponses’ EndBlock.

Requirements for Proposer Selection

This sections covers the requirements with Rx being mandatory and Ox optional requirements. The following requirements must be met by the Proposer Selection procedure:

R1: Determinism

Given a validator set V, and two honest validators p and q, for each height h and each round r the following must hold: proposer_p(h,r) = proposer_q(h,r) where proposer_p(h,r) is the proposer returned by the Proposer Selection Procedure at process p, at height h and round r.

R2: Fairness

Given a validator set with total voting power P and a sequence S of elections. In any sub-sequence of S with length C*P, a validator v must be elected as proposer P/VP(v) times, i.e. with frequency: f(v) ~ VP(v) / P where C is a tolerance factor for validator set changes with following values:

C == 1 if there are no validator set changes
C ~ k when there are validator changes

[this needs more work]

Basic Algorithm

At its core, the proposer selection procedure uses a weighted round-robin algorithm. A model that gives a good intuition on how/ why the selection algorithm works and it is fair is that of a priority queue. The validators move ahead in this queue according to their voting power (the higher the voting power the faster a validator moves towards the head of the queue). When the algorithm runs the following happens:

all validators move “ahead” according to their powers: for each validator, increase the priority by the voting power
first in the queue becomes the proposer: select the validator with highest priority
move the proposer back in the queue: decrease the proposer’s priority by the total voting power

Notation:

vset - the validator set
n - the number of validators
VP(i) - voting power of validator i
A(i) - accumulated priority for validator i
P - total voting power of set
avg - average of all validator priorities
prop - proposer

Simple view at the Selection Algorithm:

    def ProposerSelection (vset):

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

Stable Set

Consider the validator set:

Validator	p1	p2
VP	1	3

Assuming no validator changes, the following table shows the proposer priority computation over a few runs. Four runs of the selection procedure are shown, starting with the 5th the same values are computed. Each row shows the priority queue and the process place in it. The proposer is the closest to the head, the rightmost validator. As priorities are updated, the validators move right in the queue. The proposer moves left as its priority is reduced after election.

Priority Run	-2	-1	0	1	2	3	4	5	Alg step
			p1,p2						Initialized to 0
run 1				p1		p2			A(i)+=VP(i)
		p2		p1					A(p2)-= P
run 2					p1,p2				A(i)+=VP(i)
	p1				p2				A(p1)-= P
run 3		p1						p2	A(i)+=VP(i)
		p1		p2					A(p2)-= P
run 4			p1				p2		A(i)+=VP(i)
			p1,p2						A(p2)-= P

It can be shown that:

At the end of each run k+1 the sum of the priorities is the same as at end of run k. If a new set’s priorities are initialized to 0 then the sum of priorities will be 0 at each run while there are no changes.
The max distance between priorites is (n-1) P.[formal proof not finished]*

Validator Set Changes

Between proposer selection runs the validator set may change. Some changes have implications on the proposer election.

Voting Power Change

Consider again the earlier example and assume that the voting power of p1 is changed to 4:

Validator	p1	p2
VP	4	3

Let’s also assume that before this change the proposer priorites were as shown in first row (last run). As it can be seen, the selection could run again, without changes, as before.

Priority Run	-2	-1	1	2	Comment
last run		p2	p1		update VP(p1)
next run				p2	A(i)+=VP(i)
	p1			p2	A(p1)-= P

However, when a validator changes power from a high to a low value, some other validator remain far back in the queue for a long time. This scenario is considered again in the Proposer Priority Range section. As before:

At the end of each run k+1 the sum of the priorities is the same as at run k.
The max distance between priorites is (n-1) * P.

Validator Removal

Consider a new example with set:

Validator	p1	p2	p3
VP	1	2	3

Let’s assume that after the last run the proposer priorities were as shown in first row with their sum being 0. After p2 is removed, at the end of next proposer selection run (penultimate row) the sum of priorities is -2 (minus the priority of the removed process). The procedure could continue without modifications. However, after a sufficiently large number of modifications in validator set, the priority values would migrate towards maximum or minimum allowed values causing truncations due to overflow detection. For this reason, the selection procedure adds another new step that centers the current priority values such that the priority sum remains close to 0.

Priority Run	-3	-2	-1	1	2	3	Comment
last run	p3			p1	p2		remove p2
nextrun
new step		p3			p1		A(i) -= avg, avg = -1
				p3		p1	A(i)+=VP(i)
			p1	p3			A(p1)-= P

The modified selection algorithm is:

    def ProposerSelection (vset):

        // center priorities around zero
        avg = sum(A(i) for i in vset)/len(vset)
        for each validator i in vset:
            A(i) -= avg

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

Observations:

The sum of priorities is now close to 0. Due to integer division the sum is an integer in (-n, n), where n is the number of validators.

New Validator

When a new validator is added, same problem as the one described for removal appears, the sum of priorities in the new set is not zero. This is fixed with the centering step introduced above. One other issue that needs to be addressed is the following. A validator V that has just been elected is moved to the end of the queue. If the validator set is large and/ or other validators have significantly higher power, V will have to wait many runs to be elected. If V removes and re-adds itself to the set, it would make a significant (albeit unfair) “jump” ahead in the queue. In order to prevent this, when a new validator is added, its initial priority is set to:

    A(V) = -1.125 *  P

where P is the total voting power of the set including V. Current implementation uses the penalty factor of 1.125 because it provides a small punishment that is efficient to calculate. See here for more details. If we consider the validator set where p3 has just been added:

Validator	p1	p2	p3
VP	1	3	8

then p3 will start with proposer priority:

    A(p3) = -1.125 * (1 + 3 + 8) ~ -13

Note that since current computation uses integer division there is penalty loss when sum of the voting power is less than 8. In the next run, p3 will still be ahead in the queue, elected as proposer and moved back in the queue.

Priority Run	-13	-9	-5	-2	-1	2	5	6	7	Alg step
last run				p2		p1				add p3
	p3			p2		p1				A(p3) = -13
next run		p3				p2		p1		A(i) -= avg, avg = -4
					p3		p2		p1	A(i)+=VP(i)
			p1		p3		p2			A(p1)-=P

Proposer Priority Range

With the introduction of centering, some interesting cases occur. Low power validators that bind early in a set that includes high power validator(s) benefit from subsequent additions to the set. This is because these early validators run through more right shift operations during centering, operations that increase their priority. As an example, consider the set where p2 is added after p1, with priority -1.125 * 80k = -90k. After the selection procedure runs once:

Validator	p1	p2	Comment
VP	80k	10
A	0	-90k	added p2
A	45k	-45k	run selection

Then execute the following steps:

Add a new validator p3:
Validator p1 p2 p3
VP 80k 10 10
Run selection once. The notation ‘..p’/‘p..’ means very small deviations compared to column priority.
Priority Run -90k.. -60k -45k -15k 0 45k 75k 155k Comment
last run p3 p2 p1 added p3
next run
right_shift p3 p2 p1 A(i) -= avg,avg=-30k
..p3 ..p2 p1 A(i)+=VP(i)
..p3 ..p2 p1.. A(p1)-=P, P=80k+20
Remove p1 and run selection once:
Validator p3 p2 Comment
VP 10 10
A -60k -15k
A -22.5k 22.5k run selection

Validator	p1	p2	p3
VP	80k	10	10

Validator	p3	p2	Comment
VP	10	10
A	-60k	-15k
A	-22.5k	22.5k	run selection

At this point, while the total voting power is 20, the distance between priorities is 45k. It will take 4500 runs for p3 to catch up with p2. In order to prevent these types of scenarios, the selection algorithm performs scaling of priorities such that the difference between min and max values is smaller than two times the total voting power. The modified selection algorithm is:

    def ProposerSelection (vset):

        // scale the priority values
        diff = max(A)-min(A)
        threshold = 2 * P
     if  diff > threshold:
            scale = diff/threshold
            for each validator i in vset:
          A(i) = A(i)/scale

        // center priorities around zero
        avg = sum(A(i) for i in vset)/len(vset)
        for each validator i in vset:
            A(i) -= avg

        // compute priorities and elect proposer
        for each validator i in vset:
            A(i) += VP(i)
        prop = max(A)
        A(prop) -= P

Observations:

With this modification, the maximum distance between priorites becomes 2 * P.

Note also that even during steady state the priority range may increase beyond 2 * P. The scaling introduced here helps to keep the range bounded.

Wrinkles

Validator Power Overflow Conditions

The validator voting power is a positive number stored as an int64. When a validator is added the 1.125 * P computation must not overflow. As a consequence the code handling validator updates (add and update) checks for overflow conditions making sure the total voting power is never larger than the largest int64 MAX, with the property that 1.125 * MAX is still in the bounds of int64. Fatal error is return when overflow condition is detected.

Proposer Priority Overflow/ Underflow Handling

The proposer priority is stored as an int64. The selection algorithm performs additions and subtractions to these values and in the case of overflows and underflows it limits the values to:

    MaxInt64  =  1 << 63 - 1
    MinInt64  = -1 << 63

Requirement Fulfillment Claims

[R1] The proposer algorithm is deterministic giving consistent results across executions with same transactions and validator set modifications. [WIP - needs more detail] [R2] Given a set of processes with the total voting power P, during a sequence of elections of length P, the number of times any process is selected as proposer is equal to its voting power. The sequence of the P proposers then repeats. If we consider the validator set:

Validator	p1	p2
VP	1	3

With no other changes to the validator set, the current implementation of proposer selection generates the sequence: p2, p1, p2, p2, p2, p1, p2, p2,... or [p2, p1, p2, p2]* A sequence that starts with any circular permutation of the [p2, p1, p2, p2] sub-sequence would also provide the same degree of fairness. In fact these circular permutations show in the sliding window (over the generated sequence) of size equal to the length of the sub-sequence. Assigning priorities to each validator based on the voting power and updating them at each run ensures the fairness of the proposer selection. In addition, every time a validator is elected as proposer its priority is decreased with the total voting power. Intuitively, a process v jumps ahead in the queue at most (max(A) - min(A))/VP(v) times until it reaches the head and is elected. The frequency is then:

    f(v) ~ VP(v)/(max(A)-min(A)) = 1/k * VP(v)/P

For current implementation, this means v should be proposer at least VP(v) times out of k * P runs, with scaling factor k=2.

优先级运行	-90k..	-60k	-45k	-15k	45k	75k	155k	说明
上一次运行	p3		p2		p1			添加 p3
下一次运行
right_shift		p3		p2		p1		A(i) -= avg,avg=-30k
		..p3		..p2			p1	A(i)+=VP(i)
		..p3		..p2		p1..		A(p1)-=P, P=80k+20

Priority Run	-90k..	-60k	-45k	-15k	45k	75k	155k	Comment
last run	p3		p2		p1			added p3
next run
right_shift		p3		p2		p1		A(i) -= avg,avg=-30k
		..p3		..p2			p1	A(i)+=VP(i)
		..p3		..p2		p1..		A(p1)-=P, P=80k+20

​提议者选择过程

​提议者选择的要求

​R1：确定性

​R2：公平性

​基本算法

​稳定集合

​验证者集合变更

​投票权变更

​验证者移除

​新增验证者

​提议者优先级范围

​细节问题

​验证者投票权溢出条件

​提议者优先级上溢/下溢处理

​需求满足声明

​Proposer Selection Procedure

​Requirements for Proposer Selection

​R1: Determinism

​R2: Fairness

​Basic Algorithm

​Stable Set

​Validator Set Changes

​Voting Power Change

​Validator Removal

​New Validator

​Proposer Priority Range

​Wrinkles

​Validator Power Overflow Conditions

​Proposer Priority Overflow/ Underflow Handling

​Requirement Fulfillment Claims