eth-kzg-ceremony-alt/powersoftau.go
powersoftau.goRaw
1package kzgceremony
2
3import (
4 "fmt"
5 "math/big"
6
7 "golang.org/x/crypto/blake2b"
8
9 bls12381 "github.com/kilic/bls12-381"
10)
11
12// MinRandomnessLen is the minimum accepted length for the user defined
13// randomness
14const MinRandomnessLen = 64
15
16var g1 *bls12381.G1
17var g2 *bls12381.G2
18
19func init() {
20 g1 = bls12381.NewG1()
21 g2 = bls12381.NewG2()
22}
23
24// State represents the data structure obtained from the Sequencer at the
25// /info/current_state endpoint
26type State struct {
27 Transcripts []Transcript
28 ParticipantIDs []string // WIP
29 ParticipantECDSASignatures []string
30}
31
32// BatchContribution represents the data structure obtained from the Sequencer
33// at the /contribute endpoint
34type BatchContribution struct {
35 Contributions []Contribution
36}
37
38type Contribution struct {
39 NumG1Powers uint64
40 NumG2Powers uint64
41 PowersOfTau *SRS
42 PotPubKey *bls12381.PointG2
43}
44
45type Transcript struct {
46 NumG1Powers uint64
47 NumG2Powers uint64
48 PowersOfTau *SRS
49 Witness *Witness
50}
51
52type Witness struct {
53 RunningProducts []*bls12381.PointG1
54 PotPubKeys []*bls12381.PointG2
55 BLSSignatures []*bls12381.PointG1
56}
57
58// SRS contains the powers of tau in G1 & G2, eg.
59// [τ'⁰]₁, [τ'¹]₁, [τ'²]₁, ..., [τ'ⁿ⁻¹]₁,
60// [τ'⁰]₂, [τ'¹]₂, [τ'²]₂, ..., [τ'ⁿ⁻¹]₂
61type SRS struct {
62 G1Powers []*bls12381.PointG1
63 G2Powers []*bls12381.PointG2
64}
65
66type toxicWaste struct {
67 tau *big.Int
68 TauG2 *bls12381.PointG2 // Proof.G2P
69}
70
71// Proof contains g₂ᵖ and g₂^τ', used by the verifier
72type Proof struct {
73 G2P *bls12381.PointG2 // g₂ᵖ
74 G1PTau *bls12381.PointG1 // g₂^τ' = g₂^{p ⋅ τ}
75}
76
77// Contribute takes the last State and computes a new State using the defined
78// randomness
79func (cs *State) Contribute(randomness []byte) (*State, error) {
80 ns := State{}
81 ns.Transcripts = make([]Transcript, len(cs.Transcripts))
82 for i := 0; i < len(cs.Transcripts); i++ {
83 ns.Transcripts[i].NumG1Powers = cs.Transcripts[i].NumG1Powers
84 ns.Transcripts[i].NumG2Powers = cs.Transcripts[i].NumG2Powers
85
86 newSRS, proof, err := Contribute(cs.Transcripts[i].PowersOfTau, i, randomness)
87 if err != nil {
88 return nil, err
89 }
90 ns.Transcripts[i].PowersOfTau = newSRS
91
92 ns.Transcripts[i].Witness = &Witness{}
93 ns.Transcripts[i].Witness.RunningProducts =
94 append(cs.Transcripts[i].Witness.RunningProducts, proof.G1PTau)
95 ns.Transcripts[i].Witness.PotPubKeys =
96 append(cs.Transcripts[i].Witness.PotPubKeys, proof.G2P)
97 ns.Transcripts[i].Witness.BLSSignatures = cs.Transcripts[i].Witness.BLSSignatures
98 }
99 ns.ParticipantIDs = cs.ParticipantIDs // TODO add github id (id_token.sub)
100 ns.ParticipantECDSASignatures = cs.ParticipantECDSASignatures
101
102 return &ns, nil
103}
104
105// Contribute takes the last BatchContribution and computes a new
106// BatchContribution using the defined randomness
107func (pb *BatchContribution) Contribute(randomness []byte) (*BatchContribution, error) {
108 nb := BatchContribution{}
109 nb.Contributions = make([]Contribution, len(pb.Contributions))
110 for i := 0; i < len(pb.Contributions); i++ {
111 nb.Contributions[i].NumG1Powers = pb.Contributions[i].NumG1Powers
112 nb.Contributions[i].NumG2Powers = pb.Contributions[i].NumG2Powers
113
114 newSRS, proof, err := Contribute(pb.Contributions[i].PowersOfTau, i, randomness)
115 if err != nil {
116 return nil, err
117 }
118 nb.Contributions[i].PowersOfTau = newSRS
119
120 nb.Contributions[i].PotPubKey = proof.G2P
121 }
122
123 return &nb, nil
124}
125
126// newEmptySRS creates an empty SRS filled by [1]₁ & [1]₂ points in all
127// respective arrays positions
128func newEmptySRS(nG1, nG2 int) *SRS {
129 g1s := make([]*bls12381.PointG1, nG1)
130 g2s := make([]*bls12381.PointG2, nG2)
131 for i := 0; i < nG1; i++ {
132 g1s[i] = g1.One()
133 }
134 for i := 0; i < nG2; i++ {
135 g2s[i] = g2.One()
136 }
137 return &SRS{g1s, g2s}
138}
139
140func tau(round int, randomness []byte) *toxicWaste {
141 val := blake2b.Sum256(randomness)
142 tau := new(big.Int).Mod(
143 new(big.Int).SetBytes(val[:]),
144 g2.Q())
145 tau_Fr := bls12381.NewFr().FromBytes(tau.Bytes())
146 TauG2 := g2.New()
147 g2.MulScalar(TauG2, g2.One(), tau_Fr)
148
149 return &toxicWaste{tau, TauG2}
150}
151
152func computeContribution(t *toxicWaste, prevSRS *SRS) *SRS {
153 srs := newEmptySRS(len(prevSRS.G1Powers), len(prevSRS.G2Powers))
154 Q := g1.Q() // Q = |G1| == |G2|
155
156 // fmt.Println("Computing [τ'⁰]₁, [τ'¹]₁, [τ'²]₁, ..., [τ'ⁿ⁻¹]₁, for n =", len(prevSRS.G1s))
157 for i := 0; i < len(prevSRS.G1Powers); i++ {
158 tau_i := new(big.Int).Exp(t.tau, big.NewInt(int64(i)), Q)
159 tau_i_Fr := bls12381.NewFr().FromBytes(tau_i.Bytes())
160 g1.MulScalar(srs.G1Powers[i], prevSRS.G1Powers[i], tau_i_Fr)
161 }
162 // fmt.Println("Computing [τ'⁰]₂, [τ'¹]₂, [τ'²]₂, ..., [τ'ⁿ⁻¹]₂, for n =", len(prevSRS.G2s))
163 for i := 0; i < len(prevSRS.G2Powers); i++ {
164 tau_i := new(big.Int).Exp(t.tau, big.NewInt(int64(i)), Q)
165 tau_i_Fr := bls12381.NewFr().FromBytes(tau_i.Bytes())
166 g2.MulScalar(srs.G2Powers[i], prevSRS.G2Powers[i], tau_i_Fr)
167 }
168
169 return srs
170}
171
172func genProof(toxicWaste *toxicWaste, prevSRS, newSRS *SRS) *Proof {
173 G1_p := g1.New()
174 tau_Fr := bls12381.NewFr().FromBytes(toxicWaste.tau.Bytes())
175 g1.MulScalar(G1_p, prevSRS.G1Powers[1], tau_Fr) // g_1^{tau'} = g_1^{p * tau}, where p=toxicWaste.tau
176
177 return &Proof{toxicWaste.TauG2, G1_p}
178}
179
180// Contribute takes as input the previous SRS and a random
181// byte slice, and returns the new SRS together with the Proof
182func Contribute(prevSRS *SRS, round int, randomness []byte) (*SRS, *Proof, error) {
183 if len(randomness) < MinRandomnessLen {
184 return nil, nil, fmt.Errorf("err randomness") // WIP
185 }
186 // set tau from randomness
187 tw := tau(round, randomness)
188
189 newSRS := computeContribution(tw, prevSRS)
190
191 proof := genProof(tw, prevSRS, newSRS)
192
193 return newSRS, proof, nil
194}
195
196func checkG1PointCorrectness(p *bls12381.PointG1) error {
197 // i) non-empty
198 if p == nil {
199 return fmt.Errorf("empty point value")
200 }
201 // ii) non-zero
202 if g1.IsZero(p) {
203 return fmt.Errorf("point can not be zero")
204 }
205 // iii) in the correct prime order of subgroups
206 if !g1.IsOnCurve(p) {
207 return fmt.Errorf("point not on curve")
208 }
209 if !g1.InCorrectSubgroup(p) {
210 return fmt.Errorf("point not in the correct prime order of subgroups")
211 }
212 return nil
213}
214
215func checkG2PointCorrectness(p *bls12381.PointG2) error {
216 // i) non-empty
217 if p == nil {
218 return fmt.Errorf("empty point value")
219 }
220 // ii) non-zero
221 if g2.IsZero(p) {
222 return fmt.Errorf("point can not be zero")
223 }
224 // iii) in the correct prime order of subgroups
225 if !g2.IsOnCurve(p) {
226 return fmt.Errorf("point not on curve")
227 }
228 if !g2.InCorrectSubgroup(p) {
229 return fmt.Errorf("point not in the correct prime order of subgroups")
230 }
231 return nil
232}
233
234// VerifyNewSRSFromPrevSRS checks the correct computation of the new SRS
235// respectively from the previous SRS. These are the checks that the Sequencer
236// would do.
237func VerifyNewSRSFromPrevSRS(prevSRS, newSRS *SRS, proof *Proof) bool {
238 pairing := bls12381.NewEngine()
239
240 // 1. check that elements of the newSRS are valid points
241 for i := 0; i < len(newSRS.G1Powers); i++ {
242 if err := checkG1PointCorrectness(newSRS.G1Powers[i]); err != nil {
243 return false
244 }
245 }
246 for i := 0; i < len(newSRS.G2Powers); i++ {
247 if err := checkG2PointCorrectness(newSRS.G2Powers[i]); err != nil {
248 return false
249 }
250 }
251
252 // 2. check proof.G1PTau == newSRS.G1Powers[1]
253 if !g1.Equal(proof.G1PTau, newSRS.G1Powers[1]) {
254 return false
255 }
256
257 // 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prevSRS.G1s[1] (g₁^τ)
258 // e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
259 eL := pairing.AddPair(prevSRS.G1Powers[1], proof.G2P).Result()
260 eR := pairing.AddPair(newSRS.G1Powers[1], g2.One()).Result()
261 if !eL.Equal(eR) {
262 return false
263 }
264
265 // 4. check newSRS following the powers of tau structure
266 for i := 0; i < len(newSRS.G1Powers)-1; i++ {
267 // i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
268 eL := pairing.AddPair(newSRS.G1Powers[i], newSRS.G2Powers[1]).Result()
269 eR := pairing.AddPair(newSRS.G1Powers[i+1], g2.One()).Result()
270 if !eL.Equal(eR) {
271 return false
272 }
273 }
274
275 for i := 0; i < len(newSRS.G2Powers)-1; i++ {
276 // ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
277 eL := pairing.AddPair(newSRS.G1Powers[1], newSRS.G2Powers[i]).Result()
278 eR := pairing.AddPair(g1.One(), newSRS.G2Powers[i+1]).Result()
279 if !eL.Equal(eR) {
280 return false
281 }
282 }
283
284 return true
285}
286
287// VerifyState acts similarly to VerifyNewSRSFromPrevSRS, but verifying the
288// given State (which can be obtained from the Sequencer)
289func VerifyState(s *State) bool {
290 pairing := bls12381.NewEngine()
291
292 for _, t := range s.Transcripts {
293 // 1. check that elements of the SRS are valid points
294 for i := 0; i < len(t.PowersOfTau.G1Powers); i++ {
295 if err := checkG1PointCorrectness(t.PowersOfTau.G1Powers[i]); err != nil {
296 return false
297 }
298 }
299 for i := 0; i < len(t.PowersOfTau.G2Powers); i++ {
300 if err := checkG2PointCorrectness(t.PowersOfTau.G2Powers[i]); err != nil {
301 return false
302 }
303 }
304
305 // 2. check t.Witness.RunningProducts[last] == t.PowersOfTau.G1Powers[1]
306 if !g1.Equal(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-1],
307 t.PowersOfTau.G1Powers[1]) {
308 return false
309 }
310
311 // 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prevSRS.G1s[1] (g₁^τ)
312 // e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
313 eL := pairing.AddPair(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-2], t.Witness.PotPubKeys[len(t.Witness.PotPubKeys)-1]).Result()
314 eR := pairing.AddPair(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-1], g2.One()).Result()
315 if !eL.Equal(eR) {
316 return false
317 }
318
319 // 4. check newSRS following the powers of tau structure
320 for i := 0; i < len(t.PowersOfTau.G1Powers)-1; i++ {
321 // i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
322 eL := pairing.AddPair(t.PowersOfTau.G1Powers[i], t.PowersOfTau.G2Powers[1]).Result()
323 eR := pairing.AddPair(t.PowersOfTau.G1Powers[i+1], g2.One()).Result()
324 if !eL.Equal(eR) {
325 return false
326 }
327 }
328
329 for i := 0; i < len(t.PowersOfTau.G2Powers)-1; i++ {
330 // ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
331 eL := pairing.AddPair(t.PowersOfTau.G1Powers[1], t.PowersOfTau.G2Powers[i]).Result()
332 eR := pairing.AddPair(g1.One(), t.PowersOfTau.G2Powers[i+1]).Result()
333 if !eL.Equal(eR) {
334 return false
335 }
336 }
337 }
338
339 return true
340}