public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

From: Robin Linus <robinlinus@protonmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Nondeterministic Programming and Hints in Bitcoin Script
Date: Thu, 08 Dec 2022 01:14:54 +0000	[thread overview]
Message-ID: <lMxqB4zaKr33YEkv0ZykaxZa7r-yvR1rSC17rOBCRYELtYfnlUq62tyVMw0vrG1cFBeEDOMGx4qB_un0N7rMmKRdA9c8WdlvlCCPefN2f3Y=@protonmail.com> (raw)

[-- Attachment #1: Type: text/plain, Size: 2555 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 4512 bytes --]

                 reply	other threads:[~2022-12-08  1:15 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='lMxqB4zaKr33YEkv0ZykaxZa7r-yvR1rSC17rOBCRYELtYfnlUq62tyVMw0vrG1cFBeEDOMGx4qB_un0N7rMmKRdA9c8WdlvlCCPefN2f3Y=@protonmail.com' \
    --to=robinlinus@protonmail$(echo .)com \
    --cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox