Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 49409ACC; Fri, 4 Oct 2019 07:00:20 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40133.protonmail.ch (mail-40133.protonmail.ch [185.70.40.133]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B8A6C3D0; Fri, 4 Oct 2019 07:00:18 +0000 (UTC) Date: Fri, 04 Oct 2019 07:00:13 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=default; t=1570172416; bh=Dkl+quRwsD3lw4Ikj5nbMsVWKbV9/S5kN50Q0gwPHbM=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References: Feedback-ID:From; b=N0mPSg3BJRvhRMvG0vlIXEbDqfOeMSXfM01XSmTem9IkINA3cFEclSOckRgAet8xE P0Qv63pRWGXpPwvaEhrJ+9jx+h8Q4X2ze99j+5whA3LjYJBYKsHdsz+SW3Hc4m7vXy bcxw6OoiyB7XWJAPgB+ajzklP+x+jxZjWHZrDNZ8= To: Jeremy From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <87wodp7w9f.fsf@gmail.com> <20191001155929.e2yznsetqesx2jxo@erisian.com.au> Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM, FROM_LOCAL_NOVOWEL, RCVD_IN_DNSWL_LOW 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 07:00:20 -0000 Good morning Jeremy, > Awhile back, Ethan and I discussed having, rather than OP_CAT, an OP_SHA2= 56STREAM that uses the streaming properties of a SHA256 hash function to al= low 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 <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 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 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 wrote= : > > > > > > Good morning Ethan, > > > > > > > > > > To avoid derailing the NO_INPUT conversation, I have changed the > > > > subject to OP_CAT. > > > > > > > > Responding to: > > > > """ > > > > > > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a misdesig= n, sadly > > > >=C2=A0 =C2=A0 =C2=A0retained from the original BitCoin 0.1.0 Alpha f= or 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 under= stand why it was > > > >=C2=A0 =C2=A0 =C2=A0removed as the situation at the time with script= s was dire. However > > > >=C2=A0 =C2=A0 =C2=A0most of the protocols I've wanted to build on Bi= tcoin run into the > > > >=C2=A0 =C2=A0 =C2=A0limitation that stack values can not be concaten= ated. For instance > > > >=C2=A0 =C2=A0 =C2=A0TumbleBit would have far smaller transaction siz= es if OP_CAT was > > > >=C2=A0 =C2=A0 =C2=A0supported in Bitcoin. If it happens to me as a r= esearcher 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 concate= nated 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 bl= ocks. > > > 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 transac= tions 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 > > > > > > > > > > > > > >=C2=A0 =C2=A0 =C2=A0On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bit= coin-dev > > > >=C2=A0 =C2=A0 =C2=A0bitcoin-dev@lists.linuxfoundation.org wrote: > > > > > > > > > > > > > Good morning lists, > > > > > Let me propose the below radical idea: > > > > > > > > > > -=C2=A0 =C2=A0`SIGHASH` flags attached to signatures are a misdes= ign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows desig= n, 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 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-payer (i.= e. lack of P2SH) > > > > >=C2=A0 =C2=A0 =C2=A0-=C2=A0 =C2=A0`OP_CAT` and `OP_MULT` and `OP_A= DD` 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 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 (implicit `SIGHASH= _ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pu= bkey coordinate). > > > > > `OP_CHECKSIG` and friends then look at the public key to determin= e sighash algorithm rather than the signature. > > > > > As we expect public keys to be indirectly committed to on every o= utput `scriptPubKey`, this is automatically output tagging to allow particu= lar `SIGHASH`. > > > > > However, we can then utilize the many many ways to hide public ke= ys away until they are needed, exemplified in MAST-inside-Taproot. > > > > > I propose also the addition of the opcode: > > > > > > > > > >=C2=A0 =C2=A0 =C2=A0 OP_SETPUBKEYSIGHASH > > > > > > > > > > > > > > > -=C2=A0 =C2=A0`sighash` must be one byte. > > > > > -=C2=A0 =C2=A0`pubkey` may be the special byte `0x1`, meaning "ju= st use the Taproot internal pubkey". > > > > > -=C2=A0 =C2=A0`pubkey` may be 33-byte public key, in which case t= he `sighash` byte is just prepended to it. > > > > > -=C2=A0 =C2=A0`pubkey` may be 34-byte public key with sighash, 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 at tim= e-of-spending rather than time-of-payment. > > > > > This is done by using the script: > > > > > > > > > >=C2=A0 =C2=A0 =C2=A0 OP_SETPUBKEYSIGHASH OP_CHECKSIG > > > > > > > > > > > > > > > Then the sighash can be put in the witness stack after the signat= ure, 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 `SIGHA= SH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_A= LL`). > > > > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, a= s 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