Inside Bitcoin

1251        // given those of its subnodes.
1252        auto helper = [&ctx](const Node& node, std::span<InputResult> subres) -> InputResult {
1253            switch (node.fragment) {
1254                case Fragment::PK_K: {
1255                    std::vector<unsigned char> sig;
1256                    Availability avail = ctx.Sign(node.keys[0], sig);
1257                    return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
1258                }
1259                case Fragment::PK_H: {
1260                    std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig;
1261                    Availability avail = ctx.Sign(node.keys[0], sig);
1262                    return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
1263                }
1264                case Fragment::MULTI_A: {
1265                    // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
1266                    // In the loop below, these stacks are built up using a dynamic programming approach.
1267                    std::vector<InputStack> sats = Vector(EMPTY);
1268                    for (size_t i = 0; i < node.keys.size(); ++i) {
1269                        // Get the signature for the i'th key in reverse order (the signature for the first key needs to
1270                        // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction).
1271                        std::vector<unsigned char> sig;
1272                        Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig);
1273                        // Compute signature stack for just this key.
1274                        auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1275                        // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
1276                        // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature
1277                        // for the current (i'th) key. The very last element needs all signatures filled.
1278                        std::vector<InputStack> next_sats;
1279                        next_sats.push_back(sats[0] + ZERO);
1280                        for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
1281                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1282                        // Switch over.
1283                        sats = std::move(next_sats);
1284                    }
1285                    // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
1286                    // satisfying 0 keys.
1287                    auto& nsat{sats[0]};
1288                    CHECK_NONFATAL(node.k != 0);
1289                    assert(node.k < sats.size());
1290                    return {std::move(nsat), std::move(sats[node.k])};
1291                }
1292                case Fragment::MULTI: {
1293                    // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
1294                    // In the loop below, these stacks are built up using a dynamic programming approach.
1295                    // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many.
1296                    std::vector<InputStack> sats = Vector(ZERO);
1297                    for (size_t i = 0; i < node.keys.size(); ++i) {
1298                        std::vector<unsigned char> sig;
1299                        Availability avail = ctx.Sign(node.keys[i], sig);
1300                        // Compute signature stack for just the i'th key.
1301                        auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1302                        // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
1303                        // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the
1304                        // current (i'th) key. The very last element needs all signatures filled.
1305                        std::vector<InputStack> next_sats;
1306                        next_sats.push_back(sats[0]);
1307                        for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
1308                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1309                        // Switch over.
1310                        sats = std::move(next_sats);
1311                    }
1312                    // The dissatisfaction consists of k+1 stack elements all equal to 0.
1313                    InputStack nsat = ZERO;
1314                    for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO;
1315                    assert(node.k < sats.size());
1316                    return {std::move(nsat), std::move(sats[node.k])};
1317                }
1318                case Fragment::THRESH: {
1319                    // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions.
1320                    // In the loop below, these stacks are built up using a dynamic programming approach.
1321                    // sats[0] starts off empty.
1322                    std::vector<InputStack> sats = Vector(EMPTY);
1323                    for (size_t i = 0; i < subres.size(); ++i) {
1324                        // Introduce an alias for the i'th last satisfaction/dissatisfaction.
1325                        auto& res = subres[subres.size() - i - 1];
1326                        // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions
1327                        // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat
1328                        // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions.
1329                        std::vector<InputStack> next_sats;
1330                        next_sats.push_back(sats[0] + res.nsat);
1331                        for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat));
1332                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
1333                        // Switch over.
1334                        sats = std::move(next_sats);
1335                    }
1336                    // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction
1337                    // is computed by gathering all sats[i].nsat for i != k.
1338                    InputStack nsat = INVALID;
1339                    for (size_t i = 0; i < sats.size(); ++i) {
1340                        // i==k is the satisfaction; i==0 is the canonical dissatisfaction;
1341                        // the rest are non-canonical (a no-signature dissatisfaction - the i=0
1342                        // form - is always available) and malleable (due to overcompleteness).
1343                        // Marking the solutions malleable here is not strictly necessary, as they
1344                        // should already never be picked in non-malleable solutions due to the
1345                        // availability of the i=0 form.
1346                        if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon();
1347                        // Include all dissatisfactions (even these non-canonical ones) in nsat.
1348                        if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]);
1349                    }
1350                    assert(node.k < sats.size());
1351                    return {std::move(nsat), std::move(sats[node.k])};
1352                }
1353                case Fragment::OLDER: {
1354                    return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID};
1355                }
1356                case Fragment::AFTER: {
1357                    return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID};
1358                }
1359                case Fragment::SHA256: {
1360                    std::vector<unsigned char> preimage;
1361                    Availability avail = ctx.SatSHA256(node.data, preimage);
1362                    return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1363                }
1364                case Fragment::RIPEMD160: {
1365                    std::vector<unsigned char> preimage;
1366                    Availability avail = ctx.SatRIPEMD160(node.data, preimage);
1367                    return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1368                }
1369                case Fragment::HASH256: {
1370                    std::vector<unsigned char> preimage;
1371                    Availability avail = ctx.SatHASH256(node.data, preimage);
1372                    return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1373                }
1374                case Fragment::HASH160: {
1375                    std::vector<unsigned char> preimage;
1376                    Availability avail = ctx.SatHASH160(node.data, preimage);
1377                    return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1378                }
1379                case Fragment::AND_V: {
1380                    auto& x = subres[0], &y = subres[1];
1381                    // As the dissatisfaction here only consist of a single option, it doesn't
1382                    // actually need to be listed (it's not required for reasoning about malleability of
1383                    // other options), and is never required (no valid miniscript relies on the ability
1384                    // to satisfy the type V left subexpression). It's still listed here for
1385                    // completeness, as a hypothetical (not currently implemented) satisfier that doesn't
1386                    // care about malleability might in some cases prefer it still.
1387                    return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
1388                }
1389                case Fragment::AND_B: {
1390                    auto& x = subres[0], &y = subres[1];
1391                    // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here
1392                    // as malleable. While they are definitely malleable, they are also non-canonical due
1393                    // to the guaranteed existence of a no-signature other dissatisfaction (the 1st)
1394                    // option. Because of that, the 2nd and 3rd option will never be chosen, even if they
1395                    // weren't marked as malleable.
1396                    return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat};
1397                }
1398                case Fragment::OR_B: {
1399                    auto& x = subres[0], &z = subres[1];
1400                    // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat).
1401                    return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()};
1402                }
1403                case Fragment::OR_C: {
1404                    auto& x = subres[0], &z = subres[1];
1405                    return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
1406                }
1407                case Fragment::OR_D: {
1408                    auto& x = subres[0], &z = subres[1];
1409                    return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
1410                }
1411                case Fragment::OR_I: {
1412                    auto& x = subres[0], &z = subres[1];
1413                    return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)};
1414                }
1415                case Fragment::ANDOR: {
1416                    auto& x = subres[0], &y = subres[1], &z = subres[2];
1417                    return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)};
1418                }
1419                case Fragment::WRAP_A:
1420                case Fragment::WRAP_S:
1421                case Fragment::WRAP_C:
1422                case Fragment::WRAP_N:
1423                    return std::move(subres[0]);
1424                case Fragment::WRAP_D: {
1425                    auto &x = subres[0];
1426                    return {ZERO, x.sat + ONE};
1427                }
1428                case Fragment::WRAP_J: {
1429                    auto &x = subres[0];
1430                    // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists.
1431                    // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even
1432                    // if a dissatisfaction with a top zero element is found, we don't know whether another one with a
1433                    // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly
1434                    // dissatisfiable, this alternative dissatisfaction exists and leads to malleability.
1435                    return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
1436                }
1437                case Fragment::WRAP_V: {
1438                    auto &x = subres[0];
1439                    return {INVALID, std::move(x.sat)};
1440                }
1441                case Fragment::JUST_0: return {EMPTY, INVALID};
1442                case Fragment::JUST_1: return {INVALID, EMPTY};
1443            }
1444            assert(false);
1445            return {INVALID, INVALID};
1446        };
1447
1448        auto tester = [&helper](const Node& node, std::span<InputResult> subres) -> InputResult {
1449            auto ret = helper(node, subres);
1450
1451            // Do a consistency check between the satisfaction code and the type checker
1452            // (the actual satisfaction code in ProduceInputHelper does not use GetType)
1453
1454            // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0.
1455            if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 0);
1456            if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 0);
1457
1458            // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1.
1459            if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 1);
1460            if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 1);
1461
1462            // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions,
1463            // the top element cannot be 0.
1464            if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() >= 1);
1465            if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() >= 1);
1466            if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.stack.back().empty());
1467
1468            // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable,
1469            // it must be canonical.
1470            if (node.GetType() << "d"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO);
1471            if (node.GetType() << "d"_mst) CHECK_NONFATAL(!ret.nsat.has_sig);
1472            if (node.GetType() << "d"_mst && !ret.nsat.malleable) CHECK_NONFATAL(!ret.nsat.non_canon);
1473
1474            // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature.
1475            if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.has_sig);
1476            if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.has_sig);
1477
1478            // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist.
1479            if (node.GetType() << "me"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO);
1480            if (node.GetType() << "me"_mst) CHECK_NONFATAL(!ret.nsat.malleable);
1481
1482            // For 'm' nodes, if a satisfaction exists, it must be non-malleable.
1483            if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.malleable);
1484
1485            // If a non-malleable satisfaction exists, it must be canonical.
1486            if (ret.sat.available != Availability::NO && !ret.sat.malleable) CHECK_NONFATAL(!ret.sat.non_canon);
1487
1488            return ret;
1489        };
1490
1491        return TreeEval<InputResult>(tester);
1492    }
1493
1494public:
1495    /** Update duplicate key information in this Node.
1496     *
1497     * This uses a custom key comparator provided by the context in order to still detect duplicates
1498     * for more complicated types.
1499     */
1500    template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const