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.

field.gno

3.72 Kb · 150 lines
  1package drand
  2
  3import (
  4	"crypto/modexp"
  5	"encoding/binary"
  6	"math/bits"
  7)
  8
  9// fe is an element of the BN254 base field, as four little-endian 64-bit
 10// limbs, always fully reduced (< p).
 11//
 12// All the heavy arithmetic (squaring, inverse, square root, reducing a wide
 13// integer) goes to the native modexp; gno code only does limb additions.
 14type fe [4]uint64
 15
 16var (
 17	pLimbs = fe{0x3c208c16d87cfd47, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029}
 18	pBytes = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47")
 19
 20	// Exponents: p-2 (inverse), (p+1)/4 (square root, p = 3 mod 4).
 21	expInverse = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd45")
 22	expSqrt    = mustHex("0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52")
 23
 24	expOne   = []byte{1}
 25	expTwo   = []byte{2}
 26	expThree = []byte{3}
 27)
 28
 29func feFromUint(v uint64) fe { return fe{v, 0, 0, 0} }
 30
 31// feFromBytes reduces a big-endian integer of up to 64 bytes mod p.
 32func feFromBytes(b []byte) fe {
 33	return feFromCanonicalUnchecked(modexp.ModExp(b, expOne, pBytes))
 34}
 35
 36// feFromCanonical decodes exactly 32 big-endian bytes and reports whether the
 37// value is already reduced.
 38func feFromCanonical(b []byte) (fe, bool) {
 39	e := feFromCanonicalUnchecked(b)
 40	return e, e.lt(pLimbs)
 41}
 42
 43func feFromCanonicalUnchecked(b []byte) fe {
 44	be := binary.BigEndian
 45	return fe{be.Uint64(b[24:]), be.Uint64(b[16:]), be.Uint64(b[8:]), be.Uint64(b[0:])}
 46}
 47
 48// bytes returns the 32-byte big-endian encoding.
 49func (a fe) bytes() []byte {
 50	out := make([]byte, 32)
 51	be := binary.BigEndian
 52	be.PutUint64(out[0:], a[3])
 53	be.PutUint64(out[8:], a[2])
 54	be.PutUint64(out[16:], a[1])
 55	be.PutUint64(out[24:], a[0])
 56	return out
 57}
 58
 59func (a fe) isZero() bool { return a[0]|a[1]|a[2]|a[3] == 0 }
 60
 61func (a fe) isOdd() bool { return a[0]&1 == 1 }
 62
 63func (a fe) lt(b fe) bool {
 64	for i := 3; i >= 0; i-- {
 65		if a[i] != b[i] {
 66			return a[i] < b[i]
 67		}
 68	}
 69	return false
 70}
 71
 72func feAdd(a, b fe) fe {
 73	r := rawAdd(a, b) // p < 2^254, so a+b never overflows 256 bits.
 74	if !r.lt(pLimbs) {
 75		r = rawSub(r, pLimbs)
 76	}
 77	return r
 78}
 79
 80func feSub(a, b fe) fe {
 81	if a.lt(b) {
 82		return rawSub(rawAdd(a, pLimbs), b)
 83	}
 84	return rawSub(a, b)
 85}
 86
 87func feNeg(a fe) fe {
 88	if a.isZero() {
 89		return a
 90	}
 91	return rawSub(pLimbs, a)
 92}
 93
 94func rawAdd(a, b fe) fe {
 95	var r fe
 96	var c uint64
 97	r[0], c = bits.Add64(a[0], b[0], 0)
 98	r[1], c = bits.Add64(a[1], b[1], c)
 99	r[2], c = bits.Add64(a[2], b[2], c)
100	r[3], _ = bits.Add64(a[3], b[3], c)
101	return r
102}
103
104func rawSub(a, b fe) fe {
105	var r fe
106	var c uint64
107	r[0], c = bits.Sub64(a[0], b[0], 0)
108	r[1], c = bits.Sub64(a[1], b[1], c)
109	r[2], c = bits.Sub64(a[2], b[2], c)
110	r[3], _ = bits.Sub64(a[3], b[3], c)
111	return r
112}
113
114// feMul uses quarter-squares, ab = ((a+b)/2)^2 - ((a-b)/2)^2, so the only
115// heavy work is two squarings done by the native modexp. A schoolbook
116// 256x256 product interpreted by the VM costs several times more.
117func feMul(a, b fe) fe {
118	return feSub(feSquare(feHalf(feAdd(a, b))), feSquare(feHalf(feSub(a, b))))
119}
120
121// feHalf returns a/2 mod p.
122func feHalf(a fe) fe {
123	if a.isOdd() {
124		a = rawAdd(a, pLimbs) // < 2^255, no overflow
125	}
126	a[0] = a[0]>>1 | a[1]<<63
127	a[1] = a[1]>>1 | a[2]<<63
128	a[2] = a[2]>>1 | a[3]<<63
129	a[3] >>= 1
130	return a
131}
132
133func feSquare(a fe) fe { return feExp(a, expTwo) }
134
135func feExp(a fe, e []byte) fe {
136	return feFromCanonicalUnchecked(modexp.ModExp(a.bytes(), e, pBytes))
137}
138
139// feInv returns a^-1, and 0 for 0 (same convention as RFC 9380 inv0).
140func feInv(a fe) fe { return feExp(a, expInverse) }
141
142// feSqrt returns a square root of a and whether a is a non-zero square.
143// Zero is reported as a non-square, matching drand/kyber's legendre check.
144func feSqrt(a fe) (fe, bool) {
145	if a.isZero() {
146		return a, false
147	}
148	r := feExp(a, expSqrt)
149	return r, feSquare(r) == a
150}