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
211
212
213
214
215
216
217
|
Return-Path: <eth3rs@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9488C14F3;
Fri, 4 Oct 2019 00:48:56 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pg1-f176.google.com (mail-pg1-f176.google.com
[209.85.215.176])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B5CC434F;
Fri, 4 Oct 2019 00:48:54 +0000 (UTC)
Received: by mail-pg1-f176.google.com with SMTP id q1so2778425pgb.0;
Thu, 03 Oct 2019 17:48:54 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=HhvsQ2qy5ZQ6ans6rhiJNESeszyIQt+6+yngezPyUBc=;
b=XZ9s9KE+sXmfKMplnfVjGkMLdtTqhcRag3sYQuz972ASuze9z0EEpH8U0bxyp48PAB
rV9zzVei9iKrGaYMFJC2CqPa/svLwbySqNxHKHqcfZ+2zyuGDGIJBG0vJ2QQ2GAUMD0u
O2QvCCGA3ixj7T1GJBX/upunJg4qnsLyyfV9sx4NtnAh384FayYQPf7dMQy05doOKjVJ
vFw2rAbTnu5XTj3ybK49JFO7iY0JW5A+Yu2F3Ak4E49hX4dkZq2zg/hIdkwVJsIRaW5I
NENmU0FGtVXIpsiQkNWtxxOSWZ9A7jnxCQy/jCx0VIXMjUWEhvgZqkBI3Q91/3z4vKyt
FYxA==
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=HhvsQ2qy5ZQ6ans6rhiJNESeszyIQt+6+yngezPyUBc=;
b=OAEHgqSbzny9MKVkJ65/UWXDMqkBukqpUEUXmy2WLAuwH1oSGv+bBeqUOJDM1O/Pi/
8fl7DEFYPcfcUsgo7he3gLMNrHdcck9RN+PWH09s6Z9r3QbMl2evl+oYUQTXjqHakFSR
fZgqoIgACCwCz35vxEngN/GdpMh0jqVZ7RxjZJYKoUiy25YMudXk4qCsoQs4rpPWLLRC
cs96KYLK0b2oO/c4OHVHAJzWBoZ7Y91+kmN203qiTT6FwleCaSqodr1SJ0VH4tFVrhzd
UkwXoKFxvXLdTrmuUoUsODGkFswPjpgDR8u03cQw2jCkxQrQpOC+SB4LkxtCk2w5Wm4X
csJQ==
X-Gm-Message-State: APjAAAWXCieiTygridXBvZNeyMc/InPdOn0Xw1MVRbll0ZYqij1t8i0O
+CTEYCZ8rwolg1O9138qeTzWGUTxb86Ok0oxb/s=
X-Google-Smtp-Source: APXvYqxbFUPcbiF2oCELgfyG303OLXC03fxuSPdIv5Jm/RK/eAiM8HUcDXH+gQFvVGE5juVJ/jrDoEdyBTGxOAOAyhk=
X-Received: by 2002:a63:4d61:: with SMTP id n33mr12427828pgl.158.1570150133899;
Thu, 03 Oct 2019 17:48:53 -0700 (PDT)
MIME-Version: 1.0
References: <87wodp7w9f.fsf@gmail.com>
<20191001155929.e2yznsetqesx2jxo@erisian.com.au>
<CR-etCjXB-JWkvecjDog4Pkq1SuLUgndtSrZo-V4f4EGcNXzNCeAHRvCZGrxDWw7aHVdDY0pAF92jNLb_Hct0bMb3ew6JEpB9AfIm1tSGaQ=@protonmail.com>
<CAEM=y+XbP3Dn7X8rHu7h0vbX6DkKA0vFK5nQqzcJ_V+D4EVMmw@mail.gmail.com>
<C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>
In-Reply-To: <C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Thu, 3 Oct 2019 20:48:17 -0400
Message-ID: <CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM,
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
Cc: ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>,
"lightning-dev@lists.linuxfoundation.org"
<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the
discussion about noinput / anyprevout
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: Fri, 04 Oct 2019 00:48:56 -0000
I hope you are having an great afternoon ZmnSCPxj,
You make an excellent point!
I had thought about doing the following to tag nodes
|| means OP_CAT
`node = SHA256(type||SHA256(data))`
so a subnode would be
`subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
and a leaf node would be
`leafnode = SHA256(0||SHA256(leafdata))`
Yet, I like your idea better. Increasing the size of the two inputs to
OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
size of object on the stack seems sensible and also doesn't special
case the logic of OP_CAT.
It would also increase performance. SHA256(tag||subnode2||subnode3)
requires 2 compression function calls whereas
SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
function calls (due to padding).
>Or we could implement tagged SHA256 as a new opcode...
I agree that tagged SHA256 as an op code that would certainty be
useful, but OP_CAT provides far more utility and is a simpler change.
Thanks,
Ethan
On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> > To avoid derailing the NO_INPUT conversation, I have changed the
> > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > - `SIGHASH` flags attached to signatures are a misdesign, sadly
> > retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> > par with:
> > [..]
> >
> > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > [..]
> > """
> >
> > OP_CAT is an extremely valuable op code. I understand why it was
> > removed as the situation at the time with scripts was dire. However
> > most of the protocols I've wanted to build on Bitcoin run into the
> > limitation that stack values can not be concatenated. For instance
> > TumbleBit would have far smaller transaction sizes if OP_CAT was
> > supported in Bitcoin. If it happens to me as a researcher it is
> > probably holding other people back as well. If I could wave a magic
> > wand and turn on one of the disabled op codes it would be OP_CAT. Of
> > course with the change that size of each concatenated value must be 64
> > Bytes or less.
>
> Why 64 bytes in particular?
>
> It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
>
> However we have had issues with the use of Merkle trees in Bitcoin blocks.
> Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
>
> The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
>
> Or we could implement tagged SHA256 as a new opcode...
>
> Regards,
> ZmnSCPxj
>
>
> >
> > On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> > bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > - `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > > - 1 RETURN
> > > - higher-`nSequence` replacement
> > > - DER-encoded pubkeys
> > > - unrestricted `scriptPubKey`
> > > - Payee-security-paid-by-payer (i.e. lack of P2SH)
> > > - `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > > - transaction malleability
> > > - probably many more
> > >
> > > So let me propose the more radical excision, starting with SegWit v1:
> > >
> > > - Remove `SIGHASH` from signatures.
> > > - Put `SIGHASH` on public keys.
> > >
> > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > > <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > >
> > >
> > > - `sighash` must be one byte.
> > > - `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > - `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > - `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > - If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > >
> > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > > <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
|
