From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 10 Jul 2025 07:43:00 -0700 Received: from mail-oo1-f56.google.com ([209.85.161.56]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uZsUF-00046h-8G for bitcoindev@gnusha.org; Thu, 10 Jul 2025 07:43:00 -0700 Received: by mail-oo1-f56.google.com with SMTP id 006d021491bc7-611956658aasf835140eaf.2 for ; Thu, 10 Jul 2025 07:42:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1752158573; x=1752763373; 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=z6w9/hWkphlYHPcp1uSG8VHbGS6m3DNJS1KL1L7gsKk=; b=Bi/Fh/bTvYz46jUVrely3LkacYtuiVYriVCTB18D0bNzWfO7tDiriXy6NqshpJ8OGr 8QiTyJYHZmvNfeZNuDZFDXIwGqjnM0sJWI175cxZFfmlLWLbax5ViYVnY24oOLCUTFCu PuVdhN7WdBGTXMM9RUWS64ePqIJx5+s27o0J1gxLhUCmPS5wlmOuBZbagxNAdvs6mus9 /iHq0C0K1bcu2iLLvy7plrY1JAeDELlqbiPLhIH3i3w0xI1udpmCTI0oOWLQuyNAAoe+ IyBXwsDQQgqSOcLE0z0WVx5K6ZZtQm0LR6W/TvPYuiujYs5Lwht3TEBE9zLs2acrFmev ohOQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1752158573; x=1752763373; 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=z6w9/hWkphlYHPcp1uSG8VHbGS6m3DNJS1KL1L7gsKk=; b=AMTpFcxDh0NfYhJUYsNiPWYCK0f6o+CW0MfeYGczqKS+RvCAcVqGQbpO/q5PZ3JolX lJlE4XSgTw/ssUkbAeJhH8Dlyz5rCz7dF0fJkaFzhnluMMcmIWq99eClKt2Tf4xjJNHd 0r7OCE1npxsMiHMEBQ3XywxT1NV2tsZH/l++4ljW3I+eZcqxsMHYK4lCdOFhfs74yjcM sxdBhByzk3gew8uKWqGT/lOFTV8QmrEBd6nCZF29TeaecXISWOAJ/8T8qsppTGitXuHJ UW0sLPWrpWwLjDlw+geXxq1o++tF85aJpfpNWLm3sJpTDk8cn4F2kQ8rUyzOxI0Z4a4H mJXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1752158573; x=1752763373; 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=z6w9/hWkphlYHPcp1uSG8VHbGS6m3DNJS1KL1L7gsKk=; b=ZJ7gj8GZtaLBYW4Za1ajZIufFY14ChnnsVkpeusRyON86ww3/ELt9MxnL5m+GzoOes XDOz2x2niwD9FRl5+8OLTaoQv6t2yZTEK6kAytjtl7fvMknDVlhDQKBGdZsZEQV8SqSB x/PZ8YbIUSplenn1TpWxbi5g9cNufNPELp/IXclElgfpr0RNvwyCudR4c9s7Pw3hFcLy QM9feJ/yg6mfWtqhnPQTWrEzyEtZYhnkIZ5de9OJ5e0jLIOHui+1C5TfwqPAkXppst9V OnwrgDYYqFQ4b+OMNvDqvYyZ/+Elq4e8qn1s2b8xPkulw+QqGSmJNm7pRplcmlvfEn71 KYuA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUHdS1XOIZbpK5faJWGnPd3QsKPJIfWnWP5MtBGR8qmiX7kBKBIhnBUBWJ0RxiebD8rtgR4qq5L2LXX@gnusha.org X-Gm-Message-State: AOJu0YwlximZ1z6SGBSKmXfZ5apFAVLgiZ1S0dl7YDKxJxsCg6ha5IbP L4iuAiz09S7ULZxeGPdj7L0NHSbgovZr2C5CTmYfqOFNTxcQMN9Nued4 X-Google-Smtp-Source: AGHT+IGqLnc8AAYr8mKCiryh0VNNz30fgpV3K5uru4+i9k4a8kPRk7WTtQi7IN0zsURqgVEqZqczlw== X-Received: by 2002:a05:6870:e40c:b0:2d4:d9d6:c8bf with SMTP id 586e51a60fabf-2fef87c7d32mr4974795fac.32.1752158573011; Thu, 10 Jul 2025 07:42:53 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZfsQc7k0fOUzhWvqn7rjed6xHzubyHq+BWFTh7lQtCq+A== Received: by 2002:a05:6870:956e:b0:2c2:2ed7:fb78 with SMTP id 586e51a60fabf-2ff0b8d0a8els544437fac.0.-pod-prod-01-us; Thu, 10 Jul 2025 07:42:49 -0700 (PDT) X-Received: by 2002:a05:6808:470b:b0:404:12e9:c0e4 with SMTP id 5614622812f47-412bafcc34emr4625675b6e.14.1752158569638; Thu, 10 Jul 2025 07:42:49 -0700 (PDT) Received: by 2002:a05:690c:d8b:b0:710:f35d:a3b2 with SMTP id 00721157ae682-7166a91b6ffms7b3; Thu, 10 Jul 2025 07:33:02 -0700 (PDT) X-Received: by 2002:a05:690c:690b:b0:713:ff41:37f1 with SMTP id 00721157ae682-717b1a1f740mr99536087b3.29.1752157981855; Thu, 10 Jul 2025 07:33:01 -0700 (PDT) Date: Thu, 10 Jul 2025 07:33:01 -0700 (PDT) From: Josh Doman To: Bitcoin Development Mailing List Message-Id: <1d42b799-6c99-4d33-98d4-ecd333a63dbdn@googlegroups.com> In-Reply-To: References: <8a9a2299-ab4b-45a4-8b9d-95798e6bb62a@mattcorallo.com> <4TrCdBvommfJvrK94SqEmNb_pBwsF8dW1n2dY3MYX_z0IMmy4bXoMkrhQ3SBdSnWA6gYMkCgssjzLmH0iauwKuoh_9T4_kLrs_Q5knYPXG0=@protonmail.com> Subject: Re: [bitcoindev] What's a good stopping point? Making the case for the capabilities enabled by CTV+CSFS MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_17556_581902260.1752157981566" X-Original-Sender: joshsdoman@gmail.com 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.5 (/) ------=_Part_17556_581902260.1752157981566 Content-Type: multipart/alternative; boundary="----=_Part_17557_506940800.1752157981566" ------=_Part_17557_506940800.1752157981566 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Greg, I'm not sure I quite follow the membership proof concern. The reason to use= =20 MuHash is to avoid quadratic hashing, by only needing to iterate through=20 the input set once. Our goal is simply to prove that an indexed set of=20 sibling prevouts is committed to. In the naive implementation, validating a sibling commitment requires=20 hashing all other prevouts in the transaction. In the worst case, this is= =20 O(n^2) if we need to validate a sibling commitment for each input. With MuHash, this becomes O(n) because we can validate sibling commitments= =20 by precomputing a hash over all prevouts and then selectively removing one= =20 prevout, which is O(1). This gives us the same result as directly hashing= =20 the sibling prevouts. Does this address your concern? Best, Josh On Thursday, July 10, 2025 at 8:10:47=E2=80=AFAM UTC-4 Greg Sanders wrote: Hi Josh, For one, MuHash doesn't have a compact membership proof, for one, making it= =20 unlikely to be useful for anything we're likely thinking of. It's used in= =20 Bitcoin Core for equivalency of UTXO sets in snapshots. To validate=20 membership, the entire population has to be iterated. Best, Greg On Wed, Jul 9, 2025 at 5:54=E2=80=AFPM Josh Doman wrot= e: I tend to agree. It's hard to justify the leap in expressivity of OP_TX /= =20 OP_TXHASH solely on the basis of enabling commitments to sibling prevouts.= =20 A more targeted approach would be better. In that vein, I think there's a way to use MuHash to generalize CTV /=20 TEMPLATEHASH and commit to sibling prevouts in constant time. The idea is to precompute a MuHash accumulator containing SHA256(index ||= =20 prevout) for each input in the transaction. Then, to compute the sibling commitment for input i, we simply copy the=20 accumulator and remove the SHA256 hash for that input. Thanks to MuHash,=20 this takes constant time. Finally, we include the sibling commitment in the= =20 existing proposed commitment scheme. This would represent a low-cost way to commit to the next txid, providing= =20 predictability regardless of how many inputs are spent (unlike existing=20 proposals). Given that MuHash is already in the codebase, I'm inclined to= =20 believe this wouldn't be a heavy lift and would better achieve the goal of= =20 a primitive that "commits to the next transaction." Thoughts? Best, Josh On Friday, July 4, 2025 at 9:08:48=E2=80=AFAM UTC-4 Antoine Poinsot wrote: I agree the BitVM/CTV idea suggests inspection of other inputs can be=20 useful for applications=20 leveraging connector outputs.=20 While it is potentially compelling, the BitVM use case was only briefly=20 presented, with no=20 demonstration or even detailed description of how it would work in=20 practice. This makes it hard to=20 assess the costs and benefits of this approach. Furthermore, it's hard to= =20 assess how much of an=20 improvement it brings to Bitcoin users as BitVM has yet to be delivered and= =20 see any meaningful=20 adoption.=20 As Greg responded when it was raised earlier in this thread[^0], as things= =20 stand today i don't think=20 this idea justifies the leap in expressivity.=20 Best,=20 Antoine=20 [^0]:=20 https://gnusha.org/pi/bitcoindev/8d37b779-bf2e-4f63...@googlegroups.com=20 =20 On Thursday, July 3rd, 2025 at 4:54 AM, Anthony Towns = =20 wrote:=20 >=20 >=20 > On Tue, Jun 24, 2025 at 11:54:02AM -0400, Matt Corallo wrote:=20 >=20 > > > which=20 > > > warrants a compelling demonstration that arbitrary transaction=20 introspection=20 > > > does enable important use cases not achievable with more minimal=20 capabilities.=20 > > > I'm somewhat skeptical that showing this isn't rather simple,=20 >=20 >=20 > I think the BitVM/CTV idea posted on delving [0] is one such simple demo?= =20 >=20 > I gave an example in that thread of how you'd implement the desired=20 > construct using bllsh's introspection primitives, but the same could=20 > equally well be done with Rusty's as-yet unpublished OP_TX, something=20 > like:=20 >=20 > DUP 0x1011 TX 0x00000002 EQUALVERIFY 0x1009 TX 0x0809 TX EQUALVERIFY=20 >=20 > where:=20 >=20 > * "0x1011 TX" pops an input index from the stack and gives the four-byte= =20 > vout index of that input's prevout=20 > * "0x1009 TX" pops an input index from the stack and gives the txid of=20 that input's=20 > prevout=20 > * "0x0809 TX" gives the txid of the current input's prevout=20 >=20 > (this encodes "this utxo can only be spent (via this path) if its sibling= =20 > output at index 2 is also being spent in the same transaction")=20 >=20 > Cheers,=20 > aj=20 >=20 > [0] https://delvingbitcoin.org/t/how-ctv-csfs-improves-bitvm-bridges/1591= =20 >=20 > --=20 > You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group.=20 > To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com.=20 > To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/aGX_MNORQVQT_lp4%40erisian.com= .au.=20 --=20 You received this message because you are subscribed to a topic in the=20 Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this topic, visit=20 https://groups.google.com/d/topic/bitcoindev/-qJc1EWQzY0/unsubscribe. To unsubscribe from this group and all its topics, send an email to=20 bitcoindev+...@googlegroups.com. To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/b72e6f6f-af27-4043-b714-4e607b= be8880n%40googlegroups.com=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/= 1d42b799-6c99-4d33-98d4-ecd333a63dbdn%40googlegroups.com. ------=_Part_17557_506940800.1752157981566 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Greg,

I'm not sure I quite follow the membership pr= oof concern. The reason to use MuHash is to avoid quadratic hashing, by onl= y needing to iterate through the input set once. Our goal is simply to prov= e that an indexed set of sibling prevouts is committed to.

=
In the naive implementation, validating a sibling commitment req= uires hashing all other prevouts in the transaction. In the worst case, thi= s is O(n^2) if we need to validate a sibling commitment for each input.

With MuHash, this becomes O(n) because we can valid= ate sibling commitments by precomputing a hash over all prevouts and then s= electively removing one prevout, which is O(1). This gives us the same resu= lt as directly hashing the sibling prevouts.

Doe= s this address your concern?

Best,
Jos= h

On Thursday, July 10, 2025 a= t 8:10:47=E2=80=AFAM UTC-4 Greg Sanders wrote:
Hi Josh,

For one, MuHash doesn't have a compa= ct membership proof, for one, making it unlikely to be useful for anything = we're likely thinking of. It's used in Bitcoin Core for equivalency=C2=A0of= UTXO sets in snapshots. To validate membership, the entire population has = to be iterated.

Best,
Greg
=
On Wed, Jul 9, 2025 at 5:54=E2=80=AF= PM Josh Doman <joshs...@gmail.com> = wrote:
I tend to agree. It's hard to justify t= he leap in expressivity of OP_TX / OP_TXHASH solely on the basis of enablin= g commitments to sibling prevouts. A more targeted approach would be better= .

In that vein, I think there's a way to use MuHash to= generalize CTV / TEMPLATEHASH and commit to sibling prevouts in constant t= ime.

The idea is to precompute a MuHash acc= umulator containing SHA256(index || prevout) for each input in the transact= ion.

Then, to compute the sibling commitme= nt for input i, we simply copy the accumulator and remove the SHA256 hash f= or that input. Thanks to MuHash, this takes constant time. Finally, we incl= ude the sibling commitment in the existing proposed commitment scheme.

This would represent a low-cost way to c= ommit to the next txid, providing predictability regardless of how many inp= uts are spent (unlike existing proposals). Given that MuHash is already in = the codebase, I'm inclined to believe this wouldn't be a heavy lift and wou= ld better achieve the goal of a primitive that "commits to the next transac= tion."

Thoughts?

Best= ,
Josh

On Friday, July 4, 2025 = at 9:08:48=E2=80=AFAM UTC-4 Antoine Poinsot wrote:
I agre= e the BitVM/CTV idea suggests inspection of other inputs can be useful for = applications
leveraging connector outputs.

While it is potentially compelling, the BitVM use case was only brief= ly presented, with no
demonstration or even detailed description of how it would work in pr= actice. This makes it hard to
assess the costs and benefits of this approach. Furthermore, it's har= d to assess how much of an
improvement it brings to Bitcoin users as BitVM has yet to be deliver= ed and see any meaningful
adoption.

As Greg responded when it was raised earlier in this thread[^0], as t= hings stand today i don't think
this idea justifies the leap in expressivity.

Best,
Antoine

[^0]: htt= ps://gnusha.org/pi/bitcoindev/8d37b779-bf2e-4f63...@googlegroups.com


On Thursday, July 3rd, 2025 at 4:54 AM, Anthony Towns <a...@erisian.com.au> wrote:

>=20
>=20
> On Tue, Jun 24, 2025 at 11:54:02AM -0400, Matt Corallo wrote:
>=20
> > > which
> > > warrants a compelling demonstration that arbitrary tra= nsaction introspection
> > > does enable important use cases not achievable with mo= re minimal capabilities.
> > > I'm somewhat skeptical that showing this isn't rather = simple,
>=20
>=20
> I think the BitVM/CTV idea posted on delving [0] is one such sim= ple demo?
>=20
> I gave an example in that thread of how you'd implement the desi= red
> construct using bllsh's introspection primitives, but the same c= ould
> equally well be done with Rusty's as-yet unpublished OP_TX, some= thing
> like:
>=20
> DUP 0x1011 TX 0x00000002 EQUALVERIFY 0x1009 TX 0x0809 TX EQUALVE= RIFY
>=20
> where:
>=20
> * "0x1011 TX" pops an input index from the stack and gives the f= our-byte
> vout index of that input's prevout
> * "0x1009 TX" pops an input index from the stack and gives the t= xid of that input's
> prevout
> * "0x0809 TX" gives the txid of the current input's prevout
>=20
> (this encodes "this utxo can only be spent (via this path) if it= s sibling
> output at index 2 is also being spent in the same transaction")
>=20
> Cheers,
> aj
>=20
> [0] https://delvingbit= coin.org/t/how-ctv-csfs-improves-bitvm-bridges/1591
>=20
> --
> You received this message because you are subscribed to the Goog= le Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it= , send an email to bitcoindev+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/aGX_MNORQVQT_= lp4%40erisian.com.au.

--
You received this message because you are subscribed to a topic in the Goog= le Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/bitcoindev/-qJc1EWQzY0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit htt= ps://groups.google.com/d/msgid/bitcoindev/b72e6f6f-af27-4043-b714-4e607bbe8= 880n%40googlegroups.com.

--
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/1d42b799-6c99-4d33-98d4-ecd333a63dbdn%40googlegroups.com.
------=_Part_17557_506940800.1752157981566-- ------=_Part_17556_581902260.1752157981566--