1

I noticed this sentence in Taproot about the MAST build.

The remaining scripts should be organized into the leaves of a binary tree. This can be a balanced tree if each of the conditions these scripts correspond to are equally likely. If probabilities for each condition are known, consider constructing the tree as a Huffman tree.

But in the case of a balanced Merkle Tree, an observer can infer the number of layers in the tree by the Merkle proof and thus get an approximate number of leaves(scripts). For example, a P2TR ends up unlocked with a time lock, and I infer from the Merkle proof that there are 2 scripts in total. Then I can guess the other lock is a hash lock(since this is the most common script with two conditions and one of them is a time lock).

It seems that forcing the user to use an unbalanced Merkle Tree would also be an option (e.g. randomly initialising the coefficients and then constructing a Huffman tree)? Or maybe put in some fake leaves?

Improve this question
1
  • Apologies for confusing the concept of a balanced binary tree, the example in the question is not accurate.
    – sphpmp
    Jul 20, 2021 at 6:05

2 Answers 2

Reset to default
2

For example, a P2TR ends up unlocked with a time lock, and I infer from the Merkle proof that there are two scripts in total.

You can't infer this for certain. You know what layer of the Merkle tree the script was taken from (in this case the first layer) but there may be scripts present on the second, third, fourth layers etc that you don't know about. I agree that if a script is taken from the first layer it is possible (perhaps likely) there are two scripts.

Then I can guess that this is a MAST containing a hash time lock (since this is the most common script with two conditions and one of them is a time lock).

I'm not sure why you think having one leaf script with a timelock infers that another leaf script contains a hash timelock. If you are referring to Lightning, the most common channel closes are cooperative 2-of-2 closes where no alternative script paths need to be included in the output. In the case of rarer uncooperative closes it is obvious to a blockchain observer that it is an uncooperative Lightning channel close, you can't hide this.

It seems that forcing the user to use an unbalanced Merkle Tree would also be an option (e.g. randomly initialising the coefficients and then constructing a Huffman tree)? Or maybe put in some fake leaves?

You can definitely construct the Taproot tree however you wish. You can put scripts in lower layers than they need to be so it seems to a blockchain observer there are more script paths than there actually are. Typically to save on fees you will want to put the script you are most likely to use on a higher layer of the Merkle tree but if you are more concerned with privacy you may choose not to do this.

Improve this answer
12
  • First of all thank you very much for your answer!
    – sphpmp
    Jul 19, 2021 at 8:43
  • About leaves in lower layer: Maybe I misunderstand the balanced tree, I thought it likes the Merkle tree in SPV where all the leaves would be at the lowest layer. About lightning network example: What I want to discuss is whether it is possible to distinguish hash time locks from normal time locks? This will be easy if the number of scripts can be inferred. Finally, I may have misunderstood the balance tree. What I want to suggest is as you said, we should make each layer have scripts instead of putting all leaves at the last layer.
    – sphpmp
    Jul 19, 2021 at 8:55
  • 1
    You do not need to put all the scripts on the same lowest layer. That would be inefficient and more costly to spend if you say had 3 scripts and were forced to put them all on the second layer rather than 1 script on the first layer and 2 scripts on the second layer. Re Lightning I'm sorry I don't understand the question. The script for a hash timelock obviously contains a hash lock as well as a timelock. I don't understand why revealing a timelock script infers that a second script is a hash timelock. I suspect you are misunderstanding how Lightning works (but I could be wrong)
    – Michael Folkson
    Jul 19, 2021 at 9:05
  • Oh, my bad, I forgot to clarify the context. I suspect that in future Lightning Network will split the hash time lock into two separate scripts to meet Taproot, a hash lock and a time lock. So when I see that one lock is a time lock and that this MAST has two scripts, I'm guessing that the other script is a hash lock and the MAST represents the HTLC.
    – sphpmp
    Jul 19, 2021 at 9:10
  • You wouldn't be able to do this because only one script (leaf) can be used/spent in the Taproot tree. You can't combine multiple leaf scripts to spend from the output. Hence if you want an encumbrance that contains a hashlock and a timelock they both need to be within a single leaf script
    – Michael Folkson
    Jul 19, 2021 at 9:14
2

The answer is very simple, you can't independently verify that the user is using an unbalanced Merkle tree without knowing its structure in full – rendering all anonymity benefits pointless. But you are overestimating how much information about the Merkle tree can be inferred. Since during a Taproot spend only one Merkle path is revealed, unless the script is located right under the Merkle root – in which case it is provably the only script in the tree – there is no way to know for sure how many spending conditions were defined.

However, to prevent anyone from even making reasonable guesses, a wallet software could randomize the Merkle tree structure with every transaction, similarly to how some wallets randomly shuffle transaction outputs to disguise the change output.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.