Back to search

University of Waterloo

On the Performance of Pippenger's algorithm for Multi-Scalar Multiplication

Abstract

dc:description.abstract

Multi-scalar multiplication (MSM) is core to many zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) systems and remains a primary performance bottleneck in proof generation and verification. In practice, zk-SNARK implementations typically rely on Pippenger’s bucket method as the standard algorithm for MSM. This thesis targets high-throughput MSM, computing many scalar–point multiplications and summing them for a large number of scalars, up to 221 on a specific curve, with the primary goal of reducing the number of group operations. Our work consists of three main parts. First, we review background and classical MSM algorithms, with more focus on standard Pippenger's method, Pippenger's with Booth encoded digits and the Bos–Coster approach. Second, we apply a family of small-factor scalar recoding techniques that extract small factors to shorten the effective scalar bitlength, and we compare the number of point operations for the afore-mentioned methods. Third, we introduce a strategy to reduce the number of point operations in Pippenger's algorithm. It is based on clustering of scalar window digits across multiple rows. Firstly, we describe the simplest case of window digit clustering in individual columns and then its generalization to window digit clustering in multiple columns. We implement these ideas in Rust, study sensitivity to window size, and evaluate combinations of recoding and reuse. Across our benchmarks, multiple columns window digit clustering reduces total point operations by \(2.59\%\)–\(18.09\%\) relative to Booth encoded Pippenger's method, while individual column clustering yields improvements up to $8 \%$ for small number of scalars. Overall, structured reuse together with modest window tuning provides consistent operation savings, indicating a practical path to faster MSMs at scale.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Oleksandr, Hrabar

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/22953

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Oleksandr, Hrabar. On the Performance of Pippenger's algorithm for Multi-Scalar Multiplication. University of Waterloo, 2026. https://hdl.handle.net/10012/22953