Verifiable Random Function

A bespoke VRF over Edwards25519 using SHAKE256 and the Elligator map — unpredictable outputs that anyone holding the public key can verify.

A verifiable random function is a keyed hash with a proof. Given a secret key and an input message, it produces an output that looks uniformly random to anyone without the key, yet is uniquely determined by the key and message, and comes with a proof that lets anyone holding the public key confirm the output is the right one. It is the primitive you want whenever a system needs randomness that participants cannot grind and cannot dispute.

import "github.com/sonr-io/crypto/vrf"

When to use one

• Leader election. Each validator computes VRF_sk(round_seed). Whoever’s output falls below a threshold is the leader, and can prove it. Nobody can pre-compute another validator’s output, and nobody can retry with a different key without publishing that key.
• Verifiable lotteries. Draw a winner from a beacon value; the operator proves the draw was honest without revealing the key.
• Private lookup keys. In a key-transparency directory (this construction’s origin), the map index for a username is VRF_sk(username), so the directory can prove a name’s absence without its tree structure leaking the set of registered names to an enumerating client.

Do not reach for a VRF where a plain signature would do — this package offers no way to sign arbitrary data, and verification only ever answers “is this the correct output for this message”. And do not treat the output as a commitment: it is a deterministic function of the message, so once a proof is published anyone holding the public key can confirm a guess at the message by re-verifying against it. A VRF hides the output from people without the key; it does not hide the input from people who can guess it.

The construction

The package doc comment states the scheme exactly. E is Curve25519 in Edwards coordinates, h is SHA-3 (specifically SHAKE256 throughout the implementation), f is the Elligator map, and 8 is the cofactor:

The proof is a Chaum–Pedersen style sigma protocol made non-interactive, proving that the same secret x relates g → g^x and H(n) → H(n)^x:

with r = h(x, n) supplying the proof’s randomness — so proving, like computing, is fully deterministic. Verification recomputes the challenge from g^t · P^c and H(n)^t · ii^c and checks it equals the challenge carried in the proof, and separately checks that the claimed output equals h(n, ii).

Concretely, in vrf.go: hashToCurve runs sha3.ShakeSum256 over the message, maps the digest with extra25519.HashToEdwards, then applies three successive GeDouble calls — multiplication by the cofactor 8 — to land in the prime-order subgroup. The challenge is SHAKE256(g ‖ H(n) ‖ pk ‖ H(n)^x ‖ g^r ‖ H(n)^r ‖ n) reduced mod the group order. In the code the challenge scalar is named s, which is why the proof layout below reads s ‖ t ‖ ii rather than c ‖ t ‖ ii.

Sizes and constants

ErrGetPubKey is the package’s only exported error value; it is declared but never returned by any exported function in vrf.go — Public() signals failure through its boolean instead.

API

Compute and Prove return the same output for the same key and message — Prove just also gives you the evidence. Use Compute when the holder needs the value locally (deciding whether it even won a leader election, indexing its own directory) and Prove only when the value must be published. That distinction is the main performance lever in the package: skipping the proof avoids two of the three scalar multiplications.

Example

Grounded in TestHonestComplete and TestConvertPrivateKeyToPublicKey.

package main

import (
	"bytes"
	"fmt"
	"log"

	"github.com/sonr-io/crypto/vrf"
)

func main() {
	// nil reader means crypto/rand.
	sk, err := vrf.GenerateKey(nil)
	if err != nil {
		log.Fatal(err)
	}

	pk, ok := sk.Public()
	if !ok {
		log.Fatal(vrf.ErrGetPubKey)
	}

	round := []byte("epoch-4711")

	// Cheap path: the holder just wants the value.
	out := sk.Compute(round)

	// Publishing path: the value plus evidence.
	outFromProof, proof := sk.Prove(round)

	fmt.Println("Compute == Prove:", bytes.Equal(out, outFromProof)) // true
	fmt.Println("output bytes:", len(out), "proof bytes:", len(proof)) // 32 96

	// Anyone with pk can check it.
	fmt.Println("verified:", pk.Verify(round, outFromProof, proof)) // true

	// Any single flipped bit in the proof fails the check.
	tampered := append([]byte(nil), proof...)
	tampered[0] ^= 0x01
	fmt.Println("tampered verified:", pk.Verify(round, outFromProof, tampered)) // false
}

TestFlipBitForgery in the package flips bits across the proof and asserts every variant fails.

Properties a caller can rely on

Caveats

Related