Paper 2026/1316

Computing multi-scalar multiplication on memory-constrained devices

Abstract

Multi-Scalar Multiplication is a critical operation in most pairing-based zero knowledge proofs. In a lot of studies, memory limitations have often been reported to be the primary bottleneck preventing the calculation of larger MSMs. In this paper, we are particularly interested in the acceleration of this operation on devices with limited memory. Pippenger’s algorithm (also known as bucket method) is the most efficient and, consequently, the most widely used method to calculate Multi-Scalar Multiplications. We propose an optimization of Pippenger’s algorithm which is at least as efficient as the original, and significantly more effective when operating under limited memory. The main idea is to use an adapted number of buckets depending on the available memory instead of $2^w −1$. We conducted tests on the curve BLS12-381 with Multi-Scalar Multiplications ranging from $2^8$ to $2^{14}$ points. The results obtained demonstrate that we have a very significant gain (up to $40\%$) for very limited memories. This gain gradually decreases as more memory becomes available, until we achieve performance comparable to Pippenger’s once memory is no longer limited. For example, in a Multi-Scalar Multiplication with $2^{13}$ points, we observe a gain of $40\%$ with only $1$ KB of memory, $20\%$ with $15$ KB, $15\%$ with $35$ KB, and so on, down to $1.5\%$ once memory is no longer a constraint.