2

From 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 2128. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely.

This is an excellent explanation why one really doesn't need a Merkle tree deeper than 128, but it doesn't explain why it's not allowed. Would this open the protocol to some sort of attack? I don't see how a script path spend with a few thousand branch steps would be worse than multiple individual transactions with shorter branches. Or it is just a standard to set a limit like this in a protocol when confident enough that nobody could ever need to go over it?

Vojtěch Strnad
  • 5,623
  • 1
  • 8
  • 31
  • Heh, don't you think that being able to have up 3.402823669×10³⁸ leafscripts is enough?— I think you mistook the limit to be 128 instead of 2^128. ;) – Murch Aug 16 '22 at 20:45
  • @Murch I believe that OP by "a few thousand branches" means "a single control block with a few thousand Merkle branch steps". The actual number of possible branches isn't relevant here, as only one gets revealed. – Pieter Wuille Aug 16 '22 at 21:00
  • Ah, right. That makes actually a lot more sense. – Murch Aug 16 '22 at 21:06
  • Observation by Pieter is correct. I'm definitely not suggesting the limit isn't generous enough, as no one will be going around constructing Merkle trees with 2^128 different valid conditions anytime soon. But constructing an output with a spendable Merkle path 128 branches long is very much possible. – Vojtěch Strnad Aug 16 '22 at 21:07

0 Answers0