bls254.gno
9.33 Kb · 295 lines
1// Package bls254 implements BLS signature verification over BN254, plus the
2// hash-to-G1 construction and message encoding used by the SPLASH beacon.
3//
4// Curve: alt_bn128 / BN254. G1: y^2 = x^3 + 3 over Fp. Points are encoded as
5// 64 bytes (x|y), each coordinate 32-byte big-endian. G2 points (as used for
6// the publisher's public key and the fixed generator) are 128 bytes,
7// EIP-197 wire order: x_imag | x_real | y_imag | y_real.
8//
9// There is no big-integer type in Gno, so field arithmetic goes through
10// crypto/modexp (EIP-198 modular exponentiation) plus hand-rolled 4-limb
11// compare/subtract/add for the one modular addition hash-to-G1 needs.
12package bls254
13
14import (
15 "crypto/bn254"
16 "crypto/modexp"
17 "crypto/sha256"
18 "encoding/hex"
19 "math/bits"
20 "strconv"
21)
22
23// DOMAIN is the hash-to-G1 domain separation tag for the SPLASH beacon.
24const DOMAIN = "SPLASH-BEACON-BN254-G1-v1"
25
26const (
27 // pHex is the BN254 base field modulus, big-endian.
28 pHex = "30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47"
29 // sqrtExpHex is (P+1)/4, a valid modular square-root exponent because
30 // P % 4 == 3.
31 sqrtExpHex = "0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52"
32 // g2GenHex is the canonical G2 generator, EIP-197 wire order
33 // (x_imag | x_real | y_imag | y_real).
34 g2GenHex = "198e9393920d483a7260bfb731fb5d25f1aa493335a9e71297e485b7aef312c21800deef121f1e76426a00665e5c4479674322d4f75edadd46debd5cd992f6ed090689d0585ff075ec9e99ad690c3395bc4b313370b38ef355acdadcd122975b12c85ea5db8c6deb4aab71808dcb408fe3d1e7690c43d37b4ce6cc0166fa7daa"
35)
36
37var (
38 pBytes = mustDecodeHex(pHex)
39 pLimbs = toLimbs(pBytes)
40 sqrtExpBytes = mustDecodeHex(sqrtExpHex)
41 g2GenBytes = mustDecodeHex(g2GenHex)
42)
43
44func mustDecodeHex(s string) []byte {
45 b, err := hex.DecodeString(s)
46 if err != nil {
47 panic("bls254: bad constant hex")
48 }
49 return b
50}
51
52// ---- 4-limb (256-bit) field helpers. Inputs/outputs are 32-byte big-endian. ----
53//
54// Every function in this block is hand-unrolled over the four limbs rather than
55// written as a `for i := 0; i < 4; i++` loop. That is not style, it is the second
56// largest gas item in the drand path after the field multiply itself. Measured on
57// this toolchain, 100 calls with the harness baseline subtracted:
58//
59// looped unrolled saved
60// toLimbs 52,705 39,328 25%
61// fromLimbs 58,961 42,308 28%
62// addModP 56,287 49,420 12%
63//
64// The gno VM charges per interpreted operation, so the loop counter, the bound
65// test and the i*8 and 3-i index arithmetic cost real gas on top of the eight
66// shift-ors they schedule. halveModP in fieldmul.gno was already unrolled and
67// measured 21,035 against addModP's looped 56,287 for strictly more work, which
68// is what prompted this.
69//
70// The saving is smaller than that comparison suggested -- addModP gave back 12%,
71// not the 2.5x the halveModP contrast implied, because most of its cost is the
72// four bits.Add64 calls and the cmp, not the loop scaffolding. The numbers above
73// are measured on this toolchain, not predicted.
74//
75// The unrolled bodies are mechanical transcriptions of the loops they replace;
76// TestLimbHelpersUnrolledMatchLooped in bls254_test.gno keeps a copy of each
77// original loop and asserts the two agree on a large operand set, so the
78// transcription is checked rather than eyeballed.
79
80func toLimbs(b []byte) [4]uint64 {
81 var l [4]uint64
82 l[3] = uint64(b[0])<<56 | uint64(b[1])<<48 | uint64(b[2])<<40 | uint64(b[3])<<32 |
83 uint64(b[4])<<24 | uint64(b[5])<<16 | uint64(b[6])<<8 | uint64(b[7])
84 l[2] = uint64(b[8])<<56 | uint64(b[9])<<48 | uint64(b[10])<<40 | uint64(b[11])<<32 |
85 uint64(b[12])<<24 | uint64(b[13])<<16 | uint64(b[14])<<8 | uint64(b[15])
86 l[1] = uint64(b[16])<<56 | uint64(b[17])<<48 | uint64(b[18])<<40 | uint64(b[19])<<32 |
87 uint64(b[20])<<24 | uint64(b[21])<<16 | uint64(b[22])<<8 | uint64(b[23])
88 l[0] = uint64(b[24])<<56 | uint64(b[25])<<48 | uint64(b[26])<<40 | uint64(b[27])<<32 |
89 uint64(b[28])<<24 | uint64(b[29])<<16 | uint64(b[30])<<8 | uint64(b[31])
90 return l
91}
92
93func fromLimbs(l [4]uint64) []byte {
94 b := make([]byte, 32)
95 v := l[3]
96 b[0], b[1], b[2], b[3] = byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32)
97 b[4], b[5], b[6], b[7] = byte(v>>24), byte(v>>16), byte(v>>8), byte(v)
98 v = l[2]
99 b[8], b[9], b[10], b[11] = byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32)
100 b[12], b[13], b[14], b[15] = byte(v>>24), byte(v>>16), byte(v>>8), byte(v)
101 v = l[1]
102 b[16], b[17], b[18], b[19] = byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32)
103 b[20], b[21], b[22], b[23] = byte(v>>24), byte(v>>16), byte(v>>8), byte(v)
104 v = l[0]
105 b[24], b[25], b[26], b[27] = byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32)
106 b[28], b[29], b[30], b[31] = byte(v>>24), byte(v>>16), byte(v>>8), byte(v)
107 return b
108}
109
110// cmp returns -1, 0, 1 for a<b, a==b, a>b. Most-significant limb first, so the
111// common case of a difference in the top limb returns after one comparison.
112func cmp(a, b [4]uint64) int {
113 if a[3] != b[3] {
114 if a[3] < b[3] {
115 return -1
116 }
117 return 1
118 }
119 if a[2] != b[2] {
120 if a[2] < b[2] {
121 return -1
122 }
123 return 1
124 }
125 if a[1] != b[1] {
126 if a[1] < b[1] {
127 return -1
128 }
129 return 1
130 }
131 if a[0] != b[0] {
132 if a[0] < b[0] {
133 return -1
134 }
135 return 1
136 }
137 return 0
138}
139
140func sub(a, b [4]uint64) [4]uint64 {
141 var r [4]uint64
142 var borrow uint64
143 r[0], borrow = bits.Sub64(a[0], b[0], 0)
144 r[1], borrow = bits.Sub64(a[1], b[1], borrow)
145 r[2], borrow = bits.Sub64(a[2], b[2], borrow)
146 r[3], _ = bits.Sub64(a[3], b[3], borrow)
147 return r
148}
149
150func add(a, b [4]uint64) ([4]uint64, uint64) {
151 var r [4]uint64
152 var carry uint64
153 r[0], carry = bits.Add64(a[0], b[0], 0)
154 r[1], carry = bits.Add64(a[1], b[1], carry)
155 r[2], carry = bits.Add64(a[2], b[2], carry)
156 r[3], carry = bits.Add64(a[3], b[3], carry)
157 return r, carry
158}
159
160// addModP computes (a + b) mod P for a, b already reduced mod P.
161func addModP(a, b, p [4]uint64) [4]uint64 {
162 s, carry := add(a, b)
163 if carry != 0 || cmp(s, p) >= 0 {
164 s = sub(s, p)
165 }
166 return s
167}
168
169// ---- hash-to-G1 ----
170
171// hashToG1 is the non-panicking core of HashToG1. ok is false only if the
172// try-and-increment loop exhausts its bound, which does not happen for any
173// message with a well-formed hash (probability of exhaustion is ~2^-64).
174func hashToG1(msg []byte) (pt []byte, ok bool) {
175 pt, _, ok = hashToG1WithCounter(msg)
176 return pt, ok
177}
178
179// hashToG1WithCounter is hashToG1 plus the retry counter it stopped at,
180// exposed for tests that check the counter against testdata/vectors.json.
181func hashToG1WithCounter(msg []byte) (pt []byte, ctr int, ok bool) {
182 three := [4]uint64{3, 0, 0, 0}
183 for ctr := 0; ctr < 64; ctr++ {
184 buf := make([]byte, 0, len(DOMAIN)+len(msg)+1)
185 buf = append(buf, DOMAIN...)
186 buf = append(buf, msg...)
187 buf = append(buf, byte(ctr))
188 h := sha256.Sum256(buf)
189
190 x := modexp.ModExp(h[:], []byte{1}, pBytes) // reduce mod P
191 x3 := modexp.ModExp(x, []byte{3}, pBytes) // x^3 mod P
192 rhs := fromLimbs(addModP(toLimbs(x3), three, pLimbs))
193
194 y := modexp.ModExp(rhs, sqrtExpBytes, pBytes) // candidate sqrt
195 y2 := modexp.ModExp(y, []byte{2}, pBytes)
196 if !bytesEqual(y2, rhs) {
197 continue // not a quadratic residue
198 }
199
200 yl := toLimbs(y)
201 if negy := sub(pLimbs, yl); cmp(negy, yl) < 0 {
202 y = fromLimbs(negy) // canonical branch: numerically smaller root
203 }
204 out := make([]byte, 0, 64)
205 out = append(out, x...)
206 out = append(out, y...)
207 return out, ctr, true
208 }
209 return nil, 64, false
210}
211
212func bytesEqual(a, b []byte) bool {
213 if len(a) != len(b) {
214 return false
215 }
216 for i := range a {
217 if a[i] != b[i] {
218 return false
219 }
220 }
221 return true
222}
223
224// HashToG1 maps msg to a G1 point via try-and-increment. Returns 64 bytes
225// (x|y). Panics if the loop exhausts its 64-attempt bound.
226func HashToG1(msg []byte) []byte {
227 pt, ok := hashToG1(msg)
228 if !ok {
229 panic("bls254: hash_to_g1 exhausted")
230 }
231 return pt
232}
233
234// NegateG1 returns (x, P-y) for a 64-byte G1 point. Returns nil on bad input.
235func NegateG1(pt []byte) []byte {
236 return negateG1(pt)
237}
238
239func negateG1(pt []byte) []byte {
240 if len(pt) != 64 {
241 return nil
242 }
243 yl := toLimbs(pt[32:64])
244 var zero [4]uint64
245 out := make([]byte, 64)
246 copy(out[:32], pt[:32])
247 if cmp(yl, zero) == 0 {
248 // y == 0 has no distinct negation; leave as-is.
249 copy(out[32:], pt[32:64])
250 return out
251 }
252 copy(out[32:], fromLimbs(sub(pLimbs, yl)))
253 return out
254}
255
256// Verify reports whether sig is the BLS signature over msg under pubkey.
257// pubkey is 128 bytes (G2, imaginary-first), sig is 64 bytes (G1). Verify is
258// total: wrong lengths, unreduced coordinates, off-curve points and an
259// invalid precompile result all yield false. It never panics.
260func Verify(pubkey, msg, sig []byte) bool {
261 if len(pubkey) != 128 || len(sig) != 64 {
262 return false
263 }
264 h, ok := hashToG1(msg)
265 if !ok {
266 return false
267 }
268 negH := negateG1(h)
269 if negH == nil {
270 return false
271 }
272
273 in := make([]byte, 0, 384)
274 in = append(in, sig...)
275 in = append(in, g2GenBytes...)
276 in = append(in, negH...)
277 in = append(in, pubkey...)
278 if len(in) != 384 {
279 return false
280 }
281
282 out := bn254.PairingCheck(in)
283 // PairingCheck returns an empty NON-NIL slice on an invalid point or an
284 // unreduced coordinate; checking length (not nilness) is load-bearing.
285 if len(out) != bn254.PairingOutputSize {
286 return false
287 }
288 return out[len(out)-1] == 1
289}
290
291// RoundMessage builds the canonical message for a beacon round:
292// chainID || "|" || decimal(round).
293func RoundMessage(chainID string, round int64) []byte {
294 return []byte(chainID + "|" + strconv.FormatInt(round, 10))
295}
