Add partial SHA256 hash gadget

[Shigoto-dev19]

Description

• partial SHA256 hash function is an innovation by the zkEmail to "make knowledge of hash preimage verification faster everywhere!"

  So you can hash all the blocks up to the one you need outside the snark, and then only run the last few hashing blocks inside the snark. What you’re proving is not “I have a string that hashes to this value”, but rather, “I have a substring that I can combine with the partially computed hash to yield the correct final hash value.”

• partial SHA256 helps reduce binary hash function constraints along with better control of which padded preimage block to hash inside a snark.
• partial SHA256 is also the main stepping stone to implementing Arbitrary or dynamic length SHA256.

Changes

• Added a new partialHash function to the SHA256 gadget.
  • The partialHash can be used exactly the same as the SHA256.hash(data) function.
  • The partialHash function has an optional parameter that allows control of how many padded input blocks are desired to be hashed outside the circuit.
  • I used a fibonacciIndexer to set a reasonable block ratio to hash as default.
  • Having a hardcoded number of blocks is imprecise and can be impractical in some cases.
  • Setting an option for block ratio would also be impractical and misleading for the end-dev.
  • It might not be perfect, but I chose the Fibonacci sequence to have a reasonable and balanced block ratio for hashing outside the circuit.
  • Example: for a 17 block padded preimage, the last Fibonacci number up to this block limit is 13, therefore only the last 4 blocks will be hashed inside the circuit.
  • Note: There is exception handling for the Fibonacci indexer.
• Integrated partialHash into the existing SHA256 unit tests.
• Added zkProgram for partial and entire SHA2 respectively to compare the performance.
  • For a 400-byte preimage, partialHash reduces rows from 37707 to 6090 compared to hashing all blocks.
• Separated and exposed some low-level SHA256 functions including sha256Compression and prepareMessageSchedule to:
  • Refactor code
  • Enable better control over block hashing.

Notes on partialHash

• For the zkEmail implementation in o1js, it's possible to use partial SHA256 as follows:

  
  import { generateEmailVerifierInputs } from '@zk-email/helpers';
  import fs from 'fs';
  import { sha256Compression } from './partial.js';
  import { bytesToWord, wordToBytes } from './binary-utils.js';
  import { K } from './constants.js';
  import { parse512BitBlock, prepareMessageSchedule } from './preprocessing.js';
  import { Bytes, UInt32 } from 'o1js';

// Read email and generate emailVerifierInputs const emailBytes = fs.readFileSync('./src/example.eml'); const inputs = await generateEmailVerifierInputs(emailBytes, { shaPrecomputeSelector: 'thousands', });

// ---- string selector method ----

// parse the precomputedSHA to be o1js compatible let chunks: UInt32[] = []; const precomputedHash = Bytes.from( inputs.precomputedSHA!.map((x) => parseInt(x)) ).bytes; for (let i = 0; i < precomputedHash.length; i += 4) { // chunk 4 bytes into one UInt32, as expected by SHA256 // bytesToWord expects little endian, so we reverse the bytes chunks.push( UInt32.Unsafe.fromField( bytesToWord(precomputedHash.slice(i, i + 4).reverse()) ) ); }

const inputSchedule = Bytes.from(inputs.emailBody!.map((x) => parseInt(x))); const inputBlocks = Bytes.from( inputSchedule.bytes.slice(0, Number(inputs.emailBodyLength)) );

const inputBits = parse512BitBlock( inputBlocks.bytes.map((x) => x.value.toBits(8).reverse()).flat() ); const messageSchedule = prepareMessageSchedule(inputBits); let out = sha256Compression(chunks, messageSchedule, K);

let partialDigest = Bytes.from( out.map((x) => wordToBytes(x.value, 4).reverse()).flat() ); console.log('computed digest; ', partialDigest.toHex());

- As seen in the code snippet above, it's possible to use `partialSHA256` in a way that is compatible with the existing `@zk-email/helpers` package, but it requires exposing more low-level SHA256 functions and a deep understanding of SHA2 mechanics to maintain the correct order of block hashing.
  - Some low-level functions that should be exposed include `bytesToWord`, `wordToBytes`, and `parseMessageBlock`.
  - In the current implementation, `@zk-email/helpers` handles outputting `precomputedHash`, `paddedInput`, and `paddedInputLength`. These are managed with helpers for the zkEmail circuit in Circom, but the good news is that all helpers for SHA256 are exposed and can be adapted for o1js partial SHA.
  - I am not sure if it's fine to expose non-provable helpers in o1js, including what's required above.
  - Perhaps publishing a side package for such helpers for o1js, giving acknowledgment to the zkEmail organization, is a good solution!

## Notes on `Dynamic SHA` 

- Having an operation `partialHash` makes it easy to implement an `Arbitrary Length SHA256 Hash Function`.
- The only difference is: 
  - Set a max size for the preimage bytes length, e.g., 1024 bytes.
  - Slice the preimage bytes given a `stringSelector`.
  - [sha256Pad](https://github.com/zkemail/zk-email-verify/blob/main/packages/helpers/src/sha-utils.ts#L97-#L123) the remaining message blocks.
  - Generate circuit inputs as in the case for [body hashing for zkEmail](https://github.com/zkemail/zk-email-verify/blob/main/packages/helpers/src/input-generators.ts#L89-#L94).
- It would be great having helpers that handle these intricacies for better devX.

[Trivo25]

Hey @Shigoto-dev19 - I accidentally marked this PR as ready for review :D Do you need more time or can I take a look?

[Shigoto-dev19]

Hey @Shigoto-dev19 - I accidentally marked this PR as ready for review :D Do you need more time or can I take a look?

Thank you @Trivo25 - Yes, it's functional, please take a look :))

[Shigoto-dev19]

Closed upon pushing #1689