Playground
drand.gno
// Package drand verifies drand "evmnet" beacons on gno.land and turns them
// into randomness.
//
// evmnet is the drand network that signs on the BN254 curve (scheme
// bls-bn254-unchained-on-g1, one beacon every 3 seconds). gno.land ships
// BN254 as native precompiles, so a beacon is checked fully on-chain: no
// trusted relayer, no oracle committee. Whoever submits a beacon can only
// submit the real one.
//
// Verification: e(sig, G2) == e(H(m), pk), with m = keccak256(round) and H
// the RFC 9380 SVDW hash-to-curve, checked as one native pairing product.
package drand
import (
"crypto/bn254"
"crypto/keccak256"
"crypto/sha256"
"encoding/binary"
"encoding/hex"
"math/rand"
)
// evmnet network parameters, from https://api.drand.sh/<ChainHash>/info.
const (
ChainHash = "04f1e9062b8a81f848fded9c12306733282b2727ecced50032187751166ec8c3"
SchemeID = "bls-bn254-unchained-on-g1"
GenesisTime = int64(1727521075)
Period = int64(3)
SigSize = 64
)
var (
// Group public key on G2, encoded x_im|x_re|y_im|y_re (EIP-197 order).
pubKey = mustHex("07e1d1d335df83fa98462005690372c643340060d205306a9aa8106b6bd0b3820557ec32c2ad488e4d4f6008f89a346f18492092ccc0d594610de2732c8b808f0095685ae3a85ba243747b1b2f426049010f6b73a0cf1d389351d5aaaa1047f6297d3a4f9749b33eb2d904c9d9ebf17224150ddd7abd7567a9bec6c74480ee0b")
// Negated G2 generator, same encoding (y_im and y_re replaced by p - y).
negG2Gen = mustHex("198e9393920d483a7260bfb731fb5d25f1aa493335a9e71297e485b7aef312c21800deef121f1e76426a00665e5c4479674322d4f75edadd46debd5cd992f6ed275dc4a288d1afb3cbb1ac09187524c7db36395df7be3b99e673b13a075a65ec1d9befcd05a5323e6da4d435f3b617cdb3af83285c2df711ef39c01571827f9d")
)
// RoundAt returns the latest round published at or before unix time t
// (0 before genesis).
func RoundAt(t int64) uint64 {
if t < GenesisTime {
return 0
}
return uint64((t-GenesisTime)/Period) + 1
}
// TimeOf returns the unix time at which round is published.
func TimeOf(round uint64) int64 {
if round == 0 {
return GenesisTime
}
return GenesisTime + int64(round-1)*Period
}
// Message returns the digest drand signs for round: keccak256(uint64_be(round)).
func Message(round uint64) [32]byte {
var b [8]byte
binary.BigEndian.PutUint64(b[:], round)
return keccak256.Sum256(b[:])
}
// Verify reports whether sig is the evmnet signature of round, checking
// e(sig, -G2) * e(H(m), pk) == 1. The pairing native rejects points off the
// curve and non-canonical coordinates.
func Verify(round uint64, sig []byte) bool {
if round == 0 || len(sig) != SigSize {
return false
}
msg := Message(round)
in := make([]byte, 0, 2*bn254.PairingChunkSize)
in = append(in, sig...)
in = append(in, negG2Gen...)
in = append(in, HashToG1(msg[:])...)
in = append(in, pubKey...)
out := bn254.PairingCheck(in)
return len(out) == bn254.PairingOutputSize && out[31] == 1
}
// Randomness returns the beacon randomness for sig, sha256(sig), the same
// value drand publishes as "randomness".
func Randomness(sig []byte) [32]byte {
return sha256.Sum256(sig)
}
// Derive returns sha256(beacon || salt). Use a distinct salt per consumer and
// per draw so that two users of the same round get independent values.
func Derive(beacon [32]byte, salt string) [32]byte {
buf := make([]byte, 0, 32+len(salt))
buf = append(buf, beacon[:]...)
buf = append(buf, salt...)
return sha256.Sum256(buf)
}
// NewRand returns a deterministic PRNG seeded from 32 bytes of randomness,
// for drawing several values (IntN, Perm, Shuffle) from one beacon.
func NewRand(seed [32]byte) *rand.Rand {
be := binary.BigEndian
return rand.New(rand.NewPCG(be.Uint64(seed[0:8]), be.Uint64(seed[8:16])))
}
func mustHex(s string) []byte {
b, err := hex.DecodeString(s)
if err != nil {
panic(err)
}
return b
}
func mustFe(s string) fe {
e, ok := feFromCanonical(mustHex(s))
if !ok {
panic("drand: constant not reduced")
}
return e
}
field.gno
package drand
import (
"crypto/modexp"
"encoding/binary"
"math/bits"
)
// fe is an element of the BN254 base field, as four little-endian 64-bit
// limbs, always fully reduced (< p).
//
// All the heavy arithmetic (squaring, inverse, square root, reducing a wide
// integer) goes to the native modexp; gno code only does limb additions.
type fe [4]uint64
var (
pLimbs = fe{0x3c208c16d87cfd47, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029}
pBytes = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47")
// Exponents: p-2 (inverse), (p+1)/4 (square root, p = 3 mod 4).
expInverse = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd45")
expSqrt = mustHex("0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52")
expOne = []byte{1}
expTwo = []byte{2}
expThree = []byte{3}
)
func feFromUint(v uint64) fe { return fe{v, 0, 0, 0} }
// feFromBytes reduces a big-endian integer of up to 64 bytes mod p.
func feFromBytes(b []byte) fe {
return feFromCanonicalUnchecked(modexp.ModExp(b, expOne, pBytes))
}
// feFromCanonical decodes exactly 32 big-endian bytes and reports whether the
// value is already reduced.
func feFromCanonical(b []byte) (fe, bool) {
e := feFromCanonicalUnchecked(b)
return e, e.lt(pLimbs)
}
func feFromCanonicalUnchecked(b []byte) fe {
be := binary.BigEndian
return fe{be.Uint64(b[24:]), be.Uint64(b[16:]), be.Uint64(b[8:]), be.Uint64(b[0:])}
}
// bytes returns the 32-byte big-endian encoding.
func (a fe) bytes() []byte {
out := make([]byte, 32)
be := binary.BigEndian
be.PutUint64(out[0:], a[3])
be.PutUint64(out[8:], a[2])
be.PutUint64(out[16:], a[1])
be.PutUint64(out[24:], a[0])
return out
}
func (a fe) isZero() bool { return a[0]|a[1]|a[2]|a[3] == 0 }
func (a fe) isOdd() bool { return a[0]&1 == 1 }
func (a fe) lt(b fe) bool {
for i := 3; i >= 0; i-- {
if a[i] != b[i] {
return a[i] < b[i]
}
}
return false
}
func feAdd(a, b fe) fe {
r := rawAdd(a, b) // p < 2^254, so a+b never overflows 256 bits.
if !r.lt(pLimbs) {
r = rawSub(r, pLimbs)
}
return r
}
func feSub(a, b fe) fe {
if a.lt(b) {
return rawSub(rawAdd(a, pLimbs), b)
}
return rawSub(a, b)
}
func feNeg(a fe) fe {
if a.isZero() {
return a
}
return rawSub(pLimbs, a)
}
func rawAdd(a, b fe) fe {
var r fe
var c uint64
r[0], c = bits.Add64(a[0], b[0], 0)
r[1], c = bits.Add64(a[1], b[1], c)
r[2], c = bits.Add64(a[2], b[2], c)
r[3], _ = bits.Add64(a[3], b[3], c)
return r
}
func rawSub(a, b fe) fe {
var r fe
var c uint64
r[0], c = bits.Sub64(a[0], b[0], 0)
r[1], c = bits.Sub64(a[1], b[1], c)
r[2], c = bits.Sub64(a[2], b[2], c)
r[3], _ = bits.Sub64(a[3], b[3], c)
return r
}
// feMul uses quarter-squares, ab = ((a+b)/2)^2 - ((a-b)/2)^2, so the only
// heavy work is two squarings done by the native modexp. A schoolbook
// 256x256 product interpreted by the VM costs several times more.
func feMul(a, b fe) fe {
return feSub(feSquare(feHalf(feAdd(a, b))), feSquare(feHalf(feSub(a, b))))
}
// feHalf returns a/2 mod p.
func feHalf(a fe) fe {
if a.isOdd() {
a = rawAdd(a, pLimbs) // < 2^255, no overflow
}
a[0] = a[0]>>1 | a[1]<<63
a[1] = a[1]>>1 | a[2]<<63
a[2] = a[2]>>1 | a[3]<<63
a[3] >>= 1
return a
}
func feSquare(a fe) fe { return feExp(a, expTwo) }
func feExp(a fe, e []byte) fe {
return feFromCanonicalUnchecked(modexp.ModExp(a.bytes(), e, pBytes))
}
// feInv returns a^-1, and 0 for 0 (same convention as RFC 9380 inv0).
func feInv(a fe) fe { return feExp(a, expInverse) }
// feSqrt returns a square root of a and whether a is a non-zero square.
// Zero is reported as a non-square, matching drand/kyber's legendre check.
func feSqrt(a fe) (fe, bool) {
if a.isZero() {
return a, false
}
r := feExp(a, expSqrt)
return r, feSquare(r) == a
}
gnomod.toml
module = "gno.land/p/g1jz6j9hj6rdf5ltl2kcrpa4jwtdh3w30z0yul06/sinopia/drand/v0" gno = "0.9" [addpkg] creator = "g1jz6j9hj6rdf5ltl2kcrpa4jwtdh3w30z0yul06" height = 969993 max_deposit = "10000000ugnot"
hash.gno
package drand
import (
"crypto/bn254"
"crypto/keccak256"
)
// DST is the hash-to-curve domain separation tag of the evmnet scheme.
const DST = "BLS_SIG_BN254G1_XMD:KECCAK-256_SVDW_RO_NUL_"
const keccakRate = 136 // keccak256 block size in bytes
// Shallue-van de Woestijne constants for BN254 G1 (A = 0, B = 3, Z = 1),
// RFC 9380 section 6.6.1, cross-checked against drand/kyber by
// contribs/gnodrand/internal/evmnet/svdw_test.go. c1 = g(Z) = 4 is applied as two doublings.
var (
feOne = feFromUint(1)
curveB = feFromUint(3)
svdwC2 = mustFe("183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea3") // -Z/2
svdwC3 = mustFe("00000000000000016789af3a83522eb353c98fc6b36d713d5d8d1cc5dffffffa") // sqrt(-g(Z)*3Z^2), sgn0 = 0
svdwC4 = mustFe("10216f7ba065e00de81ac1e7808072c9dd2b2385cd7b438469602eb24829a9bd") // -4g(Z)/3Z^2
)
// HashToG1 hashes msg onto G1 the way drand evmnet does (RFC 9380
// hash_to_curve with expand_message_xmd/keccak256 and the SVDW map) and
// returns the 64-byte affine encoding x|y.
func HashToG1(msg []byte) []byte {
u := expandMsgXmd(msg, 96)
p0 := mapToPoint(feFromBytes(u[:48]))
p1 := mapToPoint(feFromBytes(u[48:]))
in := make([]byte, 0, bn254.G1AddInputSize)
in = append(in, p0...)
in = append(in, p1...)
out := bn254.G1Add(in)
if out == nil {
panic("drand: hash-to-curve produced an invalid point")
}
return out
}
// dstPrime is DST || I2OSP(len(DST), 1).
var dstPrime = append([]byte(DST), byte(len(DST)))
// expandMsgXmd implements RFC 9380 section 5.3.1 with keccak256 and DST.
func expandMsgXmd(msg []byte, outLen int) []byte {
b0in := make([]byte, 0, keccakRate+len(msg)+3+len(dstPrime))
b0in = append(b0in, make([]byte, keccakRate)...)
b0in = append(b0in, msg...)
b0in = append(b0in, byte(outLen>>8), byte(outLen), 0)
b0in = append(b0in, dstPrime...)
b0 := keccak256.Sum256(b0in)
out := make([]byte, 0, outLen+32)
var prev [32]byte // b_0 xor zero is b_0, so b_1 needs no special case
for i := 1; len(out) < outLen; i++ {
in := make([]byte, 0, 32+1+len(dstPrime))
for j := 0; j < 32; j++ {
in = append(in, b0[j]^prev[j])
}
in = append(in, byte(i))
in = append(in, dstPrime...)
prev = keccak256.Sum256(in)
out = append(out, prev[:]...)
}
return out[:outLen]
}
// curveG returns x^3 + 3.
func curveG(x fe) fe {
return feAdd(feExp(x, expThree), curveB)
}
// mapToPoint is the SVDW map, as in drand/kyber, returning the 64-byte
// affine encoding. Candidates x2 and x3 are only computed when needed.
func mapToPoint(u fe) []byte {
tv1 := feSquare(u)
tv1 = feAdd(tv1, tv1)
tv1 = feAdd(tv1, tv1) // * c1 (= 4)
tv2 := feAdd(feOne, tv1)
tv1 = feSub(feOne, tv1)
tv3 := feInv(feMul(tv1, tv2))
tv5 := feMul(feMul(feMul(u, tv1), tv3), svdwC3)
x := feSub(svdwC2, tv5) // x1
y, ok := feSqrt(curveG(x))
if !ok {
x = feAdd(svdwC2, tv5) // x2
y, ok = feSqrt(curveG(x))
}
if !ok {
tv8 := feMul(feSquare(tv2), tv3)
x = feAdd(feOne, feMul(feSquare(tv8), svdwC4)) // x3
y, ok = feSqrt(curveG(x))
}
if !ok {
panic("drand: svdw found no square") // unreachable: g(x3) is always square
}
if u.isOdd() != y.isOdd() {
y = feNeg(y)
}
out := make([]byte, 0, 64)
out = append(out, x.bytes()...)
return append(out, y.bytes()...)
}