algorand
vrf: Add a pure Go VRF implementation
Summary
This proposes a pure Go implementation of the VRF (Verifiable Random Functions) primitives used in Algorand.
The goal of this change is to demonstrate the viability of a pure Go implementation of the VRF primitives in Algorand.
It goes without saying that any change to the cryptographic primitives in a project must undergo significant scrutiny. I intend this changeset to be a kicking off point for further discussion.
To most closely match the existing libsodium implementation there are a few design decisions that may differ in a final implementation (better error value propagation in particular).
Test Plan
Included in this PR are a number of unit tests and benchmarks that compare the output of the two implementations.
This additional test case provides wide value coverage in terms of inputs to build confidence in the accuracy of the Go implementation.
Initial Performance Testing Results
$ benchstat results
name time/op
ProveBytes-2 283µs ± 3%
ProveBytesGo-2 257µs ± 0%
VrfVerify-2 345µs ± 1%
VrfVerifyGo-2 333µs ± 1%
These results were compiled from many runs on a GCE e2-medium (2 vCPUs, 4 GB memory) which reports as: cpu: Intel(R) Xeon(R) CPU @ 2.30GHz
Raw benchmark results are available here.
My initial interpretation of these results is that it is viable from a performance perspective to implement the core VRF algorithms in pure Go. Having this implemented directly in Go carries a number of benefits, some of which are highlighted in #2131
I'd like feedback from the core team on this proposed change and we can map out what a reasonable pathway regarding further testing and eventual inclusion might be.
I want to thank and acknowledge @FiloSottile for guidance in using the edwards25519 package.
Thank you again for the contribution!
We've been discussing, there are a couple considerations here.
The publication of the VRF internet-draft is imminent; it was assigned the number RFC 9381 a few months ago and should be published soon https://www.rfc-editor.org/auth48/C450. Since we are still using an older version of the draft, it would be great to have a consensus upgrade to the official VRF implementation standard rather than switch to a Go implementation of the same old draft. Our understanding is that it is just one delimiter / null byte difference between our draft and the latest, but it is an incompatible change, so we would want to support both the old and new format to be able to validate old VRF proofs.
It may be the case that standardization as an RFC makes the VRF feature more amenable to being merged into libraries like libsodium and Go's own crypto package. However it does feel like the kind of project that would benefit from being its own repo. Perhaps we (Algorand) could be the ones to provide this VRF implementation, e.g. at http://github.com/algorand/vrf based on this code.
Thank you again for the contribution!
We've been discussing, there are a couple considerations here.
The publication of the VRF internet-draft is imminent; it was assigned the number RFC 9381 a few months ago and should be published soon https://www.rfc-editor.org/auth48/C450. Since we are still using an older version of the draft, it would be great to have a consensus upgrade to the official VRF implementation standard rather than switch to a Go implementation of the same old draft. Our understanding is that it is just one delimiter / null byte difference between our draft and the latest, but it is an incompatible change, so we would want to support both the old and new format to be able to validate old VRF proofs.
It may be the case that standardization as an RFC makes the VRF feature more amenable to being merged into libraries like libsodium and Go's own crypto package. However it does feel like the kind of project that would benefit from being its own repo. Perhaps we (Algorand) could be the ones to provide this VRF implementation, e.g. at http://github.com/algorand/vrf based on this code.
(Rebased, pushed).
That's great to hear, I'd be happy to separate our my implementation and propose it for inclusion in https://github.com/algorand/vrf
I was wrong about the differences between our implementation and the now newly approved RFC 9381, there's a more significant difference than just one delimiter / null byte.
I think we'll discuss this topic towards the end of September when we're doing our planning exercises, and decide whether it's worth the investment at this juncture.