path: root/14/c17587ebe062059159c3488496fb2bb804da65

Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 3E54C8BF
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	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=<jl2012@xbt.hk> header.from=<jl2012@xbt.hk>
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 <jl2012@xbt.hk>
Message-Id: <D8767C89-06AF-4FA7-B640-E99FE8A443C5@xbt.hk>
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: <CAMZUoKkdjHYd8BR6PCae-UG_QRoujW36kYf8s4Gk2FVBeSJnrw@mail.gmail.com>
To: Russell O'Connor <roconnor@blockstream.io>
References: <CAPg+sBhuPG-2GXc+Bp0yv5ywry2fk56LPLT4AY0Kcs+YEoz4FA@mail.gmail.com>
	<CAMZUoK==Bdn73Lc=swgf2F5_mqE84TR1GRBFhrFkn7kab4jBaw@mail.gmail.com>
	<64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk>
	<CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
	<8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
	<CAMZUoKkdjHYd8BR6PCae-UG_QRoujW36kYf8s4Gk2FVBeSJnrw@mail.gmail.com>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <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, 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 <roconnor@blockstream.io> =
wrote:
>=20
>=20
>=20
> On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau <jl2012@xbt.hk =
<mailto: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.
>=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 =
<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

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; line-break: after-white-space;" =
class=3D"">&gt;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.<div class=3D""><br =
class=3D""></div><div class=3D"">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).</div><div class=3D""><br class=3D""></div><div =
class=3D"">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.</div><div class=3D""><br class=3D""></div><div class=3D"">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.</div><div class=3D""><br class=3D""></div><div class=3D"">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.</div><div =
class=3D""><div><br class=3D""><blockquote type=3D"cite" class=3D""><div =
class=3D"">On 23 Nov 2018, at 6:10 AM, Russell O'Connor &lt;<a =
href=3D"mailto:roconnor@blockstream.io" =
class=3D"">roconnor@blockstream.io</a>&gt; wrote:</div><br =
class=3D"Apple-interchange-newline"><div class=3D""><div dir=3D"ltr" =
class=3D""><br class=3D""><br class=3D""><div class=3D"gmail_quote"><div =
dir=3D"ltr" class=3D"">On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau =
&lt;<a href=3D"mailto:jl2012@xbt.hk" class=3D"">jl2012@xbt.hk</a>&gt; =
wrote:<br class=3D""></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc =
solid;padding-left:1ex">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.<br =
class=3D"">
<br class=3D"">
&gt;each call to this operation effectively takes O(script-size) time<br =
class=3D"">
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 <a =
href=3D"https://github.com/bitcoin/bitcoin/pull/14786" rel=3D"noreferrer" =
target=3D"_blank" =
class=3D"">https://github.com/bitcoin/bitcoin/pull/14786</a>)<br =
class=3D"">
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.<br class=3D""></blockquote><div class=3D""><br =
class=3D""></div><div class=3D"">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.&nbsp; I understood that this issue was the main motivation for =
wanting to deprecate OP_CODESEPARATOR and remove it from later versions =
of script.<br class=3D""></div></div><div class=3D"gmail_quote"><div =
class=3D""><br class=3D""></div><div class=3D"">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.</div><div class=3D""><br class=3D""></div><div class=3D"">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.<br class=3D""></div><br class=3D""></div><div =
class=3D"gmail_quote">&gt;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...<br =
class=3D""><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 =
.8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br =
class=3D""></blockquote><br class=3D""></div></div>
</div></blockquote></div><br class=3D""></div></body></html>=

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