Phase 1 — pair leaves left-to-right:
for i := 0; i < len(leaves); i += 2:
if i is the last index (odd leaf at end):
merge with the LAST branch built so far (do NOT pair as a fresh leaf)
else:
create a new branch from (leaves[i], leaves[i+1])
Phase 2 — FIFO-queue merge branches:
while branches has ≥ 2 items:
take front two, combine into a new branch, push to back of queue
This matters because @scure/btc-signer's taprootListToTree builds a
Huffman tree (weight-1 leaves combine by smallest-weight pairs). For
power-of-2 leaf counts both algorithms happen to produce the same
perfectly-balanced binary tree and agree. For any other count they
produce DIFFERENT shapes → different merkle roots → different taproot
output keys → arkd rejects spends with INVALID_PSBT_INPUT.
Reproducing btcd's algorithm here lets the SDK construct taptrees that
arkd accepts for arbitrary leaf counts.
Parameters
scripts: Bytes[]
Raw tapscript bytes for each leaf, in the order they
should be encoded in the TapTree PSBT field.
Assemble a Taproot script tree from a flat list of scripts using the exact algorithm arkd's btcd dependency uses (
txscript.AssembleTaprootScriptTree, see https://github.com/btcsuite/btcd/blob/master/txscript/taproot.go).The algorithm:
Phase 1 — pair leaves left-to-right: for i := 0; i < len(leaves); i += 2: if i is the last index (odd leaf at end): merge with the LAST branch built so far (do NOT pair as a fresh leaf) else: create a new branch from (leaves[i], leaves[i+1])
Phase 2 — FIFO-queue merge branches: while branches has ≥ 2 items: take front two, combine into a new branch, push to back of queue
This matters because
@scure/btc-signer'staprootListToTreebuilds a Huffman tree (weight-1 leaves combine by smallest-weight pairs). For power-of-2 leaf counts both algorithms happen to produce the same perfectly-balanced binary tree and agree. For any other count they produce DIFFERENT shapes → different merkle roots → different taproot output keys → arkd rejects spends withINVALID_PSBT_INPUT.Reproducing btcd's algorithm here lets the SDK construct taptrees that arkd accepts for arbitrary leaf counts.