Robin Linus [ARCHIVE] on Nostr: 📅 Original date posted:2022-12-07 📝 Original message:TL;DR: Bitcoin Script ...

📅 Original date posted:2022-12-07
📝 Original message:TL;DR: Bitcoin Script supports a lot more opcodes than previously assumed. We just have to apply nondeterministic programming, which is a concept from ZKP circuit design.

Good morning Mailinglist,

the Taproot update dropped the restrictions for script sizes, so in theory a TX can now have a script with millions of instructions. While exploring the new possibilities I noticed that we can apply to Bitcoin Script a programming concept from zero-knowledge proofs named nondeterministic programming. Whenever possible, the prover computes the result of an expensive operation and then gives that result to the verifier, who only verifies the correctness of the result, which is often much more efficient than computing it.

For example, we can represent integer division efficiently in Bitcoin Script if the result is given to us in the unlocking script. This is because multiplication with a constant is relatively cheap.

Here is a most simple example implementing integer division by 2. We use that multiplication by 2 is simply OP_DUP OP_ADD, which is cheap.

```

# Integer division by 2 with the help of a hint
# In this example, we divide 119 by 2.
# In the unlocking script the prover provides the result
# as a hint 119//2 = 59, which we verify.

btcdeb "[

119 # Some arbitrary input is on the stack
OP_OVER # Copy the hint to the top of the stack

OP_DUP OP_ADD # Multiply the hint by 2
OP_SUB # Subtract that from the 119

# Now the remainder should be on the stack
# We verify that it is exactly 0 or 1

OP_DUP # Make a copy
OP_0NOTEQUAL # Returns 0 if the input is 0. 1 otherwise.
OP_EQUALVERIFY

# ]" 59 # The hint provided is 59 = 119/2

```

Here you can find more complex examples of opcodes using hints:
https://github.com/coins/bitcoin-scripts/blob/master/composite-opcodes.md#op_2div

Here is even a script for a bitwise rotation of a 32-bit word. It requires about 100 instructions. I think that suggests it might be possible to implement something like sha256 in about 200-300k opcodes.
https://github.com/coins/bitcoin-scripts/blob/master/op_rotate.md

Furthermore, I wondered if it might be possible to implement a ZKP verifier in Bitcoin script. However, that would probably need some hack to make multiplications much cheaper.

Maybe others also find it exciting to explore the new solution spaces enabled by the Taproot update and maybe nondeterministic programming inspires some new ways of thinking about Bitcoin Script.

Have a good day everyone!
Robin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221208/ee09d2fb/attachment.html>;