4 minute read

Hash algorithms have multitude of uses like data integrity, authentication, and commitment schemes. The ZoKrates standard library supports multiple algorithms:

This post briefly introduces those algorithms and showcases benchmarks for their use in ZoKrates programs, measuring compilation, setup, and proof generation times and memory consumption, as well and number of constraints for a simple program proving knowledge of a hash preimage.

SHA-256 (Secure Hash Algorithm 256-bit)

SHA-256 is part of the SHA-2 (Secure Hash Algorithm 2) family of cryptographic hash functions, developed by the NSA and published by the National Institute of Standards and Technology (NIST) in 2001. On the one hand, it is one of the most popular and widely supported hashing algorithms, on the hand, it incurs an overhead when translated to arithmetic circuits. Circuits heavily using this may have relatively long proving times and high memory requirements.

ZoKrates Program

The program that proves knolwedge of SHA-256 preimage looks as follows:

import "hashes/sha256/sha256" as sha256;

def main(private u32[16] preimage, u32[8] image) {
    u32[8] hash = sha256([preimage]);
    assert(hash == image);
}

Benchmarks

Results

  • SHA-256 is slower compared to more recent hashing algorithms like BLAKE2s or ZK-optimized ones like Pedersen.
  • The relatively high resource usage makes it less suitable for resource-constrained devices or systems.

SHA-3 (Secure Hash Algorithm 3)

SHA-3 was developed by the Keccak team and won the NIST hash function competition in 2012, then standardized as SHA-3 in 2015. It offers better parallelization than like SHA-2 and remains secure with no practical attacks against it.

SHA-3 was developed before the zero-knowledge breakthroughs of the last decade. Its arithmetization incurs 3x the number of constraints than SHA-256, making it the most expensive hash algorithm to compute in ZoKrates.

ZoKrates Program

import "hashes/sha3/256bit" as sha3;

def main(private u8[64] preimage, u8[32] image) {
    u8[32] hash = sha3(preimage);
    assert(hash == image);
}

Benchmarks

Results

Advantages:

  • Based on the Keccak algorithm, which won the NIST hash function competition, making it a standardized and well-reviewed algorithm.
  • Improved security over SHA-2 due to its different design and resistance to known attacks.

Disadvantages:

  • Slower than both SHA-256 and BLAKE2s.
  • Very inefficient in zero-knowledge proofs.
  • Relatively new and less widely adopted, leading to less extensive real-world testing.

BLAKE2s (BLAKE2 Secure Hash Algorithm)

BLAKE2 is an improved version of the BLAKE hash function –one of the finalists in the NIST hash function competition that resulted in SHA-3. It maintains high security and improves upon the performance and parallelism of the original BLAKE hash function.

Arithmetization of BLAKE2 results in circuits that are half of the size of SHA-256, which makes it popular in the Blockchain space.

ZoKrates Program

import "hashes/blake2/blake2s";

def main(private u32[1][16] preimage, u32[8] image) {
    u32[8] hash = blake2s(preimage);
    assert(hash == image);
}

Benchmarks

Results

Advantages:

  • Designed for high performance, making it faster than both SHA-256 and SHA-3 in many use cases.
  • More efficient than the SHA family for arithmetic circuits.
  • Low memory usage, making it suitable for resource-constrained devices or systems.

Disadvantages:

  • Not as widely adopted or standardized as SHA-256 or SHA-3.
  • Although it is based on well-reviewed cryptographic principles, it has not undergone the same level of extensive real-world testing as SHA-2 or SHA-3.

Pedersen

The Pedersen hash function is inspired by Pedersen commitments and is optimized for use within arithmetic circuits of zero knowledge proofs.

ZoKrates Program

import "hashes/pedersen/512bit" as pedersen;

def main(private u32[16] preimage, u32[8] image) {
    u32[8] hash = pedersen(preimage);
    assert(hash == image);
}

Benchmarks

MiMC7

MiMC is a ZK-friendly hash algorithm with the goal of minimizing the circuit size.

ZoKrates Program

import "hashes/mimc7/mimc7";

def main(private field preimage, field k, field image) {
    field hash = mimc7::<10>(preimage, k);
    assert(image == hash);
}

Benchmarks

Poseidon Hash

Poseidon is a cryptographic hash function designed with the specific purpose of enhancing efficiency in zero-knowledge proofs. The Cryptography Group at the Institute of Science and Technology Austria introduced Poseidon in 2019, and it has rapidly gained traction in the zk-SNARK community due to its zk-friendly properties. As illustrated in the graph above, calculating a Poseidon hash is approximately 20 times faster in zk-SNARK circuits than a SHA-256. However, due to its relative novelty, the security of its construct has not yet been subjected to the same level of scrutiny as that of other hashes on this page.

ZoKrates Program

import "hashes/poseidon/poseidon" as poseidon;

def main(private field preimage, field image) {
    field hash = poseidon([preimage]);
    assert(hash == image);
}

Benchmarks

Results

Advantages:

  • Designed specifically for use in zero-knowledge proofs, resulting in significantly fewer constraints in zk-SNARK circuits.
  • Highly efficient and fast compared to traditional hash functions when used in zk-SNARKs.
  • Strong security guarantees tailored for zk-SNARK environments.

Disadvantages:

  • Less widely adopted outside of the zk-SNARK community.
  • Newer and therefore lacks the extensive real-world testing and scrutiny of more established hash functions like SHA-2 and SHA-3.

Summary

Execution time and memory consumption are directly proportional to the number constraints a program compiles to. The choice of hashing algorithm can significantly influence the number of constraints, and consequently, the performance of a zk-SNARK system. Therefore, this choice must be guided by the specific requirements of the system, including security, efficiency, and simplicity of implementation.

SHA-256 and SHA-3 are secure and widely-used options, however incur high overheads in zk-SNARK circuits. Poseidon, although newer, shows exceptional promise for zk-SNARKs due to its specialized design and efficiency in zero-knowledge environments. BLAKE2s provides a good trade-off, with similar security to the SHA family, but significantly cheaper to calculate in zk-SNARKs.

Leave a comment