A.1 A Simple PoR-Fair Lottery for a 2-Tier Reputation System

For completeness, we first repeat the informal goal of PoR-fairness in our 2-tier example.

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

1.

x₁ + x₂ = y, and

2.

x₁ = 2max{1,}x₂.

3.

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

Here is how to create a lottery which achieves the above goal. Let c := 2max{1,}. The lottery proceeds as follows:

1.

First, we choose ℓ_I = y parties randomly from ₁;

2.

Subsequently, we choose ℓ_II := y parties randomly from the union ₁ ∪₂. If a party from ₁ is chosen twice, i.e., in both of the above steps, then choose another party randomly from the parties in ₁ that have not yet been chosen in any of the steps.

3.

Take all the parties that were chosen in the above steps to form the committee.

We next show that the outcome of the above lottery satisfies, on average, the goals set for it. (Notation: For a random variable X, we denote by E(X) the expected value of X). The third property follows from the fact that the parties are chosen randomly from their respective sets. The following theorem formalizes and proves the fact that, “on average”, our above lottery satisfies the first two properties discussed in the above goal.

Proof (sketch). We prove the two equations in the theorem separately.

1.

ℓ_I + ℓ_II = ( + )y = y

2.

Let L_I denote the r.v. corresponding to the set of parties that are added on the committee in the first phase of the lottery and L_II the set added in the second and last phase. Denote by L the union, i.e., L = L_I ∪ L_II. First we note that by definition:

Additionally, since in the second phase, parties from ₂ who were already chosen in the first phase are replaced by other (not-yet chosen) parties from ₂ we know that L_I and L_II are disjoint.

The following hold: As in the first phase of the lottery no party from ₁ is chosen an all parties are chosen from ₂:

(7)

and

(8)

In the second phase, there are α₁ + α₂ parties to choose from in total, out of which α₂ are in ₂ and α₁ are in ₁. Since we chose parties randomly we have:

(9)

and

(10)

Using the above equations we can compute the expectations of X₁ and X₂:

where the second equation holds because L_I and L_II are a partition of L and the third follows from the linearity of expectation.

Similarly,

The above imply:

= c

A.2 PoR-Fair Definition and Lottery (Cont’d)

This section includes supplementary material for Section 3.1.

Rand(,t; r) 1. Initialize := ∅. 2. For each Pi ∈ with party-ID pid: (a) Compute si = h(pid,r). (b) If T(si) ≥ log , then update := ∪{Pi}. 3. Output .

Fig. 11: A simple uniform sampler based on a hash function h

RandSet(,t; r) 1. Initialize := ∅. 2. For each Pi ∈ with party-ID pida : (a) Compute si = h(pid,r). (b) Interpret h(pid,r) as a k-bit integer ni. 3. Order the parties in according to their corresponding ni’s. 4. Set to be the set of the first t parties in the above ordering. 5. Output

Fig. 12: A simple uniform sampler without replacements based on a hash function h