Delivery-date: Tue, 01 Apr 2025 15:38:38 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of martin.habovstiak@gmail.com designates 2607:f8b0:4864:20::736 as permitted sender) client-ip=2607:f8b0:4864:20::736;
MIME-Version: 1.0
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>
In-Reply-To: <frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA=@wuille.net>
From: =?UTF-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>
Date: Tue, 1 Apr 2025 17:35:53 +0200
Message-ID: <CALkkCJb1RdC646q1QrOP+yQut7EG4NLJNm3cyxW4S1=Ex1NBmQ@mail.gmail.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?=
To: Pieter Wuille <bitcoin-dev@wuille.net>
Cc: Javier Mateos <javierpmateos@gmail.com>, 
	Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="00000000000067ab4a0631b94b28"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--00000000000067ab4a0631b94b28
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=C5=88a ut 1. 4. 2025, 16:49 Pieter Wuille <bitcoin-dev@wuille.net> nap=C3=
=ADsal(a):

> 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 whe=
re
> 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 tak=
e
> 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 bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/frERrHlzWhpskJw74fBQorSrXEaB=
P1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01k=
uozA%3D%40wuille.net
> <https://groups.google.com/d/msgid/bitcoindev/frERrHlzWhpskJw74fBQorSrXEa=
BP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01=
kuozA%3D%40wuille.net?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/=
CALkkCJb1RdC646q1QrOP%2ByQut7EG4NLJNm3cyxW4S1%3DEx1NBmQ%40mail.gmail.com.

--00000000000067ab4a0631b94b28
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto">Hi,<div dir=3D"auto"><br></div><div dir=3D"auto">I was di=
smissing the proposal for the same reason you do but it just occurred to me=
 that substrings might be better than OP_CAT because it&#39;s possible to m=
ake them unabusable without any arbitrary limit on item size.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">The idea is to store stack elements o=
n the heap inside struct { ref_count, length, data[] } and put struct { poi=
nter_to_item, position, length } on the stack. (Rust developers may be fami=
liar with the `bytes` crate that does this.)</div><div dir=3D"auto">Substri=
ng operations would only duplicate the pointers with adjusted position and =
length so there&#39;s no way to blow up the stack using them.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Of course there&#39;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...</div><div dir=3D"auto"><br=
></div><div dir=3D"auto">Funnily, this can be used to optimize OP_DUP as we=
ll which would now add constant amount of memory, so the &quot;exploit&quot=
; above would need to use two bytes per every large object.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Anyway, while I would personally pref=
er not having arbitrary limits on item sizes, since the limit is already th=
ere, it might not matter. I guess something worth considering if any other =
future soft fork somehow enables larger items.</div><div dir=3D"auto"><br><=
/div><div dir=3D"auto">Have a nice day!</div><div dir=3D"auto"><br></div><d=
iv dir=3D"auto">Martin</div><br><br><div class=3D"gmail_quote gmail_quote_c=
ontainer" dir=3D"auto"><div dir=3D"ltr" class=3D"gmail_attr">D=C5=88a ut 1.=
 4. 2025, 16:49 Pieter Wuille &lt;<a href=3D"mailto:bitcoin-dev@wuille.net"=
>bitcoin-dev@wuille.net</a>&gt; nap=C3=ADsal(a):<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex"><div style=3D"font-family:Arial,sans-serif;font-size:14px"><d=
iv><div>
        On Monday, March 31st, 2025 at 4:41 PM, Javier Mateos &lt;<a href=
=3D"mailto:javierpmateos@gmail.com" target=3D"_blank" rel=3D"noreferrer">ja=
vierpmateos@gmail.com</a>&gt; wrote:<br>
        <blockquote type=3D"cite"><div>
              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</div></blockquote>=
<div><br></div><div>Whoever
 produces the signature/witness for spending the coin always knows the=20
position already, so the script can always be modified to instead take=20
that position as an additional input.</div><div><br></div><div>This is a
 general principle: the point of scripts is verifying provided=20
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=20
multiplication opcode.</div><div><br></div><div>-- <br></div><div>Pieter</d=
iv><br></div></div></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; 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" target=
=3D"_blank" rel=3D"noreferrer">bitcoindev+unsubscribe@googlegroups.com</a>.=
<br>
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-Nkww_2ulhc7i2Lqmu2kcAlvh5f=
d7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA%3D%40wuille.net?utm_medium=3Dem=
ail&amp;utm_source=3Dfooter" target=3D"_blank" rel=3D"noreferrer">https://g=
roups.google.com/d/msgid/bitcoindev/frERrHlzWhpskJw74fBQorSrXEaBP1d4XBUgM-N=
kww_2ulhc7i2Lqmu2kcAlvh5fd7LzYiBmX5HNBtg7Ownbsa0KZ26ihfJjri6R01kuozA%3D%40w=
uille.net</a>.<br><br>
</blockquote></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; 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/CALkkCJb1RdC646q1QrOP%2ByQut7EG4NLJNm3cyxW4S1%3DEx1NBmQ%40mail.g=
mail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/=
d/msgid/bitcoindev/CALkkCJb1RdC646q1QrOP%2ByQut7EG4NLJNm3cyxW4S1%3DEx1NBmQ%=
40mail.gmail.com</a>.<br />

--00000000000067ab4a0631b94b28--