Andrew Stone spent #crypto

# Tree Signature Variations using Commutative Hash Trees

Andrew Stone spent #crypto

To create more efficient multisig and increase privacy, a technology called MAST and a scriptable version of it called "tree signatures" was invented. However, tree signatures has a relatively confusing redeem script, and requires OP_CAT which was removed from the bitcoin scripting language. The problem is best illustrated by an example which I will borrow from here. Given the following tree:

R
/ \
Y1 Y2
/ \ / \
X1 X2 X3 X4
/ \ / \ / \ / \
K1 K2 K3 K4 K5 K6 K7 K8

As per [3], the redeem script looks like:

```OP_6 OP_PICK OP_SHA256 OP_SWAP OP_IF OP_SWAP OP_ENDIF OP_CAT OP_SHA256 OP_SWAP OP_IF OP_SWAP OP_ENDIF OP_CAT OP_SHA256 OP_SWAP OP_IF OP_SWAP OP_ENDIF OP_CAT OP_SHA256 <R> OP_EQUALVERIFY OP_CHECKSIG```

This is an eye-glazing script unless you are used to reading the bitcoin scripting language. Instead of analyzing it start-to-finish here, I will just focus on one part -- the repeated "OP_IF OP_SWAP OP_ENDIF" clauses. These are necessary because in the tree signature formulation, each level of the merkle tree is constructed by concatenating two siblings and calculating the SHA256 of the result. For example, Y1 = SHA256(CAT(X1,X2)).

But the concat operation is order-dependent. Let's say that we want to provide K1. In that case, the spend script could provide K1, K2 and X2 and the redeem (output) script fragment (just to get us Y1) would be the following. Note for clarity, I am using the @ sign to denote stack items that were provided by the spend script, and pretending that temporary variables exist (although these variables are actually the bitcoin script stack).

A = OP_CAT(@K1,@K2)

X1 = OP_SHA256(A)

C = OP_CAT(X1, @X2)

Y1 = OP_SHA256(C)

But what if we wanted to provide K3? In this case the redeem script fragment needs to be:

A = OP_CAT(@K3,@K4)

X2 = OP_SHA256(A)

OP_SWAP(X2, @X1) # Fix the problem that X2 and X1 are in the wrong order!

C = OP_CAT(X1,@X2)

Y1 = OP_SHA256(C)

So to make a single redeem script out of both of these options, we need to conditionally execute the OP_SWAP. This creates script complexity and the requirement on the spend script to push some 1s or 0s onto the stack to select or skip OP_SWAP. For example, to spend using K5 note the OP_0 and OP_1 instructions in the spend script from our borrowed example:

<sig> <key5> <Y1> OP_0 <X4> OP_1 <K6> OP_1

### Commutative Hash Trees

But the order of the leaves in this merkle signature tree is not relevant information in this application. So instead of a merkle tree, let us use a new hash tree formulation that is permutable. We can accomplish this by changing how we combine the tree siblings prior to SHA256 -- let's add them rather than using concatenation because addition is a commutative operation. So now Y1 = SHA256(X1 + X2). A quick google search turns up nothing, so let's tentatively call this a "commutative hash tree".

At the key level, there is another small change. For security, we must first compute the SHA256 of each key before we sum them. To explain why, let's imagine we do not do this. When Alice posts a transaction, she would divulge K1 and K2 whose sum S hashes to X1. Mallory therefore learns S and can pick his own key mK1 and any mK2 = S-mK1 whose sum therefore also hash to X1. Using this technique, Mallory could create his own tree with a key replaced by his designated value. However (back to having the additional SHA256), since Mallory must hash mK1 and mK2 first, he cannot pick mK1 and mK2 such that SHA256(mK1) + SHA256(mK2) = X1 without first breaking SHA256.

This issue also exists for interior nodes when providing merkle proofs. But an interior node Y1 is already the SHA256 of the sum of X1 and X2. So we can require that the provider of the merkle proof supply X1+X2 rather than SHA256(X1+X2). When differentiation is needed in this document, I will denote the unhashed sum with a preceding "s", for example, sY1.

### Application to Tree Signatures

The tree in our Bitcoin Cash multisig-via-tree-signatures example will therefore look as follows:

R

/ \

Y1 Y2

/ \ / \

X1 X2 X3 X4

/ \ / \ / \ / \

Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8

| | | | | | | |

K1 K2 K3 K4 K5 K6 K7 K8

The redeem script to spend any key is a merkle proof verification and is therefore:

OP_3, OP_PICK # copy the key from the bottom of the stack (where we will need it for the OP_CHECKSIG to the top for the tree calc

OP_SHA256 # combine key level

OP_SWAP, OP_SHA256, OP_ADD, OP_SHA256 # combine Z level

OP_SWAP, OP_SHA256, OP_ADD, OP_SHA256 # combine X level

OP_SWAP, OP_SHA256, OP_ADD, OP_SHA256 # combine Y level

<R> OP_EQUALVERIFY OP_CHECKSIG

```

With the above redeem script, we can make the spend scripts by including just the "other" merkle tree nodes at each level.

Spend script for K1:

K1, sY2, sX2, K2

Let me go though the execution for clarity:

OP_3, OP_PICK --> K1, sY2, sX2, K2, K1 (grab K1 from the stack top)

OP_SHA256 --> K1, sY2, sX2, K2, Z1 (turn it into Z1)

(let's break the Z level into 2 steps)

OP_SWAP, OP_SHA256, --> K1, sY2, sX2, Z1, Z2 (turns K2 into Z2 by sha256)

OP_ADD, OP_SHA256 --> K1, sY2, sX2, X1 (add Z1 and Z2 and hash so Z level becomes X1)

OP_SWAP, OP_SHA256, OP_ADD, OP_SHA256 --> K1, sY2, Y1 (the full X level)

OP_SWAP, OP_SHA256, OP_ADD, OP_SHA256 --> K1, R (The full Y level)

<R> OP_EQUALVERIFY OP_CHECKSIG --> 1

The spend script for any other key just requires different nodes in the commutative hash tree. For example, the spend script for K5 is:

K5, sY1, sX4, sZ6

During this merkle proof calculation we traded the 'OP_IF OP_SWAP OP_ENDIF' clauses for an OP_SHA256. This has two advantages: it reduces the bytes per level from 6 to 4, allowing the merkle proof validation of a larger tree to be encoded in the same space, and it uses opcodes available to the Bitcoin (Core) chain. Its disadvantage is that the extra OP_SHA256 is expensive compared to a swap.

We need this additional OP_SHA256 because of a property of addition: the set of possible results given any argument is not disjoint. In other words, with string concatenation, if the first argument is "cat", there is no possible 2nd argument that can be chosen to convert the result to "dog". The result has to be "cat<something>". So no attacker can pick a second argument that will satisfy the equation <attacker's chosen value> OP <attacker's pick> = <result>. If we could find or engineer a commutative operation with either this disjoint property (or with the irreversible property I'm taking advantage of in the extra merkle proof OP_SHA256), we could drop the additional OP_SHA256 from the script.

To go almost full circle, an example of such an engineered commutative disjoint operation is SORTCAT -- that is, first sort the inputs, then concatenate them. Given that there are only 2 inputs in this case, a "sort" is just a compare and swap -- essentially the same operations as original tree signature formulation (OP_LESSTHAN, OP_IF, OP_SWAP, OP_ENDIF, OP_CAT). However, the original tree signature formulation requires that the spend script provide additional stack parameters to control whether the swap happens, whereas the SORTCAT formulation operates solely on the tree's interior nodes. So the spend script is smaller and its formulation is conceptually simpler, but the redeem script is 1 byte larger per level.

Additionally, something like SORTCAT is interesting outside of bitcoin script because it efficiently implements a commutative but disjoint operation and so enables an efficient commutative hash tree, which has somewhat different properties than the standard merkle tree.

The paid content is just an extra -- its an idea/challenge that I put to the BCH dev community.

[1] Wuille, Peter (2015) https://www.blockstream.com/2015/08/24/treesignatures/

[2] Harding, David (2017) https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f

[3] Pacia, Chris (2018) https://www.reddit.com/r/btc/comments/8joo00/first_tree_signature_on_bitcoin_cash_using_new/

**Reviews**

24 of 24 reviewers say it's worth paying for

0 of 24 reviewers say it's not worth paying for

**Comments**

Really appreciate your great idea to use OP_ADD (or OP_XOR for that matter) to replace OP_CAT in MAST to simplify scripts and save space without sacrificing any functionality.

A few comments:

- The logic in your examples would be easier to follow for noobs like me in bitcoin script if spend script is stated before you explain redeem script. Before knowing stack status which is given by spend script, I was puzzled for quite a while by your explaining the meaning of each part in redeem script.
- Commutative hash tree does NOT require sha256'ing each public key (leaf) before building up the tree for security. Replacing OP_CAT with OP_ADD does not introduce any new vulnerability because all inner nodes of the tree are hashed in both cases. You never expose, say the sum s=K1+K2, just as you never expose the concatenation c=K1|K2. You only expose sha256(K1+K2), or sha256(K1|K2) in old MAST, from which you can not figure out K2 given K1.
- The idea behind the paywall seems interesting but vague. You may want to clarify by providing an example.

- As far as I understand, MAST of scripts is impossible in BCH without major protocol changes to allow something similar to colon word definitions in Forth language. OP_CAT/OP_ADD etc. correspond to primitives in Forth.
- A leaf node in MAST can become a script if colon definitions are allowed. The problem is, you may easily end up with mixing data and code in totally unconscionable ways.
- Leaf nodes possibly being scripts, branches in MAST may not be independent of each other any more, i.e. MAST is not a tree any more.
- In conclusion, this idea is intriguing but very confusing and confused.

@khery, about your comment that SHA256 is not required. Lets us work through a merkle proof attack without the SHA256: Say Alice creates a Merkle proof that her key K1 is in the tree. This Merkle proof includes Z2, X2 and Y2. Validating this proof gives Mallory the inner nodes he needs. He calculates Y1 from Z2, X2, and Alice's pubkey. He then calculates Y = Y1 + Y2, and R = SHA256(Y). Next he creates calculates his own mY1 from his own pubkey and arbitrary values mZ2 and mX2. He then calculates mY2 = Y - mY1. R therefore matches (its the SHA256(Y), and mY1 + mY2 = Y) and so he has created an alternate tree with the same merkle root.

Instead, my formulation works because it requires him to pick a mY1 that solves the equation mY2 = Y - SHA256(mY1), and to do that he must reverse SHA256.

@Andrew Stone Thanks a lot for taking time to provide a reply with a worked-out example which make me understand your formulation better and rethink about necessity of SHA256 to avoid alternative merkle proof attack with the same merkle root. But I'm still not settled on this issue and want to get to its bottom if at all possible.

I now understand that using OP_CAT in MAST actually makes MAST uniquely determined given a merkle root and number of tree levels while using OP_ADD will allow multiple MASTs with the same merkle root and number of tree levels. That's why you have to introduce extra SHA256 ops at each tree level to make a commutative MAST unique given a merkle root as you clearly showed in the example. Which means, for example Y1=SHA256(SHA256(X1)+SHA256(X2)) and R=SHA256((SHA256(Y1)+SHA256(Y2)), etc.

What is confusing is that in your article above, you obviously just wanted to introduce extra SHA256 op at the lowest key level of the tree as indicated by that extra Z layer in the tree graph but NOT in higher levels for internal nodes. You actually put Y1 = SHA256(X1 + X2) in the text and also said

>This issue also exists for interior nodes when providing merkle proofs. But an interior node Y1 is already the SHA256 of the sum of X1 and X2. So we can require that the provider of the merkle proof supply X1+X2 rather than SHA256(X1+X2).

which is very different from what you apparently intended to apply to the worked-out example in your reply.

If using OP_ADD instead of OP_CAT in MAST entails extra SHA256 ops in every tree level, then it is hard for me to see much advantage of your commutative MAST in terms of script compactness and computing economy. OP_SHA256 is much more costly than some OP_SWAP OP_IF/ENDIF etc.

On the other hand, it seems to me, a noob in Bitcoin tech, that attacks using alternative merkle proof are hard to imagine and may not as serious as you seem to assume. But I can be wrong. Can you give a senario of this attack? Until recent enabling of these extra OP_CODEs, most transactions use OP_EQUALVERIFY to check public key hash as an auxiliary security measure in addition to the crucial OP_CHECKSIG. After one spend, public key is exposed and an address may become a tiny bit less secure. But private key is the key to security. So what's a big deal about possible alternative merkle proof which is essentially a refined version of public key hash check?

@khery, I did "explode" the view of the leaves but hid the similar view in every node to keep the diagram sane.

The commutative hash tree is interesting because it has some unique properties.

The SHA256 formulation is less efficient in CPU time, but it is very interesting from a practical perspective because it can be used on Bitcoin's reduced instruction set, and because a larger tree will fit into the available script space which is quite small. And remember that we are talking about 2*log2(number of signatures) SHA256 operations verses log2(number of signatures). So even raspberry pi's can crank through the extra calculations quickly.

The SORTCAT formulation IS just as efficient as the CAT formulation, and SORTCAT has interesting properties as a primitive operation. Sure it does not exist as a primitive in the Bitcoin Cash instruction set, but it can be expressed there, resulting in a simple input script formulation.

And this article is meant to explore the commutative hash tree in general. SORTCAT is easily implemented in "normal" programming languages, and the commutative hash tree seems like a useful replacement whenever a merkle tree is used.