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
|
Delivery-date: Wed, 09 Apr 2025 02:23:04 -0700
Received: from mail-oo1-f61.google.com ([209.85.161.61])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDBNTKFG4EDRB3HY3C7QMGQEGKZVAGQ@googlegroups.com>)
id 1u2ReB-0001e8-6C
for bitcoindev@gnusha.org; Wed, 09 Apr 2025 02:23:04 -0700
Received: by mail-oo1-f61.google.com with SMTP id 006d021491bc7-6045ff1afc6sf40928eaf.0
for <bitcoindev@gnusha.org>; Wed, 09 Apr 2025 02:23:02 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1744190577; cv=pass;
d=google.com; s=arc-20240605;
b=ee620y2XwQREJcs4joPxF9PEswFk0zbIrVkFymHVouAV/SQSyiD+2gUIw4Pa0qvQTX
7ZncUWGzBosXJfh107jo5XQEjwheOAtpgA6q5aBBiRzNulUSNSg+HlrsTclPgYrZf46F
O/hhuW7OkAPWhEju6/IhdKgF0fZaxCuo0N3pmYw29CpPWZ4bVpmLgeojFl0CCy+/mYrq
GmCLDRZUNWkC4JBUj9yT7GnqE7xtEaxC4GsR+fYSBvZfsjk5wx+FmFD1DwYgaZrM18PR
LjxSPywT9yvWvSTZthAyZPQVwf6SsWW2/zrmdeMQzHbeAeTJeFOyuGYwXuL5cTTrrTes
i8Sw==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:in-reply-to:content-disposition
:mime-version:references:message-id:subject:cc:to:from:date:sender
:dkim-signature;
bh=5jsykOaVueEYjVi78FTQfvMKdZdPAkZOo8v2b+wvIDA=;
fh=ITxrCNiMIn1xTdxrjz6uhO7ZWFvJ5Yopb7T41urxuE0=;
b=IRteOeNhz+En2UUHu3y4ExX0ZezPsehejGyMw3HJAjrjlnOhtT7OqHqu+lyL84UTts
5LjF1ipQW6nTitIIqqOYbPWLOzqKML6qrJAHV9pt4aLD/V67CN82MglX5iTjq3Vgaogj
XUiRmd+4cLFC0YzIE983RkR4F9H/DedLAW2ieqlZoyGGkyKbyRRxExl7f+yFWT93rH6s
99ZeapeN6ZyXpp6QGfkNqj8K32MrPTDK6LXyflUanxSm6XKDR1JnqM4zxangkfOiM7MK
gLfPeLAU8YOqFOQHFiOWlxzitGJeY5uGdQOdfFvkhQhFJfWh0/61Y0ZZmyy8NjRLFFOb
b3OQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
spf=pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) smtp.mailfrom=aj@erisian.com.au
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1744190577; x=1744795377; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=5jsykOaVueEYjVi78FTQfvMKdZdPAkZOo8v2b+wvIDA=;
b=YBGYnEU6EzsD1YW8d1rcdMR7fB34fv3LVdbsJy0klffrMkkvFf+pUFSUFnendSflXZ
ZNvAhWh/aDZLg8jIwwdet/5U+uJFXBjVhKq07YY7gNoxQBwgA5Rx7Tz0wRmZ8Fsl1Kwa
Bgum/gp1NLPPKdH43GBWKOh+y5oIJemsy6y/YIgSzIxjG3sUonNgjpkyfFyQ5DIHuD5+
flirr7Wt+nrjfLO7EPEfR35KrIq/1QvmM1Hu2POIZN0SpqoHSI+n30lxZL10Z7r92Mka
WcdZ0UXS0yI5Wu5HKad9B7m+7DQLdycf2539PmX2eYdpe7hT6N9z5W6HtZuY7R8ha4LX
mZRA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1744190577; x=1744795377;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=5jsykOaVueEYjVi78FTQfvMKdZdPAkZOo8v2b+wvIDA=;
b=VandSzn5zFJC2c8r9ceqe6a/m77S2T9v9wOzEZgnGtsdi59vq1kNQN38r89gSrgKNQ
/H76Rst7IeEPG0wl6kK99bScSj1gexHKa3sw/Rd0Zlz5LjfV0wR8Tuz6w1murOn0bkRU
eKFLD3gQO2rJ+7eYAy8VFA1DT2nW/0dcnzVT5wIccor5/9kMtwG6hxDTgQumiwZNeott
vKbkD72SvVVCOSCutFEovjFQJNj0iQo52Mwaho69kMZcLxlpBBIM9jFwOSqZZvqc3ZF6
0Nc4UZtHi2xONtCUZkNjovB1H00aNbxMSRYULp836yug8P3MpWRV825IXgAFBgsJMEjb
mnWQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCX4UP1M+S3/enkyPmXlv4EZsp9yqKSs8OtLHmdZYY6ApYjgCAdoE+6GefErH+1+p0jOTZsXJ3oSvPu8@gnusha.org
X-Gm-Message-State: AOJu0YxLzZaZzarxDyePzlsR4XqDoieDj38/KLVkm7Y4XYmPfRFTwM/R
20Af2JLypDiuervw7bQCVX+PNjcc/fy9gDNxf5QQRFAEAMNoAeYr
X-Google-Smtp-Source: AGHT+IG8bWzow7ig+gxwXUcHnIDNLh53v8dR2PPOI1bAkTeo6kX4UJ5/jK2QZu8C5QNzFg0hGVOu6w==
X-Received: by 2002:a05:6870:de10:b0:29e:684d:2739 with SMTP id 586e51a60fabf-2d091b67b0emr1033201fac.32.1744190576758;
Wed, 09 Apr 2025 02:22:56 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAL0Gbur86pazdEQ0wAy5iiL2f8gphA05VtZB43nhAGEew==
Received: by 2002:a05:6871:4092:b0:2c1:3442:67b9 with SMTP id
586e51a60fabf-2cc7ab689d7ls2005987fac.2.-pod-prod-04-us; Wed, 09 Apr 2025
02:22:52 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCUDKKu3cCmNqziuMZmrxtXKsjEMV7SysprFhWpsPkvbvt5UFNAc9PDKhVZBKQ90kwBBe4i6nb35J4tP@googlegroups.com
X-Received: by 2002:a05:6808:bc5:b0:3fe:aeaf:2d3 with SMTP id 5614622812f47-400740eaf88mr777843b6e.39.1744190572478;
Wed, 09 Apr 2025 02:22:52 -0700 (PDT)
Received: by 2002:a05:6808:1b8f:b0:3fa:6f09:b173 with SMTP id 5614622812f47-40033cc69d0msb6e;
Tue, 8 Apr 2025 11:04:49 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCX1OinbitsvcapuVwoAAvRXeLeKXVgUUVPXNiR8wWasX3RFgqnJgS9XwgsH8my2FmlYEthNI0OqO5Kh@googlegroups.com
X-Received: by 2002:a05:6a21:9211:b0:1f5:7eb5:72dc with SMTP id adf61e73a8af0-2010444d827mr26550228637.3.1744135488109;
Tue, 08 Apr 2025 11:04:48 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1744135488; cv=none;
d=google.com; s=arc-20240605;
b=A+ByQSMCfljX//i/eXONsYqc1JM+KL/4bi/y4CcvkejZyd25O7FVm+aIsz9+P5zPVY
4aGjYJNKIlN6ng8IrPZBvnvrrvzHLHAhoLRTVJYVu0vfjShwBkTOT46fxG5bM1jN/WhF
LqhnaQtLgs6jELohLbQ3APuTqwQKAiQqO8WBYc5bziRqru7zJNTVX0SldIY+/dUSJomW
SEd6RQJM75m0qkMChIVTXWs9h0hJ+2usMnbXHVdNcIBCk1owhrncFHAsYmnU39d64+5k
HAnutry5pmEkYlQs1oZKnCO80ovKS4lINC+wJLTlgW6t5rcFFHxKe433J7ylGEJgY0ZX
llkA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=in-reply-to:content-disposition:mime-version:references:message-id
:subject:cc:to:from:date;
bh=Ke7SzWEtcHueRlSEePD2Ni0h5qgM59Ec+h52JYrE7q8=;
fh=tLQQpKyBnOKlOTFYM7UjJX9e4E1FI3mfqMXlqmL4Iyg=;
b=UaVOJ270Iy2uEZxdbENb0h5QDNn4UJkNOUlt897Wttha7THOtfwKv9W8I4bzORImIG
Y1ueLnbJBYoxvS494HoL1t87olMm/35x9nnX0b0E/6S+aYwrIBaX/Y4epWqoc/IeHLPy
uspGhzj85dDvnQPLDzOFogX38EXXmbpVV4DTIARU127D2VRMqnxNE4MRPVYa2qgUoW6o
fmHyO3rm2x12P6/YjezsBizxnt553/KZ3qcfFQ6lap4DPw6y5jcnrzLLkmOnjbn8i/Q0
urbQlYs8QvlM7nLAkRYCQlSO2zMZjNl9cEIzNFTtoWbjEelGcGr44p4JWGi9qEP1jNT6
7HKA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
spf=pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) smtp.mailfrom=aj@erisian.com.au
Received: from cerulean.erisian.com.au (azure.erisian.com.au. [172.104.61.193])
by gmr-mx.google.com with ESMTPS id 41be03b00d2f7-af9bc3f70e2si537964a12.4.2025.04.08.11.04.47
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Tue, 08 Apr 2025 11:04:47 -0700 (PDT)
Received-SPF: pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) client-ip=172.104.61.193;
Received: from aj@azure.erisian.com.au
by cerulean.erisian.com.au with esmtpsa (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
(Exim 4.96)
(envelope-from <aj@erisian.com.au>)
id 1u2DJR-000399-2M;
Wed, 09 Apr 2025 04:04:43 +1000
Received: by email (sSMTP sendmail emulation); Wed, 09 Apr 2025 04:04:36 +1000
Date: Wed, 9 Apr 2025 04:04:36 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Pieter Wuille <bitcoin-dev@wuille.net>
Cc: Javier Mateos <javierpmateos@gmail.com>,
Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: =?UTF-8?Q?Re=3A_=5Bbitcoindev=5D_New_Proposal=EF=BC=9AString_Substring_Sea?=
=?UTF-8?Q?rch_in_Bitcoin_Script_=2D_OP=5FISSUBSTR?=
Message-ID: <Z_VlNPeDS8Hk3Dyy@erisian.com.au>
References: <f844a85e-8be8-4429-8687-bc19dd4b96ffn@googlegroups.com>
<Z9hTu2TjMlLr5-Eg@petertodd.org>
<678d40e3-3e22-4d55-82c0-b25ccafb87ecn@googlegroups.com>
<CAD2YOAp=ft+pApAwh6CQvwMpujfZ0ysSK+=7zKA64nBeB5w3nA@mail.gmail.com>
<8c823e50-197e-479c-8651-9e0407a4168en@googlegroups.com>
<b4594133-e6e5-438b-aa56-98d6171296fan@googlegroups.com>
<e8c30db7-b509-4fbd-93ef-0bca0313003cn@googlegroups.com>
<frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA=@wuille.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
In-Reply-To: <frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA=@wuille.net>
X-Spam_score: -0.0
X-Spam_bar: /
X-Original-Sender: aj@erisian.com.au
X-Original-Authentication-Results: gmr-mx.google.com; spf=pass
(google.com: domain of aj@erisian.com.au designates 172.104.61.193 as
permitted sender) smtp.mailfrom=aj@erisian.com.au
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)
On Tue, Apr 01, 2025 at 12:25:26PM +0000, Pieter Wuille wrote:
> On Monday, March 31st, 2025 at 4:41 PM, Javier Mateos <javierpmateos@gmail.com> wrote:
> > The solution of splitting the string and using OP_CAT only works if the exact position of the substring is known. How would a case be handled where the substring could be in any position
> Whoever produces the signature/witness for spending the coin always knows the position already, so the script can always be modified to instead take that position as an additional input.
> This is a general principle: the point of scripts is verifying provided information, not computing it. As another example, this means that there is no need for a division or square root opcode if one has a multiplication opcode.
I somewhat disagree with this: there are some concerns that are *easier*
to express with different opcodes, and I think that's a factor worth
considering.
This came up with the OP_CAT based proof-of-work faucet [0] -- the
idea there is that you provide a signature and some nonce data, and
when you combine the two and hash the result, that result begins with
some sufficient number of 0 bits (that then gets related back to a
CHECKSEQUENCEVERIFY delay).
OP_CAT is *sufficient* for testing this, because you just CAT the
signature and nonce together and hash them, and can then again CAT the
the 0-bits you expect together with some other data and check that all
of those combined match the hash you calculated earlier.
But it would be more efficient, and a little easier to code, if you
could instead have used SUBSTR/LEFT to pull the initial bytes from
the calculated hash and check that those have the expected number of
leading 0-bits. More efficient, because you don't have to supply all
the trailing bytes of the hash in the witness, and easier to code,
because it's a bit more natural to think of manipulating the hash you
calculated, rather than having to put user-provided data together and
check that that actually matched what you would have extracted from
the hash had you been able to do it that way.
So just like we have unnecessary opcodes like "CHECKSIGVERIFY" (versus
"CHECKSIG VERIFY"), I think it's still worth evaluating "SUBSTR" and
"DIV" on questions of efficiency, even if they're not providing any
additional expressivity -- ie, does it provide a meaningful improvement
either for on-chain validation or when writing/maintaining scripts
compared to other ways of achieving the same goal?
(That said, I don't think "ISSUBSTR" is a great opcode; the original
SUBSTR that specifies exactly where in the original string the substring
appears seems more useful to me)
Cheers,
aj
[0] https://delvingbitcoin.org/t/proof-of-work-based-signet-faucet/937
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z_VlNPeDS8Hk3Dyy%40erisian.com.au.
|
