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 length < %d",
185 MinRandomnessLen)
186 }
187 // set tau from randomness
188 tw := tau(round, randomness)
189
190 newSRS := computeContribution(tw, prevSRS)
191
192 proof := genProof(tw, prevSRS, newSRS)
193
194 return newSRS, proof, nil
195}
196
197func checkG1PointCorrectness(p *bls12381.PointG1) error {
198 // i) non-empty
199 if p == nil {
200 return fmt.Errorf("empty point value")
201 }
202 // ii) non-zero
203 if g1.IsZero(p) {
204 return fmt.Errorf("point can not be zero")
205 }
206 // iii) in the correct prime order of subgroups
207 if !g1.IsOnCurve(p) {
208 return fmt.Errorf("point not on curve")
209 }
210 if !g1.InCorrectSubgroup(p) {
211 return fmt.Errorf("point not in the correct prime order of subgroups")
212 }
213 return nil
214}
215
216func checkG2PointCorrectness(p *bls12381.PointG2) error {
217 // i) non-empty
218 if p == nil {
219 return fmt.Errorf("empty point value")
220 }
221 // ii) non-zero
222 if g2.IsZero(p) {
223 return fmt.Errorf("point can not be zero")
224 }
225 // iii) in the correct prime order of subgroups
226 if !g2.IsOnCurve(p) {
227 return fmt.Errorf("point not on curve")
228 }
229 if !g2.InCorrectSubgroup(p) {
230 return fmt.Errorf("point not in the correct prime order of subgroups")
231 }
232 return nil
233}
234
235// VerifyNewSRSFromPrevSRS checks the correct computation of the new SRS
236// respectively from the previous SRS. These are the checks that the Sequencer
237// would do.
238func VerifyNewSRSFromPrevSRS(prevSRS, newSRS *SRS, proof *Proof) bool {
239 pairing := bls12381.NewEngine()
240
241 // 1. check that elements of the newSRS are valid points
242 for i := 0; i < len(newSRS.G1Powers); i++ {
243 if err := checkG1PointCorrectness(newSRS.G1Powers[i]); err != nil {
244 return false
245 }
246 }
247 for i := 0; i < len(newSRS.G2Powers); i++ {
248 if err := checkG2PointCorrectness(newSRS.G2Powers[i]); err != nil {
249 return false
250 }
251 }
252
253 // 2. check proof.G1PTau == newSRS.G1Powers[1]
254 if !g1.Equal(proof.G1PTau, newSRS.G1Powers[1]) {
255 return false
256 }
257
258 // 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prevSRS.G1s[1] (g₁^τ)
259 // e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
260 eL := pairing.AddPair(prevSRS.G1Powers[1], proof.G2P).Result()
261 eR := pairing.AddPair(newSRS.G1Powers[1], g2.One()).Result()
262 if !eL.Equal(eR) {
263 return false
264 }
265
266 // 4. check newSRS following the powers of tau structure
267 for i := 0; i < len(newSRS.G1Powers)-1; i++ {
268 // i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
269 eL := pairing.AddPair(newSRS.G1Powers[i], newSRS.G2Powers[1]).Result()
270 eR := pairing.AddPair(newSRS.G1Powers[i+1], g2.One()).Result()
271 if !eL.Equal(eR) {
272 return false
273 }
274 }
275
276 for i := 0; i < len(newSRS.G2Powers)-1; i++ {
277 // ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
278 eL := pairing.AddPair(newSRS.G1Powers[1], newSRS.G2Powers[i]).Result()
279 eR := pairing.AddPair(g1.One(), newSRS.G2Powers[i+1]).Result()
280 if !eL.Equal(eR) {
281 return false
282 }
283 }
284
285 return true
286}
287
288// VerifyState acts similarly to VerifyNewSRSFromPrevSRS, but verifying the
289// given State (which can be obtained from the Sequencer)
290func VerifyState(s *State) bool {
291 pairing := bls12381.NewEngine()
292
293 for _, t := range s.Transcripts {
294 // 1. check that elements of the SRS are valid points
295 for i := 0; i < len(t.PowersOfTau.G1Powers); i++ {
296 if err := checkG1PointCorrectness(t.PowersOfTau.G1Powers[i]); err != nil {
297 return false
298 }
299 }
300 for i := 0; i < len(t.PowersOfTau.G2Powers); i++ {
301 if err := checkG2PointCorrectness(t.PowersOfTau.G2Powers[i]); err != nil {
302 return false
303 }
304 }
305
306 // 2. check t.Witness.RunningProducts[last] == t.PowersOfTau.G1Powers[1]
307 if !g1.Equal(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-1],
308 t.PowersOfTau.G1Powers[1]) {
309 return false
310 }
311
312 // 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prevSRS.G1s[1] (g₁^τ)
313 // e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
314 eL := pairing.AddPair(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-2], t.Witness.PotPubKeys[len(t.Witness.PotPubKeys)-1]).Result()
315 eR := pairing.AddPair(t.Witness.RunningProducts[len(t.Witness.RunningProducts)-1], g2.One()).Result()
316 if !eL.Equal(eR) {
317 return false
318 }
319
320 // 4. check newSRS following the powers of tau structure
321 for i := 0; i < len(t.PowersOfTau.G1Powers)-1; i++ {
322 // i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
323 eL := pairing.AddPair(t.PowersOfTau.G1Powers[i], t.PowersOfTau.G2Powers[1]).Result()
324 eR := pairing.AddPair(t.PowersOfTau.G1Powers[i+1], g2.One()).Result()
325 if !eL.Equal(eR) {
326 return false
327 }
328 }
329
330 for i := 0; i < len(t.PowersOfTau.G2Powers)-1; i++ {
331 // ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
332 eL := pairing.AddPair(t.PowersOfTau.G1Powers[1], t.PowersOfTau.G2Powers[i]).Result()
333 eR := pairing.AddPair(g1.One(), t.PowersOfTau.G2Powers[i+1]).Result()
334 if !eL.Equal(eR) {
335 return false
336 }
337 }
338 }
339
340 return true
341}