Delivery-date: Mon, 31 Mar 2025 13:41:27 -0700 Received: from mail-yb1-f183.google.com ([209.85.219.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tzLwk-0001p7-6y for bitcoindev@gnusha.org; Mon, 31 Mar 2025 13:41:27 -0700 Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e643f233fbesf7235505276.0 for ; Mon, 31 Mar 2025 13:41:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1743453680; x=1744058480; 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=AIKL1AYd/xO+SLv3q7xjPwAw1WZmU0WoqzkDslwyHLg=; b=WhEyH/5AnnQH2GiXmNzLnWu5+8WdtIHiDD48YN0Dx0GJxjBRw901utqSj82FNQMA8s pJOiOQXHUnb9oTle5pR7nFkcPZVV26fWkNhkIFZF5X4rQUei8BZ8xzHXpKOgE8kpyrWl /Gaym5/Os59+N+4TAJ1+RRA4AvdHZnIVBFvhPCQLgV+BeSEK4aub2DH3AzJoFWhXDArk plQ7LHqixSsxxAKZrqgc3JDrjoCX1lYiSbepoheBzgbhh+e4AUhIfMpDoRWMpoeHyc5p yIkFtVrbwUx3j5LYleA4ca75eY2Tz/L8bn2/Bu1dr2yDhmAm6GYaCOxJNZgEYHAPaY1e rCBg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1743453680; x=1744058480; 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:from:to:cc :subject:date:message-id:reply-to; bh=AIKL1AYd/xO+SLv3q7xjPwAw1WZmU0WoqzkDslwyHLg=; b=hPe+Y74ozlNFe8Ffn5islF6nUH/SKrUkBKQUfqwLK4GttxguT6/e7VzhFjCuC1wk4z e10NZ16xzZx2KnS6pxufR34RBKbYq/wfZxum7rqpgv94ZkwyS8EIGTflqA1TTdXWlIQb Erl4KkVJqSzw5qS1hznacOIltDqp0ZNxpjuc1o28g0w6cQqxzzK6La/wy6CukIVkiDxz nLpXersyWXfV8rVjt0/C/NR70aeu9591zKadTp0OTXF1TeoEm1aM5xfODnutnhqlid23 YQor5K66veOmgXyouQWAR4Or6vaktI/b+D4MYqn9J2ZjGE8u1mYOAZJEoNWN8684n2tj uRvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1743453680; x=1744058480; 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=AIKL1AYd/xO+SLv3q7xjPwAw1WZmU0WoqzkDslwyHLg=; b=nWei1MYkU6kAB5wW37YA9D/NKJj6POJmkWaj8e4V/jzVNpb7YJFdsy85zAZb3BpJjy AoeyULivFzzGGOj6zXr6goFXVFiIVI+LH+eFlJEj8zjqyppCTGZqMa+ZF6YtcGsUaSyC 8Efmn2X5eRpVc1RguCowEz/Qe7K5KwWFUgAe+BXp2B+LbZ70Sjp7qmE0rOrjIsFsW0JC 5hGw33k+BAeNJkoazFpaHOLSzcqkgQg6sb/YbQ8oPIwCtkVlYdl3xrUxX5gZ3OYBhPuR iphVgLBb0I05194sUHdmfdGIO7p01xmUWdF4zlKgYQwVPiEstHl6tZSmyPsVr0IvcM/e MLPw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCV02INzH0BgJ53EdkPQGJf7ysyXWorIPz+CB0WQVtwJmAl+YbNESdHyEXGrDcaDwxgUZl1Qh7UiEQH6@gnusha.org X-Gm-Message-State: AOJu0YwqK28WjUyq3/bX9XsfyA+qIyhjbj2587mNv8KYIJwpZYiwWaSz X1hzIVnYi/kJmHZHv7xkVUnOMWvcMnJthYz4BOeDnZYhqvhV/V4M X-Google-Smtp-Source: AGHT+IFLnR2DwFIP33Hqhwu9EXY51XQK3r6zR4DfWbkn6TqJs66+xP4QHyOEcJqgIvXW0oYaF7Nfwg== X-Received: by 2002:a05:6902:108e:b0:e64:3f66:90b8 with SMTP id 3f1490d57ef6-e6b82dbb3c3mr15952153276.3.1743453680194; Mon, 31 Mar 2025 13:41:20 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJoVNJEQCIeyM7Q3BZ5A19yatJ3CO9lKocmUg157LwICA== Received: by 2002:a25:a05:0:b0:e63:6582:71d2 with SMTP id 3f1490d57ef6-e6942e67cf8ls1604384276.1.-pod-prod-01-us; Mon, 31 Mar 2025 13:41:16 -0700 (PDT) X-Received: by 2002:a05:690c:61c9:b0:6f7:5605:c62b with SMTP id 00721157ae682-703a40253c0mr7219127b3.27.1743453676383; Mon, 31 Mar 2025 13:41:16 -0700 (PDT) Received: by 2002:a05:690c:9a05:b0:6ef:590d:3213 with SMTP id 00721157ae682-70210946373ms7b3; Fri, 28 Mar 2025 15:40:15 -0700 (PDT) X-Received: by 2002:a05:690c:6082:b0:6f9:b12b:8943 with SMTP id 00721157ae682-702572731fbmr16213677b3.19.1743201613785; Fri, 28 Mar 2025 15:40:13 -0700 (PDT) Date: Fri, 28 Mar 2025 15:40:13 -0700 (PDT) From: Javier Mateos To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: <678d40e3-3e22-4d55-82c0-b25ccafb87ecn@googlegroups.com> <8c823e50-197e-479c-8651-9e0407a4168en@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_210538_699175425.1743201613472" X-Original-Sender: javierpmateos@gmail.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 (/) ------=_Part_210538_699175425.1743201613472 Content-Type: multipart/alternative; boundary="----=_Part_210539_408308505.1743201613472" ------=_Part_210539_408308505.1743201613472 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable The solution of splitting the string and using OP_CAT only works if the= =20 exact position of the substring is known. How would a case be handled where= =20 the substring could be in any position? =20 El mi=C3=A9rcoles, 19 de marzo de 2025 a las 22:02:05 UTC-3, Vojt=C4=9Bch S= trnad=20 escribi=C3=B3: > Hi Weichu, > > You can implement this game by having the user supply in the initial stac= k=20 > the two parts of their public key with the middle "goodluck" removed, and= =20 > inserting the "goodluck" as part of the script: > > - script: "goodluck" OP_SWAP OP_CAT OP_CAT OP_CHECKSIG > - initial stack: signature pubkey_left pubkey_right > > Hope this helps. > > Vojt=C4=9Bch > On Thursday, March 20, 2025 at 1:06:41=E2=80=AFAM UTC+1 weichu deng wrote= : > >> 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 you= r=20 >> example. However, if the target substring is located in the middle of th= e=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=9Cfo= obar=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 >> >> weich...@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 U= TC+8 10:28:25 =E5=86=99=E9=81=93=EF=BC=9A >> >>> Stack elements in Taproot are limited to 520 bytes. The current proposa= l=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 unfixe= d 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] B= AR=20 >>> CAT 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 i= n=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=20 >>> deterministic one. >>> Another case is when the substring in question is located in the middle= =20 >>> of the checked string. >>> CAT cannot replace ISSUBSTR for the following reasons: >>> >>> 1. The security of CAT is still controversial. It can easily=20 >>> generate overly long strings, potentially causing a stack overflow.= =20 >>> Additionally, whether OP_CAT will be restored is still under discuss= ion. >>> 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 = 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: >>> >=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=20 >>> OP_ISSUBSTRVERIFY=20 >>> > (similar to the relationship between OP_EQUAL and OP_EQUALVERIFY), to= =20 >>> > determine whether one string is a substring of another. As these=20 >>> opcodes 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=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b2= 5ccafb87ecn%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/= e8c30db7-b509-4fbd-93ef-0bca0313003cn%40googlegroups.com. ------=_Part_210539_408308505.1743201613472 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =C2=A0 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 w= here the substring could be in any position?=C2=A0=C2=A0

El mi=C3=A9rcole= s, 19 de marzo de 2025 a las 22:02:05 UTC-3, Vojt=C4=9Bch Strnad escribi=C3= =B3:
Hi = Weichu,

You can implement this game by having the = user supply in the initial stack the two parts of their public key with the= middle "goodluck" removed, and inserting the "goodluck"= ; as part of the script:
  • script: "goodluck" OP_= SWAP OP_CAT OP_CAT OP_CHECKSIG
  • initial stack: signature pubkey_left= pubkey_right
Hope this helps.

Vojt=C4=9Bch
On Thursday, March 20, 2025 at 1:06:41=E2=80=AFAM UTC+1 weichu de= ng wrote:

Hi Rijndael,

=C2=A0

Thanks for your example

[witness: foobar =C2=A0f= oo] 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 goo= dluck OP_ISSUBSTR...

- UnlockScript: signatur= e publicKey

How to implement it with OP_CAT?

=C2=A0

Regards

Weichu deng

weich...@stu2024.jnu.edu.cn=

=C2=A0


=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
Stac= k 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 scr= ipt).

Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOBAR FOO= BAR CAT EQ
Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D [witn= ess: FOOBAR FOO] BAR CAT EQ


rijndae= l=C2=A0


On Mar 18, 2025, at 11:32=E2=80=AFAM, weich= u deng <weich...@stu2024.jnu.edu.cn> wrote:
Hi,= Pe= ter Todd
Thanks for your = feedback. I agree that "Bitcoin scripts are about validation. Not comp= utation."
String search and= concatenation are equivalent in some cases, such as in the example you pro= vided.
However, it is still nece= ssary to introduce the OP_ISSUBSTR operation separately.
One example is converting a non-deterministic sign= ature to a deterministic one.
An= other case is when the substring in question is located in the middle of th= e checked string.
CAT cannot rep= lace ISSUBSTR for the following reasons:
    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.
  1. The other substring (bar) must be known in a= dvance.

With respect,

Weichu Deng

weic= h...@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<Peter Todd> =E5=86=99=E9=81=93=EF=BC=9A
On Mon, M= ar 17, 2025 at 09:14:05AM -0700, weichu deng wrote:
>=C2=A0
>=C2=A0
> Dear fellow Bitcoin developers,
&= gt;=C2=A0
>=C2=A0
>=C2=A0
> I am pleased to present a new BIP proposal. This proposal introdu= ces a new=C2=A0
> opcode for Bitcoin scripts: OP_ISSUBST= R.
>=C2=A0
>=C2=A0
> *Abstract*=
>=C2=A0
> This BIP introduces two string opcodes,= OP_ISSUBSTR and OP_ISSUBSTRVERIFY=C2=A0
> (similar to t= he relationship between OP_EQUAL and OP_EQUALVERIFY), to=C2=A0=
> determine whether one string is a substring of another. As these o= pcodes do=C2=A0
> not alter any blockchain state, they a= re 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
conc= atenate the substring with the rest of the string, and validate
equality= instead.

Basically speaking:

foobar foo IsSubStr

is e= quivalent to:

foobar foo bar Cat Equal

A real-world example w= ould be more complex. But I hope that illustrates
my point sufficiently.=

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

=
--=C2=A0
You received this message because you are subscribed to= the Google Groups "Bitcoin Development Mailing List" group.
T= o unsubscribe from this group and stop receiving emails from it, send an em= ail to=C2=A0bitcoindev+...@googlegroups.com= .
To view thi= s discussion visit=C2=A0https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25cc= afb87ecn%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/e8c30db7-b509-4fbd-93ef-0bca0313003cn%40googlegroups.com.
------=_Part_210539_408308505.1743201613472-- ------=_Part_210538_699175425.1743201613472--