Delivery-date: Wed, 19 Mar 2025 18:02:12 -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 1tv4IV-0004QM-Fr for bitcoindev@gnusha.org; Wed, 19 Mar 2025 18:02:12 -0700 Received: by mail-yb1-f191.google.com with SMTP id 3f1490d57ef6-e3a109984a5sf242782276.3 for ; Wed, 19 Mar 2025 18:02:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1742432526; x=1743037326; 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=lyL7fGAznaVUTmfoImjuhMWBnZzWq8eoIUenAe5hydc=; b=ovCjgGcW/4Woaugqmt1LoKhQPzZQ01Ah/QcErmb1lnctMlXNKheIrOFMxEllVs6h3L i0jqGYV3Iun0urWTnkM3KZxfxdIc6ewS/GDb6TINGRBh61rgojU6Xqy3/gdF8jYGZuH2 QMNWSoieK1GuWSrXKLGtjKB4/V3vCVplSA0AZWIDs7WWlWGjhRwcga29hVOBRrNAXguw algjNQbneefnhMnWTvmZWPOOJ8uoDJ2DZ4EGsbhgWGVemCmZvLeGMpLlUZSPt6Tp8PPl G7nusQfh3hN17Dh+SLq9kbmmvVKy2+Jr7ZX/JKTfCjAN1Vbvn8NJweG/NWSXzYULyJrB hg6Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1742432526; x=1743037326; 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=lyL7fGAznaVUTmfoImjuhMWBnZzWq8eoIUenAe5hydc=; b=k3gSezGXH9bw/NBg53ztqPFWcTExxIhr/6oV2vqoNthu5HCsiLnWPqFUAfdwaYZ3vm KSq48ztBZfVoJopMSwmHqwtv20T5Beq8v0iH5AmGvCeXAn8DgNigcjBKjMRlRWHgRaxx yLRL9ediT+EvITxrHKQ1wKYHqYIky5S60mclpCNxhGFNgjemsv0zRqDavDN1seUdrAIn MwJ5N9r1FvD/m/eps/I0FoV+cChxfEf/qSlx/w4ACkw/ougmAu6OAPjlReSwhfb7jx+C jJpLPyypx71RRfbcpCWpq8XEFNtVb3LwYQkx4SEvxV0LAwjPJUmakP+s35bWww+eQwPh L79g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742432526; x=1743037326; 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=lyL7fGAznaVUTmfoImjuhMWBnZzWq8eoIUenAe5hydc=; b=iaBKjA3jrYSvc5o1bmfIHqnuMv+uTWRXkczIbrs89uasfv/zBgmK7SQWUs43sfUnsT jASAjSrP5KboWp4mo3oTJwHeHspOlXQdPFtyuE1nCnsaLt/YZp5bWHChoPI8ccZdGzqt 7h3g0CLHps6M6BfR6RcxZqLkUpdo1yEnNQ9CHhBH+7MgUOYWC9hU/Ryj/dJ0sLG6szdG B2xDk4vWWba4FT+rQM9AUPOcUB3QDE6ci48zI1y31SptMSx3goFVLDQdXRzdIPSrmTOU EzPL0rP0kXH5NLx2VqtvfroTFff2RwDgyfrJ8qY/AG+OiCs86wWJJV+IdKNziRYrr2W8 Rt4Q== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXlnWflBLL5ewexYP8o02WA+yHSww0625sITM8+DmZfe+NPkqZW/sDFJrFYga0jcPWeGdsf4G4mxn5+@gnusha.org X-Gm-Message-State: AOJu0Yyt+7Fq6nHwuri8WSEQCnAELRGknNcP12T8DlRApDfO5eCayPxs 1ZMQURoW+DjgGpf91nYsoU4w4c7h5t42eNf4VV6GSqJ8SmX7ba9M X-Google-Smtp-Source: AGHT+IGA+VKpOxQtAw8g6C2/0u37V33WsbNgpv5aoPDbSO3otlud2cyl0j8E9MOIE2acqwl7TmkINQ== X-Received: by 2002:a05:6902:1441:b0:e60:88f9:b08a with SMTP id 3f1490d57ef6-e667b4568e2mr6382973276.45.1742432525753; Wed, 19 Mar 2025 18:02:05 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJp6pAUIrGIGEYhqsBX69/7vUOqS6m04N7OrVmoXO0yZA== Received: by 2002:a05:6902:2613:b0:e5d:f8a4:fa22 with SMTP id 3f1490d57ef6-e66908f808fls656263276.0.-pod-prod-08-us; Wed, 19 Mar 2025 18:02:02 -0700 (PDT) X-Received: by 2002:a05:690c:6c0a:b0:6f9:8605:ec98 with SMTP id 00721157ae682-700ac691e5bmr15660617b3.28.1742432521990; Wed, 19 Mar 2025 18:02:01 -0700 (PDT) Received: by 2002:a05:690c:6a86:b0:6ef:590d:3213 with SMTP id 00721157ae682-7009ba67b04ms7b3; Wed, 19 Mar 2025 17:23:54 -0700 (PDT) X-Received: by 2002:a05:690c:998a:b0:6fe:b88e:4d9b with SMTP id 00721157ae682-7009c02dc8bmr73313557b3.27.1742430233094; Wed, 19 Mar 2025 17:23:53 -0700 (PDT) Date: Wed, 19 Mar 2025 17:23:52 -0700 (PDT) From: =?UTF-8?Q?Vojt=C4=9Bch_Strnad?= To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <8c823e50-197e-479c-8651-9e0407a4168en@googlegroups.com> 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_17068_155918463.1742430232792" X-Original-Sender: vojta.strnad@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_17068_155918463.1742430232792 Content-Type: multipart/alternative; boundary="----=_Part_17069_439175514.1742430232792" ------=_Part_17069_439175514.1742430232792 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Weichu, You can implement this game by having the user supply in the initial stack= =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 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=9Cfoo= bar=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 UT= C+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] BA= R 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=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 generate= =20 >> overly long strings, potentially causing a stack overflow. Additional= ly,=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 U= TC+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 Group= s=20 >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n=20 >> email to bitcoindev+...@googlegroups.com. >> To view this discussion visit=20 >> https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25= ccafb87ecn%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/= b4594133-e6e5-438b-aa56-98d6171296fan%40googlegroups.com. ------=_Part_17069_439175514.1742430232792 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Weichu,

You can implement this game by h= aving the user supply in the initial stack the two parts of their public ke= y with the middle "goodluck" removed, and inserting the "goodluck" as part = of the script:
  • script: "goodluck" OP_SWAP OP_CAT OP_CAT O= P_CHECKSIG
  • initial stack: signature pubkey_left pubkey_right
Hope this helps.

Vojt=C4=9Bch
On Thurs= day, March 20, 2025 at 1:06:41=E2=80=AFAM UTC+1 weichu deng 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/b4594133-e6e5-438b-aa56-98d6171296fan%40googlegroups.com.
------=_Part_17069_439175514.1742430232792-- ------=_Part_17068_155918463.1742430232792--