From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <eth3rs@gmail.com> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9488C14F3; Fri, 4 Oct 2019 00:48:56 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pg1-f176.google.com (mail-pg1-f176.google.com [209.85.215.176]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B5CC434F; Fri, 4 Oct 2019 00:48:54 +0000 (UTC) Received: by mail-pg1-f176.google.com with SMTP id q1so2778425pgb.0; Thu, 03 Oct 2019 17:48:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=HhvsQ2qy5ZQ6ans6rhiJNESeszyIQt+6+yngezPyUBc=; b=XZ9s9KE+sXmfKMplnfVjGkMLdtTqhcRag3sYQuz972ASuze9z0EEpH8U0bxyp48PAB rV9zzVei9iKrGaYMFJC2CqPa/svLwbySqNxHKHqcfZ+2zyuGDGIJBG0vJ2QQ2GAUMD0u O2QvCCGA3ixj7T1GJBX/upunJg4qnsLyyfV9sx4NtnAh384FayYQPf7dMQy05doOKjVJ vFw2rAbTnu5XTj3ybK49JFO7iY0JW5A+Yu2F3Ak4E49hX4dkZq2zg/hIdkwVJsIRaW5I NENmU0FGtVXIpsiQkNWtxxOSWZ9A7jnxCQy/jCx0VIXMjUWEhvgZqkBI3Q91/3z4vKyt FYxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=HhvsQ2qy5ZQ6ans6rhiJNESeszyIQt+6+yngezPyUBc=; b=OAEHgqSbzny9MKVkJ65/UWXDMqkBukqpUEUXmy2WLAuwH1oSGv+bBeqUOJDM1O/Pi/ 8fl7DEFYPcfcUsgo7he3gLMNrHdcck9RN+PWH09s6Z9r3QbMl2evl+oYUQTXjqHakFSR fZgqoIgACCwCz35vxEngN/GdpMh0jqVZ7RxjZJYKoUiy25YMudXk4qCsoQs4rpPWLLRC cs96KYLK0b2oO/c4OHVHAJzWBoZ7Y91+kmN203qiTT6FwleCaSqodr1SJ0VH4tFVrhzd UkwXoKFxvXLdTrmuUoUsODGkFswPjpgDR8u03cQw2jCkxQrQpOC+SB4LkxtCk2w5Wm4X csJQ== X-Gm-Message-State: APjAAAWXCieiTygridXBvZNeyMc/InPdOn0Xw1MVRbll0ZYqij1t8i0O +CTEYCZ8rwolg1O9138qeTzWGUTxb86Ok0oxb/s= X-Google-Smtp-Source: APXvYqxbFUPcbiF2oCELgfyG303OLXC03fxuSPdIv5Jm/RK/eAiM8HUcDXH+gQFvVGE5juVJ/jrDoEdyBTGxOAOAyhk= X-Received: by 2002:a63:4d61:: with SMTP id n33mr12427828pgl.158.1570150133899; Thu, 03 Oct 2019 17:48:53 -0700 (PDT) MIME-Version: 1.0 References: <87wodp7w9f.fsf@gmail.com> <20191001155929.e2yznsetqesx2jxo@erisian.com.au> <CR-etCjXB-JWkvecjDog4Pkq1SuLUgndtSrZo-V4f4EGcNXzNCeAHRvCZGrxDWw7aHVdDY0pAF92jNLb_Hct0bMb3ew6JEpB9AfIm1tSGaQ=@protonmail.com> <CAEM=y+XbP3Dn7X8rHu7h0vbX6DkKA0vFK5nQqzcJ_V+D4EVMmw@mail.gmail.com> <C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com> In-Reply-To: <C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com> From: Ethan Heilman <eth3rs@gmail.com> Date: Thu, 3 Oct 2019 20:48:17 -0400 Message-ID: <CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com> To: ZmnSCPxj <ZmnSCPxj@protonmail.com> Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE 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 <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 X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Fri, 04 Oct 2019 00:48:56 -0000 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 > >