<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-07-19T22:32:50.870Z
2021-07-19T22:32:50.870Z
Vojtěch Strnad
<blockquote>
<p>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.</p>
</blockquote>
<p>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.</p>
<blockquote>
<p>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).</p>
</blockquote>
<p>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.</p>
<blockquote>
<p>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?</p>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2021-07-19T08:43:56.863Z
First of all thank you very much for your answer!
sphpmp
CC BY-SA 4.0
2021-07-19T08:55:49.557Z
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
CC BY-SA 4.0
2021-07-19T09:05:37.000Z
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
CC BY-SA 4.0
2021-07-19T09:10:29.883Z
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
CC BY-SA 4.0
2021-07-19T09:14:45.593Z
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
CC BY-SA 4.0
2021-07-19T09:18:00.870Z
Yes, but I think what HTLC means is that Alice can redeem with preimage **or** Bob can redeem after a timeout. It would be a script that could be split.
sphpmp
CC BY-SA 4.0
2021-07-19T09:25:50.703Z
No you are confusing HTLCs with uncooperative channel closes. A HTLC is a script that includes both a hashlock and a timelock. These are constructed every time a new payment is made on Lightning. An uncooperative channel close is when a transaction is broadcast that includes two outputs: one paying your counterparty without a timelock and one output paying you with a timelock. These are two outputs rather than two scripts that can be combined.
Michael Folkson
CC BY-SA 4.0
2021-07-19T09:37:47.483Z
Yes, you are right, there are two outputs when non-cooperative closing. the output Alice gives herself is locked by a time lock, and another output Bob can get immediately (but I think these are two different P2TR scripts?. I'm only talking about the P2TR that Alice gives to herself). And, the lightning network will allow Bob to take Alice's output as a penalty via a preimage to prevent one party from committing the old state, a mechanism called RSMC.

Note that I am only talking about the script of output that Alice gives to himself. The MAST of this output has two scripts.
sphpmp
CC BY-SA 4.0
2021-07-19T09:49:55.063Z
One script for Alice to get the refund after the timeout.

Another script for Bob to get the money by preimage to punish Alice.
sphpmp
CC BY-SA 4.0
2021-07-19T09:53:28.307Z
This is getting long (and moving onto Lightning which isn't the focus of the original question) so we should move to chat. But no, Bob has a time interval to broadcast a punishment transaction that spends Alice's timelocked output to an address that he controls if Alice has broadcast a revoked state. That is an additional transaction not an alternative script path within a single transaction.
Michael Folkson
CC BY-SA 4.0
2021-07-19T09:59:49.117Z
Yes, let's assume that Alice's UTXO is P2TR. There be two scripts in MAST, right (one for Alice, one for Bob)? So if Bob uses preimage to unlock and show that there are two scripts (let's assume this all scripts are placed on the same layer). Then the observer guesses that the other script is the time lock, which is what I meant initially.
sphpmp
CC BY-SA 4.0
2021-07-19T22:41:33.797Z
Spending does not revealing anything about other scripts in the same tree. You can construct a depth-128 tree with just one script. It would be inefficient, though, as you need 128 dummy branches.
Pieter Wuille
CC BY-SA 4.0
2021-07-19T08:30:37.587Z
2021-07-19T08:49:12.047Z
2021-07-19T08:49:12.047Z
Michael Folkson
<p>I noticed this sentence in Taproot about the MAST build.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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).</p>
<p>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?</p>

CC BY-SA 4.0
2021-07-20T06:05:35.810Z
Apologies for confusing the concept of a balanced binary tree, the example in the question is not accurate.
sphpmp
<privacy><taproot>
How about force the use of unbalanced Merkle tree in Taproot?
sphpmp
# How about force the use of unbalanced Merkle tree in Taproot?

(Asked by: username_0 on 2021-07-19)

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?

**Tags:** privacy, taproot

> **Comments:**
> **username_0**: Apologies for confusing the concept of a balanced binary tree, the example in the question is not accurate.  

---

## 2 answers

### Answer by username_1 on 2021-07-19. Score: 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.


---

### Answer by username_2 on 2021-07-19. Score: 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.

> **Comments:**
> **username_0**: First of all thank you very much for your answer!  
> **username_0**: 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.  
> **username_2**: 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)  
> **username_0**: 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.  
> **username_2**: 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  
> **username_0**: Yes, but I think what HTLC means is that Alice can redeem with preimage **or** Bob can redeem after a timeout. It would be a script that could be split.  
> **username_2**: No you are confusing HTLCs with uncooperative channel closes. A HTLC is a script that includes both a hashlock and a timelock. These are constructed every time a new payment is made on Lightning. An uncooperative channel close is when a transaction is broadcast that includes two outputs: one paying your counterparty without a timelock and one output paying you with a timelock. These are two outputs rather than two scripts that can be combined.  
> **username_0**: Yes, you are right, there are two outputs when non-cooperative closing. the output Alice gives herself is locked by a time lock, and another output Bob can get immediately (but I think these are two different P2TR scripts?. I'm only talking about the P2TR that Alice gives to herself). And, the lightning network will allow Bob to take Alice's output as a penalty via a preimage to prevent one party from committing the old state, a mechanism called RSMC.  Note that I am only talking about the script of output that Alice gives to himself. The MAST of this output has two scripts.  
> **username_0**: One script for Alice to get the refund after the timeout.  Another script for Bob to get the money by preimage to punish Alice.  
> **username_2**: This is getting long (and moving onto Lightning which isn't the focus of the original question) so we should move to chat. But no, Bob has a time interval to broadcast a punishment transaction that spends Alice's timelocked output to an address that he controls if Alice has broadcast a revoked state. That is an additional transaction not an alternative script path within a single transaction.  
> **username_0**: Yes, let's assume that Alice's UTXO is P2TR. There be two scripts in MAST, right (one for Alice, one for Bob)? So if Bob uses preimage to unlock and show that there are two scripts (let's assume this all scripts are placed on the same layer). Then the observer guesses that the other script is the time lock, which is what I meant initially.  
> **username_3**: Spending does not revealing anything about other scripts in the same tree. You can construct a depth-128 tree with just one script. It would be inefficient, though, as you need 128 dummy branches.  

---

