summaryrefslogtreecommitdiff
path: root/ba/1947441034d7114dd9fb3ee847c2c1a216afd0
blob: cd882fc5a95834cabd185102c916050830dfb62e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
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--