Delivery-date: Wed, 19 Mar 2025 17:06:48 -0700 Received: from mail-yb1-f191.google.com ([209.85.219.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 1tv3Qs-0003JC-Sv for bitcoindev@gnusha.org; Wed, 19 Mar 2025 17:06:47 -0700 Received: by mail-yb1-f191.google.com with SMTP id 3f1490d57ef6-e5740c858besf265214276.2 for ; Wed, 19 Mar 2025 17:06:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1742429201; x=1743034001; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=UcB/pphvkmwzNLCPkj2JdsbmVmO/f1h317q2NG0/sXw=; b=ItlrkgHTeeZprxZyab4Hg/dIbZ8QxgVPSegzVirr6KdtIQufnMVKWSvbwg3t+HNm73 k4pX2koNRBYtvjxZJ4wBa50L0OGUD9Vvr27S687W0n7FSvhZPdbtjPMy3EaKOEdFtovv +JDGcYTa71PMDb/ms3I+66vHhlVKztmDtdBYLhI/JG7QUo0Lpz/ZZqzYPTNbMpUebG28 8fJTJYTZJTe2ykzhWIAmUW3X3ONwABvBJo9/FDiOyv11AI1kBHcC847eKJBMhvY6z4ZI sgjzMgUWcJcp6RJN9UGqiWTJFJF0JNgRaGTmThrjnITzx8r5eQT2C34GX7G0+UUMY8wz gE2w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742429201; x=1743034001; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=UcB/pphvkmwzNLCPkj2JdsbmVmO/f1h317q2NG0/sXw=; b=VCpp/ME516oMwWOzFtmAf/QcGAGD4xw3sXGOY84W+xdzSMLyLD7COWQPEs/esGxl1+ 9yduGGcD9DO/iFOvQRlvnIgTYKlqHF0IhWnyHEeWXsioD0fGWA+Rf4v6vHQ+vl0Wzr/9 Fg8JtwGzU/JVf2K+H2OizSAzY6KOi9Hd9rJqr260b/Qffn9y45RQj/znXsH3k+oPsX4h eGa7BhpFfVxriVPGZo5ePX8Q1+H673vjcYDRUNNua4ZLPmf6gbHuFslSDaBIhbrtj1GM MhrGeBQq3SRBXGcWxb0isoJkAhpugtSbaO4kKLrc08Lu79eCnt0Gwd7LS9plZ0gZp1WB 6ppg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWfEo+lqfkfVGq0nxgCg8168lTeBDllel5XKlDPcpDCkcvYkN/HP1nHVP2tZCHG7UAMsBpf+OrSI24c@gnusha.org X-Gm-Message-State: AOJu0YzwqXnOfS5Ksg3Qi0t/44OiKEJZjLWv/Zt6zxYSvpi91KGa8a7k Kfd5qhEVp+r83af4d0wrywtjbkmPoZ/E1AYwBVsZK1OTCCwf1/lN X-Google-Smtp-Source: AGHT+IGavseGfFl8yUuYRWSFJ/6bEVSqpRHgo5hk//u1TU5Ui2Esp+768dumnco/C1zQL6fTrTYNyw== X-Received: by 2002:a05:6902:2b08:b0:e58:aa00:ffd5 with SMTP id 3f1490d57ef6-e667b39f5a4mr6370592276.4.1742429200858; Wed, 19 Mar 2025 17:06:40 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAIwzJMFn+V1pAJd2GNDX1CNNP+qq8ogP+hj5DzZIF03Hw== Received: by 2002:a5b:20f:0:b0:e61:1c4c:6d6b with SMTP id 3f1490d57ef6-e6690a82f1als416612276.2.-pod-prod-02-us; Wed, 19 Mar 2025 17:06:36 -0700 (PDT) X-Received: by 2002:a05:690c:b15:b0:6f9:7a38:af5b with SMTP id 00721157ae682-7009bf72520mr72034107b3.13.1742429196812; Wed, 19 Mar 2025 17:06:36 -0700 (PDT) Received: by 2002:a05:690c:6a86:b0:6ef:590d:3213 with SMTP id 00721157ae682-7009ba67b03ms7b3; Wed, 19 Mar 2025 02:07:58 -0700 (PDT) X-Received: by 2002:a05:690c:3506:b0:6f9:7fe6:9d48 with SMTP id 00721157ae682-7009bf49f65mr24946907b3.7.1742375277130; Wed, 19 Mar 2025 02:07:57 -0700 (PDT) Date: Wed, 19 Mar 2025 02:07:56 -0700 (PDT) From: weichu deng To: Bitcoin Development Mailing List Message-Id: <8c823e50-197e-479c-8651-9e0407a4168en@googlegroups.com> In-Reply-To: References: <678d40e3-3e22-4d55-82c0-b25ccafb87ecn@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?= MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_2434_1529323214.1742375276685" X-Original-Sender: weichudeng@stu2024.jnu.edu.cn 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.7 (/) ------=_Part_2434_1529323214.1742375276685 Content-Type: multipart/alternative; boundary="----=_Part_2435_1135241746.1742375276685" ------=_Part_2435_1135241746.1742375276685 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Rijndael, =20 Thanks for your example=20 [witness: foobar foo] bar CAT EQ =20 Yes, the unfixed string can be checked against a target substring in your= =20 example. However, if the target substring is located in the middle of the= =20 unfixed string, how to check it? In other words, how to have the same=20 function as =E2=80=9Cfoobar ob ISSUBSTR=E2=80=9D with CAT if =E2=80=9Cfooba= r=E2=80=9D is unfixed? =20 For example, suppose that a lucky draw game has the rule: if anyone has a= =20 publicKey which includes a special substring "goodluck", he/she will be=20 awarded.=20 This game can be easily implemented with OP_ISSUBSTR as follow. - LockScript: OP_DUP goodluck OP_ISSUBSTR... - UnlockScript: signature publicKey How to implement it with OP_CAT? =20 *Regards* Weichu deng weichudeng@stu2024.jnu.edu.cn =20 =E5=9C=A82025=E5=B9=B43=E6=9C=8819=E6=97=A5=E6=98=9F=E6=9C=9F=E4=B8=89 UTC+= 8 10:28:25 =E5=86=99=E9=81=93=EF=BC=9A > Stack elements in Taproot are limited to 520 bytes. The current proposal= =20 > for re-activating OP_CAT includes this restriction: creating a string=20 > 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= =20 > provide them at spend-time as witness data (and allow them to be unfixed = in=20 > the script). > > Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOBAR FOO BAR CAT EQ > Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D [witness: FOOBAR FOO] BAR= CAT=20 > EQ > > > rijndael=20 > > > On Mar 18, 2025, at 11:32=E2=80=AFAM, weichu deng =20 > wrote: > > Hi, Peter Todd > Thanks for your feedback. I agree that "Bitcoin scripts are about=20 > validation. Not computation." > String search and concatenation are equivalent in some cases, such as in= =20 > the example you provided. > However, it is still necessary to introduce the OP_ISSUBSTR operation=20 > separately. > One example is converting a non-deterministic signature to a deterministi= c=20 > one. > Another case is when the substring in question is located in the middle o= f=20 > the checked string. > CAT cannot replace ISSUBSTR for the following reasons: > > 1. The security of CAT is still controversial. It can easily generate= =20 > overly long strings, potentially causing a stack overflow. Additionall= y,=20 > whether OP_CAT will be restored is still under discussion. > 2. The other substring (bar) must be known in advance. > =20 > > With respect, > > Weichu Deng > > weich...@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 UT= C+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: > >=20 > >=20 > > Dear fellow Bitcoin developers, > >=20 > >=20 > >=20 > > I am pleased to present a new BIP proposal. This proposal introduces a= =20 > new=20 > > opcode for Bitcoin scripts: OP_ISSUBSTR. > >=20 > >=20 > > *Abstract* > >=20 > > This BIP introduces two string opcodes, OP_ISSUBSTR and OP_ISSUBSTRVERI= FY > =20 > > (similar to the relationship between OP_EQUAL and OP_EQUALVERIFY), to= =20 > > determine whether one string is a substring of another. As these opcode= s=20 > do=20 > > 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= =20 > "Bitcoin Development Mailing List" group. > To unsubscribe from this group and stop receiving emails from it, send an= =20 > email to bitcoindev+...@googlegroups.com. > To view this discussion visit=20 > https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25c= cafb87ecn%40googlegroups.com=20 > > . > > > --=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/= 8c823e50-197e-479c-8651-9e0407a4168en%40googlegroups.com. ------=_Part_2435_1135241746.1742375276685 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Hi Rijndael,

=C2=A0

Thanks for your example

[witness: foobar =C2= =A0foo] bar CAT EQ

=C2=A0

Yes, the unfixed string can be checked against a target substring in your example. However, if the target substrin= g is located in the middle of the unfixed string, how to check it? In other word= s, how to have the same function as =E2=80=9Cfoobar ob ISSUBSTR=E2=80=9D with = CAT if =E2=80=9Cfoobar=E2=80=9D is unfixed?

=C2=A0

For example, suppose that a lucky draw game has the rule: if anyone has a publicKey which includes a special substring "goodluck", he/she will be awarded.

This game can be easily implemented with OP_ISSUBSTR as follow.

- LockScript: OP_DUP g= oodluck OP_ISSUBSTR...

- UnlockScript: signat= ure publicKey

How to implement it with OP_CAT?

=C2=A0

Regards

Weichu deng

weichudeng@stu2024.jnu.edu.cn

=C2=A0


<= div dir=3D"auto" class=3D"gmail_attr">=E5=9C=A82025=E5=B9=B43=E6=9C=8819=E6= =97=A5=E6=98=9F=E6=9C=9F=E4=B8=89 UTC+8 10:28:25<Rijndael> =E5=86=99=E9= =81=93=EF=BC=9A
Stack elements in Taproot are limited to 520 bytes. The current proposal = for re-activating OP_CAT includes this restriction: creating a string longe= r than 520 bytes with CAT will cause the script to fail.

With either CAT or ISSUBSTR, you can either commit to the substrings or pr= ovide them at spend-time as witness data (and allow them to be unfixed in t= he script).

Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOB= AR FOO BAR CAT EQ
Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D= [witness: FOOBAR FOO] BAR CAT EQ


r= ijndael=C2=A0


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

=
<= div>
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 conv= erting 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. Additi= onally, whether OP_CAT will be restored is still under discussion.
  2. The other sub= string (bar) must be known in advance.

<= /span>

With respect,<= /span>

Weichu Deng

weich...@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<Pe= ter Todd> =E5=86=99=E9=81=93=EF=BC=9A
On Mon, Mar 17, 2025 at 09:14:= 05AM -0700, weichu deng wrote:
>=C2=A0
>=C2= =A0
> Dear fellow Bitcoin developers,
>=C2=A0
>=C2=A0
>=C2=A0
> I am pleas= ed to present a new BIP proposal. This proposal introduces a new=C2= =A0
> opcode for Bitcoin scripts: OP_ISSUBSTR.
>= =C2=A0
>=C2=A0
> *Abstract*
>= =C2=A0
> This BIP introduces two string opcodes, OP_ISSUBSTR a= nd OP_ISSUBSTRVERIFY=C2=A0
> (similar to the relationshi= p between OP_EQUAL and OP_EQUALVERIFY), to=C2=A0
> deter= mine whether one string is a substring of another. As these opcodes do=C2=A0
> not alter any blockchain state, they are secure.
=
Bitcoin scripts are about validation. Not computation.

This mean= s that substring search and concatenation are equivalent. For
every scri= pt that validates a substring search, you can instead
concatenate the su= bstring with the rest of the string, and validate
equality instead.
<= br>Basically speaking:

foobar foo IsSubStr

is equivalent to:<= br>
foobar foo bar Cat Equal

A real-world example would be more c= omplex. But I hope that illustrates
my point sufficiently.

--=C2=A0
https://petertodd.org= =C2=A0'peter'[:-1]@petertodd.org

<= /div>
--=C2=A0=
You received this message because you are subscribed to the Goog= le Groups "Bitcoin Development Mailing List" group.
To unsubsc= ribe from this group and stop receiving emails from it, send an email to=C2=A0bitcoindev+...@go= oglegroups.com.<= /span>
To view this discussion visit=C2=A0https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e2= 2-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/bitcoind= ev/8c823e50-197e-479c-8651-9e0407a4168en%40googlegroups.com.
------=_Part_2435_1135241746.1742375276685-- ------=_Part_2434_1529323214.1742375276685--