When analyzing performance in cryptography, we often describe algorithms in terms of asymptotic complexity. However, these analyses typically treat certain parameters—such as the underlying field size—as fixed.
In systems like SNARKs, those parameters often depend on the security level and not fixed. As a result, the true cost of a construction depends on how multiple parameters interact. Operations that are sublinear under one model can exhibit different scaling behavior once security parameters are taken into account.
In solutions like Parasol, proving cost is not just an academic concern: it sits directly in the path between order flow and the throughput Solana already gives us at the base layer. Polynomial commitments and elliptic curve upscalar multiplications are common operations, so even small per-operation differences compound into a hard cap on tradable volume.
In this article, we look at one such case: multi-scalar multiplication (MSM) using Pippenger’s algorithm. While MSM is sublinear in isolation, the cost of polynomial commitments built on top of it depends on the security parameter and can exhibit superlinear behavior in theory. Understanding where this distinction comes from and how it behaves in practice is key to designing systems that are both theoretically sound and efficient in real-world applications.
The Setup
Computing a multi-scalar-multiplication (MSM) with Pippenger's bucket method (see Section 4 of https://eprint.iacr.org/2022/1400.pdf for a nice exposition) is sublinear in the MSM size N, but committing to polynomials with Pippenger in the context of SNARKs is super-linear in $N$. Although this is a well-known fact, it is somewhat strange if you hear it for the first time and the difference is delicate. So we would like to discuss the subtleties.
Over a fixed field $\mathbb F$, even the trivial method based on the standard double-and-add scalar multiplication can compute MSMs in linear time because computing$a_1g_1+a_2g_2+\dots+a_N g_N,$where $a_i\in\mathbb F$ and $g_i$ are curve points, requires only $N$ scalar multiplications and $N-1$ additions, and each scalar multiplication takes approximately at most $\log_2|\mathbb F|$ additions.
Pippenger's algorithm speeds this up by a factor of $\log N.$ In fact, it computes an MSM of size $N$ in $\Theta(N/\log N)$ time. This is certainly sublinear in $N.$ Then, why is committing to a polynomial superlinear?
In the context of SNARKs, the field $\mathbb F$, and hence its size, depends on the security parameter $\lambda.$ The larger the field gets, the more every operation costs. For example, the cost of a double-and-add scalar multiplication scales by $\log_2|\mathbb F|.$ Similarly, it turns out that committing with Pippenger costs $\Theta(\lambda N/\log \lambda N).$
Now, the point is that the security parameter is super-logarithmic in $N.$ (In other words, $N,$ which is a size bound chosen in a SNARK setup phase upon input $\lambda$ must be chosen as such.) If $\lambda =O(\log N),$ then carrying out a brute force attack, for example, to find a KZG's SRS trapdoor $2^\lambda$ times only takes $O(N),$ meaning a polynomial adversary can break the system. Therefore, $\lambda$ must be super-logarithmic.
To see that the commitment cost is not linear in $N$, we need to show that if $\lambda$ is super-logarithmic in $N,$ then $\lambda N/\log \lambda N$ is super-linear. It suffices to show that, for a strictly increasing function $\lambda(N),$ if $\lambda(N) N/\log \lambda(N) N=O(N),$ then $\lambda(N)=O(N).$
Indeed, if $\lambda(N) N/\log \lambda(N) N=O(N),$ there is a constant $B>0$ such that$\lambda(N)\leq B\log(\lambda(N)N)=B\log\lambda(N)+B\log N$for all sufficiently large $N.$ Since $\lambda(N)$ is positive, we have$1\leq B\frac{\log\lambda(N)}{\lambda(N)}+B\frac{\log N}{\lambda(N)}$for all large $N.$ Since $B\frac{\log\lambda(N)}{\lambda(N)}\leq \frac{1}{2}$ for all sufficiently large $N,$ we have$\lambda(N)\leq 2B\log N$for all sufficiently large $N,$ i.e. $\lambda(N)=O(N).$This concludes the super-linearity of $\lambda N/\log \lambda N.$
What This Looks Like In Practice
The above discussion is about theoretical asymptotics. What does this mean in the real world systems? In the real world, we fix parameters. Today's SNARKs are set to $\lambda = c\log N,$ where $c$ is somewhere between $4$ and $6.$ $c\approx 4$ (resp., $\approx 6$) if $\lambda = 128$ and $N=2^{30}$ (resp., $2^{20}$). Therefore, at least when $N$ is in the range $[2^{20}, 2^{30}],$ one may say that $\lambda$ is logarithmic in $N$ in practice.
Now, the cost of Pippenger's algorithm is proportional to $\frac{\lambda N}{\log{\lambda N}}.$ (This holds not only asymptotically for a large $N$ but also for all $N$ because this cost is estimated by counting the number of required elliptic curve additions.) If we heuristically consider $\lambda = c\log N$ (which is somewhat justifiable when $2^{20}\leq N\leq 2^{30}$), we have$\frac{\lambda N}{\log{\lambda N}} = \frac{cN\log N}{\log c+\log N + \log\log N}< cN.$This suggests that committing with Pippenger may well behave linearly in practice. While asymptotics is indispensable in theoretical analysis, this highlights the importance of concrete numbers in evaluating real world systems.
Final Thoughts
Asymptotic complexity does not tell the full story.
While Pippenger’s algorithm is sublinear in isolation, the cost of polynomial commitments in SNARKs depends on additional parameters, most notably the security parameter. This can lead to a counterintuitive result: a construction built on a sublinear primitive can exhibit superlinear behavior.
In practice, however, parameter choices matter. For realistic ranges, the security parameter grows slowly enough that the overall cost behaves much closer to linear.
The key point: performance cannot be inferred from asymptotics alone. The interaction between components and concrete parameter choices is what determines real-world cost - and that's where the design wins or loses.
For Parasol, this is more than a curiosity: every microsecond saved per commitment is matching-engine headroom on Solana. Picking a primitive that is asymptotically optimal but worse in the parameter range we actually live in would be a regression at the only scale that matters, the one users trade at.
In a follow-up piece, we’ll look at a different example where asymptotics do lead to a clear improvement: polynomial multiplication via the Fast Fourier Transform (FFT), and how that gain comes from changing the representation of the problem.
