zkalc helps you calculate how much time cryptographic operations take on a real computer.
zkalc was created to instantly answer questions like "How quickly can I run an MSM of size 218218 and compute 120120 pairings on an AWS C5 machine?" or "Which curve can perform DH in less than 1010 microseconds?".
Tune in and play with it!
Why?
Cryptographers tend to be good at cryptography but they can be quite bad at estimating the time it takes a computer to run their schemes.
We hope that zkalc can help shorten the gap between cryptography and practice:
- Cryptographers can use the simple UX to learn how fast their new fancy scheme runs on various machines without wasting computer cycles and CO2;
- Protocol designers can easily tune the parameters of their protocol depending on their requirements
We designed zkalc to be easy to use but also easy to extend. Writing new types of benchmarks, or adding fresh data to the zkalc website is easy.
How does zkalc work?
Let's now go over our benchmarking pipeline and how we derive our results. In short:
- For each supported operation, we run benchmarks that measure its performance. We use criterion.rs to take multiple sample (at least 10, ever for large computations like MSMs), and then select the average.
- We collect benchmark results inside the perf/data/ directory and make them freely available for anyone to use.
- For each operation, we fit a function to its benchmark results. We use linear interpolation inside the benchmark bounds and least squares regression outside the benchmarking bounds.
- When a user queries zkalc for an operation of size n, we estimate the its running time using the produced function.
In this blog post we will go deeper into the above process. We will mainly focus on the function fitting, but if you are interested in the entire story of how our benchmarks work, or if you want to see the interactive version of the graphs below, please visit the zkalc methodology page.
Running benchmarks
For every supported operation, we write benchmarks and run them in multiple platforms. We then store the results in the perf/ directory of zkalc.
Answering user queries
Now we have benchmark data for every operation in the perf/ directory. The next step is to fit a function to every operation, so that when a user queries us for an operation with arbitrary size , we can answer it by evaluating .
For simple operations like basic scalar multiplication and field addition (which are not amortized) we consider them to be sequential computations. That is, if a single scalar multiplication takes seconds, such operations will take seconds. That results in a simple linear function
More complicated operations like MSMs and pairing products are amortized and their performance doesn't follow a simple linear curve.
For such operations, we collect benchmark data for various sizes. For example, consider the figure below which displays the benchmark data from a MSM operation for sizes from to (both axis are in log scale):
To answer user queries within the benchmark range, we perform polynomial interpolation over the benchmark data.
That is, for each pair of benchmark data and we trace the line that goes through both points. We end up with a piecewise function that covers the entire benchmark range, as we can see in the figure below:
For user queries outside of the benchmarking range we extrapolate via non-linear least squares. To make things more exciting we decided that it should be done... in Javascript inside your browser.
In the specific case of MSMs, Pippenger's complexity is well known to be asymptotically . Hence, we use least squares to fit the data set to a function solving for
Here is an illustration of the extrapolation behavior of MSM outside of the benchmarking range (that is, after ):
We do not expect extrapolation to faithfully follow the benchmarks. We believe however that the estimates provide a rough idea of how long an algorithm will take.
In the end of this process, we end up with a piecewise function for each operation that we can query inside and outside the benchmarking range to answer user queries.
Do give zkalc a try and let us know what you think!
Visualizing crypto performance with zkalc
In the zkalc website, you will also find the zcharts corner where we visualize all the raw benchmark data we used in the above section.
We hope that this visual approach will help you grok the benchmark data that zkalc is based on, but also acquire a better understanding of the performance variations between different implementations/curves.
A call for help
zkalc can be only as useful as the data it provides,and there is lots of room for additional benchmarks. Can you run benchmarks on a large cloud provider? We would love to get in touch and gather benchmarks for zkalc. Do you have access to a beefy GPU prover? We would love to help you run zkalc. Did you just design a new elliptic curve? Benchmark it with zkalc. Are you working on a new crypto library? You guessed it. Adding benchmarks to zkalc is actually not hard; check our website for instructions!
In the future, we also want to expand zkalc to support higher level primitives. From FFTs, to IPAs, to various polynomial commitment and lookup argument schemes. If you want to write benchmarks for any of these, check out our TODO file and please get in touch! :)
Acknowledgements
Many thanks to Patrick Armino and Jonathan Xu for their help with the UX.
zkalc帮助你计算在实际计算机上进行密码学运算所花费的时间。
创建 zkalc 是为了快速响应诸如 “在AWS C5 机器上能以多快的速度计算规模为 的 MSM，以及120次配对 ” 或 “ 哪条曲线可以在10微秒内执行DH变换” 之类的问题。
快来使用它！
为什么？
密码学家往往擅长密码学，但他们在估计计算机运行方案的时长方面可能相当糟糕。
我们希望 zkalc 可以帮助缩小密码学与实践之间的差距：
- 密码学家可以使用简单的用户页面来了解他们的新方案在各种机器上的运行速度，而不会浪费计算时常和能源消耗；
- 协议设计者可以根据自己的需求轻松调整协议的参数
我们将 zkalc 设计为既易于使用又易于扩展。编写新的基准测试类型或向 zkalc 网站添加新数据十分容易。
zkalc是如何工作的？
现在让我们回顾一下我们的基准测试流程以及我们如何得到结果。简而言之：
- 对每个支持的运算，我们运行衡量其性能的基准。我们使用 criterion.rs 获取多个样本数据（对于像 MSM 这样的大型计算至少取 10 个），然后选择平均值。
- 我们在
perf/data/目录中收集基准测试结果，并免费提供给任何人使用。
- 对于每个运算，我们都通过一个函数与其基准结果进行拟合。我们在基准边界内使用线性插值，在基准边界外使用最小二乘回归。
- 当用户向 zkalc 查询规模为 的运算，我们使用生成的函数估计它的运行时间。
在这篇博客中，我们将深入探讨上述过程。我们将主要关注函数拟合，如果你对我们的基准如何工作的整个流程感兴趣，或者如果你想查看如下图表的交互式版本，请访问 zkalc 的方法论页面。
运行基准测试
对于每个支持的运算，我们编写基准测试并在多个平台上运行它们。然后我们将结果存储在zkalc 的
perf/目录中。回复用户查询
现在我们在
perf/目录中有每个运算的基准数据。下一步是对每个运算拟合一个函数 ，以便当用户向我们查询任意规模 的运算，我们可以通过 求值来回答。对于像基本的标量乘法和域加法（没有摊销时）这样的简单运算，我们认为它们是顺序计算的。也就是说，如果单个标量乘法需要 秒， 个这样的运算将需要 秒。这推导出一个简单的线性函数
更复杂的运算（如 MSM 和配对）会被摊销，因此它们的性能不遵循简单的线性曲线。
为了在基准范围内回复用户查询，我们对基准数据进行多项式插值。
对于基准测试范围之外的用户查询，我们通过非线性最小二乘法进行推断。为了更进一步，我们决定浏览器中使用Javascript来实现它。
如下是超出基准测试范围进行推断的例子， 的规模大于 的 MSM 运算
我们不期望推断能够严格地遵循基准。然而，我们相信这些估计提供了一个大致的时间概念，即计算这些算法需要多长时间。
最后，我们最终得到了每个运算的分段函数，我们可以在基准范围内外回复用户的查询。
一定要试试 zkalc，让我们知道你的想法！
密码学计算性能的可视化
在 zkalc 网站上，你还可以找到zcharts，我们在其中可视化了我们在上一章节所使用的所有原始基准数据。
我们希望可视化能帮助你理解 zkalc 的基准数据，同时也能更好地理解不同实现/曲线之间的性能差异。
欢迎加入
zkalc 的意义在于其所提供的数据，并且还有许多其他基准测试的空间。如果你可以在大型云提供商上运行基准测试吗，我们很乐意合作并收集 zkalc 的基准。如果你有功能强大的 GPU 证明者的资源，我们很乐意帮助你运行 zkalc。如果你刚刚设计了一条新的椭圆曲线吗，欢迎使用 zkalc对其进行基准测试。如果你正在开发一个新的加密库吗，正如你所想的，向 zkalc 添加基准测试实际上很容易，查看我们的网站说明！
致谢
非常感谢Patrick Armino和Jonathan Xu在 UX 方面的帮助。