Subject: Re: [bitcoindev] New Proposal：String Substring Search in Bitcoin Script - OP_ISSUBSTR

From: Martin Habovštiak <[email-masked]>
Date: Tue, 1 Apr 2025 17:35:53 +0200

Hi,

I was dismissing the proposal for the same reason you do but it just
occurred to me that substrings might be better than OP_CAT because it's
possible to make them unabusable without any arbitrary limit on item size.

The idea is to store stack elements on the heap inside struct { ref_count,
length, data[] } and put struct { pointer_to_item, position, length } on
the stack. (Rust developers may be familiar with the `bytes` crate that
does this.)
Substring operations would only duplicate the pointers with adjusted
position and length so there's no way to blow up the stack using them.

Of course there's an exception if OP_SHA256 is used on a shorter slice but
the same is true today - you can already write OP_ZERO OP_SHA256 OP_DUP
OP_DUP...

Funnily, this can be used to optimize OP_DUP as well which would now add
constant amount of memory, so the "exploit" above would need to use two
bytes per every large object.

Anyway, while I would personally prefer not having arbitrary limits on item
sizes, since the limit is already there, it might not matter. I guess
something worth considering if any other future soft fork somehow enables
larger items.

Have a nice day!

Martin

Dňa ut 1. 4. 2025, 16:49 Pieter Wuille <[email-masked]> napísal(a):

> On Monday, March 31st, 2025 at 4:41 PM, Javier Mateos <
> [email-masked]> 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.
>
> --
> Pieter
>
> --
> 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 [email-masked].
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA%3D%40wuille.net
> <https://groups.google.com/d/msgid/bitcoindev/frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA%3D%40wuille.net?utm_medium=email&utm_source=footer>
> .
>
>

-- 
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 [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CALkkCJb1RdC646q1QrOP%2ByQut7EG4NLJNm3cyxW4S1%3DEx1NBmQ%40mail.gmail.com.