BIP-Taproot: Optimizing Taptree for expected Tapscript spending cost

[jachiang]

Regarding TapTree construction based on tapscript probability weights (e.g. Huffman):

There seems to be a privacy trade-off when optimizing for expected script path spending cost, as standard outputs will likely feature standard probability weightings, especially in protocols such as lightning. Spending a script branch will reveal its height in the tree and may imply the contract type.

If authors agree, is this worth mentioning in taproot-BIP?

[sipa]

It seems reasonable to point out that you can add dummy branches to the Merkle tree to bring all branches to the same length, or even increase it further.

[sipa]

@jachiang Feel like opening a PR for this?

[jachiang]

Hi @sipa, I would be happy to do so, but have also noticed that the following has been added to the security section:

Moreover, the depth of a script in the Merkle root leaks information including the minimum depth of the tree, which suggests specific wallet software that created the output and helps clustering. Therefore, the privacy of script spends can be improved by deviating from the optimal tree determined by the probability distribution over the leaves.

I suppose dummy branches would fall under deviating from the optimal tree. Do you think we should make it explicit?

[sipa]

@jachiang I don't have a very strong opinion, there is probably a lot more than can be said on the topic of constructing optimal trees (when optimal includes privacy considerations).