Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

hash.gno

3.17 Kb · 103 lines
  1package drand
  2
  3import (
  4	"crypto/bn254"
  5	"crypto/keccak256"
  6)
  7
  8// DST is the hash-to-curve domain separation tag of the evmnet scheme.
  9const DST = "BLS_SIG_BN254G1_XMD:KECCAK-256_SVDW_RO_NUL_"
 10
 11const keccakRate = 136 // keccak256 block size in bytes
 12
 13// Shallue-van de Woestijne constants for BN254 G1 (A = 0, B = 3, Z = 1),
 14// RFC 9380 section 6.6.1, cross-checked against drand/kyber by
 15// contribs/gnodrand/internal/evmnet/svdw_test.go. c1 = g(Z) = 4 is applied as two doublings.
 16var (
 17	feOne  = feFromUint(1)
 18	curveB = feFromUint(3)
 19	svdwC2 = mustFe("183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea3") // -Z/2
 20	svdwC3 = mustFe("00000000000000016789af3a83522eb353c98fc6b36d713d5d8d1cc5dffffffa") // sqrt(-g(Z)*3Z^2), sgn0 = 0
 21	svdwC4 = mustFe("10216f7ba065e00de81ac1e7808072c9dd2b2385cd7b438469602eb24829a9bd") // -4g(Z)/3Z^2
 22)
 23
 24// HashToG1 hashes msg onto G1 the way drand evmnet does (RFC 9380
 25// hash_to_curve with expand_message_xmd/keccak256 and the SVDW map) and
 26// returns the 64-byte affine encoding x|y.
 27func HashToG1(msg []byte) []byte {
 28	u := expandMsgXmd(msg, 96)
 29	p0 := mapToPoint(feFromBytes(u[:48]))
 30	p1 := mapToPoint(feFromBytes(u[48:]))
 31	in := make([]byte, 0, bn254.G1AddInputSize)
 32	in = append(in, p0...)
 33	in = append(in, p1...)
 34	out := bn254.G1Add(in)
 35	if out == nil {
 36		panic("drand: hash-to-curve produced an invalid point")
 37	}
 38	return out
 39}
 40
 41// dstPrime is DST || I2OSP(len(DST), 1).
 42var dstPrime = append([]byte(DST), byte(len(DST)))
 43
 44// expandMsgXmd implements RFC 9380 section 5.3.1 with keccak256 and DST.
 45func expandMsgXmd(msg []byte, outLen int) []byte {
 46	b0in := make([]byte, 0, keccakRate+len(msg)+3+len(dstPrime))
 47	b0in = append(b0in, make([]byte, keccakRate)...)
 48	b0in = append(b0in, msg...)
 49	b0in = append(b0in, byte(outLen>>8), byte(outLen), 0)
 50	b0in = append(b0in, dstPrime...)
 51	b0 := keccak256.Sum256(b0in)
 52
 53	out := make([]byte, 0, outLen+32)
 54	var prev [32]byte // b_0 xor zero is b_0, so b_1 needs no special case
 55	for i := 1; len(out) < outLen; i++ {
 56		in := make([]byte, 0, 32+1+len(dstPrime))
 57		for j := 0; j < 32; j++ {
 58			in = append(in, b0[j]^prev[j])
 59		}
 60		in = append(in, byte(i))
 61		in = append(in, dstPrime...)
 62		prev = keccak256.Sum256(in)
 63		out = append(out, prev[:]...)
 64	}
 65	return out[:outLen]
 66}
 67
 68// curveG returns x^3 + 3.
 69func curveG(x fe) fe {
 70	return feAdd(feExp(x, expThree), curveB)
 71}
 72
 73// mapToPoint is the SVDW map, as in drand/kyber, returning the 64-byte
 74// affine encoding. Candidates x2 and x3 are only computed when needed.
 75func mapToPoint(u fe) []byte {
 76	tv1 := feSquare(u)
 77	tv1 = feAdd(tv1, tv1)
 78	tv1 = feAdd(tv1, tv1) // * c1 (= 4)
 79	tv2 := feAdd(feOne, tv1)
 80	tv1 = feSub(feOne, tv1)
 81	tv3 := feInv(feMul(tv1, tv2))
 82	tv5 := feMul(feMul(feMul(u, tv1), tv3), svdwC3)
 83	x := feSub(svdwC2, tv5) // x1
 84	y, ok := feSqrt(curveG(x))
 85	if !ok {
 86		x = feAdd(svdwC2, tv5) // x2
 87		y, ok = feSqrt(curveG(x))
 88	}
 89	if !ok {
 90		tv8 := feMul(feSquare(tv2), tv3)
 91		x = feAdd(feOne, feMul(feSquare(tv8), svdwC4)) // x3
 92		y, ok = feSqrt(curveG(x))
 93	}
 94	if !ok {
 95		panic("drand: svdw found no square") // unreachable: g(x3) is always square
 96	}
 97	if u.isOdd() != y.isOdd() {
 98		y = feNeg(y)
 99	}
100	out := make([]byte, 0, 64)
101	out = append(out, x.bytes()...)
102	return append(out, y.bytes()...)
103}