The Power of Random Choice: Optimising Quorum Selection in Anonymous Committees

Abstract

Distributed systems that rely on consistency guarantees, such as Key Transparency and Certificate Transparency, face tension between security and efficiency when us ing anonymous committees. In such protocols, there are two key parameters: the selection probability p, which determines expected committee size, and the quorum threshold Q, the minimum number of endorsements required to accept a state. The Tail-Hammer framework already improves conservative Chernoff-based bounds by using tighter binomial tail estimates. This thesis refines the analysis further by ob serving that quorum selection from a randomly formed committee can be modelled almost identically to selecting directly from the full population, a consequence of the hypergeometric distribution collapsing to a simple ratio of binomial coefficients when the quorum is drawn without replacement from the committee. This closed form simplification yields significantly tighter probability bounds with no loss in security. For the at least one honest reliable broadcast setting with 128-bit security and a population of N = 109, the approach reduces the quorum size from Q = 481 to Q = 74 and the expected committee size from C = 828 to C = 249, reductions of approximately 85% and 70% respectively. The analysis is extended to both reliable broadcast and asynchronous network set tings, and to both at least one honest and honest majority quorum requirements. To handle a potentially malicious central server capable of selectively withholding votes, a new parameter S is introduced, representing the minimum number of votes a participant must receive before accepting a state. Security and liveness conditions on S are derived and analysed, revealing that the parameters p and Q optimised independently are not always jointly compatible with a feasible S, motivating a joint optimisation as future work. All results are implemented in Python using the gmpy2 library for arbitrary-precision arithmetic. To independently validate the numerical results, the at least one honest reliable broadcast setting is re-implemented in R us ing the Rmpfr package, with both implementations producing identical parameters across all tested population sizes.