Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

From: Jeremy <jlrubin@mit•edu>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>
Cc: ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org>,
	"lightning-dev@lists•linuxfoundation.org"
	<lightning-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout
Date: Fri, 4 Oct 2019 11:33:09 -0700	[thread overview]
Message-ID: <CAD5xwhh_WbpSvou7sORjG9JeVonU8UR3qR0Bc9cmhp5sep34OA@mail.gmail.com> (raw)
In-Reply-To: <NVDIhcpuRV6VduUgfMNyGSU1U24ErWPuxpA07fMkIIgXqxEL2aX1_oYJ189Wf5ZigGDBa860gJ-p8d3iAMAWsjHx-5tZHZLjXr7gEmQbL0c=@protonmail.com>

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

Good point -- in our discussion, we called it OP_FFS -- Fold Functional
Stream, and it could be initialized with a different integer to select for
different functions. Therefore the stream processing opcodes would be
generic, but extensible.
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

On Fri, Oct 4, 2019 at 12:00 AM ZmnSCPxj via Lightning-dev <
lightning-dev@lists•linuxfoundation.org> wrote:

> Good morning Jeremy,
>
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> function to allow concatenation of an unlimited amount of data, provided
> the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM  (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> <3> OP_SHA256STREAM
> <-2> OP_SHA256STREAM
> >
> > Or it coul
> >
>
> This seems a good idea.
>
> Though it brings up the age-old tension between:
>
> * Generically-useable components, but due to generalization are less
> efficient.
> * Specific-use components, which are efficient, but which may end up not
> being useable in the future.
>
> In particular, `OP_SHA256STREAM` would no longer be useable if SHA256
> eventually is broken, while the `OP_CAT` will still be useable in the
> indefinite future.
> In the future a new hash function can simply be defined and the same
> technique with `OP_CAT` would still be useable.
>
>
> Regards,
> ZmnSCPxj
>
> > --
> > @JeremyRubin
> >
> > On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail•com> wrote:
> >
> > > I hope you are having an great afternoon ZmnSCPxj,
> > >
> > > You make an excellent point!
> > >
> > > I had thought about doing the following to tag nodes
> > >
> > > || means OP_CAT
> > >
> > > `node = SHA256(type||SHA256(data))`
> > > so a subnode would be
> > > `subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
> > > and a leaf node would be
> > > `leafnode = SHA256(0||SHA256(leafdata))`
> > >
> > > Yet, I like your idea better. Increasing the size of the two inputs to
> > > OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
> > > size of object on the stack seems sensible and also doesn't special
> > > case the logic of OP_CAT.
> > >
> > > It would also increase performance. SHA256(tag||subnode2||subnode3)
> > > requires 2 compression function calls whereas
> > > SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
> > > function calls (due to padding).
> > >
> > > >Or we could implement tagged SHA256 as a new opcode...
> > >
> > > I agree that tagged SHA256 as an op code that would certainty be
> > > useful, but OP_CAT provides far more utility and is a simpler change.
> > >
> > > Thanks,
> > > Ethan
> > >
> > > On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail•com>
> wrote:
> > > >
> > > > Good morning Ethan,
> > > >
> > > >
> > > > > To avoid derailing the NO_INPUT conversation, I have changed the
> > > > > subject to OP_CAT.
> > > > >
> > > > > Responding to:
> > > > > """
> > > > >
> > > > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> > > > >     retained from the original BitCoin 0.1.0 Alpha for Windows
> design, on
> > > > >     par with:
> > > > >     [..]
> > > > >
> > > > > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > > >     [..]
> > > > >     """
> > > > >
> > > > >     OP_CAT is an extremely valuable op code. I understand why it
> was
> > > > >     removed as the situation at the time with scripts was dire.
> However
> > > > >     most of the protocols I've wanted to build on Bitcoin run into
> the
> > > > >     limitation that stack values can not be concatenated. For
> instance
> > > > >     TumbleBit would have far smaller transaction sizes if OP_CAT
> was
> > > > >     supported in Bitcoin. If it happens to me as a researcher it is
> > > > >     probably holding other people back as well. If I could wave a
> magic
> > > > >     wand and turn on one of the disabled op codes it would be
> OP_CAT. Of
> > > > >     course with the change that size of each concatenated value
> must be 64
> > > > >     Bytes or less.
> > > >
> > > > Why 64 bytes in particular?
> > > >
> > > > It seems obvious to me that this 64 bytes is most suited for
> building Merkle trees, being the size of two SHA256 hashes.
> > > >
> > > > However we have had issues with the use of Merkle trees in Bitcoin
> blocks.
> > > > Specifically, it is difficult to determine if a hash on a Merkle
> node is the hash of a Merkle subnode, or a leaf transaction.
> > > > My understanding is that this is the reason for now requiring
> transactions to be at least 80 bytes.
> > > >
> > > > The obvious fix would be to prepend the type of the hashed object,
> i.e. add at least one byte to determine this type.
> > > > Taproot for example uses tagged hash functions, with a different tag
> for leaves, and tagged hashes are just
> prepend-this-32-byte-constant-twice-before-you-SHA256.
> > > >
> > > > This seems to indicate that to check merkle tree proofs, an `OP_CAT`
> with only 64 bytes max output size would not be sufficient.
> > > >
> > > > Or we could implement tagged SHA256 as a new opcode...
> > > >
> > > > Regards,
> > > > ZmnSCPxj
> > > >
> > > >
> > > > >
> > > > >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > > > >     bitcoin-dev@lists•linuxfoundation.org wrote:
> > > > >
> > > > >
> > > > > > Good morning lists,
> > > > > > Let me propose the below radical idea:
> > > > > >
> > > > > > -   `SIGHASH` flags attached to signatures are a misdesign,
> sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> par with:
> > > > > >     -   1 RETURN
> > > > > >     -   higher-`nSequence` replacement
> > > > > >     -   DER-encoded pubkeys
> > > > > >     -   unrestricted `scriptPubKey`
> > > > > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > > > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > > > >     -   transaction malleability
> > > > > >     -   probably many more
> > > > > >
> > > > > > So let me propose the more radical excision, starting with
> SegWit v1:
> > > > > >
> > > > > > -   Remove `SIGHASH` from signatures.
> > > > > > -   Put `SIGHASH` on public keys.
> > > > > >
> > > > > > Public keys are now encoded as either 33-bytes (implicit
> `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type,
> followed by pubkey coordinate).
> > > > > > `OP_CHECKSIG` and friends then look at the public key to
> determine sighash algorithm rather than the signature.
> > > > > > As we expect public keys to be indirectly committed to on every
> output `scriptPubKey`, this is automatically output tagging to allow
> particular `SIGHASH`.
> > > > > > However, we can then utilize the many many ways to hide public
> keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > > > > I propose also the addition of the opcode:
> > > > > >
> > > > > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > > > > >
> > > > > >
> > > > > > -   `sighash` must be one byte.
> > > > > > -   `pubkey` may be the special byte `0x1`, meaning "just use
> the Taproot internal pubkey".
> > > > > > -   `pubkey` may be 33-byte public key, in which case the
> `sighash` byte is just prepended to it.
> > > > > > -   `pubkey` may be 34-byte public key with sighash, in which
> case the first byte is replaced with `sighash` byte.
> > > > > > -   If `sighash` is `0x00` then the result is a 33-byte public
> key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > > > > >
> > > > > > This retains the old feature where the sighash is selected at
> time-of-spending rather than time-of-payment.
> > > > > > This is done by using the script:
> > > > > >
> > > > > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > > > > >
> > > > > >
> > > > > > Then the sighash can be put in the witness stack after the
> signature, letting the `SIGHASH` flag be selected at time-of-signing, but
> only if the SCRIPT specifically is formed to do so.
> > > > > > This is malleability-safe as the signature still commits to the
> `SIGHASH` it was created for.
> > > > > > However, by default, public keys will not have an attached
> `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default
> non-`SIGHASH_ALL`).
> > > > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`,
> as they are allowed only if the output specifically says they are allowed.
> > > > > > Would this not be a superior solution?
> > > > > > Regards,
> > > > > > ZmnSCPxj
> > > > > >
> > > > > > bitcoin-dev mailing list
> > > > > > bitcoin-dev@lists•linuxfoundation.org
> > > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > > >
> > > > > Lightning-dev mailing list
> > > > > Lightning-dev@lists•linuxfoundation.org
> > > > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> > > >
> > > >
> > > _______________________________________________
> > > Lightning-dev mailing list
> > > Lightning-dev@lists•linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>

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