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
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
