Consensus plays a crucial role in distributed ledger systems, impacting both
scalability and decentralization. Many blockchain systems use a weighted
lottery based on a scarce resource such as a stake, storage, memory, or
computing power to select a committee whose members drive the consensus and are
responsible for adding new information to the ledger. Therefore, ensuring a
robust and fair committee selection process is essential for maintaining
security, efficiency, and decentralization.
There are two main approaches to randomized committee selection. In one
approach, each validator candidate locally checks whether they are elected to
the committee and reveals their proof during the consensus phase. In contrast,
in the second approach, a sortition algorithm decides a fixed-sized committee
that is globally verified. This paper focuses on the latter approach, with
cryptographic sortition as a method for fair committee selection that
guarantees a constant committee size. Our goal is to develop deterministic
guarantees that strengthen decentralization. We introduce novel methods that
provide deterministic bounds on the influence of adversaries within the
committee, as evidenced by numerical experiments. This approach overcomes the
limitations of existing protocols that only offer probabilistic guarantees,
often providing large committees that are impractical for many quorum-based
applications like atomic broadcast and randomness beacon protocols.