Examples of Graded PKI. In prior work [3, 23, 15], a graded PKI is a setup protocol, executed by the parties ahead of time, such that each party outputs a vector of verification keys with grades (with the same consistency requirements we have). In this work, we use the graded PKI to capture graded eligibility proofs for committee selection as well. In this case, the public keys may not be known in advance to honest parties. Below, we give three examples of graded PKI implementations to give some motivation for our slightly different interface. Full PKI. A full PKI (where parties agree on the entire set of valid public keys ahead of time) can trivially serve as a d-graded PKI for any d: GradeKey(vk, sid) = d if vk is a valid key in the full PKI, and 0 otherwise. PoW-based PKI Setup. Xxxxxxxxxxxx and Xxxxxxxxxxx [3] show how to construct a graded PKI (which they call a ranked key set ) without setup assumptions, using Proofs of Work instead. This protocol runs as a setup phase, requiring interaction between all participating parties and outputs the entire set of public keys with non-zero grades to each party. In this case, GradeKey(vk, sid) is the grade output by the protocol if vk is in the set, and 0 otherwise. VRF-based Eligibility. A common method of randomly electing a committee with expected size n, out of a population of N parties, is Algorand-style self-sortition [11]: each party computes a VRF of the session id (which typically includes the round number), and self-selects if the output (interpreted as a value in the range [0, 1]) is less than n/N . The VRF output also serves as a publicly-verifiable proof of eligibility. However, in some cases the number of parties N is not in full consensus. For example, parties can self-select by running a proof-of-work solver locally, and N is estimated locally by each party based on observed published proofs. In this case, parties can still generate a graded eligibility proof, assuming that for every two honest parties Pi and Pj, the disagreement about N is bounded by some fixed constant k. For a public key vk and session id sid, let GradeKey(vk, sid) return g if a VRF proof was previously received that shows VRFvk(sid) < n/(N − (k − 1) − (d − g)· k). In this case, an honest party Pi considers itself active in session sid if VRFvk(sid) < n/N . Since every other honest party has N′ ≥ N − k, if another honest party considers itself active, it will receive grade d.
