Delivery-date: Tue, 18 Mar 2025 14:25:28 -0700 Received: from mail-yb1-f185.google.com ([209.85.219.185]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tueRE-0000Gm-2H for bitcoindev@gnusha.org; Tue, 18 Mar 2025 14:25:28 -0700 Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e549b6c54a0sf9741306276.3 for ; Tue, 18 Mar 2025 14:25:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1742333122; x=1742937922; 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=WYBtHiCzxwrUNoEUKu3O7grN+TzHYVNSoIzBFI82cZo=; b=pBaewn+Z/S51MsEkjkjtM98Pitd5Krwx+jKXdDQZbir3IB6KCG/vJOs82W1VNXIRH+ nNtuSuvAOQzkE9meWQdMxmcyDwVadOYxX+fvsRgodm8pbPm9umObFi3bpAdbphc+wX6L 3EYbpfgj8NuQFfTUBEjynPl26uQsyZ/xgxt1L2X/qE0WY6T8y740bLo97VIUv0bt6Ep6 jilgU3zwqIneltkp6Vq24Aw6pisdz4sILWcWvo7rvOytYANIgR/8Qp3DQC3eqUCHh+fR Sk7dVfraMTpPoof0mRKR8vuluEMHAD89pU4+zN7D8cQ2NhMsDiH+ps8Xg2gDxCaWeKsm KRwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742333122; x=1742937922; 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=WYBtHiCzxwrUNoEUKu3O7grN+TzHYVNSoIzBFI82cZo=; b=ci6iYhd9cFBnlQblce/nZ0gZv41wKx40bZTL6qsPCprMx8VAklm+irDCDUHUz4RP1z xjV9JMm0iiz8ejCMPVjsbIUurcxXt3Q0c7wtlsRV4neYlJv1Zez5vqkAdPg8+fNI6noi Tw+oEYeURBOUbIQgr/oxnB/hHJ1hzuuB4qleYkQjWCunGnUHa58bkQ/TEO2AadB3rtc/ 6pB9XV+UWz0Ap89qh91XrzmNXLOXsze/cIRTKnJ66fhMxNCYHJz8Y0QFI6lWspuoKNKB asq8ZZ74kt6499nwl5GNdke1oep3iwUN9j35FYE3bu/J6oLVKgza92xuqZoUL7AI3f6W yVvw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWaGmfjaXQvIHQBuEOT4D2gnH8elkPQIj0Si6KyYdxBzNSbOxNpN4/UOhHi34vXFhrrszarhhduRvXz@gnusha.org X-Gm-Message-State: AOJu0YyU4ACXWqd/dHxff9YmqRAkpCy2YyfGfct3pOm9lZj8KfmKi7rU nLOzgaChDSruszDkTek0cS98hdo4z44JZ5dm19rcDsS7dkbFL/L/ X-Google-Smtp-Source: AGHT+IGmkDIfcRX6GYNwBBrtPlmElv3Uv2ormI4E5zjbOTV1JRQE14Bkre/dkzr416PqMZ7dVqQAGw== X-Received: by 2002:a05:6902:2206:b0:e5d:d4e3:ad8 with SMTP id 3f1490d57ef6-e667b3f68abmr388139276.28.1742333122386; Tue, 18 Mar 2025 14:25:22 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAKIwdj6wlzJ+RhOgo5UF6dSTMR+V6CB392tUFE73/DhKQ== Received: by 2002:a25:3d84:0:b0:e63:65ef:4018 with SMTP id 3f1490d57ef6-e63dc2c1b9els43578276.1.-pod-prod-09-us; Tue, 18 Mar 2025 14:25:18 -0700 (PDT) X-Received: by 2002:a05:690c:4912:b0:6fd:4670:80e5 with SMTP id 00721157ae682-7009c16968dmr6828967b3.35.1742333118450; Tue, 18 Mar 2025 14:25:18 -0700 (PDT) Received: by 2002:a05:690c:305:b0:6fe:b496:fc0e with SMTP id 00721157ae682-6ff454db01cms7b3; Tue, 18 Mar 2025 08:32:44 -0700 (PDT) X-Received: by 2002:a05:690c:6108:b0:6fb:b8a1:d3bb with SMTP id 00721157ae682-6ff45f202c9mr228426637b3.17.1742311960561; Tue, 18 Mar 2025 08:32:40 -0700 (PDT) Date: Tue, 18 Mar 2025 08:32:40 -0700 (PDT) From: weichu deng To: Bitcoin Development Mailing List Message-Id: <678d40e3-3e22-4d55-82c0-b25ccafb87ecn@googlegroups.com> In-Reply-To: References: 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_563456_1611484715.1742311960313" 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_563456_1611484715.1742311960313 Content-Type: multipart/alternative; boundary="----=_Part_563457_1151508066.1742311960314" ------=_Part_563457_1151508066.1742311960314 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 deterministic= =20 one. Another case is when the substring in question is located in the middle of= =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. Additionally,= =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 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:=20 >=20 >=20 > Dear fellow Bitcoin developers,=20 >=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 >=20 > *Abstract*=20 >=20 > This BIP introduces two string opcodes, OP_ISSUBSTR and 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 opcodes= =20 do=20 > not alter any blockchain state, they are secure.=20 Bitcoin scripts are about validation. Not computation.=20 This means that substring search and concatenation are equivalent. For=20 every script that validates a substring search, you can instead=20 concatenate the substring with the rest of the string, and validate=20 equality instead.=20 Basically speaking:=20 foobar foo IsSubStr=20 is equivalent to:=20 foobar foo bar Cat Equal=20 A real-world example would be more complex. But I hope that illustrates=20 my point sufficiently.=20 --=20 https://petertodd.org 'peter'[:-1]@petertodd.org=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/= 678d40e3-3e22-4d55-82c0-b25ccafb87ecn%40googlegroups.com. ------=_Part_563457_1151508066.1742311960314 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi, Peter Todd
Thanks for yo= ur feedback. I agree that "Bitcoin scripts are about validation. Not comput= ation."
String search and concatenation are equivalent in some case= s, such as in the example you provided.
However, it is still necess= ary 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 cau= sing a stack overflow. Additionally, whether OP_CAT will be restored is sti= ll 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<Peter Todd> =E5=86=99=E9=81=93=EF=BC=9A
On Mon, Mar 17, 2025 at 09:14:05= AM -0700, weichu deng wrote:
>=20
>=20
> Dear fellow Bitcoin developers,
>=20
> =20
>=20
> I am pleased to present a new BIP proposal. This proposal introd= uces a new=20
> opcode for Bitcoin scripts: OP_ISSUBSTR.
>=20
>=20
> *Abstract*
>=20
> This BIP introduces two string opcodes, OP_ISSUBSTR and OP_ISSUB= STRVERIFY=20
> (similar to the relationship between OP_EQUAL and OP_EQUALVERIFY= ), to=20
> determine whether one string is a substring of another. As these= 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. Fo= r
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 illustrat= es
my point sufficiently.

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

--
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/678d40e3-3e22-4d55-82c0-b25ccafb87ecn%40googlegroups.com.
------=_Part_563457_1151508066.1742311960314-- ------=_Part_563456_1611484715.1742311960313--