Tree Signature Variations using Commutative Hash Trees

(originally posted on yours.org on June 2018)

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.

Related thoughts

P2PKH has its script counterpart in P2SH, but “MAST tree signatures” has no “MAST tree script” counterpart. We should make script as data manipulations (e.g. an opcode named “OP_EXEC”) sufficiently powerful to allow the construction of MAST-like scripts where each leaf is itself a script not a pubkey, without making it so powerful that very-long-running scripts become possible.

This would allow us to pack a longer script into the available space, provided that the script is dominated by conditional clauses. It would also allow us to fix the awkward P2SH formulation, which is that nothing in the script actually tells the interpreter to execute the redeem script (it is after all just data pushed onto the stack). The bitcoin clients are just hard coded to do so when the P2SH script format is recognized.

[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/