In VIMz circuits, which implement various supported image transformations, array hashing serves as a fundamental primitive. During transformations applied row-by-row or region-by-region (e.g., in convolution-based editions), a running hash of both the original and transformed images is computed. This enables efficient operations, such as verification of proofs, directly on image commitments rather than the full images themselves.
However, hashing the entire image represents a significant portion of the circuit's size and computational overhead. This makes array hashing a considerable piece in terms of performance. Consequently, optimizing the hashing mechanism might be beneficial to improve overall circuit efficiency and scalability.
We evaluate three different strategies for array hashing, each with unique characteristics and trade-offs:
-
Linear Folding: In this strategy, the array is folded one element at a time using a two-element hasher. The process starts by hashing the first two elements, then sequentially folding in the next element, and so on. This is the baseline approach and has been the standard method used so far.
-
Windowed Folding: Similar to linear folding, but instead of hashing pairs of elements, we process chunks of a predefined length (e.g., 8 elements). Each chunk is hashed to produce an intermediate result, which is then combined with subsequent chunks, reducing the number of hashing steps compared to the pairwise method.
-
Tree-Based Hashing (Merkle Tree): The array is compressed by hashing disjoint chunks of a predefined length, reducing its size by a fixed factor in each step. The resulting intermediate array is then recursively hashed, forming a tree structure. This approach builds an n-ary tree over the array and processes elements in logarithmic depth relative to the array size.
We work on sonobe-integration branch, commit 29b7c4: source code.
The file circuits/src/utils/hashers.circom serves as a mini-library of hashing utilities used acrossed the whole circuit codebase. Our entrypoint is:
// Compute Poseidon hash of an array of values.
template ArrayHasher(LENGTH) {
signal input array[LENGTH];
signal output hash;
hash <== _LinearFoldHasher(LENGTH)(array);
// hash <== _WindowFoldHasher(LENGTH, 8)(array);
// hash <== _MerkleHasher(LENGTH, 8)(array);
}Our experimentation consists of two stages:
- Evaluating circuit parameters: We will analyze how the choice of hashing strategy impacts the circuit's characteristics, such as the number of constraints, wires, and overall size. This will allow us to identify the most efficient strategy in terms of circuit optimization.
- Measuring proof generation performance: Once the most promising strategy is identified, we will run proof generation to evaluate its impact on performance, specifically the time and resources required.
The first stage is hardware-independent and thus was performed on a private laptop. The second one however was run on AWS EC2 c6a.8xlarge instance.
Since these changes are backend-agnostic (they should have comparable influence on both Sonobe and NovaSnark backends), we run experiments only on the NovaSnark.
The sonobe-integration branch introduces significant changes compared to the master branch, altering the circuit structure in several ways. As a result, this report focuses exclusively on the effects of hashing strategies within the current state of VIMz development. A comprehensive comparison with prior work, including the master branch, will be addressed in a separate report.
Prerequisite: run make generate-input-data to ensure you have all required inputs generated before running experiment.
For every of the three alternatives in the ArrayHasher template we run:
make report-circuit-parametersfrom the repository root. Each run will regenerate circuit_parameters.csv file. It can be nicely printed with:
python3 analysis_utils/analyze_circuits.py nova_snark
It is important to run make clean-circuits after every step, to ensure that circuits are regenerated with a new hashing strategy.
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| | File Name | Template Instances | Non-Linear Constraints | Linear Constraints | Public Inputs | Private Inputs | Public Outputs | Wires | Labels |
+====+=============+======================+==========================+======================+=================+==================+==================+=========+==========+
| 0 | blur | 88 | 345126 | 0 | 4 | 512 | 4 | 337449 | 866504 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 1 | brightness | 87 | 353280 | 1 | 3 | 256 | 3 | 337925 | 729620 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 2 | contrast | 87 | 353280 | 1 | 3 | 256 | 3 | 337925 | 729620 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 3 | crop | 97 | 708224 | 1 | 3 | 128 | 3 | 707585 | 2688977 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 4 | grayscale | 86 | 168960 | 0 | 2 | 256 | 2 | 166403 | 383887 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 5 | hash | 76 | 30720 | 0 | 1 | 128 | 1 | 30850 | 99206 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 6 | resize | 84 | 337920 | 0 | 2 | 512 | 2 | 330243 | 843282 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 7 | sharpness | 93 | 421926 | 0 | 4 | 512 | 4 | 406569 | 1050824 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| | File Name | Template Instances | Non-Linear Constraints | Linear Constraints | Public Inputs | Private Inputs | Public Outputs | Wires | Labels |
+====+=============+======================+==========================+======================+=================+==================+==================+=========+==========+
| 0 | blur | 166 | 248934 | 0 | 4 | 512 | 4 | 241257 | 601172 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 1 | brightness | 165 | 305184 | 1 | 3 | 256 | 3 | 289829 | 596954 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 2 | contrast | 165 | 305184 | 1 | 3 | 256 | 3 | 289829 | 596954 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 3 | crop | 175 | 672272 | 1 | 3 | 128 | 3 | 671633 | 2589863 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 4 | grayscale | 164 | 120864 | 0 | 2 | 256 | 2 | 118307 | 251221 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 5 | hash | 154 | 6672 | 0 | 1 | 128 | 1 | 6787 | 32873 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 6 | resize | 162 | 241968 | 0 | 2 | 512 | 2 | 234291 | 578721 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 7 | sharpness | 171 | 325734 | 0 | 4 | 512 | 4 | 310377 | 785492 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| | File Name | Template Instances | Non-Linear Constraints | Linear Constraints | Public Inputs | Private Inputs | Public Outputs | Wires | Labels |
+====+=============+======================+==========================+======================+=================+==================+==================+=========+==========+
| 0 | blur | 169 | 253110 | 0 | 4 | 512 | 4 | 245433 | 620124 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 1 | brightness | 168 | 307272 | 1 | 3 | 256 | 3 | 291917 | 606430 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 2 | contrast | 168 | 307272 | 1 | 3 | 256 | 3 | 291917 | 606430 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 3 | crop | 179 | 673718 | 1 | 3 | 128 | 3 | 673079 | 2596586 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 4 | grayscale | 167 | 122952 | 0 | 2 | 256 | 2 | 120395 | 260697 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 5 | hash | 157 | 7716 | 0 | 1 | 128 | 1 | 7846 | 37611 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 6 | resize | 166 | 245904 | 0 | 2 | 512 | 2 | 238227 | 596905 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
| 7 | sharpness | 174 | 329910 | 0 | 4 | 512 | 4 | 314553 | 804444 |
+----+-------------+----------------------+--------------------------+----------------------+-----------------+------------------+------------------+---------+----------+
We observe that the two new strategies, WindowFoldHasher and MerkleHasher, yield very comparable results, with a slight edge in performance favoring the WindowFoldHasher.
When comparing the baseline LinearFoldHasher to WindowFoldHasher, we note a trade-off: while the number of template instances approximately doubles, there is a significant reduction in key circuit parameters, including constraints, wires, and labels. This reduction indicates improved efficiency in the overall circuit design despite the increased complexity in template instantiation. Below we present comparison table
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| | File Name | Template Instances Diff | Non-Linear Constraints Diff | Linear Constraints Diff | Public Inputs Diff | Private Inputs Diff | Public Outputs Diff | Wires Diff | Labels Diff |
+====+=============+===========================+===============================+===========================+======================+=======================+=======================+==============+===============+
| 0 | blur | 78 | -96192 | 0 | 0 | 0 | 0 | -96192 | -265332 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 1 | brightness | 78 | -48096 | 0 | 0 | 0 | 0 | -48096 | -132666 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 2 | contrast | 78 | -48096 | 0 | 0 | 0 | 0 | -48096 | -132666 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 3 | crop | 78 | -35952 | 0 | 0 | 0 | 0 | -35952 | -99114 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 4 | grayscale | 78 | -48096 | 0 | 0 | 0 | 0 | -48096 | -132666 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 5 | hash | 78 | -24048 | 0 | 0 | 0 | 0 | -24063 | -66333 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 6 | resize | 78 | -95952 | 0 | 0 | 0 | 0 | -95952 | -264561 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
| 7 | sharpness | 78 | -96192 | 0 | 0 | 0 | 0 | -96192 | -265332 |
+----+-------------+---------------------------+-------------------------------+---------------------------+----------------------+-----------------------+-----------------------+--------------+---------------+
Based on this comparison, we choose WindowFoldHasher.
For both LinearFoldHasher and WindowFoldHasher we run folding pipeline, but only for the first 10 steps (demo mode) - this should already give some good notion of speed-up while making reproduction fairly easy and cheap. In the repository root we run
make run-nova-snark-benchmarks
This produces a file that reports how much time was spent on the pure folding (ignoring key generation, proof verification etc.). Between runs, you should run rm -rf runs/.
Blur: 17.5s
Brightness: 16.2s
Contrast: 16.4s
Crop: 23.6s
Grayscale: 11.0s
Hash: 6.29s
Resize: 17.3s
Sharpness: 19.4s
Blur: 14.6s
Brightness: 14.8s
Contrast: 14.9s
Crop: 21.1s
Grayscale: 9.63s
Hash: 5.69s
Resize: 14.2s
Sharpness: 16.8s
Regarding efficiency, we see that by changing hashing strategy, we can gain 8.5% - 18% efficiency boost:
- Blur: 16.57%
- Brightness: 8.64%
- Contrast: 9.15%
- Crop: 10.59%
- Grayscale: 12.45%
- Hash: 9.54%
- Resize: 17.92%
- Sharpness: 13.40%
while reducing number of wires and labels approximately by:
- Blur: 30.62%
- Brightness: 18.18%
- Contrast: 18.18%
- Crop: 3.69%
- Grayscale: 34.56%
- Hash: 66.86%
- Resize: 31.37%
- Sharpness: 25.25%
Potentially, we can gain even better performance by tuning the window size (we only tried 8), however, it doesn't make much sense until we have other parts still in the development phase.