At the heart of our construction is a lottery that chooses a (sublinear) set of parties according to their reputation. To demonstrate the idea, let us first consider two extreme scenarios: Scenario 1: No reputation party _i has R_i > 0.5. Scenario 2: All reputation parties _i have (independent) reputation R_i > 0.5 + ϵ for a constant ϵ, e.g,. R_i > 0.51.

In Scenario 1, one can prove that users cannot use the recommendation of the reputation parties to agree on a sequence of transactions. Roughly, the reason is that with good probability, the majority of the reputation parties might be dishonest and try to split the network of users, so that they accept conflicting transaction sequences. In Scenario 2, on the other hand, the situation is different. Here, by choosing a polylogarithmic random committee we can guarantee (except with negligible probability)⁸ that the majority of those parties will be honest (recall that we assume independent reputations), and we can therefore employ a consensus protocol to achieve agreement on each transaction (block).

In the above definition, the corrupted parties are chosen according to Rep from the entire reputation-party set , and independently of the coins of A. (Indeed, otherwise it would be trivial to corrupt a majority.)

It is easy to verify that to maximize the (expected) number of honest parties in the committee it suffices to always choose the parties with the highest reputation. In fact, [13] generalized this to arbitrary correlation-free reputation systems by proving that for any ϵ-feasible reputation system Rep (i.e., for any Rep-adversary ) the algorithm which orders that parties according to their reputation chooses sufficiently many (see. [13]) parties with the highest reputation induces a set which has honest majority. We denote this algorithm by Amax.

As discussed in the introduction, despite yielding a maximally safe lottery, Amax has issues with fairness which renders it suboptimal for use in a blockchain ledger protocol. In the following we introduce an appropriate notion of reputation-fairness for lotteries and an algorithm for achieving it.

3.1 PoR-Fairness

As a warm up, let us consider a simple case, where all reputations parties can be partitioned in two subsets: ₁ consisting of parties with reputation at least 0.76, and ₂ consisting of parties with reputation between 0.51 and 0.75. Let |₁| = α₁ and |₂| = α₂. We want to sample a small (sublinear in || = α₁ + α₂) number y of parties in total.

Recall that we want to give every reputation party a chance (to be part of the committee) while ensuring that, the higher the reputation, the better his relative chances. A first attempt would be to first sample a set where each party _i is sampled according to his reputation (i.e., with probability R_i) and then reduce the size of the sampled set by randomly picking the desired number of parties. This seemingly natural idea suffers from the fact that if there are many parties with low reputation—this is not the case in our above example where everyone has reputation at least 0.51, but it might be the case in reality—then it will not yield an honest majority committee even when the reputation system is feasible.

A second attempt is the following. Observe that per our specification of the above tiers, the parties in ₁ are about twice more likely to be honest than parties in ₂. Hence we can try to devise a lottery which selects (on expectation) twice as many parties from ₁ as the number of parties selected from ₂. This will make the final set sufficiently biased towards high reputations (which can ensure honest majorities) but has the following side-effect: The chances of a party being selected diminish with the number of parties in his reputation tier. This effectively penalizes large sets of high-reputation parties; but formation of such sets should be a desideratum for a blockchain protocol. To avoid this situation we tune our goals to require that when the higher-reputation set |₁| is much larger than |₂|, then we want to start shifting the selection towards ₁. This leads to the following informal fairness goal:

Goal (informal): We want to randomly select x₁ parties from ₁ and x₂ parties from ₂ so that:

1.

x₁ + x₂ = y

2.

x₁ = 2max{1,}x₂ (representation fairness)

3.

For each i ∈{1,2} : No party in _i has significantly lower probability of getting picked than other parties in _i (non-discrimination), but parties in ₁ are twice as likely to be selected as parties in ₂ (selection fairness).

Assuming α₁ and α₂ are sufficiently large, the above goal can be achieved by the following sampler: For appropriately chosen numbers ℓ₁ and ℓ₂ ≥ 0 with ℓ₁ + ℓ₂ = y, sample ℓ₁ parties from ₁, and then sample ℓ₂ parties from ₁ ∪₂ (where if you sample a party from ₁ twice, replace him with a random, upsampled party from ₁). As it will become clear in the following general analysis, by carefully choosing ℓ₁ and ℓ₂ we can ensure that the conditions of the above goal are met. For the interested reader, we analyze the above lottery in Appendix  A.1 . Although this is a special case of the general lottery which follows, going over that simpler analysis might be helpful to a reader, who wishes to ease into our techniques and design choices.

Our PoR-Fairness Definition and Lottery

We next discuss how to turn the above informal fairness goals into a formal definition, and generalize the above lottery mechanism to handle more than two reputation tiers and to allow for arbitrary reputations. To this direction we partition, as in the simple example, the reputations in m = O(1) tiers¹⁰ as follows: For a given small δ > 0, the first tier includes parties with reputation between + δ and 1, the second tier includes parties with reputation between + δ and + δ, and so on. Parties with reputation 0 are ignored.¹¹ We refer to the above partitioning of the reputations as an m-tier partition.

The main differences of the generalized reputation-fairness notion from the above informal goal, is that (1) we parameterize the relation between the representation of different ties by a parameter c (in the above informal goal c = 2) and (2) we do not only require an appropriate relation on the expectations of the numbers of parties from the different tiers but require that these numbers are concentrated around numbers that satisfy this relation. The formal reputation fairness definition follows.

A high level description of the lottery is given in Fig.  5 . Informally, lottery for the m-tier case is similar in spirit to the two-tier case: First we sample a number of ℓ₁ parties from the highest reputation set ₁, then we sample ℓ₂ parties from the union of second-highest and the highest 1 ∪₂, then we sample ℓ₃ parties from the union of the three highest reputation tiers ₁ ∪₂ ∪₃, and so on. As we prove, the values ℓ₁,ℓ₂,ℓ₃ etc. can be carefully chosen so that the above fairness goal is reached whenever there are sufficiently many parties in the different tiers. We next detail our generalized sampling mechanism and prove its security properties.

We start by describing two standard methods for sampling a size-t subset of a party set —where each party P ∈ is associated with a unique identifier pid¹²—which will both be utilized in our fair sampling algorithm. Intuitively, the first sampler samples the set with replacement and the second without. The first method, denoted by Rand, takes as input/parameters the set , the size of the target set t—where naturally t < ||—and a nonce r. It also makes use of a hash function h which we will assume behaves as a random oracle.¹³ In order to sample the set, for each party with ID pid, the sampler evaluates the random oracle on input (pid,r) and if the output has more than log tailing 0’s the party is added to the output set. By a simple Chernoff bound, the size of the output set will be concentrated around t. The second sampler denoted by RandSet is the straight-forward way to sample a random subset of t parties from without replacement: Order the parties according to the output of h on input (pid,r) and select the ones with the highest value (where the output h is taken as the standard binary representation of integers). It follows directly from the fact that h behaves as a random oracle—and, therefore, assigns to each P_i ∈ a random number from {0,…,2^k - 1}—that the above algorithm uniformly samples a set ⊂ of size t out of all the possible size-t subsets of . For completeness we have included detailed description of both samplers in Appendix  A.2 . Given the above two samplers, we can provide the formal description of our PoR-fair lottery, see Figure  6 . Theorem  1 states the achieved security.

L(,Rep,c,δ,ϵ,r) 1. Divide the reputation parties into m tiers 1,…,m as follows,a : For i = 0…,m - 1, define m-i to be the set of parties in with reputation Repj ∈ ( + δ, + δ]. 2. Initialize i := ∅ for each i ∈ [m]. 3. Let ci = max{c,c}, i = 1,,m - 1. Let cm =. 4. For each i = 1,…,m: αi := |i|. 5. For each i = 1,…,m - 1: Let and let 6. For each i = 1,…,m do the following: If |∪j=1i j|≥ ℓi: (a) Invoke Rand(∪j=1i j,⌈ℓi⌉; (r||i)) to choose a set i of parties uniformly at random from ∪j=1i j. (b) For each j ∈ [i] compute coli,j := i ∩j and update j := j ∪ (i ∩j). (c) For each j ∈ [i] if coli,j≠∅, then i. if |j \j| < |coli,j| then reset the lottery and select sel as the output of Amax. ii. Else Invoke RandSet(j \j,|coli,j|; (r||i||j)) to choose a set i,j+; For each j ∈ [i] update j := j ∪i,j+. iii. Set i+ := ∪ j=1m i,j+ Else (i.e., |∪j=1i j| < ℓi): Reset the lottery and select (and output) sel as the output of Amax for choosing log 1+ϵn. 7. If the lottery was not reset in any of the above steps, then set sel := ∪j=1m j(= ∪i=1m(Q i ∪ Qi+)) and output sel.

Fig. 6: c-fair reputation-based lottery for m=O(1) tiers

The complete proof can be found in Appendix  C.1 . In the following we included a sketch of the main proof ideas. Proof (sketch). We consider two cases: Case 1: L noes not reset, and Case 2: L resets.
In Case 1, The lottery is never reset. This case is the bulk of the proof. First, in Lemma  3 using a combination of Chernoff bounds we prove that the random variable X_i corresponding to the number of parties from _i selected in the lottery is concentrated around the (expected) value:

(1)

i.e., for any constant λ_i ∈ (0,1):

(2)

Hence, by inspection of the protocol one can verify that the x_i’s and the ℓ_j’s satisfy the following system of linear equations:

(3)

Where B is an m × m matrix with the (i,j) position being

The above system of m equations has 2m unknowns. To solve it we add the following m equations which are derived from the desired reputation fairness: For each i ∈ [m - 1] :

(4)

and

(5)

This yields 2m linear equations. By solving the above system of equations we can compute:

for each i ∈ [m - 1], and

This already explains some of the mystery around the seemingly complicated choice of the ℓ_i’s in the protocol. Next we observe that for each j ∈ [m] : ∑ _i=1^mB_i,j = 1 which implies that

(6)

Because in each round we choose parties whose number is from a distribution centered around ℓ_i, the above implies that the sum of the parties we sample is centered around ∑ _j=1^mℓ_j = log ^1+ϵk which proves Property 1.

Property 2 is proven by a delicate counting of the parties which are corrupted, using Chernoff bounds for bounding the number of corrupted parties selected by Rand (which selects with replacement) and Hoeffding’s inequality for bounding the number of parties selected by RandSet (which selects without replacement). The core idea of the argument is that because the reputation in different tiers reduces in a linear manner but the representation to the output of the lottery reduces in an exponential manner, even if the adversary corrupts for free all the selected parties from the lowest half reputation tiers, still the upper half will have a strong super-majority to compensate so that overall the majority is honest.

Finally, the c-fairness (Property 3) is argued as follows:

–The c-Representation Fairness follows directly from Equations  1 ,  2 and  4 .
–The non-discrimination property follows from the fact that our lottery picks each party in every _i with exactly the same probability as any other party.
–The c-Selection Fairness is proved by using the fact that the non-discrimination property mandates that each party in sel ∩_i is selected with probability p_i = . By using our counting of the sets’ cardinalities computed above we can show that for any constant c′ < c: ≥ c′.

In Case 2 the lottery is reset and the output sel is selected by means of invocation of algorithm Amax. This is the simpler case since Lemma  1 ensures that if the reputation system is ϵ_f-feasible, then a fraction 1∕2 + ϵ_f of the parties in sel will be honest except with negligible probability. Note that Amax is only invoked if a reset occurs, i.e., if in some step there are no sufficiently many parties to select from; this occurs only if any set _i does not have sufficiently many parties to choose from. But the above analysis, for δ < γ - 1, the sampling algorithms choose at most (1 + δ)log ^1+ϵn with overwhelming probability. Hence when each _i has size at least γ ⋅ log ^1+ϵn, with overwhelming probability no reset occurs. In this case, by inspection of the protocol one can verify that the number of selected parties is |sel| = log ^1+ϵn.