<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$2^w - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mi>w</mi> </msup> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. We conducted tests on the curve BLS12-381 with Multi-Scalar Multiplications ranging from <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$2^8$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>8</mn> </msup> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$2^{14}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>14</mn> </msup> </math></EquationSource> </InlineEquation> points. The results obtained demonstrate that we have a very significant gain (up to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$40\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>40</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation>) 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$2^{13}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>13</mn> </msup> </math></EquationSource> </InlineEquation> points, we observe a gain of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$40\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>40</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> with only 1 KB of memory, <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$20\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>20</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> with 15 KB, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$15\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>15</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> with 35 KB, and so on, down to be equivalent to Pippenger’s algorithm once memory is no longer a constraint.</p>

Computing multi-scalar multiplication on memory-constrained devices

期刊论文
发表日期：

2026年5月11日

查看全文

Léo Noël,
Thomas Plantard

摘要

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$ $2^{w} - 1$ . We conducted tests on the curve BLS12-381 with Multi-Scalar Multiplications ranging from $2^8$ $2^{8}$ to $2^{14}$ $2^{14}$ points. The results obtained demonstrate that we have a very significant gain (up to $40\%$ $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}$ $2^{13}$ points, we observe a gain of $40\%$ $40 %$ with only 1 KB of memory, $20\%$ $20 %$ with 15 KB, $15\%$ $15 %$ with 35 KB, and so on, down to be equivalent to Pippenger’s algorithm once memory is no longer a constraint.