SHA256 O1JS

Description

This repo is a proof of concept for developing the SHA256 hashing algorithm using the o1js SDK during ZK-HACK Istanbul.

The o1js sdk offers powerful native binary functions that can help build an efficient SHA2 circuit for zk-apps in the Mina blockchain.

Optimizations

• SHA2 circuits are generally quite inefficient considering that binaries(0 or 1) take the space of a whole field element.

• Doing multiple binary operations on multiple binaries represented as field elements, the SHA2 algorithm becomes a constraint-heavy circuit.

• Regarding that SHA256 construction(Merkle–Damgård) operates on 32-bit words, o1js SDK aims to optimize the circuit implementation by operating on the 32-bit words(32 field elements) as a single field element.

---

• In its final stages of development, this repository took the initiative to construct a partial or updatable SHA256 hash function, enabling the continuation of hashing given previous blocks.
  • This shift moves the hashing of SHA256 blocks out of the circuit, accelerating the verification of hash preimage knowledge.
  • The updatable feature greatly aids in hashing data streams and proving knowledge of a chunk of a preimage.

How does SHA-256 work?

• SHA-2 algorithms can be described in two stages: preprocessing and hash computation.

• Preprocessing involves:

  1. padding a message.
  2. parsing the padded message into m-bit blocks.
  3. setting initialization values to be used in the hash computation.

• The hash computation generates a message schedule from the padded message and uses that schedule, along with functions, constants, and word operations to iteratively generate a series of hash values. The final hash value generated by the hash computation is used to determine the message digest.

• For a detailed explanation, I highly recommend you to walk through this Notion Page that I prepared.

How to build

npm run build

How to run tests

npm run test
npm run testw # watch mode

How to run coverage

npm run coverage

How to run SHA256 constraints summary

This script will print the number of rows for one message chunk along with the execution time of compile, prove, and verify.

npm run summary

How to hash & print

The preimage is set to default as an empty string. This script will display the digest of the preimage using different SHA256 implementations, along with their respective execution times.

It is useful for checking the integrity of custom SHA256 implementations and gaining insights into performance differences.

npm run digest <preimage>

How to benchmark

The number of iterations is set to the default value of 2500. This script will benchmark and compare the performance of the released SHA256 by o1js, the personal implementation of SHA256 using the o1js API in this repository, the circom implementation simulated in o1js, and other JS SHA256 implementations such as node and noble.

npm run benchmark <iterations>

For a preview, please refer to benchmarks.md.

Acknowledement

• Big thanks to paulmillr for the amazing benchmarking package micro-bmark.

• This repository utilizes a forked version called micro-bmark-ts, which includes type definitions and upgrades the package to be compatible with all TypeScript projects, including o1js.

License

Apache-2.0