Author: Robin Linus 2022-12-08 01:14:54
Published on: 2022-12-08T01:14:54+00:00
The recent Taproot update has lifted the restriction on script sizes, allowing transactions to have scripts with millions of instructions. Robin, a member of a mailing list, has explored the new possibilities and discovered that Bitcoin Script can use a programming concept from zero-knowledge proofs known as nondeterministic programming. This concept involves the prover computing the result of an expensive operation and providing it to the verifier, who only verifies the correctness of the result. For instance, integer division can be efficiently represented in Bitcoin Script if the result is given in the unlocking script since multiplication with a constant is relatively cheap. Robin provides an example of integer division by 2 using OP_DUP and OP_ADD, which cost less. More complex opcode examples using hints can be found on GitHub, including a script for a bitwise rotation of a 32-bit word requiring around 100 instructions. Robin believes it might be possible to implement something like sha256 in approximately 200-300k opcodes.Robin also ponders the possibility of implementing a ZKP verifier in Bitcoin Script, but it would require making multiplications much cheaper. Overall, Robin encourages others to explore the new solution spaces opened up by the Taproot update, and perhaps nondeterministic programming will inspire some innovative ways of thinking about Bitcoin Script.
Updated on: 2023-05-22T23:05:03.668062+00:00