I’d definitely recommend reading Ignacio’s article to understand what’s going on.
The code handles different parts of committee and leader selection in different places, so it’s kind of confusing and not really a great starting point.
If you already understand what’s going on at a high level and want to see how the code actually does it, read on!
(The line numbers I’m giving are as of commit e2874b1e7183eb59be6b854bca7140625a901a9f, the latest commit on the “master” branch at time of writing.)
The unauthenticatedVote.verify function (agreement/vote.go line 89) checks whether a vote we hear from the network is valid (which includes checking that the voter was actually selected). First there are various checks that the vote is properly constructed and signed. Then we get to the interesting part on line 133, verifying the “credential”.
cred, err := uv.Cred.Verify(proto, m)
if err != nil {
return vote{}, fmt.Errorf("unauthenticatedVote.verify: got a vote, but sender was not selected: %v", err)
}
The credential is the part of a vote that proves you were selected. Concretely, it’s a VRF proof from which we can derive the voter’s unique, pseudorandom VRF output hash, which is then used to determine whether the voter was selected as described in Ignacio’s article.
[Sergey’s blog post about VRFs][https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61] explains what VRFs do in a little more detail.
So now we’ll jump to the unauthenticatedCredential.Verify function (in data/committee/credential.go starting on line 68)
// Verify an unauthenticated Credential that was received from the network.
//
// Verify checks if the given credential is a valid proof of membership
// conditioned on the provided committee membership parameters.
//
// If it is, the returned Credential constitutes a proof of this fact.
// Otherwise, an error is returned.
func (cred UnauthenticatedCredential) Verify(proto config.ConsensusParams, m Membership) (res Credential, err error) {
(If you’re curious, Credential and UnauthenticatedCredential are different types so that the compiler won’t let us accidentally pass something we haven’t yet verified to a function that thinks its input has already been verified.)
selectionKey := m.Record.SelectionID
ok, vrfOut := selectionKey.Verify(cred.Proof, m.Selector)
Here we verify the VRF proof that appeared in the vote using the voter’s VRF public key. One difference between Sergey’s article and the code: In the article, a voter would send both their VRF output Y and the proof rho. With the specific VRF construction we’re using you can calculate the output Y just by looking at proof rho, so to save bandwidth the voter only sends the proof and receivers calculate the output themselves (vrfOut).
m.Selector is used as input to the VRF. It contains the seed, round, period, and step. (As Ignacio’s article mentions, there’s one committee per round, period, and step, and the seed is a systemwide parameter that changes from block to block to make selection unpredictable.) The selector struct is in agreement/selector.go if you’re curious.
Continuing onto line 79 of data/committee/credential.go:
hashable := hashableCredential{
RawOut: vrfOut,
Member: m.Record.Addr,
}
// Also hash in the address. This is necessary to decorrelate the selection of different accounts that have the same VRF key.
var h crypto.Digest
if proto.CredentialDomainSeparationEnabled {
h = crypto.HashObj(hashable)
} else {
h = crypto.Hash(append(vrfOut[:], m.Record.Addr[:]...))
}
Here we do something subtle but important: Instead of using the VRF output directly, we hash it with the voter’s address. (Ignore the “if”, we used to hash differently and for now the old code is still around for backward compatibility.) This defends against the following attack: If I split my money into a large number of small accounts, I can register the same VRF key on all the accounts. Then the accounts will always have the same VRF output – if one account is selected, they’ll all be selected, which will give me a huge number of votes. Binomial sampling isn’t enough to save us here – as Ignacio mentions in the “Sybil Attacks” section, we need each account to have independent VRF outputs. So we hash the address in with the VRF output, and the result is guaranteed to be independent for different accounts even if they have the same VRF key.
Continuing with line 92,
if !ok {
err = fmt.Errorf("UnauthenticatedCredential.Verify: could not verify VRF Proof with %v (parameters = %+v, proof = %#v)", selectionKey, m, cred.Proof)
return
}
var weight uint64
userMoney := m.Record.VotingStake()
expectedSelection := float64(m.Selector.CommitteeSize(proto))
if m.TotalMoney.Raw < userMoney.Raw {
logging.Base().Panicf("UnauthenticatedCredential.Verify: total money = %v, but user money = %v", m.TotalMoney, userMoney)
} else if m.TotalMoney.IsZero() || expectedSelection == 0 || expectedSelection > float64(m.TotalMoney.Raw) {
logging.Base().Panicf("UnauthenticatedCredential.Verify: m.TotalMoney %v, expectedSelection %v", m.TotalMoney.Raw, expectedSelection)
} else if !userMoney.IsZero() {
weight = sortition.Select(userMoney.Raw, m.TotalMoney.Raw, expectedSelection, h)
}
We reject invalid VRF proofs (which we could have done earlier), check that our selection parameters are at all reasonable, and then call sortition.Select, which uses the user’s balance, the total balance, the expected committee size, and the vrf output (hashed with the address) to do binomial sampling as described in Ignacio’s article. That code is all in data/committee/sortition/, and it’s pretty much exactly as Ignacio’s article describes, where we interpret the random value as a value between 0 and 1 on the Y axis and see where on the X axis it lands on the binomial CDF curve. (We use libboost to actually calculate the CDF.)
Hope this is helpful, or at least interesting!