-
Notifications
You must be signed in to change notification settings - Fork 150
/
sumcheck.go
181 lines (153 loc) · 7.03 KB
/
sumcheck.go
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
// Copyright 2020 Consensys Software Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Code generated by consensys/gnark-crypto DO NOT EDIT
package sumcheck
import (
"fmt"
"github.com/consensys/gnark-crypto/ecc/bw6-761/fr"
"github.com/consensys/gnark-crypto/ecc/bw6-761/fr/polynomial"
fiatshamir "github.com/consensys/gnark-crypto/fiat-shamir"
"strconv"
)
// This does not make use of parallelism and represents polynomials as lists of coefficients
// It is currently geared towards arithmetic hashes. Once we have a more unified hash function interface, this can be generified.
// Claims to a multi-sumcheck statement. i.e. one of the form ∑_{0≤i<2ⁿ} fⱼ(i) = cⱼ for 1 ≤ j ≤ m.
// Later evolving into a claim of the form gⱼ = ∑_{0≤i<2ⁿ⁻ʲ} g(r₁, r₂, ..., rⱼ₋₁, Xⱼ, i...)
type Claims interface {
Combine(a fr.Element) polynomial.Polynomial // Combine into the 0ᵗʰ sumcheck subclaim. Create g := ∑_{1≤j≤m} aʲ⁻¹fⱼ for which now we seek to prove ∑_{0≤i<2ⁿ} g(i) = c := ∑_{1≤j≤m} aʲ⁻¹cⱼ. Return g₁.
Next(fr.Element) polynomial.Polynomial // Return the evaluations gⱼ(k) for 1 ≤ k < degⱼ(g). Update the claim to gⱼ₊₁ for the input value as rⱼ
VarsNum() int //number of variables
ClaimsNum() int //number of claims
ProveFinalEval(r []fr.Element) interface{} //in case it is difficult for the verifier to compute g(r₁, ..., rₙ) on its own, the prover can provide the value and a proof
}
// LazyClaims is the Claims data structure on the verifier side. It is "lazy" in that it has to compute fewer things.
type LazyClaims interface {
ClaimsNum() int // ClaimsNum = m
VarsNum() int // VarsNum = n
CombinedSum(a fr.Element) fr.Element // CombinedSum returns c = ∑_{1≤j≤m} aʲ⁻¹cⱼ
Degree(i int) int //Degree of the total claim in the i'th variable
VerifyFinalEval(r []fr.Element, combinationCoeff fr.Element, purportedValue fr.Element, proof interface{}) error
}
// Proof of a multi-sumcheck statement.
type Proof struct {
PartialSumPolys []polynomial.Polynomial `json:"partialSumPolys"`
FinalEvalProof interface{} `json:"finalEvalProof"` //in case it is difficult for the verifier to compute g(r₁, ..., rₙ) on its own, the prover can provide the value and a proof
}
func setupTranscript(claimsNum int, varsNum int, settings *fiatshamir.Settings) (challengeNames []string, err error) {
numChallenges := varsNum
if claimsNum >= 2 {
numChallenges++
}
challengeNames = make([]string, numChallenges)
if claimsNum >= 2 {
challengeNames[0] = settings.Prefix + "comb"
}
prefix := settings.Prefix + "pSP."
for i := 0; i < varsNum; i++ {
challengeNames[i+numChallenges-varsNum] = prefix + strconv.Itoa(i)
}
if settings.Transcript == nil {
transcript := fiatshamir.NewTranscript(settings.Hash, challengeNames...)
settings.Transcript = &transcript
}
for i := range settings.BaseChallenges {
if err = settings.Transcript.Bind(challengeNames[0], settings.BaseChallenges[i]); err != nil {
return
}
}
return
}
func next(transcript *fiatshamir.Transcript, bindings []fr.Element, remainingChallengeNames *[]string) (fr.Element, error) {
challengeName := (*remainingChallengeNames)[0]
for i := range bindings {
bytes := bindings[i].Bytes()
if err := transcript.Bind(challengeName, bytes[:]); err != nil {
return fr.Element{}, err
}
}
var res fr.Element
bytes, err := transcript.ComputeChallenge(challengeName)
res.SetBytes(bytes)
*remainingChallengeNames = (*remainingChallengeNames)[1:]
return res, err
}
// Prove create a non-interactive sumcheck proof
func Prove(claims Claims, transcriptSettings fiatshamir.Settings) (Proof, error) {
var proof Proof
remainingChallengeNames, err := setupTranscript(claims.ClaimsNum(), claims.VarsNum(), &transcriptSettings)
transcript := transcriptSettings.Transcript
if err != nil {
return proof, err
}
var combinationCoeff fr.Element
if claims.ClaimsNum() >= 2 {
if combinationCoeff, err = next(transcript, []fr.Element{}, &remainingChallengeNames); err != nil {
return proof, err
}
}
varsNum := claims.VarsNum()
proof.PartialSumPolys = make([]polynomial.Polynomial, varsNum)
proof.PartialSumPolys[0] = claims.Combine(combinationCoeff)
challenges := make([]fr.Element, varsNum)
for j := 0; j+1 < varsNum; j++ {
if challenges[j], err = next(transcript, proof.PartialSumPolys[j], &remainingChallengeNames); err != nil {
return proof, err
}
proof.PartialSumPolys[j+1] = claims.Next(challenges[j])
}
if challenges[varsNum-1], err = next(transcript, proof.PartialSumPolys[varsNum-1], &remainingChallengeNames); err != nil {
return proof, err
}
proof.FinalEvalProof = claims.ProveFinalEval(challenges)
return proof, nil
}
func Verify(claims LazyClaims, proof Proof, transcriptSettings fiatshamir.Settings) error {
remainingChallengeNames, err := setupTranscript(claims.ClaimsNum(), claims.VarsNum(), &transcriptSettings)
transcript := transcriptSettings.Transcript
if err != nil {
return err
}
var combinationCoeff fr.Element
if claims.ClaimsNum() >= 2 {
if combinationCoeff, err = next(transcript, []fr.Element{}, &remainingChallengeNames); err != nil {
return err
}
}
r := make([]fr.Element, claims.VarsNum())
// Just so that there is enough room for gJ to be reused
maxDegree := claims.Degree(0)
for j := 1; j < claims.VarsNum(); j++ {
if d := claims.Degree(j); d > maxDegree {
maxDegree = d
}
}
gJ := make(polynomial.Polynomial, maxDegree+1) //At the end of iteration j, gJ = ∑_{i < 2ⁿ⁻ʲ⁻¹} g(X₁, ..., Xⱼ₊₁, i...) NOTE: n is shorthand for claims.VarsNum()
gJR := claims.CombinedSum(combinationCoeff) // At the beginning of iteration j, gJR = ∑_{i < 2ⁿ⁻ʲ} g(r₁, ..., rⱼ, i...)
for j := 0; j < claims.VarsNum(); j++ {
if len(proof.PartialSumPolys[j]) != claims.Degree(j) {
return fmt.Errorf("malformed proof")
}
copy(gJ[1:], proof.PartialSumPolys[j])
gJ[0].Sub(&gJR, &proof.PartialSumPolys[j][0]) // Requirement that gⱼ(0) + gⱼ(1) = gⱼ₋₁(r)
// gJ is ready
//Prepare for the next iteration
if r[j], err = next(transcript, proof.PartialSumPolys[j], &remainingChallengeNames); err != nil {
return err
}
// This is an extremely inefficient way of interpolating. TODO: Interpolate without symbolically computing a polynomial
gJCoeffs := polynomial.InterpolateOnRange(gJ[:(claims.Degree(j) + 1)])
gJR = gJCoeffs.Eval(&r[j])
}
return claims.VerifyFinalEval(r, combinationCoeff, gJR, proof.FinalEvalProof)
}