issue when implementing sha256

[zhfnjust]

i am implementing sha256:

now I have a version that validates normally

sCrypt-Inc/snarkyjs-sha256@bd52bdd

But if we make a simple modification and comment out lines 254~257, that is, run one more line of code 259, the whole circuit will crash.

see this commit :

sCrypt-Inc/snarkyjs-sha256@fcaefcc

[mitschabaude]

Amazing that you got this far! Will check it out on monday

[zhfnjust]

this is the error message:

[mitschabaude]

By the way, you get more useful error traces with
node --stack-trace-limit=1000

[zhfnjust]

I think this may be because I implemented the not operation on Uint32, and the inversion of 1 becomes -2. Because sha256 needs to use xor and not. Please help to see if there is a problem with the implementation of these two functions, and if there is a better way to implement it

[zhfnjust]

all strace:

RuntimeError: unreachable
    at wasm://wasm/00b11606:wasm-function[782]:0x1fe03b
    at wasm://wasm/00b11606:wasm-function[2036]:0x2a53dd
    at wasm://wasm/00b11606:wasm-function[104]:0xaa5a1
    at wasm://wasm/00b11606:wasm-function[448]:0x16cce0
    at Object.module.exports.caml_pasta_fp_plonk_index_create (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/plonk_wasm.js:1856:14)
    at caml_pasta_fp_plonk_index_create (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:3:12353)
    at _f32_ (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2215:3669980)
    at caml_call3 (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:4:693)
    at R (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2215:3466003)
    at caml_call1 (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:4:543)
    at generate$0 (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2215:3894164)
    at /Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2215:5060508
    at caml_call_gen (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2:39192)
    at Function.<anonymous> (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/node_bindings/snarky_js_node.bc.js:2:73570)
    at Function.a.type.l.<computed> [as generateKeypair] (/Users/hh/code/zk/snarky-ex/node_modules/snarkyjs/dist/server/index.js:1:6157)
    at main (file:///Users/hh/code/zk/snarky-ex/build/src/sha256.js:210:23)

[zhfnjust]

A version with simpler code implementation has just been submitted, which removes the for loop. but still has pb

[zhfnjust]

Another possibility is that my circuit is triggering some limitation of the system

[zhfnjust]

any update?

[zhfnjust]

a minimal reproducible example : sCrypt-Inc/snarkyjs-sha256@33f89d1

it just crashed when calling generateKeypair(), has nothing to do with proving.

If you comment the following line of code, generateKeypair() will run successfully

https://github.com/sCrypt-Inc/snarkyjs-sha256/blob/master/src/sha256.ts#L121

[mitschabaude]

Update: discussion on this was continued on discord. The issue turned out to be a limitation on circuit size, uncovered by this error message from kimchi:

panicked at 'add_lagrange_basis: Domain size 131072 larger than SRS size 65536'

To uncover this error in snarkyjs, we needed to improve the stack trace, by printing error messages from Rust in the JS console: MinaProtocol/mina#11644
With this PR merged, these changes are now available in the snarkyjs main branch: #338

[xhliu]

Our sha256 is finally working, thanks to your help! It has 58830 constraints.

Unfortunately, we need double sha256, and it exceeded constraint limits of 2^16=65536. Any way to bump the limit or alternative to get around this limit?

[jackryanservia]

Unfortunately, bumping up the constraint limit is not as simple as changing a hardcoded number somewhere in SnarkyJS, but you could use recursion! :) Try proving the first SHA-256 evaluation, then verifying that proof inside the proof where you do the second evaluation.

[xhliu]

Hmm, 58k constraints is just for hashing one chunk. And a bitcoin transaction is at least 5 chunks (250 bytes: 1 input & 2 outputs). On top of that, we need to double hashing. A second recursion is gonna be very difficult, we need to break it into 5 smaller steps (5 chunks + second hashing) to fit in 2^16 constraint limit.

[Trivo25]

closing, sha256 is now natively avaiable in o1js with roughly 5000 constrains per block hash