eth-kzg-ceremony-alt/powersoftau.go
powersoftau.goRaw
1package kzgceremony
2
3import (
4 "fmt"
5 "math/big"
6
7 bls12381 "github.com/kilic/bls12-381"
8)
9
10// todo: unify addition & multiplicative notation in the comments
11
12const MinRandomnessLen = 64
13
14type Witness struct {
15 RunningProducts []*bls12381.PointG1
16 PotPubKeys []*bls12381.PointG2
17 BLSSignatures []*bls12381.PointG1
18}
19
20type Transcript struct {
21 NumG1Powers uint64
22 NumG2Powers uint64
23 PowersOfTau *SRS
24 Witness *Witness
25}
26
27type State struct {
28 Transcripts []Transcript
29 ParticipantIDs []string // WIP
30 ParticipantECDSASignatures []string
31}
32
33type Contribution struct {
34 NumG1Powers uint64
35 NumG2Powers uint64
36 PowersOfTau *SRS
37 PotPubKey *bls12381.PointG2
38}
39type BatchContribution struct {
40 Contributions []Contribution
41}
42
43func (cs *State) Contribute(randomness []byte) (*State, error) {
44 ns := State{}
45 ns.Transcripts = make([]Transcript, len(cs.Transcripts))
46 for i := 0; i < len(cs.Transcripts); i++ {
47 ns.Transcripts[i].NumG1Powers = cs.Transcripts[i].NumG1Powers
48 ns.Transcripts[i].NumG2Powers = cs.Transcripts[i].NumG2Powers
49
50 newSRS, proof, err := Contribute(cs.Transcripts[i].PowersOfTau, randomness)
51 if err != nil {
52 return nil, err
53 }
54 ns.Transcripts[i].PowersOfTau = newSRS
55
56 ns.Transcripts[i].Witness = &Witness{}
57 ns.Transcripts[i].Witness.RunningProducts =
58 append(cs.Transcripts[i].Witness.RunningProducts, proof.G1PTau)
59 ns.Transcripts[i].Witness.PotPubKeys =
60 append(cs.Transcripts[i].Witness.PotPubKeys, proof.G2P)
61 ns.Transcripts[i].Witness.BLSSignatures = cs.Transcripts[i].Witness.BLSSignatures
62 }
63 ns.ParticipantIDs = cs.ParticipantIDs // TODO add github id (id_token.sub)
64 ns.ParticipantECDSASignatures = cs.ParticipantECDSASignatures
65
66 return &ns, nil
67}
68
69func (pb *BatchContribution) Contribute(randomness []byte) (*BatchContribution, error) {
70 nb := BatchContribution{}
71 nb.Contributions = make([]Contribution, len(pb.Contributions))
72 for i := 0; i < len(pb.Contributions); i++ {
73 nb.Contributions[i].NumG1Powers = pb.Contributions[i].NumG1Powers
74 nb.Contributions[i].NumG2Powers = pb.Contributions[i].NumG2Powers
75
76 newSRS, proof, err := Contribute(pb.Contributions[i].PowersOfTau, randomness)
77 if err != nil {
78 return nil, err
79 }
80 nb.Contributions[i].PowersOfTau = newSRS
81
82 nb.Contributions[i].PotPubKey = proof.G2P
83 }
84
85 return &nb, nil
86}
87
88// SRS contains the powers of tau in G1 & G2, eg.
89// [τ'⁰]₁, [τ'¹]₁, [τ'²]₁, ..., [τ'ⁿ⁻¹]₁,
90// [τ'⁰]₂, [τ'¹]₂, [τ'²]₂, ..., [τ'ⁿ⁻¹]₂
91type SRS struct {
92 G1Powers []*bls12381.PointG1
93 G2Powers []*bls12381.PointG2
94}
95
96type toxicWaste struct {
97 tau *big.Int
98 TauG2 *bls12381.PointG2
99}
100
101// Proof contains g₂ᵖ and g₂^τ', used by the verifier
102type Proof struct {
103 G2P *bls12381.PointG2 // g₂ᵖ
104 G1PTau *bls12381.PointG1 // g₂^τ' = g₂^{p ⋅ τ}
105}
106
107// newEmptySRS creates an empty SRS
108func newEmptySRS(nG1, nG2 int) *SRS {
109 g1s := make([]*bls12381.PointG1, nG1)
110 g2s := make([]*bls12381.PointG2, nG2)
111 g1 := bls12381.NewG1()
112 g2 := bls12381.NewG2()
113 // one_G1 := g1.One()
114 // one_G2 := g2.One()
115 for i := 0; i < nG1; i++ {
116 g1s[i] = g1.One()
117 // g1.MulScalar(g1s[i], one_G1, big.NewInt(int64(i)))
118 }
119 for i := 0; i < nG2; i++ {
120 g2s[i] = g2.One()
121 // g2.MulScalar(g2s[i], one_G2, big.NewInt(int64(i)))
122 }
123 return &SRS{g1s, g2s}
124}
125
126func tau(randomness []byte) *toxicWaste {
127 g2 := bls12381.NewG2()
128 tau := new(big.Int).Mod(
129 new(big.Int).SetBytes(randomness),
130 g2.Q())
131 tau_Fr := bls12381.NewFr().FromBytes(tau.Bytes())
132 TauG2 := g2.New()
133 g2.MulScalar(TauG2, g2.One(), tau_Fr)
134
135 return &toxicWaste{tau, TauG2}
136}
137
138func computeContribution(t *toxicWaste, prevSRS *SRS) *SRS {
139 srs := newEmptySRS(len(prevSRS.G1Powers), len(prevSRS.G2Powers))
140 g1 := bls12381.NewG1()
141 g2 := bls12381.NewG2()
142 Q := g1.Q() // Q = |G1| == |G2|
143
144 // fmt.Println("Computing [τ'⁰]₁, [τ'¹]₁, [τ'²]₁, ..., [τ'ⁿ⁻¹]₁, for n =", len(prevSRS.G1s))
145 for i := 0; i < len(prevSRS.G1Powers); i++ {
146 tau_i := new(big.Int).Exp(t.tau, big.NewInt(int64(i)), Q)
147 tau_i_Fr := bls12381.NewFr().FromBytes(tau_i.Bytes())
148 g1.MulScalar(srs.G1Powers[i], prevSRS.G1Powers[i], tau_i_Fr)
149 }
150 // fmt.Println("Computing [τ'⁰]₂, [τ'¹]₂, [τ'²]₂, ..., [τ'ⁿ⁻¹]₂, for n =", len(prevSRS.G2s))
151 for i := 0; i < len(prevSRS.G2Powers); i++ {
152 tau_i := new(big.Int).Exp(t.tau, big.NewInt(int64(i)), Q)
153 tau_i_Fr := bls12381.NewFr().FromBytes(tau_i.Bytes())
154 g2.MulScalar(srs.G2Powers[i], prevSRS.G2Powers[i], tau_i_Fr)
155 }
156
157 return srs
158}
159
160func genProof(toxicWaste *toxicWaste, prevSRS, newSRS *SRS) *Proof {
161 g1 := bls12381.NewG1()
162 G1_p := g1.New()
163 tau_Fr := bls12381.NewFr().FromBytes(toxicWaste.tau.Bytes())
164 g1.MulScalar(G1_p, prevSRS.G1Powers[1], tau_Fr) // g_1^{tau'} = g_1^{p * tau}, where p=toxicWaste.tau
165
166 return &Proof{toxicWaste.TauG2, G1_p}
167}
168
169// Contribute takes as input the previous SRS and a random
170// byte slice, and returns the new SRS together with the Proof
171func Contribute(prevSRS *SRS, randomness []byte) (*SRS, *Proof, error) {
172 if len(randomness) < MinRandomnessLen {
173 return nil, nil, fmt.Errorf("err randomness") // WIP
174 }
175 // set tau from randomness
176 tw := tau(randomness)
177
178 newSRS := computeContribution(tw, prevSRS)
179
180 proof := genProof(tw, prevSRS, newSRS)
181
182 return newSRS, proof, nil
183}
184
185// Verify checks the correct computation of the new SRS respectively from the
186// previous SRS
187func Verify(prevSRS, newSRS *SRS, proof *Proof) bool {
188 g1 := bls12381.NewG1()
189 g2 := bls12381.NewG2()
190 pairing := bls12381.NewEngine()
191
192 // 1. check that elements of the newSRS are valid points
193 for i := 0; i < len(newSRS.G1Powers); i++ {
194 // i) non-empty
195 if newSRS.G1Powers[i] == nil {
196 return false
197 }
198 // ii) non-zero
199 if g1.IsZero(newSRS.G1Powers[i]) {
200 return false
201 }
202 // iii) in the correct prime order of subgroups
203 if !g1.IsOnCurve(newSRS.G1Powers[i]) {
204 return false
205 }
206 if !g1.InCorrectSubgroup(newSRS.G1Powers[i]) {
207 return false
208 }
209 }
210 for i := 0; i < len(newSRS.G2Powers); i++ {
211 // i) non-empty
212 if newSRS.G2Powers[i] == nil {
213 return false
214 }
215 // ii) non-zero
216 if g2.IsZero(newSRS.G2Powers[i]) {
217 return false
218 }
219 // iii) in the correct prime order of subgroups
220 if !g2.IsOnCurve(newSRS.G2Powers[i]) {
221 return false
222 }
223 if !g2.InCorrectSubgroup(newSRS.G2Powers[i]) {
224 return false
225 }
226 }
227
228 // 2. check proof.G1PTau == newSRS.G1Powers[1]
229 if !g1.Equal(proof.G1PTau, newSRS.G1Powers[1]) {
230 return false
231 }
232
233 // 3. check newSRS.G1s[1] (g₁^τ'), is correctly related to prevSRS.G1s[1] (g₁^τ)
234 // e([τ]₁, [p]₂) == e([τ']₁, [1]₂)
235 eL := pairing.AddPair(prevSRS.G1Powers[1], proof.G2P).Result()
236 eR := pairing.AddPair(newSRS.G1Powers[1], g2.One()).Result()
237 if !eL.Equal(eR) {
238 return false
239 }
240
241 // 4. check newSRS following the powers of tau structure
242 for i := 0; i < len(newSRS.G1Powers)-1; i++ {
243 // i) e([τ'ⁱ]₁, [τ']₂) == e([τ'ⁱ⁺¹]₁, [1]₂), for i ∈ [1, n−1]
244 eL := pairing.AddPair(newSRS.G1Powers[i], newSRS.G2Powers[1]).Result()
245 eR := pairing.AddPair(newSRS.G1Powers[i+1], g2.One()).Result()
246 if !eL.Equal(eR) {
247 return false
248 }
249 }
250
251 for i := 0; i < len(newSRS.G2Powers)-1; i++ {
252 // ii) e([τ']₁, [τ'ʲ]₂) == e([1]₁, [τ'ʲ⁺¹]₂), for j ∈ [1, m−1]
253 eL := pairing.AddPair(newSRS.G1Powers[1], newSRS.G2Powers[i]).Result()
254 eR := pairing.AddPair(g1.One(), newSRS.G2Powers[i+1]).Result()
255 if !eL.Equal(eR) {
256 return false
257 }
258 }
259
260 return true
261}