Tree Signature Variations using Commutative Hash Trees

            R 
/ \
Y1 Y2
/ \ / \
X1 X2 X3 X4
/ \ / \ / \ / \
K1 K2 K3 K4 K5 K6 K7 K8
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
<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”.

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
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
K1, sY2, sX2, K2
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
K5, sY1, sX4, sZ6

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store