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)

[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.

[Sergio_Demian_Lerner]

I support OP_CAT, but Bitcoin L2s need more decentralized bridges now. We'll develop BitVMX with optional support of OP_CAT, so that we can make use of OP_CAT if/when it is activated.

[NotATether]

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.

I am not familiar with those kinds of signatures so let me ask you a question: How would the SHA256 output being split into nibbles help to verify Lamport or WInternitz signatures?

Also what is the use case for those two kinds of signatures, and how does it compare to something like ECDSA (which is recoverable) or maybe Schnorr even.

I do know that having the ability to verify signatures inline of the script is a good thing as CHECKSIG-like opcodes are not going to be introduced anytime soon, so I want to know what kind of things you can do with this.