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>
In-Reply-To: <64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 22 Nov 2018 11:23:54 -0500
Message-ID: <CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
To: Johnson Lau <jl2012@xbt.hk>
Content-Type: multipart/alternative; boundary="000000000000b38d81057b434b21"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
Precedence: list

--000000000000b38d81057b434b21
Content-Type: text/plain; charset="UTF-8"

I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can be
replaced by a Merklized Script tree of that depth in practice.

I'm concerned that at script creation time it takes exponential time to
complete a Merkle root of depth 'n'.  Can anyone provide benchmarks or
estimates of how long it takes to compute a Merkle root of a full tree of
various depths on typical consumer hardware?  I would guess things stop
becoming practical at a depth of 20-30.

On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau <jl2012@xbt.hk> wrote:

> With MAST in taproot, OP_IF etc become mostly redundant, with worse
> privacy. To maximise fungibility, we should encourage people to use MAST,
> instead of improve the functionality of OP_IF and further complicate the
> protocol.
>
>
> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> So my question is whether anyone can see ways in which this introduces
>> redundant flexibility, or misses obvious use cases?
>>
>
> Hopefully my comment is on-topic for this thread:
>
> Given that we want to move away from OP_CODESEPARATOR, because each call
> to this operation effectively takes O(script-size) time, we need a
> replacement for the functionality it currently provides.  While perhaps the
> original motivation for OP_CODESEPARTOR is surrounded in mystery, it
> currently can be used (or perhaps abused) for the task of creating
> signature that covers, not only which input is being signed, but which
> specific branch within that input Script code is being signed for.
>
> For example, one can place an OP_CODESEPARATOR within each branch of an IF
> block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG
> operation.  By doing so, signatures created for one clause cannot be used
> as signatures for another clause.  Since different clauses in Bitcoin
> Script may be enforcing different conditions (such as different time-locks,
> hash-locks, etc), it is useful to be able to sign in such a way that your
> signature is only valid when the conditions for a particular branch are
> satisfied.  In complex Scripts, it may not be practical or possible to use
> different public keys for every different clause. (In practice, you will be
> able to get away with fewer OP_CODESEPARATORS than one in every IF block).
>
> 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, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover
> the value of this counter.  Equivalently we divide every Bitcoin Script
> program into blocks deliminated by these control flow operator and have the
> signature cover the index of the block that the OP_CHECKSIG occurs within.
> More specifically, we will want a SigHash flag to enables/disable the
> signature covering this counter.
>
> There are many different ways one might go about replacing the remaining
> useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be
> happy with any solution.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>

--000000000000b38d81057b434b21
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I see, so your suggestion is that a sequence of OP_IF=
 ... OP_ENDIF can be replaced by a Merklized Script tree of that depth in p=
ractice.<br></div><div><br></div><div>I&#39;m concerned that at script crea=
tion time it takes exponential time to complete a Merkle root of depth &#39=
;n&#39;.=C2=A0 Can anyone provide benchmarks or estimates of how long it ta=
kes to compute a Merkle root of a full tree of various depths on typical co=
nsumer hardware?=C2=A0 I would guess things stop becoming practical at a de=
pth of 20-30.<br></div><div><br><div class=3D"gmail_quote"><div dir=3D"ltr"=
>On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau &lt;<a href=3D"mailto:jl2012@x=
bt.hk">jl2012@xbt.hk</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div style=3D"word-wrap:break-word;line-break:after-white-space">With MAST=
 in taproot, OP_IF etc become mostly redundant, with worse privacy. To maxi=
mise fungibility, we should encourage people to use MAST, instead of improv=
e the functionality of OP_IF and further complicate the protocol.<div><br><=
/div><div><div><br><blockquote type=3D"cite"><div>On 22 Nov 2018, at 1:07 A=
M, Russell O&#39;Connor via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@l=
ists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundati=
on.org</a>&gt; wrote:</div><br class=3D"m_-4299852792247931392Apple-interch=
ange-newline"><div><div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"=
ltr">On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev &lt;<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bit=
coin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">So my question is whether anyone can see ways in which this =
introduces<br>
redundant flexibility, or misses obvious use cases?<br></blockquote><div><b=
r></div><div>Hopefully my comment is on-topic for this thread:</div><div><b=
r></div><div>Given that we want to move away from OP_CODESEPARATOR, because=
 each call to this operation effectively takes O(script-size) time, we need=
 a replacement for the functionality it currently provides.=C2=A0 While per=
haps the original motivation for OP_CODESEPARTOR is surrounded in mystery, =
it currently can be used (or perhaps abused) for the task of creating signa=
ture that covers, not only which input is being signed, but which specific =
branch within that input Script code is being signed for.</div><div><br></d=
iv><div>For example, one can place an OP_CODESEPARATOR within each branch o=
f an IF block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG op=
eration.=C2=A0 By doing so, signatures created for one clause cannot be use=
d as signatures for another clause.=C2=A0 Since different clauses in Bitcoi=
n Script may be enforcing different conditions (such as different time-lock=
s, hash-locks, etc), it is useful to be able to sign in such a way that you=
r signature is only valid when the conditions for a particular branch are s=
atisfied.=C2=A0 In complex Scripts, it may not be practical or possible to =
use different public keys for every different clause. (In practice, you wil=
l be able to get away with fewer OP_CODESEPARATORS than one in every IF blo=
ck).<br></div><div><br></div><div>One suggestion I heard (I think I heard i=
t from Pieter) to achieve the above is to add an internal counter that incr=
ements on every control flow operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, =
and have the signature cover the value of this counter.=C2=A0 Equivalently =
we divide every Bitcoin Script program into blocks deliminated by these con=
trol flow operator and have the signature cover the index of the block that=
 the OP_CHECKSIG occurs within.=C2=A0 More specifically, we will want a Sig=
Hash flag to enables/disable the signature covering this counter.<br></div>=
<div><br></div><div>There are many different ways one might go about replac=
ing the remaining useful behaviour of OP_CODESEPARATOR than the one I gave =
above. I would be happy with any solution.<br></div></div></div>
_______________________________________________<br>bitcoin-dev mailing list=
<br><a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a><br><a href=3D"https://lists.l=
inuxfoundation.org/mailman/listinfo/bitcoin-dev" target=3D"_blank">https://=
lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br></div></block=
quote></div><br></div></div></blockquote></div></div></div>

--000000000000b38d81057b434b21--