Delivery-date: Wed, 09 Apr 2025 02:23:04 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) client-ip=172.104.61.193;
Date: Wed, 9 Apr 2025 04:04:36 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Pieter Wuille <bitcoin-dev@wuille.net>
Cc: Javier Mateos <javierpmateos@gmail.com>,
	Bitcoin Development Mailing List <bitcoindev@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?=
Message-ID: <Z_VlNPeDS8Hk3Dyy@erisian.com.au>
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>
 <e8c30db7-b509-4fbd-93ef-0bca0313003cn@googlegroups.com>
 <frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA=@wuille.net>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
In-Reply-To: <frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA=@wuille.net>
X-Spam_score: -0.0
X-Spam_bar: /
X-Original-Sender: aj@erisian.com.au
X-Original-Authentication-Results: gmr-mx.google.com;       spf=pass
 (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as
 permitted sender) smtp.mailfrom=aj@erisian.com.au
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.8 (/)

On Tue, Apr 01, 2025 at 12:25:26PM +0000, Pieter Wuille wrote:
> On Monday, March 31st, 2025 at 4:41 PM, Javier Mateos <javierpmateos@gmail.com> wrote:
> > 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 where the substring could be in any position
> Whoever produces the signature/witness for spending the coin always knows the position already, so the script can always be modified to instead take that position as an additional input.
> This is a general principle: the point of scripts is verifying provided information, not computing it. As another example, this means that there is no need for a division or square root opcode if one has a multiplication opcode.

I somewhat disagree with this: there are some concerns that are *easier*
to express with different opcodes, and I think that's a factor worth
considering.

This came up with the OP_CAT based proof-of-work faucet [0] -- the
idea there is that you provide a signature and some nonce data, and
when you combine the two and hash the result, that result begins with
some sufficient number of 0 bits (that then gets related back to a
CHECKSEQUENCEVERIFY delay).

OP_CAT is *sufficient* for testing this, because you just CAT the
signature and nonce together and hash them, and can then again CAT the
the 0-bits you expect together with some other data and check that all
of those combined match the hash you calculated earlier.

But it would be more efficient, and a little easier to code, if you
could instead have used SUBSTR/LEFT to pull the initial bytes from
the calculated hash and check that those have the expected number of
leading 0-bits. More efficient, because you don't have to supply all
the trailing bytes of the hash in the witness, and easier to code,
because it's a bit more natural to think of manipulating the hash you
calculated, rather than having to put user-provided data together and
check that that actually matched what you would have extracted from
the hash had you been able to do it that way.

So just like we have unnecessary opcodes like "CHECKSIGVERIFY" (versus
"CHECKSIG VERIFY"), I think it's still worth evaluating "SUBSTR" and
"DIV" on questions of efficiency, even if they're not providing any
additional expressivity -- ie, does it provide a meaningful improvement
either for on-chain validation or when writing/maintaining scripts
compared to other ways of achieving the same goal?

(That said, I don't think "ISSUBSTR" is a great opcode; the original
SUBSTR that specifies exactly where in the original string the substring
appears seems more useful to me)

Cheers,
aj

[0] https://delvingbitcoin.org/t/proof-of-work-based-signet-faucet/937

-- 
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 email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z_VlNPeDS8Hk3Dyy%40erisian.com.au.