path: root/ba/1947441034d7114dd9fb3ee847c2c1a216afd0

Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 569B38D4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 22 Nov 2018 16:24:08 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it1-f193.google.com (mail-it1-f193.google.com
	[209.85.166.193])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 67A815D4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 22 Nov 2018 16:24:07 +0000 (UTC)
Received: by mail-it1-f193.google.com with SMTP id c9so14554781itj.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 22 Nov 2018 08:24:07 -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=jTGWgjjtpBexp6f03xiG4FsNNBT4PpDvCcjl4q7awX8=;
	b=nkz+JH1G8hKClKGze9SKATfQmRhYktgLhbOicCLO0VZoVdvBWrOJaaOgm7ujK5qnQz
	sCDe3aau3Xiey28F2wzeiVGNeP4XSvCP+52DUeQMcFtMUEQrJJWs0vj/M28ioyZHhEzD
	r5pT+ELepU/g+dIV8Phj6i0FL+8skZl+aWu7A=
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=jTGWgjjtpBexp6f03xiG4FsNNBT4PpDvCcjl4q7awX8=;
	b=mxvLMszuOwhDKitSUK9gHsnyANjnr09Jc1L4nq7Es5TMA8VQ9OsTodbB0PyTbpdY5+
	XTuhQyinZOKMQCO7Fd5BQo0hNf9NvPAlz2uhIhiWT44wuRmoq1SJVheUCiJksLVqlCI0
	TDiLlPmvb81n+qPyFEXLTvczDaVtroh0y/FIwRcyYo5rNtHZuQyOiYnSwMFPGcxwyxiO
	8qfNJZ4lrixEDShqJDvSMrKMiOdJPoxU0cDaWjagCE2EWFftgTLDU7rSAXORQvtNx+bP
	VBSBDi0OtCA4XR37ueIYME/6eyvgGmDUXm95ju5AcatOAh2fssSKaTH63L++SXwqNbp0
	omyw==
X-Gm-Message-State: AGRZ1gJDHjtqw641IToX8yRsq3/MVRAdk5yMfijpUCEDdMcunNgG+2iL
	0MSoY1d/Gy37zgXYQY/lqz+EGagtUt7w7+yx0YnWdA==
X-Google-Smtp-Source: AFSGD/X+ju64PMRzNHsEUSySZFj7jl/MdTpldwwoSmqWEjIYc2Tv6/HnGhSfuIutoDr17JAjJocGKJ102+fz26SKPZE=
X-Received: by 2002:a24:79c2:: with SMTP id
	z185-v6mr11811299itc.101.1542903846624; 
	Thu, 22 Nov 2018 08:24:06 -0800 (PST)
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"
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 <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: Thu, 22 Nov 2018 16:24:08 -0000

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