Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3E54C8BF for ; Fri, 23 Nov 2018 10:47:37 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender-of-o53.zoho.com (sender-of-o53.zoho.com [135.84.80.218]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5221677E for ; Fri, 23 Nov 2018 10:47:35 +0000 (UTC) ARC-Seal: i=1; a=rsa-sha256; t=1542970048; cv=none; d=zoho.com; s=zohoarc; b=aRr9zM1ojfwdW6JtHzjepvmzTuKh7+u87/sBuzX+htMk9Jwy5XXdEZ+gkMHZxLeEN0/lw83q5v2dL1y04yr+q/RsMk6iXnghtDnKfcGtNcvDVjz2D2pHCqIj9t6y1RUHKdoa2gHRs6phTGeBAdtVEyDHrspOqR76wA4UYIf2LFI= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com; s=zohoarc; t=1542970048; h=Content-Type:Cc:Date:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:To:ARC-Authentication-Results; bh=xPdWAo3aK4jMQqDzVCOBMl12zmc4MUgrzh+/iKiXtwQ=; b=UCuqrDqhcVl8cofJdbVb0WR81cqQZBkuBlG2Txj8RCe92lMX3Xuhr6n2A5xQWOjHDhe9X0vqudt/kcaPj2HCxQpr5dSNFHOm/6dmMT6yygl17YxaeqtjCppBn0THJ5A5jap3sck5Nicgwf1dW9M4286yS4bMnHmJNOwIH2lKpmk= ARC-Authentication-Results: i=1; mx.zoho.com; dkim=pass header.i=xbt.hk; spf=pass smtp.mailfrom=jl2012@xbt.hk; dmarc=pass header.from= header.from= Received: from [10.8.0.105] (n218103234118.netvigator.com [218.103.234.118]) by mx.zohomail.com with SMTPS id 1542970034772440.5779598685011; Fri, 23 Nov 2018 02:47:14 -0800 (PST) From: Johnson Lau Message-Id: Content-Type: multipart/alternative; boundary="Apple-Mail=_2045A314-FBA1-4308-A2EE-575C59A225F1" Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\)) Date: Fri, 23 Nov 2018 18:47:10 +0800 In-Reply-To: To: Russell O'Connor References: <64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk> <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk> X-Mailer: Apple Mail (2.3445.100.39) X-ZohoMailClient: External X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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: Sat, 24 Nov 2018 02:17:49 +0000 Cc: bitcoin-dev 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: Fri, 23 Nov 2018 10:47:37 -0000 --Apple-Mail=_2045A314-FBA1-4308-A2EE-575C59A225F1 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 >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. In the existing sighash (i.e. legacy and BIP143), there are 6 canonical = SIGHASH types: 1, 2, 3, 0x81, 0x82, 0x83. In consensus, however, all 256 = types are valid and distinct. An adversarial miner could use = non-standard sighash types to nullify any attempt to cache sighash = values (i.e. you have to compute a new tx digest for every OP_CHECKSIG, = even without using OP_CODESEPARATOR). The only way to prevent this is reject OP_CODESEPARATOR, = FindAndDelete(), and non-standard SIGHASH with a softfork. However, this = doesn=E2=80=99t work in the next-generation SIGHASH, as tens of standard = sighash types will exist. And, more importantly, sighash cache is no = longer necessary in segwit, with the legacy O(n^2) hash bug being fixed. In summary, sighash cache is not necessary nor efficient in the = next-generation SIGHASH, and is not a sufficient reason to remove = OP_CODESEPARATOR, especially when people find OP_CODESEPARATOR useful in = some way. But just to be clear, I think OP_CODESEPARATOR should be deprecated in = legacy scripts. There is a general negative sentiment against = OP_CODESEPARATOR but I think we need to evaluate case by case. > On 23 Nov 2018, at 6:10 AM, Russell O'Connor = wrote: >=20 >=20 >=20 > 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. >=20 > >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_MASK acceptable, there should be no reason to reject = OP_CODESEPARATOR. >=20 > 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. >=20 > 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. >=20 > 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. >=20 > >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 = counting=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. >=20 --Apple-Mail=_2045A314-FBA1-4308-A2EE-575C59A225F1 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 >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.

In the existing sighash (i.e. legacy = and BIP143), there are 6 canonical SIGHASH types: 1, 2, 3, 0x81, 0x82, = 0x83. In consensus, however, all 256 types are valid and distinct. An = adversarial miner could use non-standard sighash types to nullify any = attempt to cache sighash values (i.e. you have to compute a new tx = digest for every OP_CHECKSIG, even without using = OP_CODESEPARATOR).

The only way to prevent this is reject OP_CODESEPARATOR, = FindAndDelete(), and non-standard SIGHASH with a softfork. However, this = doesn=E2=80=99t work in the next-generation SIGHASH, as tens of standard = sighash types will exist. And, more importantly, sighash cache is no = longer necessary in segwit, with the legacy O(n^2) hash bug being = fixed.

In = summary, sighash cache is not necessary nor efficient in the = next-generation SIGHASH, and is not a sufficient reason to remove = OP_CODESEPARATOR, especially when people find OP_CODESEPARATOR useful in = some way.

But = just to be clear, I think OP_CODESEPARATOR should be deprecated in = legacy scripts. There is a general negative sentiment against = OP_CODESEPARATOR but I think we need to evaluate case by case.

On 23 Nov 2018, at 6:10 AM, Russell O'Connor <roconnor@blockstream.io> wrote:



On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau = <jl2012@xbt.hk> = 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_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.  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 = counting=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.


= --Apple-Mail=_2045A314-FBA1-4308-A2EE-575C59A225F1--