diff options
| author | Javier Mateos <javierpmateos@gmail.com> | 2025-03-28 15:40:13 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@googlegroups.com> | 2025-03-31 13:41:27 -0700 |
| commit | 42beff0ca9c4a49a6d9d81508f04b314832f8852 (patch) | |
| tree | 68c2c64b1874d5de17dea55cff745cf06c5814fa | |
| parent | 73299f3e822d3efec5fae86fac5b1fb02cd6cebc (diff) | |
| download | pi-bitcoindev-42beff0ca9c4a49a6d9d81508f04b314832f8852.tar.gz pi-bitcoindev-42beff0ca9c4a49a6d9d81508f04b314832f8852.zip | |
Re: [bitcoindev] New Proposal：String Substring Search in Bitcoin Script - OP_ISSUBSTR
| -rw-r--r-- | 57/20aec1288fa217895508abab570ebb8e78de83 | 635 |
1 files changed, 635 insertions, 0 deletions
diff --git a/57/20aec1288fa217895508abab570ebb8e78de83 b/57/20aec1288fa217895508abab570ebb8e78de83 new file mode 100644 index 000000000..ec22c80c0 --- /dev/null +++ b/57/20aec1288fa217895508abab570ebb8e78de83 @@ -0,0 +1,635 @@ +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 <bitcoindev+bncBDQ6BG4PT4CRB3H3VO7QMGQEIZFJVUI@googlegroups.com>) + 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 <bitcoindev@gnusha.org>; 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 <javierpmateos@gmail.com> +To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Message-Id: <e8c30db7-b509-4fbd-93ef-0bca0313003cn@googlegroups.com> +In-Reply-To: <b4594133-e6e5-438b-aa56-98d6171296fan@googlegroups.com> +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> +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: <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.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<Rijndael> =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 <weich...@stu2024.jnu= +.edu.cn>=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<Peter Todd> =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 +>>> <https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b= +25ccafb87ecn%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter> +>>> . +>>> +>>> +>>> + +--=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<br /><br /><div cl= +ass=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">El mi=C3=A9rcole= +s, 19 de marzo de 2025 a las 22:02:05 UTC-3, Vojt=C4=9Bch Strnad escribi=C3= +=B3:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8= +ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div>Hi = +Weichu,</div><div><br></div><div>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:</div><div><ul><li>script: "goodluck" OP_= +SWAP OP_CAT OP_CAT OP_CHECKSIG</li><li>initial stack: signature pubkey_left= + pubkey_right</li></ul></div><div>Hope this helps.</div><div><br></div><div= +>Vojt=C4=9Bch</div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gm= +ail_attr">On Thursday, March 20, 2025 at 1:06:41=E2=80=AFAM UTC+1 weichu de= +ng wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 = +0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p><span lan= +g=3D"EN-US">Hi Rijndael,</span></p> + +<p><span lang=3D"EN-US">=C2=A0</span></p> + +<p><span lang=3D"EN-US">Thanks for your example </span></p> + +<p style=3D"text-indent:12pt"><span lang=3D"EN-US">[witness: foobar =C2=A0f= +oo] bar CAT +EQ</span></p> + +<p><span lang=3D"EN-US">=C2=A0</span></p> + +<p><span lang=3D"EN-US">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?</span></p> + +<p><span lang=3D"EN-US">=C2=A0</span></p> + +<p><span lang=3D"EN-US">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. </span></p> + +<p><span lang=3D"EN-US">This game can be easily implemented with +OP_ISSUBSTR as follow.</span></p> + +<p style=3D"text-indent:48pt"><span lang=3D"EN-US">- LockScript: OP_DUP goo= +dluck OP_ISSUBSTR...</span></p> + +<p style=3D"text-indent:48pt"><span lang=3D"EN-US">- UnlockScript: signatur= +e publicKey</span></p> + +<p><span lang=3D"EN-US">How to implement it with OP_CAT?<b></b></span></p> + +<p><b><span lang=3D"EN-US">=C2=A0</span></b></p> + +<p><b><span lang=3D"EN-US">Regards</span></b><span lang=3D"EN-US"></span></= +p> + +<p><span lang=3D"EN-US">Weichu deng</span></p> + +<p><span lang=3D"EN-US"><a rel=3D"nofollow">weich...@stu2024.jnu.edu.cn</a>= +</span></p> + +<p><span lang=3D"EN-US">=C2=A0</span></p><br><div class=3D"gmail_quote"><di= +v 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<br></div><blockquote class=3D"gmail_quote" style=3D"marg= +in:0 0 0 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di= +v dir=3D"ltr"><div dir=3D"auto" style=3D"line-break:after-white-space">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.<div><br></div><div>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).</div><div><br></div><div>Fixed: FOOBAR BAR ISSUBSTR =3D=3D FOOBAR FOO= + BAR CAT EQ</div><div>Variable: [witness: FOOBAR] BAR ISSUBSTR =3D=3D [witn= +ess: FOOBAR FOO] BAR CAT EQ</div><div><br></div><div><br></div><div>rijndae= +l=C2=A0</div><div><br><div style=3D"direction:ltr"><br><blockquote type=3D"= +cite"></blockquote></div></div></div></div><div dir=3D"ltr"><div dir=3D"aut= +o" style=3D"line-break:after-white-space"><div><div style=3D"direction:ltr"= +><blockquote type=3D"cite"><div>On Mar 18, 2025, at 11:32=E2=80=AFAM, weich= +u deng <<a rel=3D"nofollow">weich...@stu2024.jnu.edu.cn</a>> wrote:</= +div><br></blockquote></div></div></div></div><div dir=3D"ltr"><div dir=3D"a= +uto" style=3D"line-break:after-white-space"><div><div style=3D"direction:lt= +r"><blockquote type=3D"cite"><div><div style=3D"font-size:12px;font-style:n= +ormal;font-variant-caps:normal;font-weight:400;text-align:start;text-indent= +:0px;text-transform:none;white-space:pre-wrap;word-spacing:0px;text-decorat= +ion:none;padding:0px;border:0px;font-variant-numeric:inherit;font-variant-e= +ast-asian:inherit;font-variant-alternates:inherit;font-stretch:inherit;line= +-height:24px;font-family:-apple-system,BlinkMacSystemFont,"Helvetica N= +eue",Helvetica,"Segoe UI",Arial,Roboto,"PingFang SC&quo= +t;,MIUI,"Hiragino Sans GB","Microsoft YaHei",sans-serif= +;font-size-adjust:inherit;font-kerning:inherit;font-feature-settings:inheri= +t;vertical-align:baseline;margin:0px 0px 0.859em;letter-spacing:0.25px;max-= +width:100%;overflow:auto hidden;color:rgb(6,6,7);word-break:break-word">Hi,= + <span style=3D"color:rgb(32,33,36);font-family:Roboto,Arial,sans-serif">Pe= +ter Todd</span></div><div style=3D"font-size:12px;font-style:normal;font-va= +riant-caps:normal;font-weight:400;text-align:start;text-indent:0px;text-tra= +nsform:none;white-space:pre-wrap;word-spacing:0px;text-decoration:none;padd= +ing:0px;border:0px;font-variant-numeric:inherit;font-variant-east-asian:inh= +erit;font-variant-alternates:inherit;font-stretch:inherit;line-height:24px;= +font-family:-apple-system,BlinkMacSystemFont,"Helvetica Neue",Hel= +vetica,"Segoe UI",Arial,Roboto,"PingFang SC",MIUI,"= +;Hiragino Sans GB","Microsoft YaHei",sans-serif;font-size-ad= +just:inherit;font-kerning:inherit;font-feature-settings:inherit;vertical-al= +ign:baseline;margin:0px 0px 0.859em;letter-spacing:0.25px;max-width:100%;ov= +erflow:auto hidden;color:rgb(6,6,7);word-break:break-word">Thanks for your = +feedback. I agree that "Bitcoin scripts are about validation. Not comp= +utation."</div><div style=3D"font-size:12px;font-style:normal;font-var= +iant-caps:normal;font-weight:400;text-align:start;text-indent:0px;text-tran= +sform:none;white-space:pre-wrap;word-spacing:0px;text-decoration:none;paddi= +ng:0px;border:0px;font-variant-numeric:inherit;font-variant-east-asian:inhe= +rit;font-variant-alternates:inherit;font-stretch:inherit;line-height:24px;f= +ont-family:-apple-system,BlinkMacSystemFont,"Helvetica Neue",Helv= +etica,"Segoe UI",Arial,Roboto,"PingFang SC",MIUI,"= +Hiragino Sans GB","Microsoft YaHei",sans-serif;font-size-adj= +ust:inherit;font-kerning:inherit;font-feature-settings:inherit;vertical-ali= +gn:baseline;margin:0px 0px 0.859em;letter-spacing:0.25px;max-width:100%;ove= +rflow:auto hidden;color:rgb(6,6,7);word-break:break-word">String search and= + concatenation are equivalent in some cases, such as in the example you pro= +vided.</div><div style=3D"font-size:12px;font-style:normal;font-variant-cap= +s:normal;font-weight:400;text-align:start;text-indent:0px;text-transform:no= +ne;white-space:pre-wrap;word-spacing:0px;text-decoration:none;padding:0px;b= +order:0px;font-variant-numeric:inherit;font-variant-east-asian:inherit;font= +-variant-alternates:inherit;font-stretch:inherit;line-height:24px;font-fami= +ly:-apple-system,BlinkMacSystemFont,"Helvetica Neue",Helvetica,&q= +uot;Segoe UI",Arial,Roboto,"PingFang SC",MIUI,"Hiragino= + Sans GB","Microsoft YaHei",sans-serif;font-size-adjust:inhe= +rit;font-kerning:inherit;font-feature-settings:inherit;vertical-align:basel= +ine;margin:0px 0px 0.859em;letter-spacing:0.25px;max-width:100%;overflow:au= +to hidden;color:rgb(6,6,7);word-break:break-word">However, it is still nece= +ssary to introduce the OP_ISSUBSTR operation separately.</div><div style=3D= +"font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:400;= +text-align:start;text-indent:0px;text-transform:none;white-space:pre-wrap;w= +ord-spacing:0px;text-decoration:none;padding:0px;border:0px;font-variant-nu= +meric:inherit;font-variant-east-asian:inherit;font-variant-alternates:inher= +it;font-stretch:inherit;line-height:24px;font-family:-apple-system,BlinkMac= +SystemFont,"Helvetica Neue",Helvetica,"Segoe UI",Arial,= +Roboto,"PingFang SC",MIUI,"Hiragino Sans GB","Micr= +osoft YaHei",sans-serif;font-size-adjust:inherit;font-kerning:inherit;= +font-feature-settings:inherit;vertical-align:baseline;margin:0px 0px 0.859e= +m;letter-spacing:0.25px;max-width:100%;overflow:auto hidden;color:rgb(6,6,7= +);word-break:break-word">One example is converting a non-deterministic sign= +ature to a deterministic one.</div><div style=3D"font-size:12px;font-style:= +normal;font-variant-caps:normal;font-weight:400;text-align:start;text-inden= +t:0px;text-transform:none;white-space:pre-wrap;word-spacing:0px;text-decora= +tion:none;padding:0px;border:0px;font-variant-numeric:inherit;font-variant-= +east-asian:inherit;font-variant-alternates:inherit;font-stretch:inherit;lin= +e-height:24px;font-family:-apple-system,BlinkMacSystemFont,"Helvetica = +Neue",Helvetica,"Segoe UI",Arial,Roboto,"PingFang SC&qu= +ot;,MIUI,"Hiragino Sans GB","Microsoft YaHei",sans-seri= +f;font-size-adjust:inherit;font-kerning:inherit;font-feature-settings:inher= +it;vertical-align:baseline;margin:0px 0px 0.859em;letter-spacing:0.25px;max= +-width:100%;overflow:auto hidden;color:rgb(6,6,7);word-break:break-word">An= +other case is when the substring in question is located in the middle of th= +e checked string.</div><div style=3D"font-size:12px;font-style:normal;font-= +variant-caps:normal;font-weight:400;text-align:start;text-indent:0px;text-t= +ransform:none;white-space:pre-wrap;word-spacing:0px;text-decoration:none;pa= +dding:0px;border:0px;font-variant-numeric:inherit;font-variant-east-asian:i= +nherit;font-variant-alternates:inherit;font-stretch:inherit;line-height:24p= +x;font-family:-apple-system,BlinkMacSystemFont,"Helvetica Neue",H= +elvetica,"Segoe UI",Arial,Roboto,"PingFang SC",MIUI,&qu= +ot;Hiragino Sans GB","Microsoft YaHei",sans-serif;font-size-= +adjust:inherit;font-kerning:inherit;font-feature-settings:inherit;vertical-= +align:baseline;margin:0px 0px 0.859em;letter-spacing:0.25px;max-width:100%;= +overflow:auto hidden;color:rgb(6,6,7);word-break:break-word">CAT cannot rep= +lace ISSUBSTR for the following reasons:</div><ol start=3D"1" style=3D"font= +-size:12px;font-style:normal;font-variant-caps:normal;font-weight:400;text-= +align:start;text-indent:0px;text-transform:none;white-space:normal;word-spa= +cing:0px;text-decoration:none;padding:0px 0px 0px 2em;border:0px;font-varia= +nt-numeric:inherit;font-variant-east-asian:inherit;font-variant-alternates:= +inherit;font-stretch:inherit;line-height:inherit;font-family:-apple-system,= +BlinkMacSystemFont,"Helvetica Neue",Helvetica,"Segoe UI"= +;,Arial,Roboto,"PingFang SC",MIUI,"Hiragino Sans GB",&q= +uot;Microsoft YaHei",sans-serif;font-size-adjust:inherit;font-kerning:= +inherit;font-feature-settings:inherit;vertical-align:baseline;list-style-po= +sition:initial;margin:0.859em 0px 0px;color:rgb(6,6,7);letter-spacing:0.5px= +"><li style=3D"margin:0px;padding:0px;border:0px;font-style:inherit;font-va= +riant-ligatures:inherit;font-variant-caps:inherit;font-variant-alternates:i= +nherit;font-variant-numeric:inherit;font-variant-east-asian:inherit;font-we= +ight:inherit;font-stretch:inherit;font-size:inherit;line-height:24px;font-f= +amily:inherit;font-size-adjust:inherit;font-kerning:inherit;font-feature-se= +ttings:inherit;vertical-align:baseline;letter-spacing:0.25px"><div style=3D= +"padding:0px;border:0px;font-style:inherit;font-variant-ligatures:inherit;f= +ont-variant-caps:inherit;font-variant-alternates:inherit;font-variant-numer= +ic:inherit;font-variant-east-asian:inherit;font-weight:inherit;font-stretch= +:inherit;line-height:24px;font-family:inherit;font-size-adjust:inherit;font= +-kerning:inherit;font-feature-settings:inherit;vertical-align:baseline;marg= +in:0px;max-width:100%;overflow:visible;word-break:break-word">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.</div></li><li style=3D"margin:0px;paddi= +ng:0px;border:0px;font-style:inherit;font-variant-ligatures:inherit;font-va= +riant-caps:inherit;font-variant-alternates:inherit;font-variant-numeric:inh= +erit;font-variant-east-asian:inherit;font-weight:inherit;font-stretch:inher= +it;font-size:inherit;line-height:24px;font-family:inherit;font-size-adjust:= +inherit;font-kerning:inherit;font-feature-settings:inherit;vertical-align:b= +aseline;letter-spacing:0.25px"><div style=3D"padding:0px;border:0px;font-st= +yle:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;font-v= +ariant-alternates:inherit;font-variant-numeric:inherit;font-variant-east-as= +ian:inherit;font-weight:inherit;font-stretch:inherit;line-height:24px;font-= +family:inherit;font-size-adjust:inherit;font-kerning:inherit;font-feature-s= +ettings:inherit;vertical-align:baseline;margin:0px;max-width:100%;overflow:= +visible;word-break:break-word">The other substring (bar) must be known in a= +dvance.</div></li></ol><div style=3D"font-family:Helvetica;font-size:12px;f= +ont-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:no= +rmal;text-align:start;text-indent:0px;text-transform:none;white-space:norma= +l;word-spacing:0px;text-decoration:none"><font color=3D"#060607" face=3D"-a= +pple-system, BlinkMacSystemFont, Helvetica Neue, Helvetica, Segoe UI, Arial= +, Roboto, PingFang SC, MIUI, Hiragino Sans GB, Microsoft YaHei, sans-serif"= +><span style=3D"letter-spacing:0.25px"><br></span></font></div><div style= +=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-variant-cap= +s:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent= +:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoratio= +n:none"><p><span lang=3D"EN-US">With respect,</span></p><p><span lang=3D"EN= +-US">Weichu Deng</span></p><p><span lang=3D"EN-US"><a rel=3D"nofollow">weic= +h...@stu2024.jnu.edu.cn</a></span></p></div><div style=3D"font-family:Helve= +tica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:= +400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:n= +one;white-space:normal;word-spacing:0px;text-decoration:none"><div dir=3D"a= +uto">=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<br></div><blo= +ckquote style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left= +-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">On Mon, M= +ar 17, 2025 at 09:14:05AM -0700, weichu deng wrote:<br>><span>=C2=A0</sp= +an><br>><span>=C2=A0</span><br>> Dear fellow Bitcoin developers,<br>&= +gt;<span>=C2=A0</span><br>><span>=C2=A0</span><br>><span>=C2=A0</span= +><br>> I am pleased to present a new BIP proposal. This proposal introdu= +ces a new<span>=C2=A0</span><br>> opcode for Bitcoin scripts: OP_ISSUBST= +R.<br>><span>=C2=A0</span><br>><span>=C2=A0</span><br>> *Abstract*= +<br>><span>=C2=A0</span><br>> This BIP introduces two string opcodes,= + OP_ISSUBSTR and OP_ISSUBSTRVERIFY<span>=C2=A0</span><br>> (similar to t= +he relationship between OP_EQUAL and OP_EQUALVERIFY), to<span>=C2=A0</span>= +<br>> determine whether one string is a substring of another. As these o= +pcodes do<span>=C2=A0</span><br>> not alter any blockchain state, they a= +re secure.<br><br>Bitcoin scripts are about validation. Not computation.<br= +><br>This means that substring search and concatenation are equivalent. For= +<br>every script that validates a substring search, you can instead<br>conc= +atenate the substring with the rest of the string, and validate<br>equality= + instead.<br><br>Basically speaking:<br><br>foobar foo IsSubStr<br><br>is e= +quivalent to:<br><br>foobar foo bar Cat Equal<br><br>A real-world example w= +ould be more complex. But I hope that illustrates<br>my point sufficiently.= +<br><br>--<span>=C2=A0</span><br><a href=3D"https://petertodd.org/" rel=3D"= +nofollow" target=3D"_blank" data-saferedirecturl=3D"https://www.google.com/= +url?hl=3Des&q=3Dhttps://petertodd.org/&source=3Dgmail&ust=3D174= +3287600558000&usg=3DAOvVaw1Ik2DvB3qmfvCC6WNopIcs">https://petertodd.org= +</a><span>=C2=A0</span>'peter'[:-1]@<a href=3D"http://petertodd.org= +/" rel=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https://www.g= +oogle.com/url?hl=3Des&q=3Dhttp://petertodd.org/&source=3Dgmail&= +ust=3D1743287600558000&usg=3DAOvVaw3q9sFCwjUyG-epYef9h89z">petertodd.or= +g</a><br></blockquote></div><div style=3D"font-family:Helvetica;font-size:1= +2px;font-style:normal;font-variant-caps:normal;font-weight:400;letter-spaci= +ng:normal;text-align:start;text-indent:0px;text-transform:none;white-space:= +normal;word-spacing:0px;text-decoration:none"><br></div></div></blockquote>= +</div></div></div></div><div dir=3D"ltr"><div dir=3D"auto" style=3D"line-br= +eak:after-white-space"><div><div style=3D"direction:ltr"><blockquote type= +=3D"cite"><div><span style=3D"font-family:Helvetica;font-size:12px;font-sty= +le:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;te= +xt-align:start;text-indent:0px;text-transform:none;white-space:normal;word-= +spacing:0px;text-decoration:none;float:none;display:inline!important">--<sp= +an>=C2=A0</span></span><br style=3D"font-family:Helvetica;font-size:12px;fo= +nt-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:nor= +mal;text-align:start;text-indent:0px;text-transform:none;white-space:normal= +;word-spacing:0px;text-decoration:none"><span style=3D"font-family:Helvetic= +a;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:400= +;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none= +;white-space:normal;word-spacing:0px;text-decoration:none;float:none;displa= +y:inline!important">You received this message because you are subscribed to= + the Google Groups "Bitcoin Development Mailing List" group.</spa= +n><br style=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-= +variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;= +text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;tex= +t-decoration:none"><span style=3D"font-family:Helvetica;font-size:12px;font= +-style:normal;font-variant-caps:normal;font-weight:400;letter-spacing:norma= +l;text-align:start;text-indent:0px;text-transform:none;white-space:normal;w= +ord-spacing:0px;text-decoration:none;float:none;display:inline!important">T= +o unsubscribe from this group and stop receiving emails from it, send an em= +ail to<span>=C2=A0</span></span><a style=3D"font-family:Helvetica;font-size= +:12px;font-style:normal;font-variant-caps:normal;font-weight:400;letter-spa= +cing:normal;text-align:start;text-indent:0px;text-transform:none;white-spac= +e:normal;word-spacing:0px" rel=3D"nofollow">bitcoindev+...@googlegroups.com= +</a><span style=3D"font-family:Helvetica;font-size:12px;font-style:normal;f= +ont-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:st= +art;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px= +;text-decoration:none;float:none;display:inline!important">.</span><br styl= +e=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-variant-ca= +ps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-inden= +t:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decorati= +on:none"><span style=3D"font-family:Helvetica;font-size:12px;font-style:nor= +mal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-ali= +gn:start;text-indent:0px;text-transform:none;white-space:normal;word-spacin= +g:0px;text-decoration:none;float:none;display:inline!important">To view thi= +s discussion visit<span>=C2=A0</span></span><a href=3D"https://groups.googl= +e.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25ccafb87ecn%40googlegrou= +ps.com?utm_medium=3Demail&utm_source=3Dfooter" style=3D"font-family:Hel= +vetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weigh= +t:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform= +:none;white-space:normal;word-spacing:0px" rel=3D"nofollow" target=3D"_blan= +k" data-saferedirecturl=3D"https://www.google.com/url?hl=3Des&q=3Dhttps= +://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25ccafb87e= +cn%2540googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&source= +=3Dgmail&ust=3D1743287600558000&usg=3DAOvVaw24Jy-cBu9db9jrBHwaj2U3"= +>https://groups.google.com/d/msgid/bitcoindev/678d40e3-3e22-4d55-82c0-b25cc= +afb87ecn%40googlegroups.com</a><span style=3D"font-family:Helvetica;font-si= +ze:12px;font-style:normal;font-variant-caps:normal;font-weight:400;letter-s= +pacing:normal;text-align:start;text-indent:0px;text-transform:none;white-sp= +ace:normal;word-spacing:0px;text-decoration:none;float:none;display:inline!= +important">.</span></div></blockquote></div><br></div></div></div> +</blockquote></div></blockquote></div></blockquote></div> + +<p></p> + +-- <br /> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" group.<br /> +To unsubscribe from this group and stop receiving emails from it, send an e= +mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind= +ev+unsubscribe@googlegroups.com</a>.<br /> +To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= +bitcoindev/e8c30db7-b509-4fbd-93ef-0bca0313003cn%40googlegroups.com?utm_med= +ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= +ev/e8c30db7-b509-4fbd-93ef-0bca0313003cn%40googlegroups.com</a>.<br /> + +------=_Part_210539_408308505.1743201613472-- + +------=_Part_210538_699175425.1743201613472-- + |