SHA-256 implementation in Bitcoin script under 400K vbytes

[Sergio_Demian_Lerner]

Martin Jonas (BitVMX team) created a SHA-256 code in Bitcoin script that hashes 64 bytes, and the code fits into a standard taproot script.  

The limiting factor is the maximum script stack (1000 elements). With a larger stack, it could probably be shrank to ~100 Kb.

This was a contribution to the BitVM2 implementation in Rust.

https://github.com/BitVM/BitVM/pull/65

It's interesting the use of nibbles (4-bit words) instead of 32-bit words to operate. That's perfect for tables involving two 4-bit operands (AND, OR, XOR, SHIFT, etc.).

Why create a SHA-256 implementation in script if there is a OP_SHA256 opcode?

Because Bitcoin script cannot expand the OP_SHA256 output value (32 bytes) into individual bytes in the stack. Therefore, OP_SHA256 cannot be used to check properties of the input and output inside the script. This prevents the use of OP_SHA256 to verify Lamport/Winternitz signatures.

(Note: Martin works @ https://fairgate.io and he is a contributor to the https://BitVMX.org project)

[1715218616]

1715218616

[1715218616]

1715218616

[1715218616]

1715218616

[garlonicon]

Because Bitcoin script cannot expand the OP_SHA256 output value (32 bytes) into individual bytes in the stack.

I think people should support OP_CAT soft-fork, because that single opcode can solve a lot of issues there.