Verkle IPA - Incomplete test suite - bugs in prover & verifier

[mratsim]

The test suite for Verkle Tries IPA is incomplete.

We're missing at least:

• Transcript test: https://github.com/crate-crypto/verkle-trie-ref/blob/2332ab8/ipa/ipa_test.py#L38-L50
• Multiproof: https://github.com/crate-crypto/verkle-trie-ref/blob/2332ab8/multiproof/multiproof_test.py
• CRS: https://github.com/crate-crypto/go-ipa/blob/b1e8a79/ipa/ipa_test.go#L253-L264
• Multiproof: https://github.com/crate-crypto/go-ipa/blob/b1e8a79/multiproof_test.go#L63-L132
• Multiproof: https://github.com/crate-crypto/rust-verkle/blob/442174e/ipa-multipoint/src/multiproof.rs#L435-L509

And all the test vectors implemented here: https://github.com/jsign/verkle-test-vectors

In particular test011 is supposed to to negative testing and verify that multiproofs fail for incorrect inputs: https://github.com/jsign/verkle-test-vectors/blob/735b7d6/crypto/clients/go-ipa/crypto_test.go#L320-L326

	// Walk the [0, 255] range and verify the proof fails for every evaluation point but the correct one.
	for i := 0; i < 256; i++ {
		transcript := common.NewTranscript("multiproof")
		ok, err := multiproof.CheckMultiProof(transcript, config, &proof, []*banderwagon.Element{&commitment}, []*fr.Element{&evalResult}, []uint8{uint8(i)})
		require.NoError(t, err)
		require.True(t, ok == (i == data.TestData.ForgedEvaluationResult.EvaluationPoint))
	}

but we don't do that

constantine/tests/t_ethereum_verkle_ipa_primitives.nim

Lines 702 to 710 in 9fe5e49

	for i in 0 ..< EthVerkleDomain:
	var tr {.noInit.}: sha256
	tr.newTranscriptGen(asBytes"multiproof")
	Zs[0] = i
	var ok: bool
	ok = multiproof.verifyMultiproof(tr, ipaConfig, Cs, Ys, Zs)
	if i == MultiProofEvaluationPoint:
	doAssert ok == true, "Issue with Multiproof!"

And when checking other evaluation points the test seems to always return true?

[mratsim]

And the first multiproof test is flawed, Fs is of length 256 while the rest is length 1:

constantine/tests/t_ethereum_verkle_ipa_primitives.nim

Lines 641 to 659 in 9fe5e49

	var Fs = new array[EthVerkleDomain, array[EthVerkleDomain, Fr[Banderwagon]]]
	for i in 0 ..< EthVerkleDomain:
	for j in 0 ..< EthVerkleDomain:
	Fs[i][j].setZero()
	var Zs: seq[int]
	var Ys: seq[Fr[Banderwagon]]
	Cs.add(prover_comm)
	Fs[0] = poly
	Zs.add(0)
	Ys.add(one)
	var multiproof {.noInit.}: MultiProof
	var stat_create_mult: bool
	stat_create_mult = multiproof.createMultiProof(prover_transcript, ipaConfig, Cs, Fs[], Zs)

And they should be same length:

constantine/constantine/eth_verkle_ipa/multiproof.nim

Lines 206 to 215 in 9fe5e49

	func verifyMultiproof*[MultiProof](multiProof: var MultiProof, transcript : var CryptoHash, ipaSettings: IPASettings, Cs: openArray[EC_P], Ys: openArray[Fr[Banderwagon]], Zs: openArray[int]) : bool =
	# Multiproof verifier verifies the multiproof for several polynomials in the evaluation form
	# The list of triplets (C,Y,Z) represents each polynomial commitment, evaluation
	# result, and evaluation point in the domain
	var res {.noInit.} : bool
	transcript.domain_separator(asBytes"multiproof")
	debug: doAssert Cs.len == Ys.len, "Number of commitments and the Number of output points don't match!"
	debug: doAssert Cs.len == Zs.len, "Number of commitments and the Number of input points don't match!"

[mratsim]

It seems like there is a bug in the IPA proof generation:

• Number of rounds is log₂(domain), so 8 for a domain of size 256
  

  constantine/constantine/eth_verkle_ipa/common_utils.nim

  Lines 121 to 130 in 9fe5e49

  	func computeNumRounds*(res: var uint32, vectorSize: SomeUnsignedInt)=
  	## This method takes the log2(vectorSize), a separate checker is added to prevent 0 sized vectors
  	## An additional checker is added because we also do not allow for vectors whose size is a power of 2.
  	debug: doAssert (vectorSize == uint64(0)).bool() == false, "Zero is not a valid input!"
  	let isP2 = isPowerOf2_vartime(vectorSize)
  	debug: doAssert isP2 == true, "not a power of 2, hence not a valid inputs"
  	res = uint32(log2_vartime(vectorSize))

• The code actually does only 7 rounds:
  1. it initializes the index at 0, and num_rounds to 8
     

     constantine/constantine/eth_verkle_ipa/ipa_prover.nim

     Lines 164 to 168 in 9fe5e49

     	var idx = 0
     	var num_rounds = 8
     	# 0-indexed
     	discard coverIPARounds(res, transcript, ic, a, b, ic.crs, q, idx, num_rounds)

  2. To pass to this recursive function

     constantine/constantine/eth_verkle_ipa/ipa_prover.nim

     Lines 57 to 66 in 9fe5e49

     	func coverIPARounds*(
     	res: var IPAProof,
     	transcript: var CryptoHash,
     	ic: IPASettings,
     	a: openArray[Fr[Banderwagon]],
     	b: openArray[Fr[Banderwagon]],
     	cb_c: openArray[ECP_TwEdwards_Aff[Fp[Banderwagon]]],
     	q: EC_P,
     	idx: var int,
     	rounds: int): bool =

  3. The function increment the index, but then checks if it is at 7 instead of num_rounds

     constantine/constantine/eth_verkle_ipa/ipa_prover.nim

     Lines 104 to 128 in 9fe5e49

     	idx = idx + 1
     	transcript.pointAppend(asBytes"L", C_L)
     	transcript.pointAppend(asBytes"R", C_R)
     	var x_big: matchingOrderBigInt(Banderwagon)
     	x_big.generateChallengeScalar(transcript, asBytes"x")
     	var x {.noInit.}: Fr[Banderwagon]
     	x.fromBig(x_big)
     	var xInv {.noInit.}: Fr[Banderwagon]
     	xInv.inv(x)
     	var ai, bi = newSeq[Fr[Banderwagon]](a_L.len)
     	var gi = newSeq[ECP_TwEdwards_Aff[Fp[Banderwagon]]](a_L.len)
     	ai.foldScalars(a_L, a_R, x)
     	bi.foldScalars(b_L, b_R, xInv)
     	gi.foldPoints(G_L, G_R, xInv)
     	res.A_scalar = a_L[0]
     	if idx == 7:
     	return true

     
     So we do rounds 0, 1, 2, 3, 4, 5, 6 increment to 7 and exit without doing the very last processing.

This not caught in the test suite because the test suite tests the evaluation but does not compare proofs with other implementations.

constantine/tests/t_ethereum_verkle_ipa_primitives.nim

Lines 504 to 508 in 9fe5e49

	var op_point: Fr[Banderwagon]
	op_point.computeInnerProducts(lagrange_coeffs, poly)
	doAssert op_point.toHex(littleEndian) == "0x4a353e70b03c89f161de002e8713beec0d740a5e20722fd5bd68b30540a33208", "Issue with computing commitment"

Dumping the proof shows a large amount of zeros that confirm that suspicions

Furthermore, the verifier does do 8 rounds

constantine/constantine/eth_verkle_ipa/ipa_verifier.nim

Lines 70 to 95 in 9fe5e49

	var challenges {.noInit.}: array[8,Fr[Banderwagon]]
	for i in 0 ..< 8:
	challenges[i].fromBig(challenges_big[i])
	var challengesInv {.noInit.}: array[8,Fr[Banderwagon]]
	challengesInv.batchInv_vartime(challenges)
	for i in 0 ..< challenges.len:
	var x = challenges[i]
	var L = proof.L_vector[i]
	var R = proof.R_vector[i]
	var p11 {.noInit.}: array[3, EC_P]
	p11[0] = commitment
	p11[1] = L
	p11[2] = R
	var p22 {.noInit.}: array[3, Fr[Banderwagon]]
	var one {.noInit.}: Fr[Banderwagon]
	one.setOne()
	p22[0] = one
	p22[1] = x
	p22[2] = challengesInv[i]
	commitment.pedersen_commit(p22, p11)

which means it mistakenly verifies wrong proofs, which also concords with my first comment about test011 and the need of negative testing.