Delivery-date: Tue, 18 Mar 2025 19:28:31 -0700 Received: from mail-oi1-f191.google.com ([209.85.167.191]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tujAU-0004P6-UF for bitcoindev@gnusha.org; Tue, 18 Mar 2025 19:28:31 -0700 Received: by mail-oi1-f191.google.com with SMTP id 5614622812f47-3f9ce53ab0bsf5551856b6e.2 for ; Tue, 18 Mar 2025 19:28:31 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1742351305; cv=pass; d=google.com; s=arc-20240605; b=MpUAb0l1KX211N6tR+nVSVtuyLCgcOGNRORi17AQtsn+h6M4srUMtL3TzlgxAdHUyy UhluUNFbbjID6aDvD46gL38ek5EuaugPgIhPTyrvUkA7A/GBxDkE8HeBADn6u9YtKKQf WiN+ZfGwtPYPSmy96XfQvRk2SypH3IzgPuJl9+9Xs6q4z+MQuRKN6R673mtXAc0SYwb1 N6cgXSCyQBep7rDyppQ6WVXRMjSXAuzwL19enc2WQVuly4cqHLS8e5oVQkehSKE47lKi jPCPPz7W3lNvm1pYPaWx644RWMLMeBh6x/e52rVxsm1DkL9mYdhCpA1n0V5BeMRL4YIX Xbxg== 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=jdjjZrAwYEZj0Zv7KLg/BdituB++L6Gi3+qsRRrIB8w=; fh=mQhQR9WxicsbSsSpg3ZDkkemsNwPUcEA7+/xLD+RRwI=; b=I7OTHKFVt38O+IhFG9m0HzcXaSsfYn5dd5FOKKpIfQfdGUOCl1hsDsleASjUOieYe1 axrdWcr+86q9GNvFIQqq94vp3uQbzcdVZXpcBomAD4LYr5a00f0uGRO++U5DaNusC93f jEj0zQap3+T1vmAmb8ViZ3Tc3v2znGctMVoEeW1cWs3ausGdndcdjEoB1kJCOIfpTluX yUMutTL79J8O0EX3cKO4h5QgqUa5hO81lgxZqU49bTpK/ecN/D2oHmrXz/+0dKYE+zK5 +J7HASDTjIWkJ6vdo/gPBCwhjj/72FUdgMdBycP6TVFmOSm1cmMhZIL4mERRfipBFHJg DnSQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=euzvv+5F; spf=pass (google.com: domain of rot13maxi@gmail.com designates 2a00:1450:4864:20::632 as permitted sender) smtp.mailfrom=rot13maxi@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1742351305; x=1742956105; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=jdjjZrAwYEZj0Zv7KLg/BdituB++L6Gi3+qsRRrIB8w=; b=EkgzwAr03hO7FA8bdOVryCq03tCXgGHH8tzZa5JQFoSzxWgdKQWZRJQj+IIp6vLkPk yGcUjlJRR+tFOnin4Dqbg//vjXcmjRWKuZ9cSvGTQ6i0J+/LUA77D8S5QyN5mhGIFWU1 GE3OeJLiC4VFsxMd2UcBtyaG44qtCld2J1KkmDFmfDcMsZpCE4MIegQ63L6zIwW/L5jT ZpUXL7UmzOGJ2KTOXe9zoWGZbZmvpBhYVvpgCtz+s8eTLek7OcBT2r98RUrTtwW9nWSu F1Ks0OpvVvQHXYxyqUVXoG5VrE0hIsicesHnzfAwPxQlIA/Vv39A9knMDTu8QMoMS5bn pnpA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1742351305; x=1742956105; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=jdjjZrAwYEZj0Zv7KLg/BdituB++L6Gi3+qsRRrIB8w=; b=M/COj3Kq8L7MHjA1pI5YX5HocK17dg9wvVxCaf9GLxh0JD5WdKJVC1rWa7xaxOyvBt uYb6Kcvjq8PevsFOd/I4i/wTN+RjbfUeACtvbtl+T8HxqTq2Z6rj3Wi1fvvUw5dC4AOh hx43hhWugdXySHykRo8+5DYbIVw8kyDW+6GK24cPCTqIclK3CadQwaIWWMm8moaokcbv x194xJbB43F6DEp1bTILfbstu7DU5OumqJlf6EYmtI8eIHGZjnX0xJpNc+bjHR1/1TXA nP3O+hdxnx3wzF38u5mMeBuhFzpJ2FO/o5iTvtCqtR2DuvJdsaIdyZsf6cO9GFv7f8EY 6Tkg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742351305; x=1742956105; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-beenthere:x-gm-message-state:sender:from :to:cc:subject:date:message-id:reply-to; bh=jdjjZrAwYEZj0Zv7KLg/BdituB++L6Gi3+qsRRrIB8w=; b=bs3CusSc1W+IFVVz//PSqFCmuJ0WJewyY277jnls8KtrgGu4GNR9HFBp4ZXNjEmOAp Aum8KsW82ekV0Grm8jG7qWkEcEAWXE/AYl6FGH6rmBVAhx8aqjWyM43XKknX2t+mSJMI L8YPjngahkRvKJrWVWmPJo+9khw9b7JaER0LKaaVrfzsEgFC1k3S8v3QL+Yun7t6WBuc ICW5nw68Llc+KpG18Jmyhe0LVCs4DoA19DAcsVXZI+RQ+gj/y1Y0rNLOrKyrxd0BB7qb pXGYcUI8NJVlRuYXQ/MHVi8Po8FmP7X4KLWIQjrcoihKszyyQ5EGVrjSbSnlqhVt950j pjhw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCVOYC8yaSUTzYqtV3V15goFQj7sJbksLSG4g8XHorvm1Y6WFUV4rEAfQKkv4eHtCAMQufZ/hgSZasnm@gnusha.org X-Gm-Message-State: AOJu0YyFJ9tFoF1t+5Lxse5P8ThSQpMiq4Kk3oBMzKmEGXxgXa5O+adv 0CmS7/KUegPkajVyhE6eJV1JSJlOEU9dY/lzaeR1Xx+thh9yt9Z5 X-Google-Smtp-Source: AGHT+IHI+CSjLqQROHUK9sdDngEn7i3CjA4Szi+TP+SAUqQcv+YyTXEZ7DwFWzSE+kYZR41i8RDRww== X-Received: by 2002:a05:6808:16a8:b0:3fc:1f7b:c3a2 with SMTP id 5614622812f47-3fead59213amr700762b6e.17.1742351305170; Tue, 18 Mar 2025 19:28:25 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAIHtauat2kUKVZi9/eFT3ihTu7eg5NUr9ke4wyzU4O74w== Received: by 2002:a4a:e50e:0:b0:600:5d08:133f with SMTP id 006d021491bc7-6021b748228ls257004eaf.0.-pod-prod-03-us; Tue, 18 Mar 2025 19:28:22 -0700 (PDT) X-Received: by 2002:a05:6808:23c2:b0:3fa:53b5:6f87 with SMTP id 5614622812f47-3fead610777mr740283b6e.34.1742351302474; Tue, 18 Mar 2025 19:28:22 -0700 (PDT) Received: by 2002:a05:6402:2293:b0:5e6:412b:7fe with SMTP id 4fb4d7f45d1cf-5eb8049a833msa12; Tue, 18 Mar 2025 14:33:50 -0700 (PDT) X-Received: by 2002:a17:907:96a8:b0:ac1:e1da:8744 with SMTP id a640c23a62f3a-ac3b7ed0692mr15319566b.38.1742333628990; Tue, 18 Mar 2025 14:33:48 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1742333628; cv=none; d=google.com; s=arc-20240605; b=K/eOxB47cJZ/Nvc8a1oz7WwAyvkvWZ1m1PsYu8cZbl5hyOj4Qg/R428oc+0ZG1ftQ6 mKkoCpJTOxsIwvsKcirL9/Ty8uNxNWTSJc1HuoSPeo7kfiYhmAC+jdS6IW9aLAqA9ORM t8nwoLVLfgO0djTkl+ol0znv25a42wjw/MeqfgNVwhlajvGv5yPZ3b2kw42TeGq4Rx/A 7buJ4f9rOh/5dMKWOoUMd/sjDo8FZvoAwxQx8vU7Dlv3dAxnhus/dm9KkS7jqtGd2wgs HqCElXr08t160bQmfusXg8Y/pVDAP/Vav5rCXzWac67hI8/zWBzT/IekIKC8Kxsr5Xtc An6g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=6tZw5D5zTe02zx0uoxDSgbb4npBwawbWYKNIz6Iyh/w=; fh=ZezIQ4DPobkbkSLZGiZg2aqbrl+dlXwRCknPDPYULyQ=; b=EcopE3qq0Ak8BWq/J4bmdvOXca+QDXtkvNx1uzzm8hoITqdAxigV08w2DI4+x6FQy+ 3M0jWQ8BIQE/6//OQgtaWcOkzZxvRQVzA30Busth+ab2RTREY3jFSGNRlWUdJ+acxHon H2RSm2lXh3Y4UPZhoCxWCrGikkPKDrNgVKYaTme3xiCA7dWtEWwZGxGSaHR7T/JrJRjf NSsUGav2br+MqvZMh4+OgPRDf8JjAYVl6HKXxO4YUWZ+ozo+nwtPxYRRU2e0ZLtO4HnF fpAOIi+QHXfggLWw/0xbm3H5gy8bagOL4roSTLjGWkKFZw/5eib5I95XTGnJEy7oWH6T cmwA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=euzvv+5F; spf=pass (google.com: domain of rot13maxi@gmail.com designates 2a00:1450:4864:20::632 as permitted sender) smtp.mailfrom=rot13maxi@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com. [2a00:1450:4864:20::632]) by gmr-mx.google.com with ESMTPS id 4fb4d7f45d1cf-5e816ada5c5si384856a12.4.2025.03.18.14.33.48 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 18 Mar 2025 14:33:48 -0700 (PDT) Received-SPF: pass (google.com: domain of rot13maxi@gmail.com designates 2a00:1450:4864:20::632 as permitted sender) client-ip=2a00:1450:4864:20::632; Received: by mail-ej1-x632.google.com with SMTP id a640c23a62f3a-ac2af2f15d1so877890066b.1 for ; Tue, 18 Mar 2025 14:33:48 -0700 (PDT) X-Gm-Gg: ASbGncuHLqUlM2dFIeqS234TA/g5Y/i3Po2OFvkcFOBLAMsE/yTKRWcLS1MOzx8khFH /TR2teJbMbduy8qvsE/hNfG5D2Ip12VwAe1Km0nQj4DtJ5p8su1tu1sgCCnqnANAVUnFfP+2EE6 H+ybBuG9E41a9B1u1irBwPZGvQBm8t7UBvg3ye X-Received: by 2002:a17:907:e88c:b0:ac2:64eb:d4e8 with SMTP id a640c23a62f3a-ac3b7365683mr30605966b.0.1742333628299; Tue, 18 Mar 2025 14:33:48 -0700 (PDT) MIME-Version: 1.0 References: <678d40e3-3e22-4d55-82c0-b25ccafb87ecn@googlegroups.com> In-Reply-To: <678d40e3-3e22-4d55-82c0-b25ccafb87ecn@googlegroups.com> From: Rijndael Date: Tue, 18 Mar 2025 17:33:37 -0400 X-Gm-Features: AQ5f1JplQejEWfovx9OUo7cXVn3EA43QUSK4qfnRAfzXFSi1ut-FJPHH_K8q1Gk Message-ID: 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?= To: weichu deng Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000fecf750630a4a85a" X-Original-Sender: rot13maxi@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=euzvv+5F; spf=pass (google.com: domain of rot13maxi@gmail.com designates 2a00:1450:4864:20::632 as permitted sender) smtp.mailfrom=rot13maxi@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) --000000000000fecf750630a4a85a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Stack elements in Taproot are limited to 520 bytes. The current proposal for re-activating OP_CAT includes this restriction: creating a string longer than 520 bytes with CAT will cause the script to fail. With either CAT or ISSUBSTR, you can either commit to the substrings or provide them at spend-time as witness data (and allow them to be unfixed in the script). Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOBAR FOO BAR CAT EQ Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D [witness: FOOBAR FOO] BAR C= AT EQ rijndael On Mar 18, 2025, at 11:32=E2=80=AFAM, weichu deng wrote: Hi, Peter Todd Thanks for your feedback. I agree that "Bitcoin scripts are about validation. Not computation." String search and concatenation are equivalent in some cases, such as in the example you provided. However, it is still necessary to introduce the OP_ISSUBSTR operation separately. One example is converting a non-deterministic signature to a deterministic one. Another case is when the substring in question is located in the middle of the checked string. CAT cannot replace ISSUBSTR for the following reasons: 1. The security of CAT is still controversial. It can easily generate overly long strings, potentially causing a stack overflow. Additionally, whether OP_CAT will be restored is still under discussion. 2. The other substring (bar) must be known in advance. With respect, Weichu Deng weichudeng@stu2024.jnu.edu.cn =E5=9C=A82025=E5=B9=B43=E6=9C=8818=E6=97=A5=E6=98=9F=E6=9C=9F=E4=BA=8C UTC+= 8 01:01:16 =E5=86=99=E9=81=93=EF=BC=9A On Mon, Mar 17, 2025 at 09:14:05AM -0700, weichu deng wrote: > > > Dear fellow Bitcoin developers, > > > > I am pleased to present a new BIP proposal. This proposal introduces a ne= w > opcode for Bitcoin scripts: OP_ISSUBSTR. > > > *Abstract* > > This BIP introduces two string opcodes, OP_ISSUBSTR and OP_ISSUBSTRVERIFY > (similar to the relationship between OP_EQUAL and OP_EQUALVERIFY), to > determine whether one string is a substring of another. As these opcodes do > not alter any blockchain state, they are secure. Bitcoin scripts are about validation. Not computation. This means that substring search and concatenation are equivalent. For every script that validates a substring search, you can instead concatenate the substring with the rest of the string, and validate equality instead. Basically speaking: foobar foo IsSubStr is equivalent to: foobar foo bar Cat Equal A real-world example would be more complex. But I hope that illustrates my point sufficiently. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --=20 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/678d40e3-3e22-4d55-82c0-b25cca= fb87ecn%40googlegroups.com . --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= CAD2YOAp%3Dft%2BpApAwh6CQvwMpujfZ0ysSK%2B%3D7zKA64nBeB5w3nA%40mail.gmail.co= m. --000000000000fecf750630a4a85a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
S= tack elements in Taproot are limited to 520 bytes. The current proposal for= re-activating OP_CAT includes this restriction: creating a string longer t= han 520 bytes with CAT will cause the script to fail.

Wi= th either CAT or ISSUBSTR, you can either commit to the substrings or provi= de them at spend-time as witness data (and allow them to be unfixed in the = script).

Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOBAR = FOO BAR CAT EQ
Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D [w= itness: FOOBAR FOO] BAR CAT EQ


rijn= dael=C2=A0


On = Mar 18, 2025, at 11:32=E2=80=AFAM, weichu deng <weichudeng@stu2024.jnu.edu.cn> wrote:

Hi, Peter Tod= d
Thanks for your feedbac= k. I agree that "Bitcoin scripts are about validation. Not computation= ."
String search and concat= enation are equivalent in some cases, such as in the example you provided.<= /div>
However, it is still necessary t= o introduce the OP_ISSUBSTR operation separately.
One example is converting a non-deterministic signature t= o a deterministic one.
Another c= ase is when the substring in question is located in the middle of the check= ed string.
CAT cannot replace IS= SUBSTR for the following reasons:
  1. The security of CAT = is still controversial. It can easily generate overly long strings, potenti= ally causing a stack overflow. Additionally, whether OP_CAT will be restore= d is still under discussion.
  2. The other substring (bar) must be known in advance.=

=E5=9C=A82025=E5=B9=B43=E6=9C= =8818=E6=97=A5=E6=98=9F=E6=9C=9F=E4=BA=8C UTC+8 01:01:16<Peter Todd> = =E5=86=99=E9=81=93=EF=BC=9A
On Mon, Mar 17, 2025 at 09:14:05AM -0700, w= eichu deng wrote:
>=C2=A0
>=C2=A0
= > Dear fellow Bitcoin developers,
>=C2=A0
>=C2=A0
>=C2=A0
> I am pleased to present = a new BIP proposal. This proposal introduces a new=C2=A0
&g= t; opcode for Bitcoin scripts: OP_ISSUBSTR.
>=C2=A0
&= gt;=C2=A0
> *Abstract*
>=C2=A0
>= ; This BIP introduces two string opcodes, OP_ISSUBSTR and OP_ISSUBSTRVERIFY= =C2=A0
> (similar to the relationship between OP_EQUAL a= nd OP_EQUALVERIFY), to=C2=A0
> determine whether one str= ing is a substring of another. As these opcodes do=C2=A0
&g= t; not alter any blockchain state, they are secure.

Bitcoin scripts = are about validation. Not computation.

This means that substring sea= rch and concatenation are equivalent. For
every script that validates a = substring search, you can instead
concatenate the substring with the res= t of the string, and validate
equality instead.

Basically speakin= g:

foobar foo IsSubStr

is equivalent to:

foobar foo ba= r Cat Equal

A real-world example would be more complex. But I hope t= hat illustrates
my point sufficiently.

--=C2=A0
<= a href=3D"https://petertodd.org/" rel=3D"nofollow" target=3D"_blank">https:= //petertodd.org=C2=A0'peter'[:-1]@petertodd.org
<= /blockquote>

--=C2=A0
You received this messag= e because you are subscribed to the Google Groups "Bitcoin Development= Mailing List" group.
To unsubscribe from this group and stop recei= ving emails from it, send an email to=C2=A0bitcoindev+unsubsc= ribe@googlegroups.com.
To view this discussion visit=C2=A0https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0= -b25ccafb87ecn%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.= com/d/msgid/bitcoindev/CAD2YOAp%3Dft%2BpApAwh6CQvwMpujfZ0ysSK%2B%3D7zKA64nB= eB5w3nA%40mail.gmail.com.
--000000000000fecf750630a4a85a--