A Pure-Go VRF, Five Years Later

In 2021 I ported Algorand’s VRF off cgo as a series of PRs. They weren’t accepted and the code sat on a branch for five years. This is what I eventually did with it.

A verifiable random function gives you a pseudorandom output along with a proof that the output is the right one for a given key and message. Anyone holding the public key can check the proof, and nobody without the private key can steer the output. Algorand uses one for sortition: picking which nodes participate in a round without letting them pick themselves.

In 2021 I started porting Algorand’s VRF from a cgo wrapper around libsodium to pure Go. The work got finished and it never landed upstream. I’ve now published it as github.com/tmc/vrf.

Porting off cgo

The reasons for wanting this in Go were ordinary. A cgo dependency in the consensus path means every build needs a C toolchain, cross compilation stops being simple, and the Go tooling you would otherwise have — race detector, fuzzing, vet — doesn’t see past the language boundary. By then filippo.io/edwards25519 had made the curve arithmetic available in Go, so the part that is genuinely dangerous to write yourself was already written and maintained.

I sent the work as a series of PRs to algorand/go-algorand, on a branch named tmc/purego-vrf-crypto-split-out with tip 852d600c9. Filippo Valsorda reviewed it. It agreed byte for byte with the cgo implementation on captured vectors, with tests and benchmarks. It wasn’t accepted.

That’s a defensible call. Swapping a reviewed C library for a fresh reimplementation, in the code path that decides who participates in consensus, is a large ask, and the risk lands on the people running the chain rather than on me.

The branch then sat for about five years. It was finished and tested and had nowhere to go, so nothing happened to it. Publishing it myself had been available the entire time.

The standard moved underneath it

Some of the delay was the spec. Algorand implemented draft-irtf-cfrg-vrf-03 and their consensus locked it in, since a chain can’t change how it derives sortition without a hard fork. RFC 9381 finished the standard in 2023 and changed the construction underneath: hash-to-curve went from SHA-512 over a few concatenated fields to RFC 9380’s expand_message_xmd with a structured domain separation tag, and the challenge went from hashing four points to five. Proofs from one don’t verify under the other.

The suite identifier, a single octet, is 0x04 in both. Same octet, same curve, same hash, same 80-byte proof encoding, different algorithm. That decided one thing about the library. The two suites are separate packages with distinct types rather than one package with a suite flag, because nothing in the bytes tells them apart. A draft-03 proof handed to an RFC 9381 verifier parses fine and then fails the check, and the failure reads as “invalid proof” rather than “wrong protocol”. Separate types make it a compile error instead.

Relicensing

The code started life as PRs to an AGPL-3.0 project, so publishing it under BSD-3-Clause needed a reason. Algorand asks for no CLA, no DCO and no copyright assignment, and merging a PR doesn’t transfer copyright anyway (17 U.S.C. § 201(a)). The AGPL that go-algorand puts on its codebase doesn’t reach back and take ownership of inbound commits either. The copyright stayed with me, so the relicense was mine to make. The AGPL-era history is published on an agpl-history branch rather than scrubbed out.

What’s in the repo

Pure Go, one dependency (filippo.io/edwards25519), no cgo and no assembly. There are two packages: draft03 for Algorand compatibility and rfc9381 for the finished standard. The root package re-exports rfc9381, since new code should be using the standard.

The API follows crypto/ed25519:

pub, priv, err := vrf.GenerateKey(rand.Reader)
proof, err := priv.Prove(message)
output, err := vrf.Verify(pub, message, proof)

Verify hands back the output instead of a boolean, so there’s no way to hash a proof you haven’t checked. On an M4 Max over a 64-byte message, draft-03 proves in 156 µs and verifies in 149 µs; RFC 9381 proves in 198 µs and verifies in 247 µs.

draft03 is in there because Algorand’s consensus can’t move, and a library that only implements the final standard is no use to the ecosystem that shipped first. Everyone else should be using rfc9381.

Publishing it took an afternoon. Whether a finished branch will ever land upstream and whether anyone can go get it are separate questions. I spent five years treating them as one.