Content-Type: multipart/alternative;
 boundary="------------6BOv2TMXW5HQXzS585uNkSQt"
Message-ID: <211ab58c-707e-97bb-241b-6fe809fd2bdb@roose.io>
Date: Fri, 6 Oct 2023 18:38:22 +0100
MIME-Version: 1.0
To: Steven Roose via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
References: <e98d76f2-6f2c-9c3a-6a31-bccb34578c31@roose.io>
Content-Language: en-US
From: Steven Roose <steven@roose.io>
In-Reply-To: <e98d76f2-6f2c-9c3a-6a31-bccb34578c31@roose.io>
Subject: Re: [bitcoin-dev] Draft BIP: OP_TXHASH and OP_CHECKTXHASHVERIFY
Precedence: list

This is a multi-part message in MIME format.
--------------6BOv2TMXW5HQXzS585uNkSQt
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

I updated the draft BIP with a proposed reference implementation and a 
link to an implementation of a caching strategy.

It shows that it's possible to achieve TXHASH in a way that after each 
large tx element (scripts, annexes) has been hashed exactly once, 
invocations of TXHASH have clear constant upper limits on the number of 
bytes hashes.

Link to the draft BIP in above e-mail and link to the cache impl here: 
https://github.com/stevenroose/rust-bitcoin/blob/txhash/bitcoin/src/blockdata/script/txhash.rs


On 9/30/23 12:44, Steven Roose via bitcoin-dev wrote:
>
> Hey all
>
>
> The idea of TXHASH has been around for a while, but AFAIK it was never 
> formalized. After conversations with Russell, I worked on a 
> specification and have been gathering some feedback in the last 
> several weeks.
>
> I think the draft is in a state where it's ready for wider feedback 
> and at the same time I'm curious about the sentiment in the community 
> about this idea.
>
> The full BIP text can be found in the attachment as well as at the 
> following link:
> https://github.com/bitcoin/bips/pull/1500
>
> I will summarize here in this writing.
>
> *What does the BIP specify?*
>
>   * The concept of a TxFieldSelector, a serialized data structure for
>     selecting data inside a transaction.
>       o The following global fields are available:
>           + version
>           + locktime
>           + number of inputs
>           + number of outputs
>           + current input index
>           + current input control block
>       o For each input, the following fields are available:
>           + previous outpoint
>           + sequence
>           + scriptSig
>           + scriptPubkey of spending UTXO
>           + value of spending UTXO
>           + taproot annex
>       o For each output, the following fields are available:
>           + scriptPubkey
>           + value
>       o There is support for selecting inputs and outputs as follows:
>           + all in/outputs
>           + a single in/output at the same index as the input being
>             executed
>           + any number of leading in/outputs up to 2^14 - 1 (16,383)
>           + up to 64 individually selected in/outputs (up to 2^16 or
>             65,536)
>       o The empty byte string is supported and functions as a default
>         value which commits to everything except the previous
>         outpoints and the scriptPubkeys of the spending UTXOs.
>
>   * An opcode OP_TXHASH, enabled only in tapscript, that takes a
>     serialized TxFieldSelector from the stack and pushes on the stack
>     a hash committing to all the data selected.
>
>   * An opcode OP_CHECKTXHASHVERIFY, enabled in all script contexts,
>     that expects a single item on the stack, interpreted as a 32-byte
>     hash value concatenated with (at the end) a serialized
>     TxFieldSelector. Execution fails is the hash value in the data
>     push doesn't equal the calculated hash value based on the
>     TxFieldSelector.
>
>   * A consideration for resource usage trying to address concerns
>     around quadratic hashing. A potential caching strategy is outlined
>     so that users can't trigger excessive hashing.
>       o Individual selection is limited to 64 items.
>       o Selecting "all" in/outputs can mostly use the same caches as
>         sighash calculations.
>       o For prefix hashing, intermediate SHA256 contexts can be stored
>         every N items so that at most N-1 items have to be hashed when
>         called repeatedly.
>       o In non-tapscript contexts, at least 32 witness bytes are
>         required and because (given the lack of OP_CAT) subsequent
>         calls can only re-enforce the same TxFieldSelector, no
>         additional limitations are put in place.
>       o In tapscript, because OP_TXHASH doesn't require 32 witness
>         bytes and because of a potential addition of operations like
>         OP_CAT, the validation budget is decreased by 10 for every
>         OP_TXHASH or OP_CHECKTXHASHVERIFY operation.
>
>
> *What does this achieve?*
>
>   * Since the default TxFieldSelector is functionally equivalent to
>     OP_CHECKTEMPLATEVERIFY, with no extra bytes required, this
>     proposal is a strict upgrade of BIP-119.
>
>   * The flexibility of selecting transaction fields and in/output
>     (ranges), makes this construction way more useful
>       o when designing protocols where users want to be able to add
>         fees to their transactions without breaking a transaction chain;
>       o when designing protocols where users construct transactions
>         together, each providing some of their own in- and outputs and
>         wanting to enforce conditions only on these in/outputs.
>
>   * OP_TXHASH, together with OP_CHECKSIGFROMSTACK (and maybe OP_CAT*)
>     could be used as a replacement for almost arbitrarily complex
>     sighash constructions, like SIGHASH_ANYPREVOUT.
>
>   * Apart from being able to enforce specific fields in the
>     transaction to have a pre-specified value, equality can also be
>     enforced, which can f.e. replace the desire for opcodes like
>     OP_IN_OUT_VALUE.*
>
>   * The same TxFieldSelector construction would function equally well
>     with a hypothetical OP_TX opcode that directly pushes the selected
>     fields on the stack to enable direct introspection.
>
>
> *What are still open questions?*
>
>   * Does the proposal sufficiently address concerns around resource
>     usage and quadratic hashing?
>
>   * *: Miraculously, once we came up with all possible fields that we
>     might consider interesting, we filled exactly 16 spots. There is
>     however one thing that I would have liked to be optionally
>     available and I am unsure of which side to take in the proposal.
>     This is including the TxFieldSelector as part of the hash. Doing
>     so no longer makes the hash only represent the value being hashed,
>     but also the field selector that was used; this would no longer
>     make it possible to proof equality of fields. If a txhash as
>     specified here would ever be used as a signature hash, it would
>     definitely have to be included, but this could be done after the
>     fact if OP_CAT was available. For signature hashes, the hash
>     should ideally be somehow tagged, so we might need OP_CAT, or
>     OP_CATSHA256 or something anyway.
>
>       * A solution could be to take an additional bit from each of the
>         two "in/output selector" bytes, and assign to this bit "commit
>         to total number of in/outputs" (instead of having 2 bits for
>         this in the first byte).
>           o This would free up 2 bits in the first byte, one of which
>             could be used for including the TxFieldSelector in the
>             hash and the other one could be left free (OP_SUCCESS) to
>             potentially revisit later-on.
>           o This would limit the number of selectable leading
>             in/outputs to 8,191 and the number of individually
>             selectable in/outputs to 32, both of which seem reasonable
>             or maybe even more desirable from a resource usage
>             perspective.
>
>   * General feedback of how people feel towards a proposal like this,
>     which could either be implemented in a softfork as is, like
>     BIP-119 or be combined in a single softfork with
>     OP_CHECKSIGFROMSTACK and perhaps OP_CAT, OP_TWEAKADD and/or a
>     hypothetical OP_TX.
>
>
> This work is just an attempt to make some of the ideas that have been 
> floating around into a concrete proposal. If there is community 
> interest, I would be willing to spend time to adequately formalize 
> this BIP and to work on an implementation for Bitcoin Core.
>
>
> Looking forward to your thoughts
>
> Steven
>
>
>
>
>
>
>
>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
--------------6BOv2TMXW5HQXzS585uNkSQt
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <p>I updated the draft BIP with a proposed reference implementation
      and a link to an implementation of a caching strategy.</p>
    <p>It shows that it's possible to achieve TXHASH in a way that after
      each large tx element (scripts, annexes) has been hashed exactly
      once, invocations of TXHASH have clear constant upper limits on
      the number of bytes hashes.</p>
    <p>Link to the draft BIP in above e-mail and link to the cache impl
      here:
<a class="moz-txt-link-freetext" href="https://github.com/stevenroose/rust-bitcoin/blob/txhash/bitcoin/src/blockdata/script/txhash.rs">https://github.com/stevenroose/rust-bitcoin/blob/txhash/bitcoin/src/blockdata/script/txhash.rs</a></p>
    <p><br>
    </p>
    <div class="moz-cite-prefix">On 9/30/23 12:44, Steven Roose via
      bitcoin-dev wrote:<br>
    </div>
    <blockquote type="cite"
      cite="mid:e98d76f2-6f2c-9c3a-6a31-bccb34578c31@roose.io">
      <meta http-equiv="content-type" content="text/html; charset=UTF-8">
      <p>Hey all</p>
      <p><br>
      </p>
      <p>The idea of TXHASH has been around for a while, but AFAIK it
        was never formalized. After conversations with Russell, I worked
        on a specification and have been gathering some feedback in the
        last several weeks.</p>
      <p>I think the draft is in a state where it's ready for wider
        feedback and at the same time I'm curious about the sentiment in
        the community about this idea.</p>
      <p>The full BIP text can be found in the attachment as well as at
        the following link:<br>
        <a class="moz-txt-link-freetext"
          href="https://github.com/bitcoin/bips/pull/1500"
          moz-do-not-send="true">https://github.com/bitcoin/bips/pull/1500</a><br>
      </p>
      <p>I will summarize here in this writing.</p>
      <p><b>What does the BIP specify?</b></p>
      <ul>
        <li>The concept of a TxFieldSelector, a serialized data
          structure for selecting data inside a transaction.</li>
        <ul>
          <li>The following global fields are available:</li>
          <ul>
            <li>version</li>
            <li>locktime</li>
            <li>number of inputs</li>
            <li>number of outputs</li>
            <li>current input index</li>
            <li>current input control block</li>
          </ul>
          <li>For each input, the following fields are available:</li>
          <ul>
            <li>previous outpoint</li>
            <li>sequence</li>
            <li>scriptSig</li>
            <li>scriptPubkey of spending UTXO</li>
            <li>value of spending UTXO</li>
            <li>taproot annex</li>
          </ul>
          <li>For each output, the following fields are available:</li>
          <ul>
            <li>scriptPubkey</li>
            <li>value<br>
            </li>
          </ul>
          <li>There is support for selecting inputs and outputs as
            follows:</li>
          <ul>
            <li>all in/outputs<br>
            </li>
            <li>a single in/output at the same index as the input being
              executed</li>
            <li>any number of leading in/outputs up to 2^14 - 1 (16,383)<br>
            </li>
            <li>up to 64 individually selected in/outputs (up to 2^16 or
              65,536)</li>
          </ul>
          <li>The empty byte string is supported and functions as a
            default value which commits to everything except the
            previous outpoints and the scriptPubkeys of the spending
            UTXOs.<br>
          </li>
        </ul>
      </ul>
      <ul>
        <li>An opcode OP_TXHASH, enabled only in tapscript, that takes a
          serialized TxFieldSelector from the stack and pushes on the
          stack a hash committing to all the data selected.</li>
      </ul>
      <ul>
        <li>An opcode OP_CHECKTXHASHVERIFY, enabled in all script
          contexts, that expects a single item on the stack, interpreted
          as a 32-byte hash value concatenated with (at the end) a
          serialized TxFieldSelector. Execution fails is the hash value
          in the data push doesn't equal the calculated hash value based
          on the TxFieldSelector.</li>
      </ul>
      <ul>
        <li>A consideration for resource usage trying to address
          concerns around quadratic hashing. A potential caching
          strategy is outlined so that users can't trigger excessive
          hashing.</li>
        <ul>
          <li>Individual selection is limited to 64 items.</li>
          <li>Selecting "all" in/outputs can mostly use the same caches
            as sighash calculations.</li>
          <li>For prefix hashing, intermediate SHA256 contexts can be
            stored every N items so that at most N-1 items have to be
            hashed when called repeatedly.</li>
          <li>In non-tapscript contexts, at least 32 witness bytes are
            required and because (given the lack of OP_CAT) subsequent
            calls can only re-enforce the same TxFieldSelector, no
            additional limitations are put in place.</li>
          <li>In tapscript, because OP_TXHASH doesn't require 32 witness
            bytes and because of a potential addition of operations like
            OP_CAT, the validation budget is decreased by 10 for every
            OP_TXHASH or OP_CHECKTXHASHVERIFY operation.</li>
        </ul>
      </ul>
      <p><br>
      </p>
      <p><b>What does this achieve?</b></p>
      <ul>
        <li>Since the default TxFieldSelector is functionally equivalent
          to OP_CHECKTEMPLATEVERIFY, with no extra bytes required, this
          proposal is a strict upgrade of BIP-119.</li>
      </ul>
      <ul>
        <li>The flexibility of selecting transaction fields and
          in/output (ranges), makes this construction way more useful</li>
        <ul>
          <li>when designing protocols where users want to be able to
            add fees to their transactions without breaking a
            transaction chain;</li>
          <li>when designing protocols where users construct
            transactions together, each providing some of their own in-
            and outputs and wanting to enforce conditions only on these
            in/outputs.</li>
        </ul>
      </ul>
      <ul>
        <li>OP_TXHASH, together with OP_CHECKSIGFROMSTACK (and maybe
          OP_CAT*) could be used as a replacement for almost arbitrarily
          complex sighash constructions, like SIGHASH_ANYPREVOUT.</li>
      </ul>
      <ul>
        <li>Apart from being able to enforce specific fields in the
          transaction to have a pre-specified value, equality can also
          be enforced, which can f.e. replace the desire for opcodes
          like OP_IN_OUT_VALUE.*</li>
      </ul>
      <ul>
        <li>The same TxFieldSelector construction would function equally
          well with a hypothetical OP_TX opcode that directly pushes the
          selected fields on the stack to enable direct introspection.<br>
        </li>
      </ul>
      <p><br>
      </p>
      <p><b>What are still open questions?</b></p>
      <ul>
        <li>Does the proposal sufficiently address concerns around
          resource usage and quadratic hashing?</li>
      </ul>
      <ul>
        <li>*: Miraculously, once we came up with all possible fields
          that we might consider interesting, we filled exactly 16
          spots. There is however one thing that I would have liked to
          be optionally available and I am unsure of which side to take
          in the proposal. This is including the TxFieldSelector as part
          of the hash. Doing so no longer makes the hash only represent
          the value being hashed, but also the field selector that was
          used; this would no longer make it possible to proof equality
          of fields. If a txhash as specified here would ever be used as
          a signature hash, it would definitely have to be included, but
          this could be done after the fact if OP_CAT was available. For
          signature hashes, the hash should ideally be somehow tagged,
          so we might need OP_CAT, or OP_CATSHA256 or something anyway.</li>
      </ul>
      <blockquote>
        <ul>
          <li>A solution could be to take an additional bit from each of
            the two "in/output selector" bytes, and assign to this bit
            "commit to total number of in/outputs" (instead of having 2
            bits for this in the first byte).</li>
          <ul>
            <li>This would free up 2 bits in the first byte, one of
              which could be used for including the TxFieldSelector in
              the hash and the other one could be left free (OP_SUCCESS)
              to potentially revisit later-on.</li>
            <li>This would limit the number of selectable leading
              in/outputs to 8,191 and the number of individually
              selectable in/outputs to 32, both of which seem reasonable
              or maybe even more desirable from a resource usage
              perspective.<br>
            </li>
          </ul>
        </ul>
      </blockquote>
      <ul>
        <li>General feedback of how people feel towards a proposal like
          this, which could either be implemented in a softfork as is,
          like BIP-119 or be combined in a single softfork with
          OP_CHECKSIGFROMSTACK and perhaps OP_CAT, OP_TWEAKADD and/or a
          hypothetical OP_TX.</li>
      </ul>
      <p><br>
      </p>
      <p>This work is just an attempt to make some of the ideas that
        have been floating around into a concrete proposal. If there is
        community interest, I would be willing to spend time to
        adequately formalize this BIP and to work on an implementation
        for Bitcoin Core.<br>
      </p>
      <p><br>
      </p>
      <p>Looking forward to your thoughts<br>
      </p>
      <p>Steven<br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <p><br>
      </p>
      <br>
      <fieldset class="moz-mime-attachment-header"></fieldset>
      <pre class="moz-quote-pre" wrap="">_______________________________________________
bitcoin-dev mailing list
<a class="moz-txt-link-abbreviated" href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>
<a class="moz-txt-link-freetext" href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a>
</pre>
    </blockquote>
  </body>
</html>

--------------6BOv2TMXW5HQXzS585uNkSQt--