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 B90BD25A for ; Thu, 22 Nov 2018 22:10:24 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it1-f173.google.com (mail-it1-f173.google.com [209.85.166.173]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 289695D4 for ; Thu, 22 Nov 2018 22:10:23 +0000 (UTC) Received: by mail-it1-f173.google.com with SMTP id i7so15952881iti.2 for ; Thu, 22 Nov 2018 14:10:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Z+FCY9qEN93e9BkC6UTVJnapMNBcvJJEddAH2G3k8ic=; b=H3sdf7CpIIFd3jphK0LmyRPEuZdfMLIBm1HhOX44/5J+etZ1to4y4Z/VpULsd6fKxE u5ypvtqx5unct+j5BcfwXGCRdwifLuyHJiRgtiwZ/T3yOxXeozNIFPAAiFHe2wfixjY9 bByS2tcurEX+/DxOXH3yswzBeBjX1Qii57tXc= 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=Z+FCY9qEN93e9BkC6UTVJnapMNBcvJJEddAH2G3k8ic=; b=mT7aikPlYu5mnFfA3Mx+DTvhjVTgbHw0O21SCE47pK4R8quwNT7SVO8V3bhtsx7bTY 7ympCHjPCWco3a6pR0fvkkr+ZT46dpI3R8UNOL6jXY0uq8wBasj6zeCkZlbpvObYshsX sBK2rJ+YNZLwjAJokTDj2seyjZkekJT8qx1E9esYkB/iHsUoMNKYaenHGO0H24vHzQtQ klUMntYaeq+/3+iig6OGiPg6LceAzbWTQiYoZJSA6jzQXxpWM5E19ULq+s9xNmjMNfF6 4xfi4UTgpWLTjzXYsmKzTpvlK4oK1qGniRYra2AwJ6RHEXVZSli3qtmATnMxjypLosiL wAqw== X-Gm-Message-State: AGRZ1gInEwS9D5lRm10ScT2lmMu1kbzFSgY7HibkXr0e1+FFmp07zWzX XjlBzsug4X9A6iQoE5PYlXdmmdvNpJB8VRvUgY6+IA== X-Google-Smtp-Source: AJdET5eoPbr98bcojJC0mHHCQs9F2aEB4sCmqXlJ5KUP2XHQm43gtbGy4eGwjNECEN1Csm1SXuypTHINc6ey6mKjF74= X-Received: by 2002:a24:d4:: with SMTP id 203-v6mr10484474ita.26.1542924623189; Thu, 22 Nov 2018 14:10:23 -0800 (PST) MIME-Version: 1.0 References: <64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk> <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk> In-Reply-To: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk> From: "Russell O'Connor" Date: Thu, 22 Nov 2018 17:10:11 -0500 Message-ID: To: Johnson Lau Content-Type: multipart/alternative; boundary="00000000000014b1a9057b482254" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, 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 X-Mailman-Approved-At: Fri, 23 Nov 2018 04:04:44 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT 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: Thu, 22 Nov 2018 22:10:24 -0000 --00000000000014b1a9057b482254 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau wrote: > Assuming a script size of 128 bytes (including SHA256 padding), 2^20 > scripts is 134MB. Double it to 268MB for the merkle branch hashes. With > roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). However, > memory use is not considered. > > >each call to this operation effectively takes O(script-size) time > I=E2=80=99m not sure if this is correct. Actually, > CTransactionSignatureSerializer() scans every script for OP_CODESEPARATOR= . > Scripts with and without OP_CODESEPARATOR should take exactly the same > O(script-size) time (see https://github.com/bitcoin/bitcoin/pull/14786) > Also, this is no longer a concern under segwit (BIP143), which > CTransactionSignatureSerializer() is not used. Actually, OP_CODESEPARATOR > under segwit is way simpler than the proposed OP_MASK. If one finds OP_MA= SK > acceptable, there should be no reason to reject OP_CODESEPARATOR. > Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair requires recomputing a new #5. scriptCode from BIP 143, and hence computes a new transaction digest. I understood that this issue was the main motivation for wanting to deprecate OP_CODESEPARATOR and remove it from later versions of script. However, given that we are looking at a combinatorial explosion in SIGHASH flag combinations already, coupled with existing SigOp limitations, maybe the cost of recomputing scriptCode with OP_CODESEPARATOR isn't such a big deal. And even if we choose remove the behavior of OP_CODESEPARATOR in new versions of Script, it seems more than 30 layers of sequential OP_IFs can be MASTified, so there is no need to use OP_CODESEPARATOR within that limit= . >One suggestion I heard (I think I heard it from Pieter) to achieve the above is to add an internal counter that increments on every control flow operator,=E2=80=A6=E2=80=A6... > If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator cou= nting=E2=80=9D, > I=E2=80=99d rather choose OP_CODESEPARATOR. At least we don=E2=80=99t nee= d to add more > lines to the consensus code, just for something that is mostly archivable > with MAST. > --00000000000014b1a9057b482254 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


On Thu= , Nov 22, 2018 at 3:53 PM Johnson Lau <= jl2012@xbt.hk> wrote:
Assumi= ng a script size of 128 bytes (including SHA256 padding), 2^20 scripts is 1= 34MB. Double it to 268MB for the merkle branch hashes. With roughly 100MB/s= , this should take 2.5s (or 42min for 30 levels). However, memory use is no= t considered.

>each call to this operation effectively takes O(script-size) time
I=E2=80=99m not sure if this is correct. Actually, CTransactionSignatureSer= ializer() scans every script for OP_CODESEPARATOR. Scripts with and without= OP_CODESEPARATOR should take exactly the same O(script-size) time (see https://github.com/bitcoin/bitcoin/pull/14786)
Also, this is no longer a concern under segwit (BIP143), which CTransaction= SignatureSerializer() is not used. Actually, OP_CODESEPARATOR under segwit = is way simpler than the proposed OP_MASK. If one finds OP_MASK acceptable, = there should be no reason to reject OP_CODESEPARATOR.
=
Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair= requires recomputing a new #5. scriptCode from BIP 143, and hence computes= a new transaction digest.=C2=A0 I understood that this issue was the main = motivation for wanting to deprecate OP_CODESEPARATOR and remove it from lat= er versions of script.

<= /div>
However, given that we are looking at a combinatorial explosion i= n SIGHASH flag combinations already, coupled with existing SigOp limitation= s, maybe the cost of recomputing scriptCode with OP_CODESEPARATOR isn't= such a big deal.

And even if we choose remove the= behavior of OP_CODESEPARATOR in new versions of Script, it seems more than= 30 layers of sequential OP_IFs can be MASTified, so there is no need to us= e OP_CODESEPARATOR within that limit.

>One suggestion I heard (I think I heard it from Pieter) to ach= ieve the above is to add an internal counter that increments on every contr= ol flow operator,=E2=80=A6=E2=80=A6...
If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator count= ing=E2=80=9D, I=E2=80=99d rather choose OP_CODESEPARATOR. At least we don= =E2=80=99t need to add more lines to the consensus code, just for something= that is mostly archivable with MAST.

--00000000000014b1a9057b482254--