From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id B118E105B; Fri, 4 Oct 2019 05:02:30 +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 00EFEA8; Fri, 4 Oct 2019 05:02:28 +0000 (UTC) Received: from mail-io1-f49.google.com (mail-io1-f49.google.com [209.85.166.49]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id x9452Qoa030285 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT); Fri, 4 Oct 2019 01:02:27 -0400 Received: by mail-io1-f49.google.com with SMTP id n197so10750982iod.9; Thu, 03 Oct 2019 22:02:27 -0700 (PDT) X-Gm-Message-State: APjAAAUdxtBMvCJA4Le/V37GyRZRHvChHqFC4/1BmFoYTn4f712lsk6E SVPvdD4CgHdCd8MQ6va8zrFMvJgfoURfnytScqU= X-Google-Smtp-Source: APXvYqxX4wp0qdK3i3VD9SOxl3VOXCVlx92+opnaNo8l4Jj3R73TsuKJFt7wqLCzF3BUrMw6mlEOHyEG07SINCvMia8= X-Received: by 2002:a5e:8902:: with SMTP id k2mr11708140ioj.49.1570165346480; Thu, 03 Oct 2019 22:02:26 -0700 (PDT) MIME-Version: 1.0 References: <87wodp7w9f.fsf@gmail.com> <20191001155929.e2yznsetqesx2jxo@erisian.com.au> In-Reply-To: From: Jeremy Date: Thu, 3 Oct 2019 22:02:14 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Ethan Heilman Content-Type: multipart/alternative; boundary="000000000000b73a1105940e9b4e" 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 05:02:30 -0000 --000000000000b73a1105940e9b4e Content-Type: text/plain; charset="UTF-8" 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 -- @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 > --000000000000b73a1105940e9b4e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Awhile back, Ethan and I = discussed having, rather than OP_CAT, an OP_SHA256STREAM that uses the stre= aming properties of a SHA256 hash function to allow concatenation of an unl= imited amount of data, provided the only use is to hash it.

You can t= hen use it perhaps as follows:

// start a new hash with item
OP_SHA256STREAM=C2=A0 (-1) -> [state]<= /div>
// Add item to the hash in state
<= /div>
OP_SHA256STREAM n [item] [state] -&g= t; [state]
// Finalize
OP_SHA256STREAM (-2) [state] -> [Hash]

&= lt;-1> OP_SHA256STREAM <tag> <subnode 2> <subnode 3> &= lt;3> OP_SHA256STREAM <-2> OP_SHA256STREAM


Or it coul




On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman <eth3rs@gmail.com> wrote:
I hope you are having an great afterno= on 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 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=3D3 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<= br> > > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a misdes= ign, 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 friends
> >=C2=A0 =C2=A0 =C2=A0[..]
> >=C2=A0 =C2=A0 =C2=A0"""
> >
> >=C2=A0 =C2=A0 =C2=A0OP_CAT is an extremely valuable op code. I und= erstand why it was
> >=C2=A0 =C2=A0 =C2=A0removed as the situation at the time with scri= pts was dire. However
> >=C2=A0 =C2=A0 =C2=A0most of the protocols I've wanted to build= on Bitcoin run into the
> >=C2=A0 =C2=A0 =C2=A0limitation that stack values can not be concat= enated. For instance
> >=C2=A0 =C2=A0 =C2=A0TumbleBit would have far smaller transaction s= izes 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 as 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 conca= tenated 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 Bitcoin blo= cks.
> 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 transact= ions 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 f= or leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-b= efore-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` w= ith 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 ZmnSCPxj via b= itcoin-dev
> >=C2=A0 =C2=A0 =C2=A0bitcoin-dev@lists.linuxfoundation.org wrot= e:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a m= isdesign, sadly retained from the original BitCoin 0.1.0 Alpha for 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` replacem= ent
> > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0DER-encoded pubkeys
> > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0unrestricted `scriptPubKey`=
> > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0Payee-security-paid-by-paye= r (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 malleability > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0probably many more
> > >
> > > So let me propose the more radical excision, starting with S= egWit 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 (implicit `SI= GHASH_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 det= ermine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on ev= ery output `scriptPubKey`, this is automatically output tagging to allow pa= rticular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide publ= ic keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > >=C2=A0 =C2=A0 =C2=A0<sighash> <pubkey> OP_SETPUBK= EYSIGHASH
> > >
> > >
> > > -=C2=A0 =C2=A0`sighash` must be one byte.
> > > -=C2=A0 =C2=A0`pubkey` may be the special byte `0x1`, meanin= g "just use the Taproot internal pubkey".
> > > -=C2=A0 =C2=A0`pubkey` may be 33-byte public key, in which c= ase the `sighash` byte is just prepended to it.
> > > -=C2=A0 =C2=A0`pubkey` may be 34-byte public key with sighas= h, in which case the first byte is replaced with `sighash` byte.
> > > -=C2=A0 =C2=A0If `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 a= t time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > >=C2=A0 =C2=A0 =C2=A0<pubkey> OP_SETPUBKEYSIGHASH OP_CHE= CKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the s= ignature, letting the `SIGHASH` flag be selected at time-of-signing, but on= ly 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-`SIGH= ASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGL= E`, as they are allowed only if the output specifically says they are allow= ed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoun= dation.org/mailman/listinfo/bitcoin-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
--000000000000b73a1105940e9b4e--