Key Question

How does Algorand use Verifiable Random Functions to select a random committee for each block?

Deep Dive

Algorand (Silvio Micali, 2017) asks: what if you could randomly select a different committee of validators for every single block — and do it without any communication overhead? The answer: Verifiable Random Functions (VRFs). Algorand calls this Pure Proof-of-Stake (PPoS) because every coin holder has influence proportional to their stake, and no one needs to “lock” their coins.

Verifiable Random Functions are the cryptographic backbone. A VRF is like a public-key signature that returns a random number instead of a message:

VRF operation:

Private Key (sk)              Public Key (pk)
     │                              │
     │                              │
     ▼                              ▼
VRF_hash(sk, seed) ──────► [hash]  ◄──── VRF_verify(pk, seed, hash, proof)
                                    │
                                  proof

Properties:
1. Only sk holder can compute [hash, proof]
2. Anyone with pk can verify: "this hash came from this seed"
3. The hash is uniformly random — no one can predict it
4. The hash is deterministic — same seed + same sk = same hash

Committee selection per round: At the start of round r, every user computes a VRF using their secret key and the round’s seed (derived from previous rounds). If the VRF output is below a threshold proportional to their stake, they become a committee member for that round.

Example with 4 users (Alice 40%, Bob 30%, Carol 20%, Dave 10%):

Expected committee size = 20 users

User     Stake    VRF threshold    Elected?
───────────────────────────────────────────
Alice    40%      40% of users     ⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛  Yes (8 times)
Bob      30%      30% of users     ⬛⬛⬛⬛⬛⬛       Yes (6 times)
Carol    20%      20% of users     ⬛⬛⬛⬛          Yes (4 times)
Dave     10%      10% of users     ⬛⬛             Yes (2 times)

Each user independently knows they're elected — no one needs to tell them.

The threshold adjusts automatically so that each committee has roughly 1,000-4,000 members. This ensures Byzantine fault tolerance (the committee is almost certainly honest if fewer than 1/3 of all coins are adversarial).

Phases of consensus (simplified):

1. Proposal phase: Each committee member can propose a block. The VRF output also creates a priority — the smallest VRF hash becomes the “official” proposer.
2. Soft vote (BA★): The committee votes on whether the proposed block is valid. BA★ (Binary Agreement) runs a Byzantine agreement protocol that tolerates up to 1/3 malicious members.
3. Certification: If 2/3+ of the committee certifies the block, it’s final.

Handling network asynchrony: Algorand’s BA★ protocol gracefully degrades under network partitions. It uses a “Graded Consensus” and “Binary Byzantine Agreement” to eventually reach agreement even if messages are delayed. The protocol progresses in steps, each with a fresh VRF-selected committee:

BA★ Agreement Protocol:

Round r
  │
  ├── Step 1: Reduce (reduce proposals to a binary choice)
  ├── Step 2: Binary agreement (O(log n) rounds of voting)
  ├── Step 3: If agreed → output block
  └── Step 4: Else → try again with new committee

The key insight: since every step uses a fresh random committee, an adversary cannot predict who will be on the next committee. This defeats adaptive corruption attacks where an attacker tries to corrupt committee members mid-protocol.

Comparison of committee-based approaches:

Algorand’s VRF approach is unique: it selects committees without any communication, making it resilient to network partitions and adaptive adversaries. The downside: VRF computation is cryptographic work for every user every round, though verification is fast.

Check Your Understanding

1. What prevents an attacker from predicting which users will be on the next Algorand committee?
2. Why does Algorand need a different committee for each step of BA★ rather than using the same committee for the whole round?
3. How does Algorand ensure that a user with more stake is more likely to be on the committee?

The “So What?”

Algorand’s VRF-based committee selection is arguably the most elegant solution to the Byzantine consensus problem in PoS. It achieves instant finality, tolerates adaptive adversaries, and works under network asynchrony. If Ethereum’s Beacon Chain is the “practical” design, Algorand is the “theoretically clean” design.

✏️ Exercises

Proof of Stake & Modern Consensus: Exercises

Exercise 1: Nothing-at-Stake and Slashing

Consider a proof-of-stake system with 10 validators, each with 10% of the total stake. At block height 100, a network partition occurs: 5 validators see fork A, and 5 see fork B. Under a naive (no slashing) PoS design, explain:

• What each validator would do
• What happens to the two forks over time
• How adding a slashing condition that punishes double-signing changes the outcome

Exercise 2: Ethereum Committee Calculation

The Ethereum Beacon Chain uses a fixed committee size of 128 validators per slot. A validator is assigned to exactly one committee per epoch. Given:

• Total active validators: 100,000
• Slots per epoch: 32
• Committee size: 128

Calculate:

1. How many validators are actively attesting in each slot?
2. How many committees exist per slot?
3. How often does each validator attest per epoch (on average)?
4. What fraction of total validators attests per slot?

Exercise 3: Comparing Committee Selection

Consider three protocols:

• Ethereum: Committees selected via RANDAO (public randomness, all validators partitioned into fixed-size committees each epoch)
• Tendermint: No committees — every validator votes on every block
• Algorand: Committees selected via VRF (private randomness, each user independently computes their eligibility)

Answer:

1. Which protocol has the lowest communication overhead for selecting a committee? Why?
2. Which protocol is most vulnerable to adaptive corruption (attacker can corrupt validators mid-consensus)? Why?
3. For each protocol, estimate the fraction of total validators that participate in each block’s consensus. Is it all validators, a random subset, or a fixed subset?