1package fri
  2
  3import (
  4	"math"
  5
  6	"github.com/consensys/gnark-crypto/field/goldilocks"
  7	"github.com/succinctlabs/gnark-plonky2-verifier/types"
  8	"github.com/succinctlabs/gnark-plonky2-verifier/variables"
  9)
 10
 11type PolynomialInfo struct {
 12	OracleIndex    uint64
 13	PolynomialInfo uint64
 14}
 15
 16type OracleInfo struct {
 17	NumPolys uint64
 18	Blinding bool
 19}
 20
 21type PlonkOracle struct {
 22	index    uint64
 23	blinding bool
 24}
 25
 26var CONSTANTS_SIGMAS = PlonkOracle{
 27	index:    0,
 28	blinding: false,
 29}
 30
 31var WIRES = PlonkOracle{
 32	index:    1,
 33	blinding: true,
 34}
 35
 36var ZS_PARTIAL_PRODUCTS = PlonkOracle{
 37	index:    2,
 38	blinding: true,
 39}
 40
 41var QUOTIENT = PlonkOracle{
 42	index:    3,
 43	blinding: true,
 44}
 45
 46func polynomialInfoFromRange(c *types.CommonCircuitData, oracleIdx uint64, startPolyIdx uint64, endPolyIdx uint64) []PolynomialInfo {
 47	returnArr := make([]PolynomialInfo, 0)
 48	for i := startPolyIdx; i < endPolyIdx; i++ {
 49		returnArr = append(returnArr,
 50			PolynomialInfo{
 51				OracleIndex:    oracleIdx,
 52				PolynomialInfo: i,
 53			})
 54	}
 55
 56	return returnArr
 57}
 58
 59// Range of the sigma polynomials in the `constants_sigmas_commitment`.
 60func sigmasRange(c *types.CommonCircuitData) []uint64 {
 61	returnArr := make([]uint64, 0)
 62	for i := c.NumConstants; i <= c.NumConstants+c.Config.NumRoutedWires; i++ {
 63		returnArr = append(returnArr, i)
 64	}
 65
 66	return returnArr
 67}
 68
 69func numPreprocessedPolys(c *types.CommonCircuitData) uint64 {
 70	sigmasRange := sigmasRange(c)
 71	return sigmasRange[len(sigmasRange)-1]
 72}
 73
 74func numZSPartialProductsPolys(c *types.CommonCircuitData) uint64 {
 75	return c.Config.NumChallenges * (1 + c.NumPartialProducts)
 76}
 77
 78func numQuotientPolys(c *types.CommonCircuitData) uint64 {
 79	return c.Config.NumChallenges * c.QuotientDegreeFactor
 80}
 81
 82func friPreprocessedPolys(c *types.CommonCircuitData) []PolynomialInfo {
 83	return polynomialInfoFromRange(
 84		c,
 85		CONSTANTS_SIGMAS.index,
 86		0,
 87		numPreprocessedPolys(c),
 88	)
 89}
 90
 91func friWirePolys(c *types.CommonCircuitData) []PolynomialInfo {
 92	numWirePolys := c.Config.NumWires
 93	return polynomialInfoFromRange(c, WIRES.index, 0, numWirePolys)
 94}
 95
 96func friZSPartialProductsPolys(c *types.CommonCircuitData) []PolynomialInfo {
 97	return polynomialInfoFromRange(
 98		c,
 99		ZS_PARTIAL_PRODUCTS.index,
100		0,
101		numZSPartialProductsPolys(c),
102	)
103}
104
105func friQuotientPolys(c *types.CommonCircuitData) []PolynomialInfo {
106	return polynomialInfoFromRange(
107		c,
108		QUOTIENT.index,
109		0,
110		numQuotientPolys(c),
111	)
112}
113
114func friZSPolys(c *types.CommonCircuitData) []PolynomialInfo {
115	return polynomialInfoFromRange(
116		c,
117		ZS_PARTIAL_PRODUCTS.index,
118		0,
119		c.Config.NumChallenges,
120	)
121}
122
123func friOracles(c *types.CommonCircuitData) []OracleInfo {
124	return []OracleInfo{
125		{
126			NumPolys: numPreprocessedPolys(c),
127			Blinding: CONSTANTS_SIGMAS.blinding,
128		},
129		{
130			NumPolys: c.Config.NumWires,
131			Blinding: WIRES.blinding,
132		},
133		{
134			NumPolys: numZSPartialProductsPolys(c),
135			Blinding: ZS_PARTIAL_PRODUCTS.blinding,
136		},
137		{
138			NumPolys: numQuotientPolys(c),
139			Blinding: QUOTIENT.blinding,
140		},
141	}
142}
143
144func friAllPolys(c *types.CommonCircuitData) []PolynomialInfo {
145	returnArr := make([]PolynomialInfo, 0)
146	returnArr = append(returnArr, friPreprocessedPolys(c)...)
147	returnArr = append(returnArr, friWirePolys(c)...)
148	returnArr = append(returnArr, friZSPartialProductsPolys(c)...)
149	returnArr = append(returnArr, friQuotientPolys(c)...)
150
151	return returnArr
152}
153
154// This does not add any constraints, it's just a sanity check on the friParams
155// It's a 1-1 port of assert_noncanonical_indices_ok from fri::recursive_verifier in plonky2
156func assertNoncanonicalIndicesOK(friParams types.FriParams) {
157	numAmbiguousElems := uint64(math.MaxUint64) - goldilocks.Modulus().Uint64() + 1
158	queryError := friParams.Config.Rate()
159	pAmbiguous := float64(numAmbiguousElems) / float64(goldilocks.Modulus().Uint64())
160	if pAmbiguous >= queryError*1e-5 {
161		panic("A non-negligible portion of field elements are in the range that permits non-canonical encodings. Need to do more analysis or enforce canonical encodings.")
162	}
163}
164
165// This does not add any constraints, it is just a sanity check on the shapes of the proof variable
166// and given FriParams. It's a 1-1 port of validate_fri_proof_shape from fri::validate_shape in plonky2
167func validateFriProofShape(proof *variables.FriProof, instance InstanceInfo, params *types.FriParams) {
168	const SALT_SIZE = 4
169
170	commitPhaseMerkleCaps := proof.CommitPhaseMerkleCaps
171	queryRoundProofs := proof.QueryRoundProofs
172	finalPoly := proof.FinalPoly
173
174	capHeight := params.Config.CapHeight
175	for _, cap := range commitPhaseMerkleCaps {
176		if 1<<capHeight != len(cap) {
177			panic("config cap_height does not match commit_phase_merkle_caps")
178		}
179	}
180
181	for _, queryRound := range queryRoundProofs {
182		initialTreesProof := queryRound.InitialTreesProof
183		steps := queryRound.Steps
184		if len(initialTreesProof.EvalsProofs) != len(instance.Oracles) {
185			panic("eval proofs length is not equal to instance oracles length")
186		}
187		for i, evalProof := range initialTreesProof.EvalsProofs {
188			leaf := evalProof.Elements
189			merkleProof := evalProof.MerkleProof
190			oracle := instance.Oracles[i]
191			salt_size := 0
192			if oracle.Blinding && params.Hiding {
193				salt_size = SALT_SIZE
194			}
195			if len(leaf) != (int(oracle.NumPolys) + salt_size) {
196				panic("eval proof leaf length doesn't match oracle info")
197			}
198			if len(merkleProof.Siblings)+int(capHeight) != params.LdeBits() {
199				panic("length of merkle proof + capHeight doesn't match lde_bits from params")
200			}
201		}
202		if len(steps) != len(params.ReductionArityBits) {
203			panic("length of steps != params.reduction_arity_bits")
204		}
205
206		codewordLenBits := params.LdeBits()
207		for i, step := range steps {
208			evals := step.Evals
209			merkleProof := step.MerkleProof
210			arityBits := params.ReductionArityBits[i]
211
212			arity := 1 << arityBits
213			codewordLenBits -= int(arityBits)
214
215			if len(evals) != arity {
216				panic("len evals doesn't match arity")
217			}
218
219			if len(merkleProof.Siblings)+int(capHeight) != codewordLenBits {
220				panic("len merkleProof doesn't match codewordLenBits")
221			}
222		}
223	}
224
225	if len(finalPoly.Coeffs) != params.FinalPolyLen() {
226		panic("len finalPoly doesn't match params FinalPolyLen")
227	}
228}