BitVM explained: Simple explanation of BitVM \ stacker news ~bitcoin

pull down to refresh

So you're telling me if I was better at shameless self-promotion and published this on my own I could have stacked 4k sats :)

Anyway, the thing is likely still quite broken (afterall it's based on my limited understanding), PRs welcome.

0 sats \ 3 replies \ @k00b 10 Oct 2023

I saw on twitter:

In theory circuits can have up to 2^128 gates.

Does anyone know where this limit comes from? Is this the limit on taproot leaves?

2191 sats \ 2 replies \ @supertestnet 10 Oct 2023

Yes, I don't understand the explanation but there is one: it appears in footnote 6 of bip341

Why is the Merkle path length limited to 128? The optimally space-efficient Merkle tree can be constructed based on the probabilities of the scripts in the leaves, using the Huffman algorithm. This algorithm will construct branches with lengths approximately equal to log2(1/probability), but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in 2^128. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely. source

I don't know what it means by "that is our security bound."

In the case of BitVM we use the furthest branches of the tap tree not to hide scripts that are unlikely to execute but just because there are that many possible operations in some very large programs, so we might need to fill up the whole tree sometimes with branching logic if we want to fit the whole program into one bitcoin address.

Anyway I'm not sure what all the terms in that footnote mean and the low-likeliness reasoning doesn't seem to apply to what we're doing, but the limits are what they are so we'll work within those constraints.

0 sats \ 0 replies \ @fiksn 11 Oct 2023

IMO, this comes from the fact the feature was designed with a very narrow use-case in mind. MAST was just about pushing more unlikely spending conditions more down the tree. Luckily this can still be used in a different way (and 128 is then just some arbitrary limit).

A good reminder that when designing an API we shoud give the consumers some lego bricks and then allow them to come up with something creative on their side instead of prescribing what exacty can be done and just giving them a few very rigid methods.

0 sats \ 0 replies \ @k00b 10 Oct 2023

Ah sounds like the merkle tree depth is max 128 levels and with 2 children for every parent, you get max 2^128 leaves.