Scalar Redundancy Elimination Boosts ZKP Efficiency

What are Zero-Knowledge Proofs and Their Applications

Zero-knowledge proofs allow one party to prove a statement is true without revealing the underlying data. In layperson’s terms, ZKP makes it possible for people to prove that something about them is true without exchanging any other data [1].

The technology is moving from research prototypes to regulatory-driven deployment. The European Union’s eIDAS Regulation set to take effect in 2026 encourages Member States to integrate privacy-enhancing technologies like ZKP into the European Digital Identity Wallet (“EUDI Wallet”) [1].

Open sourcing of cryptographic tooling is accelerating adoption. Open sourcing these powerful cryptographic tools will make it much easier for private and public sector developers to build their own privacy-enhancing applications and digital ID solutions, meeting an urgent need [1]. Developers can freely use the ZKP codebase to build privacy-focused applications [1].

In ZKP systems based on Groth16, as used with Circom, a trusted setup is something we run once as a pre-processing step. This generates what is called a Common Reference String (CRS), which consists of a proving key and a verification key [2].

The prover key embeds all the information necessary to be able to generate a proof in a zero-knowledge preserving fashion for that specific circuit. Similarly, the verifier key embeds all the information necessary to verify that the proof is indeed correct [2].

With Circom we are using the Groth16 proof system which does requires a trusted setup. Specifically, the setup is split into two phases: phase 1 and phase 2 [2].

Witness generation in practice relies on WebAssembly. The .wasm file contains WebAssembly, which is what we need to generate our witness [2].

The practical construction of interactive proofs is well understood, and the interactivity of our protocol isn’t inherent and can be removed rather easily [3]. The theorem by Goldreich, Micali, and Wigderson says that the same can be done without any trusted authority, and for any algorithm A [3].

The Current State of Multi-Scalar Multiplication

Multi-scalar multiplication, MSM, is a core operation in many zero-knowledge proof protocols. The performance of proof generation is dominated by how efficiently MSM is performed.

The current state-of-the-art algorithm for large-scale MSM is Pippenger's bucket method [4]. The current state-of-the-art algorithm for large-scale MSM is Pippenger's bucket method, which consists of three main steps: point merging, bucket aggregation, and window aggregation [4].

Among these, the point merging step is the primary performance bottleneck [4].

In the Pippenger workflow, point merging combines many elliptic curve points into a smaller set of representatives before the scalar-dependent work begins. Bucket aggregation then accumulates points per window, and window aggregation combines the windows into the final linear combination. The cost model is dominated by elliptic curve additions in the merging phase, which scales with the number of distinct points.

For engineers deploying Groth16 provers, this means that circuits with large numbers of constraints produce large MSM instances during proof generation. The proving key size and the witness size both feed directly into the input set for MSM, so any growth in circuit complexity translates into more point merging work.

Memory bandwidth also matters. Bucket aggregation requires maintaining many intermediate accumulators, and window aggregation requires repeated scalar multiplications by powers of the window size. In practice, the three stages are pipelined, but the merging stage cannot be overlapped with later stages because its output is required for the bucket structure to be correct.

Scalar Redundancy Elimination: A Game-Changer for ZKP

Scalar Redundancy Elimination, SRE, is proposed as an optimization for large-scale MSM inside ZKP pipelines. The technique targets the cost structure of Pippenger’s bucket method without changing the proof semantics.

The core idea is to identify and collapse scalar redundancies before the point merging step begins. Redundant scalars appear frequently in real circuits where the same sub-circuit is instantiated multiple times, or where range checks and lookups reuse the same field elements across different constraints. By detecting equivalence classes of scalars, the algorithm can merge their associated points earlier, reducing the effective input size to Pippenger.

The proposed MSM algorithm, enhanced with the SRE technique, incurs less than 3% additional search time, while reducing the number of operations by 25%, leading to a 30% speedup in runtime compared to the standard Pippenger's bucket method [4].

Search cost is incurred once per proof generation to build a hash map of scalar values and find duplicates. The overhead stays low because scalar values are already materialized during witness generation, and the comparison is a cheap field equality check relative to an elliptic curve addition.

From an implementation perspective, SRE is a pre-processing pass inserted between witness generation and MSM. It does not modify the circuit, the trusted setup, or the CRS. The proving key and verification key remain unchanged, preserving the zero-knowledge guarantees established by the underlying proof system.

# Illustrative pre-processing for SRE
def deduplicate_scalars(scalars, points):
  seen = {}
  merged_points = []
  merged_scalars = []
  for s, P in zip(scalars, points):
  if s in seen:
  idx = seen[s]
  merged_points[idx] = point_add(merged_points[idx], P)
  else:
  seen[s] = len(merged_points)
  merged_points.append(P)
  merged_scalars.append(s)
  return merged_scalars, merged_points

The merged representation is then fed into Pippenger. The reduction in distinct points directly reduces the number of additions in point merging, which is the primary bottleneck.

Accelerating ZKP with Scalar Redundancy Elimination

For developers building on ZKP stacks, the practical impact of faster MSM is shorter proving times and lower compute cost per proof.

The improvement can be summarized as a trade-off between a small search overhead and a large reduction in arithmetic work.

Metric	Pippenger’s bucket method	Proposed MSM with SRE
Primary bottleneck	Point merging step	Reduced via redundancy elimination
Operation count	Baseline	-25%
Runtime	Baseline	~30% speedup
Additional search cost	—	<3%

Migration considerations are limited. The technique operates on the scalar-point pairs produced after witness generation, so existing Circom workflows and WebAssembly witness generation remain compatible. No changes to circuit design are required, and the trusted setup artifacts are reused without modification.

What to watch for in production: scalar distributions vary by circuit. Circuits with high reuse, such as those implementing Merkle tree verification or repeated arithmetic constraints, tend to benefit most. Circuits with mostly unique scalars see less reduction and the <3% search overhead becomes relatively more visible. Engineers should profile scalar histograms before enabling SRE globally.

Another operational note is memory layout. The deduplication map grows with the number of distinct scalars. For very large MSM instances with tens of millions of entries, the hash map must fit in available RAM alongside the point buffers. Streaming the deduplication pass or using sorting-based deduplication can mitigate peak memory use at the cost of slightly higher latency.

The speedup compounds in systems that generate many proofs per session, such as age assurance flows or wallet credential issuance mandated by upcoming eIDAS requirements.

Impact on Cryptographic Protocols and Future Directions

Faster MSM lowers the barrier for integrating ZKPs into production services. Open sourcing ZKP libraries will make it easier for private and public sector developers to build their own privacy-enhancing applications and digital ID solutions [1].

The European Union’s eIDAS Regulation set to take effect in 2026 encourages Member States to integrate privacy-enhancing technologies like ZKP into the European Digital Identity Wallet (“EUDI Wallet”) [1].

Adoption paths are straightforward for teams already using Groth16. The SRE pass can be wrapped as a library call between witness generation and the MSM routine in the prover. Because the CRS and keys are unchanged, verification remains identical and no verifier updates are needed.

Future work will likely focus on making redundancy elimination adaptive to scalar distributions observed in real circuits, and on integrating the technique with existing open source ZKP toolchains so developers can adopt it without changing circuit design.

For now, the combination of a mature MSM baseline and a targeted optimization like SRE provides a concrete path to 30% faster proof generation while keeping the zero-knowledge guarantees intact.

References

1. Opening up ‘Zero-Knowledge Proof’ technology to promote privacy in age assurance — blog.google (1 July 2026)
2. Programming ZKPs: From Zero to Hero — zkintro.com (30 August 2024)
3. Zero-knowledge proofs — vasekrozhon.wordpress.com (18 March 2025)
4. SRE: Accelerating Zero-Knowledge Proofs via Scalar Redundancy Elimination in Multi-Scalar Multiplication — arxiv.org