Re: [bitcoindev] What's a good stopping point? Making the case for the capabilities enabled by CTV+CSFS

[Josh Doman <joshsdoman@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 6100 bytes --]

Hi Greg,

I'm not sure I quite follow the membership proof concern. The reason to use 
MuHash is to avoid quadratic hashing, by only needing to iterate through 
the input set once. Our goal is simply to prove that an indexed set of 
sibling prevouts is committed to.

In the naive implementation, validating a sibling commitment requires 
hashing all other prevouts in the transaction. In the worst case, this is 
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 
by precomputing a hash over all prevouts and then selectively removing one 
prevout, which is O(1). This gives us the same result as directly hashing 
the sibling prevouts.

Does this address your concern?

Best,
Josh

On Thursday, July 10, 2025 at 8:10:47 AM UTC-4 Greg Sanders wrote:

Hi Josh,

For one, MuHash doesn't have a compact 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 of UTXO sets in snapshots. To validate 
membership, the entire population has to be iterated.

Best,
Greg

On Wed, Jul 9, 2025 at 5:54 PM Josh Doman <joshs...@gmail.com> wrote:

I tend to agree. It's hard to justify the leap in expressivity of OP_TX / 
OP_TXHASH solely on the basis of enabling 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 time.

The idea is to precompute a MuHash accumulator containing SHA256(index || 
prevout) for each input in the transaction.

Then, to compute the sibling commitment for input i, we simply copy the 
accumulator and remove the SHA256 hash for that input. Thanks to MuHash, 
this takes constant time. Finally, we include the sibling commitment in the 
existing proposed commitment scheme.

This would represent a low-cost way to commit to the next txid, providing 
predictability regardless of how many inputs 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 would better achieve the goal of 
a primitive that "commits to the next transaction."

Thoughts?

Best,
Josh

On Friday, July 4, 2025 at 9:08:48 AM UTC-4 Antoine Poinsot wrote:

I agree 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 briefly 
presented, with no 
demonstration or even detailed description of how it would work in 
practice. This makes it hard to 
assess the costs and benefits of this approach. Furthermore, it's hard to 
assess how much of an 
improvement it brings to Bitcoin users as BitVM has yet to be delivered and 
see any meaningful 
adoption. 

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

Best, 
Antoine 

[^0]: 
https://gnusha.org/pi/bitcoindev/8d37b779-bf2e-4f63...@googlegroups.com 
<https://gnusha.org/pi/bitcoindev/8d37b779-bf2e-4f63-a51c-9953434d7553n@googlegroups.com> 


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

> 
> 
> On Tue, Jun 24, 2025 at 11:54:02AM -0400, Matt Corallo wrote: 
> 
> > > which 
> > > warrants a compelling demonstration that arbitrary transaction 
introspection 
> > > does enable important use cases not achievable with more minimal 
capabilities. 
> > > I'm somewhat skeptical that showing this isn't rather simple, 
> 
> 
> I think the BitVM/CTV idea posted on delving [0] is one such simple demo? 
> 
> I gave an example in that thread of how you'd implement the desired 
> construct using bllsh's introspection primitives, but the same could 
> equally well be done with Rusty's as-yet unpublished OP_TX, something 
> like: 
> 
> DUP 0x1011 TX 0x00000002 EQUALVERIFY 0x1009 TX 0x0809 TX EQUALVERIFY 
> 
> where: 
> 
> * "0x1011 TX" pops an input index from the stack and gives the four-byte 
> vout index of that input's prevout 
> * "0x1009 TX" pops an input index from the stack and gives the txid of 
that input's 
> prevout 
> * "0x0809 TX" gives the txid of the current input's prevout 
> 
> (this encodes "this utxo can only be spent (via this path) if its sibling 
> output at index 2 is also being spent in the same transaction") 
> 
> Cheers, 
> aj 
> 
> [0] https://delvingbitcoin.org/t/how-ctv-csfs-improves-bitvm-bridges/1591 
> 
> -- 
> 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+...@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 
Google 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 
https://groups.google.com/d/msgid/bitcoindev/b72e6f6f-af27-4043-b714-4e607bbe8880n%40googlegroups.com 
<https://groups.google.com/d/msgid/bitcoindev/b72e6f6f-af27-4043-b714-4e607bbe8880n%40googlegroups.com?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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/1d42b799-6c99-4d33-98d4-ecd333a63dbdn%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 8539 bytes --]