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
|
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 2F0EB8CC
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 22 Nov 2018 20:53:12 +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 1FD295E2
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 22 Nov 2018 20:53:10 +0000 (UTC)
ARC-Seal: i=1; a=rsa-sha256; t=1542919982; cv=none; d=zoho.com; s=zohoarc;
b=kIY4eXeXK3v7vURU+9K70aHIZPNDRNKb3vctT7z68aSRCBoG63YM6pguXP48YHM1UZxt+tM2lslPrIVyZuzm9RpzOh5YxCd+7i3rJAB/lI2SmNGZiY/A/Wk9BnScX/qFK66P6mBxiDZZlw8gWqQnOFVNCvqfob26OBQjmEA2+2w=
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com;
s=zohoarc; t=1542919982;
h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:To:ARC-Authentication-Results;
bh=WlyM59OEDkYeLF0U7REYULF0wMMjicwpGDBFVTc1+ys=;
b=APdhqeUfZqOUWdERebGyFWgCuqELrhlB7pdcbyOr8AMWP6An905KKFPd0kRWsMiUshEaDmuPwPA+JdnIpLfhw1ey83qXQPCIFDeeLFJru6yWDjii6bfGWmkJPdGt+U+r7RZrTEvJRNetHhT677aloW9/d7FYsxXIqSQ7FvV1OJM=
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 1542919979271609.3178364483915;
Thu, 22 Nov 2018 12:52:59 -0800 (PST)
Content-Type: text/plain;
charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
Date: Fri, 23 Nov 2018 04:52:54 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
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>
To: Russell O'Connor <roconnor@blockstream.io>
X-Mailer: Apple Mail (2.3445.100.39)
X-ZohoMailClient: External
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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-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: Thu, 22 Nov 2018 20:53:12 -0000
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_MASK acceptable, there should be no reason to reject =
OP_CODESEPARATOR.
>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.
> On 23 Nov 2018, at 12:23 AM, Russell O'Connor =
<roconnor@blockstream.io> wrote:
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
>=20
>> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>>=20
>> 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?
>>=20
>> Hopefully my comment is on-topic for this thread:
>>=20
>> 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.
>>=20
>> 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).
>>=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, 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.
>>=20
>> 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
>=20
|
