Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BC6AFD0A; Fri, 4 Oct 2019 18:33:24 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id EB5308BB; Fri, 4 Oct 2019 18:33:22 +0000 (UTC) Received: from mail-io1-f44.google.com (mail-io1-f44.google.com [209.85.166.44]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id x94IXKqv028848 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT); Fri, 4 Oct 2019 14:33:21 -0400 Received: by mail-io1-f44.google.com with SMTP id z19so15743409ior.0; Fri, 04 Oct 2019 11:33:21 -0700 (PDT) X-Gm-Message-State: APjAAAUGowNjQZANtRRyZzZGieHY+fegnDcktHaxPvDUS6mcVki6rdu1 mznftwrIt6GrV8HUCv2BN2bw9d2IOcYp7ZVZVK4= X-Google-Smtp-Source: APXvYqw1ZRbAjY3NH1JsmkUmk7a0d9ve1v9PQmKRHNiCOAm2AsrDrw0droZ2WyO3yKanKHxSSkGVgo0wLkY3ndzM56s= X-Received: by 2002:a6b:c382:: with SMTP id t124mr2121770iof.105.1570214000448; Fri, 04 Oct 2019 11:33:20 -0700 (PDT) MIME-Version: 1.0 References: <87wodp7w9f.fsf@gmail.com> <20191001155929.e2yznsetqesx2jxo@erisian.com.au> In-Reply-To: From: Jeremy Date: Fri, 4 Oct 2019 11:33:09 -0700 X-Gmail-Original-Message-ID: Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="000000000000b7dbbf059419efb4" X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,HTML_MESSAGE, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: ZmnSCPxj via bitcoin-dev , "lightning-dev@lists.linuxfoundation.org" Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 Oct 2019 18:33:24 -0000 --000000000000b7dbbf059419efb4 Content-Type: text/plain; charset="UTF-8" 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 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 <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 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 > 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: > > > > > > > > > > > > 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: > > > > > > > > > > > > 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 > --000000000000b7dbbf059419efb4 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Good point -- in our disc= ussion, we called it OP_FFS -- Fold Functional Stream, and it could be init= ialized with a different integer to select for different functions. Therefo= re the stream processing opcodes would be generic, but extensible.


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

> Awhile back, Ethan and I discussed having, rather than OP_CAT, an OP_S= HA256STREAM 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=C2=A0 (-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 effici= ent.
* Specific-use components, which are efficient, but which may end up not be= ing useable in the future.

In particular, `OP_SHA256STREAM` would no longer be useable if SHA256 event= ually 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 techni= que 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 =3D SHA256(type||SHA256(data))`
> > so a subnode would be
> > `subnode1 =3D SHA256(1||SHA256(subnode2||subnode3))`
> > and a leaf node would be
> > `leafnode =3D SHA256(0||SHA256(leafdata))`
> >
> > Yet, I like your idea better. Increasing the size of the two inpu= ts to
> > OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowa= ble
> > size of object on the stack seems sensible and also doesn't s= pecial
> > case the logic of OP_CAT.
> >
> > It would also increase performance. SHA256(tag||subnode2||subnode= 3)
> > requires 2 compression function calls whereas
> > SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3D3 compressio= n
> > 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<= br> > > useful, but OP_CAT provides far more utility and is a simpler cha= nge.
> >
> > Thanks,
> > Ethan
> >
> > On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wro= te:
> > >
> > > Good morning Ethan,
> > >
> > >
> > > > To avoid derailing the NO_INPUT conversation, I have ch= anged the
> > > > subject to OP_CAT.
> > > >
> > > > Responding to:
> > > > """
> > > >
> > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures ar= e a misdesign, sadly
> > > >=C2=A0 =C2=A0 =C2=A0retained from the original BitCoin 0= .1.0 Alpha for Windows design, on
> > > >=C2=A0 =C2=A0 =C2=A0par with:
> > > >=C2=A0 =C2=A0 =C2=A0[..]
> > > >
> > > > -=C2=A0 =C2=A0`OP_CAT` and `OP_MULT` and `OP_ADD` and f= riends
> > > >=C2=A0 =C2=A0 =C2=A0[..]
> > > >=C2=A0 =C2=A0 =C2=A0"""
> > > >
> > > >=C2=A0 =C2=A0 =C2=A0OP_CAT is an extremely valuable op c= ode. I understand why it was
> > > >=C2=A0 =C2=A0 =C2=A0removed as the situation at the time= with scripts was dire. However
> > > >=C2=A0 =C2=A0 =C2=A0most of the protocols I've wante= d to build on Bitcoin run into the
> > > >=C2=A0 =C2=A0 =C2=A0limitation that stack values can not= be concatenated. For instance
> > > >=C2=A0 =C2=A0 =C2=A0TumbleBit would have far smaller tra= nsaction sizes if OP_CAT was
> > > >=C2=A0 =C2=A0 =C2=A0supported in Bitcoin. If it happens = to me as a researcher it is
> > > >=C2=A0 =C2=A0 =C2=A0probably holding other people back a= s well. If I could wave a magic
> > > >=C2=A0 =C2=A0 =C2=A0wand and turn on one of the disabled= op codes it would be OP_CAT. Of
> > > >=C2=A0 =C2=A0 =C2=A0course with the change that size of = each concatenated value must be 64
> > > >=C2=A0 =C2=A0 =C2=A0Bytes 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 B= itcoin blocks.
> > > Specifically, it is difficult to determine if a hash on a Me= rkle node is the hash of a Merkle subnode, or a leaf transaction.
> > > My understanding is that this is the reason for now requirin= g transactions to be at least 80 bytes.
> > >
> > > The obvious fix would be to prepend the type of the hashed o= bject, i.e. add at least one byte to determine this type.
> > > Taproot for example uses tagged hash functions, with a diffe= rent tag for leaves, and tagged hashes are just prepend-this-32-byte-consta= nt-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
> > >
> > >
> > > >
> > > >=C2=A0 =C2=A0 =C2=A0On Tue, Oct 1, 2019 at 10:04 PM ZmnS= CPxj via bitcoin-dev
> > > >=C2=A0 =C2=A0 =C2=A0bitcoin-dev@lists.linuxfoundation.or= g wrote:
> > > >
> > > >
> > > > > Good morning lists,
> > > > > Let me propose the below radical idea:
> > > > >
> > > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatur= es are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha fo= r Windows design, on par with:
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A01 RETURN
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0higher-`nSequence= ` replacement
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0DER-encoded pubke= ys
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0unrestricted `scr= iptPubKey`
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0Payee-security-pa= id-by-payer (i.e. lack of P2SH)
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0`OP_CAT` and `OP_= MULT` and `OP_ADD` and friends
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0transaction malle= ability
> > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0probably many mor= e
> > > > >
> > > > > So let me propose the more radical excision, start= ing with SegWit v1:
> > > > >
> > > > > -=C2=A0 =C2=A0Remove `SIGHASH` from signatures. > > > > > -=C2=A0 =C2=A0Put `SIGHASH` on public keys.
> > > > >
> > > > > Public keys are now encoded as either 33-bytes (im= plicit `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 committe= d to on every output `scriptPubKey`, this is automatically output tagging t= o 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-Ta= proot.
> > > > > I propose also the addition of the opcode:
> > > > >
> > > > >=C2=A0 =C2=A0 =C2=A0<sighash> <pubkey> = OP_SETPUBKEYSIGHASH
> > > > >
> > > > >
> > > > > -=C2=A0 =C2=A0`sighash` must be one byte.
> > > > > -=C2=A0 =C2=A0`pubkey` may be the special byte `0x= 1`, meaning "just use the Taproot internal pubkey".
> > > > > -=C2=A0 =C2=A0`pubkey` may be 33-byte public key, = in which case the `sighash` byte is just prepended to it.
> > > > > -=C2=A0 =C2=A0`pubkey` may be 34-byte public key w= ith sighash, in which case the first byte is replaced with `sighash` byte.<= br> > > > > > -=C2=A0 =C2=A0If `sighash` is `0x00` then the resu= lt 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:
> > > > >
> > > > >=C2=A0 =C2=A0 =C2=A0<pubkey> OP_SETPUBKEYSIGH= ASH OP_CHECKSIG
> > > > >
> > > > >
> > > > > Then the sighash can be put in the witness stack a= fter the signature, letting the `SIGHASH` flag be selected at time-of-signi= ng, but only if the SCRIPT specifically is formed to do so.
> > > > > This is malleability-safe as the signature still c= ommits 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` `SIG= HASH_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.li= nuxfoundation.org/mailman/listinfo/lightning-dev
> > >
> > >
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundat= ion.org/mailman/listinfo/lightning-dev


_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/ma= ilman/listinfo/lightning-dev
--000000000000b7dbbf059419efb4--