[BugFix] Make PSBT serializations 174 compliant by excluding empty taptree from serialization

JeremyRubin commented at 1:53 am on August 16, 2022: contributor

According to BIP-174, the tap_tree field must be:

One or more tuples representing the depth, leaf version, and script for a leaf in the Taproot tree, allowing the entire tree to be reconstructed. The tuples must be in depth first search order so that the tree is correctly reconstructed. Each tuple is an 8-bit unsigned integer representing the depth in the Taproot tree for this script, an 8-bit unsigned integer representing the leaf version, the length of the script as a compact size unsigned integer, and the script itself.

allowing serializing an empty tap tree tuple breaks the “one or more"ness of the field, so serializations should ignore empty but initialized tap_trees.

see also https://github.com/rust-bitcoin/rust-bitcoin/pull/1194, where this caused downstream issues.

[BugFix] Make PSBT serializations 174 compliant by excluding empty taptree from serialization ca776f6d01

JeremyRubin requested review from achow101 on Aug 16, 2022

achow101 commented at 5:17 am on August 16, 2022: member

In what situation are we creating empty output taprtrees? It seems like the only way this can happen is if a PSBT created by something else is being processed. In that case, we should reject the empty taptree during parsing rather than accepting the ostensibly bad PSBT and silently dropping the bad field. The general principle for PSBT is if it came in or if we filled the field internally, then it should be serialized. So changing the serialization in this way is incorrect IMO. Rather we should not accept empty taptrees and make it impossible to add one to the psbt in our own processing.

JeremyRubin commented at 5:44 pm on August 16, 2022: contributor

Here is a script you can run to generate the bad behavior. It is not using any external tools.

I am indifferent on if the empty TapTree is not serialized, or if it is an Option null.

0ADDR=$(./bitcoin-cli -signet getnewaddress "" bech32m)
1TXID=$(./bitcoin-cli -signet send "{\"$ADDR\":20}" | jq '.txid' | xargs echo)
2VOUT=$(./bitcoin-cli -signet gettransaction $TXID true true | jq "(.decoded.vout | map(select(.scriptPubKey.address == \"$ADDR\")))[].n")
3INPUT="[{\"txid\":\"$TXID\",\"vout\":$VOUT}]"
4ADDR2=$(./bitcoin-cli -signet getnewaddress "" bech32m)
5PSBT=$(./bitcoin-cli -signet walletcreatefundedpsbt "$INPUT" "[{\"$ADDR2\": 0.1}]" | jq ".psbt" | xargs echo)
6echo "PSBT IS: " $PSBT

on master:

0cHNidP8BAIkCAAAAAapfm08b0MipBvW9thL06f8rMbeazW7TIa0W9plHj4WoAAAAAAD9////AoCWmAAAAAAAIlEgC+blBlIP1iijRWxqjw1u9H02sqr7y8fno6/LdnvGqPl895x2AAAAACJRIM5wyjSexMbADl4K+AI1/68zyaDlE7guKvrEDUAjwqU1AAAAAAABASsAlDV3AAAAACJRIDfCpO/CIAqc0JKgBhsCfaPGdyroYtmH+4gQK/Mnn72UIRZGOixxmh9h2gqDIecYHcQHRa8w+Sokc//iDiqXz7uMGRkAHzYIzlYAAIABAACAAAAAgAAAAABhAAAAARcgRjoscZofYdoKgyHnGB3EB0WvMPkqJHP/4g4ql8+7jBkAAQUg1YCB33LpmkGemw3ncz7fcnjhL/bBG/PjH8vpgr2L3cUBBgAhB9WAgd9y6ZpBnpsN53M+33J44S/2wRvz4x/L6YK9i93FGQAfNgjOVgAAgAEAAIAAAACAAAAAAGIAAAAAAQUg9jMNus8cd+GAosBk9wn+pNP9wn7A+jy2Vq0cy+siJ8wBBgAhB/YzDbrPHHfhgKLAZPcJ/qTT/cJ+wPo8tlatHMvrIifMGQAfNgjOVgAAgAEAAIAAAACAAQAAAFEBAAAA

with this patch

0cHNidP8BAIkCAAAAATpwsU9MR76awftD8FkbSHpWSl7aXJShh0Zt/Qhs2nxxAAAAAAD9////AoCWmAAAAAAAIlEgXVnPV8AvZ8aaQrx5yD9j3f/2sC5HyZRFZSiAmJpNTMx895x2AAAAACJRINESxWA49wL5zMro5bHRFQs1uYXY/rkh7YHWo8ryt4pNAAAAAAABASsAlDV3AAAAACJRIGnS8YOeOIEB3SGewSxxyHAVyL1G1hKZpzDMNablWo/hIRaSI43XyWhcnQ9kvKrZQuFwJhg/MtXjsYIoywerZApowBkAHzYIzlYAAIABAACAAAAAgAAAAABdAAAAARcgkiON18loXJ0PZLyq2ULhcCYYPzLV47GCKMsHq2QKaMAAAQUgyUyJb6VUpCjCmi7Z1CGvPn6K3BFlzxPpsJ3szGn4eQMhB8lMiW+lVKQowpou2dQhrz5+itwRZc8T6bCd7Mxp+HkDGQAfNgjOVgAAgAEAAIAAAACAAAAAAF4AAAAAAQUgsx/g/7PwwPDAdHz2Qvl1IHuYKRppAYZoSAqyyEU9DXohB7Mf4P+z8MDwwHR89kL5dSB7mCkaaQGGaEgKsshFPQ16GQAfNgjOVgAAgAEAAIAAAACAAQAAAEkBAAAA

decoded master:

  0{
  1  "tx": {
  2    "txid": "aae4ec9b7a539b7ac60ad39dda5c3a537aaf5c2b42f744343f1c110af156d0fa",
  3    "hash": "aae4ec9b7a539b7ac60ad39dda5c3a537aaf5c2b42f744343f1c110af156d0fa",
  4    "version": 2,
  5    "size": 137,
  6    "vsize": 137,
  7    "weight": 548,
  8    "locktime": 0,
  9    "vin": [
 10      {
 11        "txid": "a8858f4799f616ad21d36ecd9ab7312bffe9f412b6bdf506a9c8d01b4f9b5faa",
 12        "vout": 0,
 13        "scriptSig": {
 14          "asm": "",
 15          "hex": ""
 16        },
 17        "sequence": 4294967293
 18      }
 19    ],
 20    "vout": [
 21      {
 22        "value": 0.10000000,
 23        "n": 0,
 24        "scriptPubKey": {
 25          "asm": "1 0be6e506520fd628a3456c6a8f0d6ef47d36b2aafbcbc7e7a3afcb767bc6a8f9",
 26          "desc": "rawtr(0be6e506520fd628a3456c6a8f0d6ef47d36b2aafbcbc7e7a3afcb767bc6a8f9)#sfw45af0",
 27          "hex": "51200be6e506520fd628a3456c6a8f0d6ef47d36b2aafbcbc7e7a3afcb767bc6a8f9",
 28          "address": "tb1pp0nw2pjjpltz3g69d34g7rtw737ndv42l09u0ear4l9hv77x4rusu9dad7",
 29          "type": "witness_v1_taproot"
 30        }
 31      },
 32      {
 33        "value": 19.89998460,
 34        "n": 1,
 35        "scriptPubKey": {
 36          "asm": "1 ce70ca349ec4c6c00e5e0af80235ffaf33c9a0e513b82e2afac40d4023c2a535",
 37          "desc": "rawtr(ce70ca349ec4c6c00e5e0af80235ffaf33c9a0e513b82e2afac40d4023c2a535)#sydncjf5",
 38          "hex": "5120ce70ca349ec4c6c00e5e0af80235ffaf33c9a0e513b82e2afac40d4023c2a535",
 39          "address": "tb1peecv5dy7cnrvqrj7ptuqyd0l4ueung89zwuzu2h6csx5qg7z556sjz72rf",
 40          "type": "witness_v1_taproot"
 41        }
 42      }
 43    ]
 44  },
 45  "global_xpubs": [
 46  ],
 47  "psbt_version": 0,
 48  "proprietary": [
 49  ],
 50  "unknown": {
 51  },
 52  "inputs": [
 53    {
 54      "witness_utxo": {
 55        "amount": 20.00000000,
 56        "scriptPubKey": {
 57          "asm": "1 37c2a4efc2200a9cd092a0061b027da3c6772ae862d987fb88102bf3279fbd94",
 58          "desc": "rawtr(37c2a4efc2200a9cd092a0061b027da3c6772ae862d987fb88102bf3279fbd94)#ryczaytf",
 59          "hex": "512037c2a4efc2200a9cd092a0061b027da3c6772ae862d987fb88102bf3279fbd94",
 60          "address": "tb1pxlp2fm7zyq9fe5yj5qrpkqna50r8w2hgvtvc07ugzq4lxfulhk2qlkpf56",
 61          "type": "witness_v1_taproot"
 62        }
 63      },
 64      "taproot_bip32_derivs": [
 65        {
 66          "pubkey": "463a2c719a1f61da0a8321e7181dc40745af30f92a2473ffe20e2a97cfbb8c19",
 67          "master_fingerprint": "1f3608ce",
 68          "path": "m/86'/1'/0'/0/97",
 69          "leaf_hashes": [
 70          ]
 71        }
 72      ],
 73      "taproot_internal_key": "463a2c719a1f61da0a8321e7181dc40745af30f92a2473ffe20e2a97cfbb8c19"
 74    }
 75  ],
 76  "outputs": [
 77    {
 78      "taproot_internal_key": "d58081df72e99a419e9b0de7733edf7278e12ff6c11bf3e31fcbe982bd8bddc5",
 79      "taproot_tree": [
 80      ],
 81      "taproot_bip32_derivs": [
 82        {
 83          "pubkey": "d58081df72e99a419e9b0de7733edf7278e12ff6c11bf3e31fcbe982bd8bddc5",
 84          "master_fingerprint": "1f3608ce",
 85          "path": "m/86'/1'/0'/0/98",
 86          "leaf_hashes": [
 87          ]
 88        }
 89      ]
 90    },
 91    {
 92      "taproot_internal_key": "f6330dbacf1c77e180a2c064f709fea4d3fdc27ec0fa3cb656ad1ccbeb2227cc",
 93      "taproot_tree": [
 94      ],
 95      "taproot_bip32_derivs": [
 96        {
 97          "pubkey": "f6330dbacf1c77e180a2c064f709fea4d3fdc27ec0fa3cb656ad1ccbeb2227cc",
 98          "master_fingerprint": "1f3608ce",
 99          "path": "m/86'/1'/0'/1/337",
100          "leaf_hashes": [
101          ]
102        }
103      ]
104    }
105  ],
106  "fee": 0.00001540
107}

decode patched

  0{
  1  "tx": {
  2    "txid": "4e7d1ab0ae861c82a973c23bf13cebf24ce3af009c591a4169ea56b95e72b92a",
  3    "hash": "4e7d1ab0ae861c82a973c23bf13cebf24ce3af009c591a4169ea56b95e72b92a",
  4    "version": 2,
  5    "size": 137,
  6    "vsize": 137,
  7    "weight": 548,
  8    "locktime": 0,
  9    "vin": [
 10      {
 11        "txid": "717cda6c08fd6d4687a1945cda5e4a567a481b59f043fbc19abe474c4fb1703a",
 12        "vout": 0,
 13        "scriptSig": {
 14          "asm": "",
 15          "hex": ""
 16        },
 17        "sequence": 4294967293
 18      }
 19    ],
 20    "vout": [
 21      {
 22        "value": 0.10000000,
 23        "n": 0,
 24        "scriptPubKey": {
 25          "asm": "1 5d59cf57c02f67c69a42bc79c83f63ddfff6b02e47c99445652880989a4d4ccc",
 26          "desc": "rawtr(5d59cf57c02f67c69a42bc79c83f63ddfff6b02e47c99445652880989a4d4ccc)#qa5395xa",
 27          "hex": "51205d59cf57c02f67c69a42bc79c83f63ddfff6b02e47c99445652880989a4d4ccc",
 28          "address": "tb1pt4vu747q9anudxjzh3uus0mrmhlldvpwglyeg3t99zqf3xjdfnxqpsn99y",
 29          "type": "witness_v1_taproot"
 30        }
 31      },
 32      {
 33        "value": 19.89998460,
 34        "n": 1,
 35        "scriptPubKey": {
 36          "asm": "1 d112c56038f702f9cccae8e5b1d1150b35b985d8feb921ed81d6a3caf2b78a4d",
 37          "desc": "rawtr(d112c56038f702f9cccae8e5b1d1150b35b985d8feb921ed81d6a3caf2b78a4d)#z88xvjpv",
 38          "hex": "5120d112c56038f702f9cccae8e5b1d1150b35b985d8feb921ed81d6a3caf2b78a4d",
 39          "address": "tb1p6yfv2cpc7up0nnx2arjmr5g4pv6mnpwcl6ujrmvp663u4u4h3fxsrqclw3",
 40          "type": "witness_v1_taproot"
 41        }
 42      }
 43    ]
 44  },
 45  "global_xpubs": [
 46  ],
 47  "psbt_version": 0,
 48  "proprietary": [
 49  ],
 50  "unknown": {
 51  },
 52  "inputs": [
 53    {
 54      "witness_utxo": {
 55        "amount": 20.00000000,
 56        "scriptPubKey": {
 57          "asm": "1 69d2f1839e388101dd219ec12c71c87015c8bd46d61299a730cc35a6e55a8fe1",
 58          "desc": "rawtr(69d2f1839e388101dd219ec12c71c87015c8bd46d61299a730cc35a6e55a8fe1)#lcncmzh8",
 59          "hex": "512069d2f1839e388101dd219ec12c71c87015c8bd46d61299a730cc35a6e55a8fe1",
 60          "address": "tb1pd8f0rqu78zqsrhfpnmqjcuwgwq2u302x6cffnfeses66de263lss3w2r37",
 61          "type": "witness_v1_taproot"
 62        }
 63      },
 64      "taproot_bip32_derivs": [
 65        {
 66          "pubkey": "92238dd7c9685c9d0f64bcaad942e17026183f32d5e3b18228cb07ab640a68c0",
 67          "master_fingerprint": "1f3608ce",
 68          "path": "m/86'/1'/0'/0/93",
 69          "leaf_hashes": [
 70          ]
 71        }
 72      ],
 73      "taproot_internal_key": "92238dd7c9685c9d0f64bcaad942e17026183f32d5e3b18228cb07ab640a68c0"
 74    }
 75  ],
 76  "outputs": [
 77    {
 78      "taproot_internal_key": "c94c896fa554a428c29a2ed9d421af3e7e8adc1165cf13e9b09deccc69f87903",
 79      "taproot_bip32_derivs": [
 80        {
 81          "pubkey": "c94c896fa554a428c29a2ed9d421af3e7e8adc1165cf13e9b09deccc69f87903",
 82          "master_fingerprint": "1f3608ce",
 83          "path": "m/86'/1'/0'/0/94",
 84          "leaf_hashes": [
 85          ]
 86        }
 87      ]
 88    },
 89    {
 90      "taproot_internal_key": "b31fe0ffb3f0c0f0c0747cf642f975207b98291a69018668480ab2c8453d0d7a",
 91      "taproot_bip32_derivs": [
 92        {
 93          "pubkey": "b31fe0ffb3f0c0f0c0747cf642f975207b98291a69018668480ab2c8453d0d7a",
 94          "master_fingerprint": "1f3608ce",
 95          "path": "m/86'/1'/0'/1/329",
 96          "leaf_hashes": [
 97          ]
 98        }
 99      ]
100    }
101  ],
102  "fee": 0.00001540
103}

JeremyRubin commented at 5:46 pm on August 16, 2022: contributor

(I also find the empty leaf_hashes field a bit sus, but couldn’t find anything in the spec around if they are allowed to be empty)

JeremyRubin commented at 6:13 pm on August 16, 2022: contributor

On further research, I do think this is the correct behavior, but the issue is that the field name m_tap_tree should be refactored (in follow up work?) to be m_taproot_builder, because it is the builder (which also contains the pubkey if key-only). The “true” field of tap_tree is only available when derived from taproot_builder by calling the function to check for presence of branches.

Thus there is no “stopping this issue at the source”, it’s just a logic bug in serializing of PSBT from core.

achow101 commented at 6:52 pm on August 16, 2022: member

I think the correct behavior is to change PSBTOutput::FromSignatureData to only fill in m_tap_tree when SignatureData.tr_builder has a merkle root. We should also check that the tree is not empty when deserializing

Also I think the decdepsbt change is strictly incorrect. If the field is there and we did not fail parsing, then we need to output it when decoding. Otherwise we cannot trust decodepsbt for tests to be sure that unexpected fields do not sneak in.

This could also use a test.

[BugFix]: Do not allow deserializing PSBT with empty PSBT_OUT_TAP_TREE 615a7aa1b8

JeremyRubin commented at 7:15 pm on August 16, 2022: contributor

Added a patch to prevent invalid deserialization. I think that with that patch, the approach used here is sufficient because not deserializing an empty Tap Tree is something that can, now, only be the result of an internal logic error.

W.r.t. “preventing it at the source”, I tried this patch independent of any others, but it didn’t seem to work. Maybe you can figure out where the bad state is coming from?

 0diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
 1index 9bcbe1cee..f6a67be5a 100644
 2--- a/src/script/descriptor.cpp
 3+++ b/src/script/descriptor.cpp
 4@@ -885,20 +885,28 @@ class TRDescriptor final : public DescriptorImpl
 5 protected:
 6     std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
 7     {
 8-        TaprootBuilder builder;
 9+        std::optional<TaprootBuilder> builder;
10         assert(m_depths.size() == scripts.size());
11         for (size_t pos = 0; pos < m_depths.size(); ++pos) {
12-            builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT);
13+            if (!builder.has_value()) {
14+                builder = TaprootBuilder{};
15+            }
16+            builder->Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT);
17         }
18-        if (!builder.IsComplete()) return {};
19+        if (builder && !builder->IsComplete()) return {};
20         assert(keys.size() == 1);
21         XOnlyPubKey xpk(keys[0]);
22         if (!xpk.IsFullyValid()) return {};
23-        builder.Finalize(xpk);
24-        WitnessV1Taproot output = builder.GetOutput();
25-        out.tr_trees[output] = builder;
26-        out.pubkeys.emplace(keys[0].GetID(), keys[0]);
27-        return Vector(GetScriptForDestination(output));
28+        if (builder) {
29+            builder->Finalize(xpk);
30+            WitnessV1Taproot output = builder->GetOutput();
31+            out.tr_trees[output] = *builder;
32+            out.pubkeys.emplace(keys[0].GetID(), keys[0]);
33+            return Vector(GetScriptForDestination(output));
34+        } else {
35+            out.pubkeys.emplace(keys[0].GetID(), keys[0]);
36+            return Vector(GetScriptForDestination(WitnessV1Taproot(xpk)));
37+        }
38     }
39     bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const override
40     {

achow101 added this to the milestone 24.0 on Aug 16, 2022

achow101 commented at 8:15 pm on August 16, 2022: member

Alternative in #25858

DrahtBot commented at 7:49 am on August 17, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#25877 (refactor: Do not use CScript for tapleaf scripts until the tapleaf version is known by roconnor-blockstream)
#25858 (psbt: Only include PSBT_OUT_TAP_TREE when the output has a script path by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

glozow added the label PSBT on Aug 19, 2022

fanquake commented at 9:49 am on September 14, 2022: member

Going to close this in favour of #25858 for now, as it seems that PR has a number of concept/approach ACKs (including from @JeremyRubin). Jeremy please let me know if this is incorrect.

fanquake closed this on Sep 14, 2022

fanquake removed this from the milestone 24.0 on Sep 14, 2022

glozow referenced this in commit 147d64dbdf on Oct 13, 2022

sidhujag referenced this in commit c95704fb03 on Oct 23, 2022

bitcoin locked this on Sep 14, 2023

[BugFix] Make PSBT serializations 174 compliant by excluding empty taptree from serialization #25856

Conflicts