Consensus via Anonymous Committees - Investigating Robustness Against Imprecise Security Settings and Quantum Adversaries

Abstract

Current solutions for achieving agreement in distributed systems often scale poorly or are resource intensive. Achieving agreement is necessary to distribute correct public keys using key transparency logs. Consensus mechanisms that rely on anonymous committees are a novel approach with the explicit goal of improved scalability in this task. Anonymous committees are chosen using a cryptographic function, which allows them to prove membership. Nodes reveal committee membership only upon casting votes, and are therefore anonymous, making them difficult to target with attacks before voting. To improve scalability, it is possible to derive optimal settings from the system’s assumed fractions of inactive and adversarial nodes. This report quantifies how security is affected if those assumptions are incorrect. Using plots of bit security dependent on changes in inactive or malicious node shares it shows that the system is susceptible to such variations. Even using high security margins the system might be vulnerable when assumptions are only a few percentage points wrong. As the security is probabilistic, it does not break at any certain point. Instead security gradually weakens as the share of malicious nodes increases. Additionally, as future viability is necessary for adoption of new systems, suitable post-quantum secure cryptographic selection functions are presented and compared. As scalability is a major selling point of anonymous committees, it is relevant to find a measurement for how the size of the subset necessary to approve proposals changes as a function of node count. Testing data shows the subset size is only weakly dependent on the node count, and approaches an upper limit as node count increases.