MIME-Version: 1.0
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>
In-Reply-To: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 22 Nov 2018 17:10:11 -0500
Message-ID: <CAMZUoKkdjHYd8BR6PCae-UG_QRoujW36kYf8s4Gk2FVBeSJnrw@mail.gmail.com>
To: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/alternative; boundary="00000000000014b1a9057b482254"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
Precedence: list

--00000000000014b1a9057b482254
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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_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

<div dir=3D"ltr"><br><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu=
, Nov 22, 2018 at 3:53 PM Johnson Lau &lt;<a href=3D"mailto:jl2012@xbt.hk">=
jl2012@xbt.hk</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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.<br>
<br>
&gt;each call to this operation effectively takes O(script-size) time<br>
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 <a =
href=3D"https://github.com/bitcoin/bitcoin/pull/14786" rel=3D"noreferrer" t=
arget=3D"_blank">https://github.com/bitcoin/bitcoin/pull/14786</a>)<br>
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.<br></blockquote><div>=
<br></div><div>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.<br></div></div><div class=3D"gmail_quote"><div><br><=
/div><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&#39;t=
 such a big deal.</div><div><br></div><div>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.<br></div><br></div><div class=3D"gmai=
l_quote">&gt;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...<br><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 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.<br></blockquote><br></div></div>

--00000000000014b1a9057b482254--