[bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode

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

* [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode
@ 2024-12-09 13:27 Weikeng Chen
  2024-12-09 19:08 ` Andrew Poelstra
  0 siblings, 1 reply; 5+ messages in thread
From: Weikeng Chen @ 2024-12-09 13:27 UTC (permalink / raw)
  To: Bitcoin Development Mailing List

[-- Attachment #1.1: Type: text/plain, Size: 3537 bytes --]

When I am implementing fraud proofs in Bitcoin script, I find it useful to 
have an opcode "OP_SUCCESS" that will mark the execution to be successful 
without running the rest of the script, if this opcode is being executed. 
This is useful for writing code for fraud proofs such as BitVM, where the 
verifier wins if it finds one mismatch, and the verifier does not need to 
show the other mismatches.

This OP_SUCCESS is weaker version of the OP_SUCCESSx in the Taproot 
upgrade, which marks the execution as successful for the mere presence of 
OP_SUCCESSx anywhere in the script. Rusty Russell in a 2023 article, 
"Covenants: Examining ScriptPubkeys in Bitcoin Script", also mentioned 
about the usefulness of such an opcode. 

Of course, this opcode can be emulated, and one can rewrite the existing 
script in a way to realize the same functionality without adding a new 
opcode to Bitcoin.

The problem is that such rewriting is indeed fairly complicated. For 
example, say that we have the following program.

```
OP_NOP1
OP_IF
    OP_NOP2
    OP_IF_SUCCESS
    OP_NOP3
    OP_IF_SUCCESS
    OP_NOP4
    OP_IF_SUCCESS
    OP_NOP5
OP_ENDIF
OP_NOP6
```
with OP_IF_SUCCESS short for "OP_IF OP_SUCCESS OP_ENDIF"

The equivalent version without using new opcode is as follows (generated by 
computer, using a rewriting tool: 
https://github.com/Bitcoin-Wildlife-Sanctuary/fraud-proof-compiler)

```
OP_NOP1
OP_IF
    OP_NOP2
    OP_IF
        1
        0
    OP_ELSE
        OP_NOP3
        OP_IF
            1
            0
        OP_ELSE
            OP_NOP4
            OP_IF
                1
            OP_ELSE
                OP_NOP5
                0
                0
                0
            OP_ENDIF
        OP_ENDIF
        OP_IF 1 OP_ENDIF
    OP_ENDIF
    OP_IF 1 OP_ENDIF
OP_ELSE
    0
OP_ENDIF
OP_IF
    1
OP_ELSE
    OP_NOP6
    0
OP_ENDIF
OP_IF
    OP_DEPTH 512 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (256 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 256 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (128 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 128 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (64 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 64 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (32 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 32 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (16 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 16 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (8 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 8 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (4 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 4 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP ... OP_2DROP (2 OP_2DROP)
    OP_ENDIF
    OP_DEPTH 2 OP_GREATERTHANOREQUAL OP_IF
        OP_2DROP
    OP_ENDIF
    OP_DEPTH OP_IF
        OP_DROP
    OP_ENDIF
    OP_TRUE
OP_ENDIF
```

The second part of the code is mainly a general-purpose and 
stack-size-independent method to remove all the stack elements in order to 
be standard. 

For this reason, it seems better to avoid the need for developers to 
"emulate" such a weak version of OP_SUCCESS but to actually implement an 
opcode for that.

What do you think?

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/ebd77d82-96ab-4530-909a-d085378b9868n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 4876 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode
  2024-12-09 13:27 [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode Weikeng Chen
@ 2024-12-09 19:08 ` Andrew Poelstra
  2024-12-09 22:06   ` Brandon Black
  0 siblings, 1 reply; 5+ messages in thread
From: Andrew Poelstra @ 2024-12-09 19:08 UTC (permalink / raw)
  To: Weikeng Chen; +Cc: Bitcoin Development Mailing List

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

On Mon, Dec 09, 2024 at 05:27:54AM -0800, Weikeng Chen wrote:
> When I am implementing fraud proofs in Bitcoin script, I find it useful to 
> have an opcode "OP_SUCCESS" that will mark the execution to be successful 
> without running the rest of the script, if this opcode is being executed. 
> This is useful for writing code for fraud proofs such as BitVM, where the 
> verifier wins if it finds one mismatch, and the verifier does not need to 
> show the other mismatches.
> 
> This OP_SUCCESS is weaker version of the OP_SUCCESSx in the Taproot 
> upgrade, which marks the execution as successful for the mere presence of 
> OP_SUCCESSx anywhere in the script. Rusty Russell in a 2023 article, 
> "Covenants: Examining ScriptPubkeys in Bitcoin Script", also mentioned 
> about the usefulness of such an opcode. 
> 
> Of course, this opcode can be emulated, and one can rewrite the existing 
> script in a way to realize the same functionality without adding a new 
> opcode to Bitcoin.
> 
> The problem is that such rewriting is indeed fairly complicated. For 
> example, say that we have the following program.
>
> <snip>

I raised the question on IRC about why the existing SUCCESSx codes work
the way they do, and got several good anwsers that you can read here

https://gnusha.org/bitcoin-wizards/2024-12-09.log

In short, for purpose of softforking upgrade mechanism, the existing
SUCCESS codes give us way more freedom of action.

But it sounds like you want a "weak SUCCESS" opcode in order to use the
success semantics, not as an upgrade mechanism. Maybe it makes sense to
propose that one of the existing OP_SUCCESSx opcodes should be
softforked to become OP_WEAK_SUCCESS?

-- 
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z1dAQ8pSIqn8XA56%40camus.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode
  2024-12-09 19:08 ` Andrew Poelstra
@ 2024-12-09 22:06   ` Brandon Black
       [not found]     ` <87ttbccrql.fsf@rustcorp.com.au>
  0 siblings, 1 reply; 5+ messages in thread
From: Brandon Black @ 2024-12-09 22:06 UTC (permalink / raw)
  To: Andrew Poelstra
  Cc: Weikeng Chen, Bitcoin Development Mailing List, Rusty Russell

Hey list,

On 2024-12-09 (Mon) at 19:08:51 +0000, Andrew Poelstra wrote:
> On Mon, Dec 09, 2024 at 05:27:54AM -0800, Weikeng Chen wrote:
> > When I am implementing fraud proofs in Bitcoin script, I find it useful to 
> > have an opcode "OP_SUCCESS" that will mark the execution to be successful 
> > without running the rest of the script, if this opcode is being executed. 
> > This is useful for writing code for fraud proofs such as BitVM, where the 
> > verifier wins if it finds one mismatch, and the verifier does not need to 
> > show the other mismatches.
> > 
> > This OP_SUCCESS is weaker version of the OP_SUCCESSx in the Taproot 
> > upgrade, which marks the execution as successful for the mere presence of 
> > OP_SUCCESSx anywhere in the script. Rusty Russell in a 2023 article, 
> > "Covenants: Examining ScriptPubkeys in Bitcoin Script", also mentioned 
> > about the usefulness of such an opcode. 
> > 
> > <snip>
> 
> In short, for purpose of softforking upgrade mechanism, the existing
> SUCCESS codes give us way more freedom of action.
> 
> But it sounds like you want a "weak SUCCESS" opcode in order to use the
> success semantics, not as an upgrade mechanism. Maybe it makes sense to
> propose that one of the existing OP_SUCCESSx opcodes should be
> softforked to become OP_WEAK_SUCCESS?

An alternative that Rusty Russel has discussed wanting as part of his
script restoration work is "OP_SEGMENT" which would split the script
execution for purposes of SUCCESS checking, allowing (for example) a
prefix to be required to execute before an arbitrary user provided
script that might contain an OP_SUCCESS.

It occurred to me today when thinking about Weikeng's post that we can
slightly weaken the existing OP_SUCCESS behavior while retaining
essentially all of its benefits in practice without introducing
OP_SEGMENT by leveraging OP_CODESEPARATOR. Redefine OP_SUCCESS with a
soft fork from "make the script unconditionally valid" to "make the
script segment unconditionally valid", and define a script segment as
"each lexicographic section of the script containing no
OP_CODESEPARATOR".

The script interpreter can perform SUCCESS checking as it currently does
until it encounters an OP_CODESEPARATOR. Each OP_CODESEPARATOR gets a
"SUCCESS" flag defaulted to false and SUCCESS checking now sets that
flag to true on the most recently encountered OP_CODESEPARATOR.

During script execution, whenever an OP_CODESEPARATOR is popped (not
executed) its "SUCCESS" flag value is copied to the interpreter state.
After this state setting conditional, if the interpreter "SUCCESS" flag
is true, and fExec is true, the script immediately succeeds.

For Weikeng's scripts, this would require 2 OP_CODESEPARATORS for each
OP_SUCCESS (or some really weird logic about what's executed in what
SUCCESS state).

Thoughts on this approach?

--Brandon

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z1dp0Jtbrkcf7Roi%40console.

^ permalink raw reply	[flat|nested] 5+ messages in thread

[parent not found: <87ttbccrql.fsf@rustcorp.com.au>]

* Re: [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode
       [not found]     ` <87ttbccrql.fsf@rustcorp.com.au>
@ 2024-12-12  3:17       ` Weikeng Chen
  2024-12-12  5:49       ` Brandon Black
  1 sibling, 0 replies; 5+ messages in thread
From: Weikeng Chen @ 2024-12-12  3:17 UTC (permalink / raw)
  To: Rusty Russell
  Cc: Brandon Black, Andrew Poelstra, Bitcoin Development Mailing List

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

I was mostly thinking about the names atm. OP_RETURN_TRUE may be a name
less confusing than OP_SUCCESS. It helps if one day we nickname/alias
OP_RETURN as OP_RETURN_FALSE.

This could eventually become an opcode BIP proposal that is pretty
causal---if a major soft fork happens (like the one that adds tapscript),
it could be piggybacked into it, otherwise, it would just stay as a
proposal as there is no urgency since it doesn't enhance the ability of
Bitcoin script (you can emulate it), but more to avoid bugs in code and for
clarity.

On Thu, Dec 12, 2024 at 10:54 AM Rusty Russell <rusty@rustcorp•com.au>
wrote:

> Brandon Black <freedom@reardencode•com> writes:
> > Hey list,
> >
> > On 2024-12-09 (Mon) at 19:08:51 +0000, Andrew Poelstra wrote:
> >> On Mon, Dec 09, 2024 at 05:27:54AM -0800, Weikeng Chen wrote:
> >> > When I am implementing fraud proofs in Bitcoin script, I find it
> useful to
> >> > have an opcode "OP_SUCCESS" that will mark the execution to be
> successful
> >> > without running the rest of the script, if this opcode is being
> executed.
> >> > This is useful for writing code for fraud proofs such as BitVM, where
> the
> >> > verifier wins if it finds one mismatch, and the verifier does not
> need to
> >> > show the other mismatches.
> >> >
> >> > This OP_SUCCESS is weaker version of the OP_SUCCESSx in the Taproot
> >> > upgrade, which marks the execution as successful for the mere
> presence of
> >> > OP_SUCCESSx anywhere in the script. Rusty Russell in a 2023 article,
> >> > "Covenants: Examining ScriptPubkeys in Bitcoin Script", also
> mentioned
> >> > about the usefulness of such an opcode.
> >> >
> >> > <snip>
> >>
> >> In short, for purpose of softforking upgrade mechanism, the existing
> >> SUCCESS codes give us way more freedom of action.
> >>
> >> But it sounds like you want a "weak SUCCESS" opcode in order to use the
> >> success semantics, not as an upgrade mechanism. Maybe it makes sense to
> >> propose that one of the existing OP_SUCCESSx opcodes should be
> >> softforked to become OP_WEAK_SUCCESS?
> >
> > An alternative that Rusty Russel has discussed wanting as part of his
> > script restoration work is "OP_SEGMENT" which would split the script
> > execution for purposes of SUCCESS checking, allowing (for example) a
> > prefix to be required to execute before an arbitrary user provided
> > script that might contain an OP_SUCCESS.
> >
> > It occurred to me today when thinking about Weikeng's post that we can
> > slightly weaken the existing OP_SUCCESS behavior while retaining
> > essentially all of its benefits in practice without introducing
> > OP_SEGMENT by leveraging OP_CODESEPARATOR. Redefine OP_SUCCESS with a
> > soft fork from "make the script unconditionally valid" to "make the
> > script segment unconditionally valid", and define a script segment as
> > "each lexicographic section of the script containing no
> > OP_CODESEPARATOR".
> >
> > The script interpreter can perform SUCCESS checking as it currently does
> > until it encounters an OP_CODESEPARATOR. Each OP_CODESEPARATOR gets a
> > "SUCCESS" flag defaulted to false and SUCCESS checking now sets that
> > flag to true on the most recently encountered OP_CODESEPARATOR.
> >
> > During script execution, whenever an OP_CODESEPARATOR is popped (not
> > executed) its "SUCCESS" flag value is copied to the interpreter state.
> > After this state setting conditional, if the interpreter "SUCCESS" flag
> > is true, and fExec is true, the script immediately succeeds.
>
> Beware success inside branches?  This is why I preferred to segment the
> script and scan for OP_SUCCESS and evaluate each part in order (if you
> have part of an if statement inside one segment, you fail as expected).
> This is actually not that different inside Bitcoin's script.cpp.
>
> But that's kind of a detail.  IMHO there's nothing fundamentally wrong
> with runtime success opcodes, in fact several proposals work better if
> you allow them (e.g. "undefined bit patterns in operand to OP_TXHASH
> cause immediate success" lets you reserve some bits for future
> extension).
>
> (Also: OP_CODESEPARATOR is cursed, so I chose a different name :)
>
> Cheers,
> Rusty.
>

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAHNroFfAiBMFnUPxqAV-spGB_Nt2juf6-8J3bGAJbDQKM_w2bQ%40mail.gmail.com.

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

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode
       [not found]     ` <87ttbccrql.fsf@rustcorp.com.au>
  2024-12-12  3:17       ` Weikeng Chen
@ 2024-12-12  5:49       ` Brandon Black
  1 sibling, 0 replies; 5+ messages in thread
From: Brandon Black @ 2024-12-12  5:49 UTC (permalink / raw)
  To: Rusty Russell
  Cc: Andrew Poelstra, Weikeng Chen, Bitcoin Development Mailing List

On 2024-12-10 (Tue) at 10:51:38 +1030, Rusty Russell wrote:
> Brandon Black <freedom@reardencode•com> writes:
> > It occurred to me today when thinking about Weikeng's post that we can
> > slightly weaken the existing OP_SUCCESS behavior while retaining
> > essentially all of its benefits in practice without introducing
> > OP_SEGMENT by leveraging OP_CODESEPARATOR. Redefine OP_SUCCESS with a
> > soft fork from "make the script unconditionally valid" to "make the
> > script segment unconditionally valid", and define a script segment as
> > "each lexicographic section of the script containing no
> > OP_CODESEPARATOR".
> >
> > The script interpreter can perform SUCCESS checking as it currently does
> > until it encounters an OP_CODESEPARATOR. Each OP_CODESEPARATOR gets a
> > "SUCCESS" flag defaulted to false and SUCCESS checking now sets that
> > flag to true on the most recently encountered OP_CODESEPARATOR.
> >
> > During script execution, whenever an OP_CODESEPARATOR is popped (not
> > executed) its "SUCCESS" flag value is copied to the interpreter state.
> > After this state setting conditional, if the interpreter "SUCCESS" flag
> > is true, and fExec is true, the script immediately succeeds.
> 
> Beware success inside branches?  This is why I preferred to segment the
> script and scan for OP_SUCCESS and evaluate each part in order (if you
> have part of an if statement inside one segment, you fail as expected).
> This is actually not that different inside Bitcoin's script.cpp.

I believe my description of CODESEPARATOR segments has a predictable but
different handling of SUCCESS with conditionals. As long as interpreter
state change are handled in order:

* update success mode if opcode is CODESEPARATOR
* if execution enabled by flow control and success mode is true, succeed
* execute operation if enabled or operation is flow control

That said, I've just reread [BIP342] and realized that the designers of
tapscript had greater things in mind for SUCCESS than I had remembered
(e.g. the existence of an SUCCESS can be used to change the behavior of
other opcodes or even stack limits) which would not work at all well
with segmented SUCCESS.

Some of these be possible with segmented execution, but not all.

Based on this, I'm now in favor of Weikeng's idea for a runtime success
operator possibly akin to the original RETURN. If it were equivalent to
the original RETURN, it would be a useful alternative to VERIFY in
certain cases.

> (Also: CODESEPARATOR is cursed, so I chose a different name :)

Isn't tapscript CODESEPARATOR uncursed? :)

Aside: Because SUCCESS allows for changing resource limits and more,
restored script can mostly be implemented in tapscript 0xc0. If any of
the new opcodes are present, 1NEGATE is redefined to TX (or something),
numbers are bigwholes, limits are varops, etc. Gets a little weird if
someone wants to write a restored script without any of the new ops, so
maybe you also provide an RESTORE that does nothing other than trigger
the mode change.

All the best,

--Brandon

[BIP342]: https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z1p5fA6-ZcMtPLOq%40console.

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2024-12-12  6:15 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-12-09 13:27 [bitcoindev] Difficulty in emulating "weaker" OP_SUCCESS and why it should be a real opcode Weikeng Chen
2024-12-09 19:08 ` Andrew Poelstra
2024-12-09 22:06   ` Brandon Black
     [not found]     ` <87ttbccrql.fsf@rustcorp.com.au>
2024-12-12  3:17       ` Weikeng Chen
2024-12-12  5:49       ` Brandon Black

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