sha2-on-cq

SHA256 PLONKish circuit implementation based on:

• Ariel's notes on the general design harnessing CQ protocol
• spreadsheet with table design

Visualisation

Current PLONKish table for an empty input to be hashed can be found in table.md.

Assumptions

1. We are implementing a SNARK (not necessarily ZK-) for the SHA256 hashing algorithm, where the input message is at most 512 bits long (i.e. single message chunk).
2. We are using CQ lookup protocol with tables of size up to 13·2³².
3. The whole protocol is a pairing based, non-interactive protocol with a trusted setup based on KZG.
4. Protocol implementation (in particular everything connected with PCS) is done with arkworks libraries.

Arithmetization and 'plonkization' approach

(Based on V2 sheet from the link above)

1. There are no copy constraints: all gates use fixed offsets.
2. We have a single column for public input (instance) containing the SHA256 hash of the secret input.
3. We have a single column for fixed values (constants). It contains round constants (k₀, k₁, ..., k₆₃) and initial hash words (h₀, h₁, ..., h₇). Values are spread out to enable convenient access from gates that are working with them.
4. We have 6 different gates and thus 6 corresponding selector columns. Ultimately they will be squashed into one, similarly to the halo2 optimization.
5. Advice area (private input and intermediate values):
   • Uses 9 columns.
   • The main part consists of 64 repetitions of 4 rows that represent single SHA256 round.
   • There are 3 mocked rounds in the beginning (initialization buffer) enabling uniform gates.
   • First 16 message schedule values (w₀, w₁, ..., w₁₅ - the input chunk of 512 bits) are the actual secret input to the circuit.
   • Further schedule values (w₁₆, w₁₇, ..., w₆₃) are computed on demand (during the rounds they are needed).
   • Instead of explicit representing all the current hash words (a, b, ..., h) we are working only with a and e, and when we need the other words, we are reusing a and e from previous rounds (rows above).

Running code

Currently, the Rust package contains two crates:

• library representing witness generation (i.e. PLONKish table creation, together with gates validation),
• binary (can be run with cargo run) instantiating the table for the empty input and rendering the result to the markdown file

Tools

• https://sha256algorithm.com/