feat: precompute from public inputs in verification

[akakou]

Background

In Groth16, the verification process incurs a linear latency increase due to the computation of the multi-scalar multiplication (MSM). When there are many public inputs, this computation becomes a significant bottleneck in the system.

Problem

When a verifier uses the same part of the public inputs for every proof, it redundantly computes the MSM during each verification, even though the MSM result remains unchanged.

Solution

I propose precomputing the MSM value from fixed parts of the public inputs. In this scheme, the MSM is calculated once for a given set of already decided public inputs, and the result is then used in all subsequent verifications for which the inputs remain unchanged. This approach reduces the online cost of calculating the MSM: in online verification, the verifier only needs to compute the MSM from the undecided parts.

Remark

Similar functionality is implemented in arkworks via the prepare_inputs and verify_proof_with_prepared_inputs methods.

[akakou]

As far as I understand the verification code, this update simply requires splitting the verification logic into several functions. For example, we could verify with the below code based on this (but my code is a little rough).

// Copyright 2020-2025 Consensys Software Inc.
// Licensed under the Apache License, Version 2.0. See the LICENSE file for details.

// Code generated by gnark DO NOT EDIT

package bls12381

import (
	"errors"

	"github.com/consensys/gnark-crypto/ecc"
	curve "github.com/consensys/gnark-crypto/ecc/bls12-381"
	"github.com/consensys/gnark-crypto/ecc/bls12-381/fr"

	// groth16_bls12381 "github.com/consensys/gnark/backend/groth16/bls12-381"
	// fr_bls12381 "github.com/consensys/gnark-crypto/ecc/bls12-381/fr"

	groth16_bls12381 "github.com/consensys/gnark/backend/groth16/bls12-381"
)

var (
	errPairingCheckFailed         = errors.New("pairing doesn't match")
	errCorrectSubgroupCheckFailed = errors.New("points in the proof are not in the correct subgroup")
)

type PreparedVKParams struct {
	e               curve.GT
	deltaNeg        curve.G2Affine
	gammaNeg        curve.G2Affine
	preComputeIndex int
}

func isValid(proof *groth16_bls12381.Proof) bool {
	return proof.Ar.IsInSubGroup() && proof.Krs.IsInSubGroup() && proof.Bs.IsInSubGroup()
}

func PrecomputeVKParams(vk *groth16_bls12381.VerifyingKey, preComputeIndex int) (*PreparedVKParams, error) {
	var params PreparedVKParams
	var err error

	params.e, err = curve.Pair([]curve.G1Affine{vk.G1.Alpha}, []curve.G2Affine{vk.G2.Beta})
	if err != nil {
		return nil, err
	}

	params.deltaNeg.Neg(&vk.G2.Delta)
	params.gammaNeg.Neg(&vk.G2.Gamma)

	params.preComputeIndex = preComputeIndex

	return &params, nil
}

// compute e(Σx.[Kvk(t)]1, -[γ]2)
func PreparePublicInputs(vk *groth16_bls12381.VerifyingKey, publicWitness fr.Vector, params *PreparedVKParams) (*curve.G1Jac, error) {
	var kSum curve.G1Jac

	if _, err := kSum.MultiExp(vk.G1.K[1+params.preComputeIndex:], publicWitness[params.preComputeIndex:], ecc.MultiExpConfig{}); err != nil {
		return nil, err
	}

	return &kSum, nil
}

func VerifyPrepared(proof *groth16_bls12381.Proof, vk *groth16_bls12381.VerifyingKey, publicWitness fr.Vector, preparedPublicWitness *curve.G1Jac, params *PreparedVKParams) error {
	// check that the points in the proof are in the correct subgroup
	if !isValid(proof) {
		return errCorrectSubgroupCheckFailed
	}

	var doubleML curve.GT
	chDone := make(chan error, 1)

	// compute (eKrsδ, eArBs)
	go func() {
		var errML error
		doubleML, errML = curve.MillerLoop([]curve.G1Affine{proof.Krs, proof.Ar}, []curve.G2Affine{params.deltaNeg, proof.Bs})
		chDone <- errML
		close(chDone)
	}()

	prepared := curve.G1Jac{}
	prepared.Set(preparedPublicWitness)

	var kSum curve.G1Jac
	if _, err := kSum.MultiExp(vk.G1.K[1:params.preComputeIndex+1], publicWitness[:params.preComputeIndex], ecc.MultiExpConfig{}); err != nil {
		return err
	}

	prepared.AddMixed(&vk.G1.K[0])
	prepared.AddAssign(&kSum)

	for i := range proof.Commitments {
		prepared.AddMixed(&proof.Commitments[i])
	}

	var kSumAff curve.G1Affine
	kSumAff.FromJacobian(&prepared)

	right, err := curve.MillerLoop([]curve.G1Affine{kSumAff}, []curve.G2Affine{params.gammaNeg})
	if err != nil {
		return err
	}

	// wait for (eKrsδ, eArBs)
	if err := <-chDone; err != nil {
		return err
	}

	right = curve.FinalExponentiation(&right, &doubleML)
	if !params.e.Equal(&right) {
		return errPairingCheckFailed
	}

	return nil

}

[akakou]

@ivokub

Does this look correct?

And, are you interested in adding this update?
If so, I can draft the changes on this and open a pull request.

[akakou]

Just a moment, please. I found a significant mistake.

[ivokub]

In essence I understand your proposal (the MSM is provided precomputed). But I have initial intuition that this is not safe approach in general as it potentially introduces malleability in the proofs. For example lets say we have a very basic circuit

func (c *Circuit) Define(api frontend.API) error {
    res := api.Mul(c.A, c.B)
    // now use res in computation
}

In this case even if the verifier would expect the public inputs be {A: x, B: y}, then the prover could also compute the proof using {A: y, B: x} and it would pass as valid proof. I understand this is a very simplified constructed example, but should illustrate the potential problem.

This could potentially be mitigated by providing proof of knowledge of the prepared witness, but this requires additional pairing check by the verifier.

However, if the public inputs are always the same, then it would be possible to encode the known public inputs in the circuit description itself a la instead of

type Circuit struct {
    A frontend.Variable `gnark:",public"`
    B frontend.Variable `gnark",public"`
 ....
    X frontend.Variable `gnark:",secret"`
}

we can define the circuit as

type CircuitConstant struct {
    A frontend.Variable `gnark:"-"`
    B frontend.Variable `gnark:"-"`
    X frontend.Variable `gnark:",secret"`
}

Now, we would have to define A, B at circuit compile time and the values become embedded in the circuit itself, not as part of the witness.

Maybe you have an example where the public inputs of the circuits would be fixed, so maybe I can understand problem better?

[akakou]

I’ve fixed the discussion above (including the code) because of a mistake.

This capability is particularly useful when the verifier has many fixed public parameters plus a few that vary from run to run, rather than when the verifier reuses the exact same public parameters every time.

[akakou]

Now, I’ll read your message, so it may take me a moment to reply.

[akakou]

@ivokub
In my case, I prefer the pre-computation pattern to embedding patterns directly in the circuit, because compilation is slower than MSM.

To be honest, I still don’t fully understand your concern. If you’re willing, could you explain the attacks you have in mind in more detail? In particular, I’d like to confirm the following points:

1. Who pre-computes the MSM (in case that your attack occurs)? Is it the verifier?
2. Can the attacks still be carried out if the verifier pre-computes all public parameters?
3. You mean the about PublicAndCommitmentCommitted?

[ivokub]

@ivokub In my case, I prefer the pre-computation pattern to embedding patterns directly in the circuit, because compilation is slower than MSM.

To be honest, I still don’t fully understand your concern. If you’re willing, could you explain the attacks you have in mind in more detail? In particular, I’d like to confirm the following points:

1. Who pre-computes the MSM (in case that your attack occurs)? Is it the verifier?
2. Can the attacks still be carried out if the verifier pre-computes all public parameters?
3. You mean the about PublicAndCommitmentCommitted?

Sorry for the delay - I'll answer in a few days.

[ivokub]

@ivokub In my case, I prefer the pre-computation pattern to embedding patterns directly in the circuit, because compilation is slower than MSM.

But the thing is that circuit compilation is done once forever. The workflow is:

1. Circuit is developed
2. Circuit is compiled, this outputs backend-specific system of constraints (i.e. R1CS or PLONKish)
3. Constraint system is used to precompute the circuit-specific setup (proving key and verification key).

All these steps are done only once. Now, every time a prover wants to show that a statement is true for this specific circuit, it uses private and public witness together with the proving key to compute a proof. Later, the verifier can take the proof, verification key and public witness to verify the correctness of the proof. This essentially ensures that the private witness prover provided was correct.

To be honest, I still don’t fully understand your concern. If you’re willing, could you explain the attacks you have in mind in more detail? In particular, I’d like to confirm the following points:

1. Who pre-computes the MSM (in case that your attack occurs)? Is it the verifier?

Usually, it should be the verifier who does that. If the verifier does it then it ensures that the MSM is computed correctly i.e. with the points from verification key and scalars from the witness. If we provide the precomputed MSM to the verification routine, then we need to assert that it was correctly computed. Imo it can be done either:

• providing additional ZK proof for the correctness of the precomputed MSM. For verifier this incurs additional pairing check. In that case the verifier doesn't need to trust the precomputed MSM. But the problem with this approach is that the pairing check is fairly expensive computation wise and it would be cheaper to just compute the MSM itself.
• for a single verifier it only computes the MSM once and then reuses it for future verification. In essence the verifier trusts the precomputed MSM.

2. Can the attacks still be carried out if the verifier pre-computes all public parameters?

If we only have a single verifier and it trusts the precomputed MSM, then it should be sound. Essentially we are caching some fixed computation. But the moment we want to target multiple verifiers then there is potential for attack. And imo here the context really matters - we support Solidity verifiers, native verifiers etc. I'm not really sure how we could do it in Solidity, and even for native verifiers we would need to consider if it runs in a single process or is invoked every time proof needs to be verified.

3. You mean the about PublicAndCommitmentCommitted?

It is something different - we have api.Commit method in gnark which allows to efficiently compute Fiat-Shamir challenges and its implementation depends on the visibility of the inputs. For example when we call api.Commit for public inputs, then the verifer just computes hash of the public inputs itself.

---

To conclude - there is a potential for allowing to precompute part of the verifier computation and reuse when the public witness is the same. But if used too eagerly then it causes potential soundness issues (when the precomputed part isn't trusted in the view of the current verifier). And as MSM computation natively is very efficient, then I'm not sure if adding such optimization would be worth it as it creates potential security issues.

To understand if it would really be worth it, then it would be great if you could give an example what is your target verifier, how big are the public inputs what is the overhead for the MSM part etc. I.e. if the MSM computation is 50% of the verifier runtime then it could be worth it, but for a few percent probably not.

[akakou]

@ivokub

Thank you for your kind and thorough response.

In other words, am I correct in understanding that it is safe as long as the verifier performs all of the pre-computations themselves? Being able to confirm this point first would be extremely helpful for me.

I apologize that I am not yet able to share the specific use case. However, based on the above, I will move forward with our own activities. Once they are made public, I would be grateful if you could revisit this discussion with me.

[ivokub]

Indeed - in case of a single verifier which trusts that the MSM was correctly computed, then it should be safe.

[akakou]

I completely understand—thank you so much for your help; I truly appreciate it!