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}