-
Notifications
You must be signed in to change notification settings - Fork 11
/
Copy pathblst_recovery.nim
156 lines (126 loc) · 5 KB
/
blst_recovery.nim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import
sequtils,
results,
stew/objects,
./blst_lowlevel,
./blst_min_pubkey_sig_core
export
results
type
ID* = object
## A point on X axis used for key and signature recovery
point: blst_scalar
func fromUint32*(T: type ID, value: array[8, uint32]): T =
blst_scalar_from_uint32(toCV(result.point, cblst_scalar), value)
func `/`(a: blst_fr, b: blst_fr): blst_fr =
var t: blst_fr
blst_fr_eucl_inverse(toCV(t, cblst_fr), toCC(b, cblst_fr))
blst_fr_mul(toCV(result, cblst_fr), toCC(a, cblst_fr), toCC(t, cblst_fr))
func toScalar(a: blst_fr): blst_scalar =
blst_scalar_from_fr(toCV(result, cblst_scalar), toCC(a, cblst_fr))
func `*=`(a: var blst_fr, b: blst_fr) =
blst_fr_mul(toCV(a, cblst_fr), toCC(a, cblst_fr), toCC(b, cblst_fr))
func `*`(a: blst_fr, b: blst_fr): blst_fr=
blst_fr_mul(toCV(result, cblst_fr), toCC(a, cblst_fr), toCC(b, cblst_fr))
func `-`(a: blst_fr, b: blst_fr): blst_fr=
blst_fr_sub(toCV(result, cblst_fr), toCC(a, cblst_fr), toCC(b, cblst_fr))
func `+=`(a: var blst_fr, b: blst_fr) =
blst_fr_add(toCV(a, cblst_fr), toCC(a, cblst_fr), toCC(b, cblst_fr))
func `+`(a: blst_fr, b: blst_fr): blst_fr =
blst_fr_add(toCV(result, cblst_fr), toCC(a, cblst_fr), toCC(b, cblst_fr))
func `*=`(a: var blst_p2; s: blst_fr) =
let scalar = s.toScalar()
blst_p2_mult(toCV(a, cblst_p2), toCC(a, cblst_p2),
unsafeAddr scalar.b[0], 255)
func `*`(a: blst_p2; s: blst_fr): blst_p2 =
let scalar = s.toScalar()
blst_p2_mult(toCV(result, cblst_p2), toCC(a, cblst_p2),
unsafeAddr scalar.b[0], 255)
func `+=`(a: var blst_p2; b: blst_p2) =
blst_p2_add(toCV(a, cblst_p2), toCC(a, cblst_p2), toCC(b, cblst_p2))
func toFr(sk: SecretKey): blst_fr =
let scalar = sk.getScalar()
blst_fr_from_scalar(toCV(result, cblst_fr), toCC(scalar, cblst_scalar))
func toFr(id: ID): blst_fr =
blst_fr_from_scalar(toCV(result, cblst_fr), toCC(id.point, cblst_scalar))
func toP2(s: Signature): blst_p2 =
let point = s.getPoint()
blst_p2_from_affine(toCV(result, cblst_p2), toCC(point, cblst_p2_affine))
func add*(a: SecretKey, b: SecretKey): SecretKey =
var r: blst_fr
let
afr = a.toFr()
bfr = b.toFr()
blst_fr_add(toCV(r, cblst_fr), toCC(afr, cblst_fr), toCC(bfr, cblst_fr))
SecretKey.fromFr(r)
func evaluatePolynomial(cfs: openArray[blst_fr], x: blst_fr): blst_fr =
let count = len(cfs)
if count == 0:
return blst_fr()
if count == 1:
return cfs[0]
# Horner's method
# We will calculate a0 + X(a1 + X(a2 + ..X(an-1 + Xan))
var y = cfs[count - 1]
for i in 2 .. count:
y = y * x + cfs[count - i]
return y
func lagrangeInterpolation[T, U](yVec: openArray[T], xVec: openArray[U]): Result[T, cstring] =
let k = len(xVec)
if k == 0 or k != len(yVec):
return err "invalid inputs"
if k == 1:
return ok yVec[0]
# We calculate L(0) so we can simplify
# (X - X0) .. (X - Xj-1) * (X - Xj+1) .. (X - Xk) to just X0 * X1 .. Xk
# Later we can divide by Xi for each basis polynomial li(0)
var a = xVec[0]
for i in 1 ..< k:
a *= xVec[i]
if a.isZeroMemory:
return err "zero secret share id"
var r: T
for i in 0 ..< k:
var b = xVec[i]
for j in 0 ..< k:
if j != i:
let v = xVec[j] - xVec[i]
if v.isZeroMemory:
return err "duplicate secret share id"
b *= v
# Ith basis polynomial for X = 0
let li0 = (a / b)
r += yVec[i] * li0
ok(r)
func genSecretShare*(mask: openArray[SecretKey], id: ID): SecretKey =
## https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
##
## In Shamir's secret sharing, a secret is encoded as a n-degree polynomial
## F where the secret value is equal to F(0). Here, F(0) is provided as mask[0].
##
## A key share is generated by evaluating the polynomial in the `id` point.
## Later we can use at least N of these points to recover the original secret.
##
## Furthermore, if we sign some message M with at least K of the secret key
## shares we can restore from them the signature of the same message signed
## with original secret key.
##
## For a more gentle introductiont to Shamir's secret sharing, see also:
##
## https://github.com/dashpay/dips/blob/master/dip-0006/bls_m-of-n_threshold_scheme_and_dkg.md
## https://medium.com/toruslabs/what-distributed-key-generation-is-866adc79620
let cfs = mask.mapIt(it.toFr)
SecretKey.fromFr evaluatePolynomial(cfs, id.toFr)
func recover*(secrets: openArray[SecretKey],
ids: openArray[ID]): Result[SecretKey, cstring] =
## Recover original secret key from N points generated by genSecretShare
let ys = secrets.mapIt(it.toFr)
let xs = ids.mapIt(it.toFr)
ok SecretKey.fromFr(? lagrangeInterpolation(ys, xs))
func recover*(signs: openArray[Signature],
ids: openArray[ID]): Result[Signature, cstring] =
## Recover signature from the original secret key from N signatures
## produced by at least N different secret shares generated by genSecretShare
let ys = signs.mapIt(it.toP2)
let xs = ids.mapIt(it.toFr)
ok Signature.fromP2(? lagrangeInterpolation(ys, xs))