Inside Bitcoin

1001    }
1002
1003private:
1004    internal::Ops CalcOps() const {
1005        switch (fragment) {
1006            case Fragment::JUST_1: return {0, 0, {}};
1007            case Fragment::JUST_0: return {0, {}, 0};
1008            case Fragment::PK_K: return {0, 0, 0};
1009            case Fragment::PK_H: return {3, 0, 0};
1010            case Fragment::OLDER:
1011            case Fragment::AFTER: return {1, 0, {}};
1012            case Fragment::SHA256:
1013            case Fragment::RIPEMD160:
1014            case Fragment::HASH256:
1015            case Fragment::HASH160: return {4, 0, {}};
1016            case Fragment::AND_V: return {subs[0].ops.count + subs[1].ops.count, subs[0].ops.sat + subs[1].ops.sat, {}};
1017            case Fragment::AND_B: {
1018                const auto count{1 + subs[0].ops.count + subs[1].ops.count};
1019                const auto sat{subs[0].ops.sat + subs[1].ops.sat};
1020                const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat};
1021                return {count, sat, dsat};
1022            }
1023            case Fragment::OR_B: {
1024                const auto count{1 + subs[0].ops.count + subs[1].ops.count};
1025                const auto sat{(subs[0].ops.sat + subs[1].ops.dsat) | (subs[1].ops.sat + subs[0].ops.dsat)};
1026                const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat};
1027                return {count, sat, dsat};
1028            }
1029            case Fragment::OR_D: {
1030                const auto count{3 + subs[0].ops.count + subs[1].ops.count};
1031                const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)};
1032                const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat};
1033                return {count, sat, dsat};
1034            }
1035            case Fragment::OR_C: {
1036                const auto count{2 + subs[0].ops.count + subs[1].ops.count};
1037                const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)};
1038                return {count, sat, {}};
1039            }
1040            case Fragment::OR_I: {
1041                const auto count{3 + subs[0].ops.count + subs[1].ops.count};
1042                const auto sat{subs[0].ops.sat | subs[1].ops.sat};
1043                const auto dsat{subs[0].ops.dsat | subs[1].ops.dsat};
1044                return {count, sat, dsat};
1045            }
1046            case Fragment::ANDOR: {
1047                const auto count{3 + subs[0].ops.count + subs[1].ops.count + subs[2].ops.count};
1048                const auto sat{(subs[1].ops.sat + subs[0].ops.sat) | (subs[0].ops.dsat + subs[2].ops.sat)};
1049                const auto dsat{subs[0].ops.dsat + subs[2].ops.dsat};
1050                return {count, sat, dsat};
1051            }
1052            case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
1053            case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0};
1054            case Fragment::WRAP_S:
1055            case Fragment::WRAP_C:
1056            case Fragment::WRAP_N: return {1 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat};
1057            case Fragment::WRAP_A: return {2 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat};
1058            case Fragment::WRAP_D: return {3 + subs[0].ops.count, subs[0].ops.sat, 0};
1059            case Fragment::WRAP_J: return {4 + subs[0].ops.count, subs[0].ops.sat, 0};
1060            case Fragment::WRAP_V: return {subs[0].ops.count + (subs[0].GetType() << "x"_mst), subs[0].ops.sat, {}};
1061            case Fragment::THRESH: {
1062                uint32_t count = 0;
1063                auto sats = Vector(internal::MaxInt<uint32_t>(0));
1064                for (const auto& sub : subs) {
1065                    count += sub.ops.count + 1;
1066                    auto next_sats = Vector(sats[0] + sub.ops.dsat);
1067                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ops.dsat) | (sats[j - 1] + sub.ops.sat));
1068                    next_sats.push_back(sats[sats.size() - 1] + sub.ops.sat);
1069                    sats = std::move(next_sats);
1070                }
1071                assert(k < sats.size());
1072                return {count, sats[k], sats[0]};
1073            }
1074        }
1075        assert(false);
1076    }
1077
1078    internal::StackSize CalcStackSize() const {
1079        using namespace internal;
1080        switch (fragment) {
1081            case Fragment::JUST_0: return {{}, SatInfo::Push()};
1082            case Fragment::JUST_1: return {SatInfo::Push(), {}};
1083            case Fragment::OLDER:
1084            case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}};
1085            case Fragment::PK_K: return {SatInfo::Push()};
1086            case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()};
1087            case Fragment::SHA256:
1088            case Fragment::RIPEMD160:
1089            case Fragment::HASH256:
1090            case Fragment::HASH160: return {
1091                SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(),
1092                {}
1093            };
1094            case Fragment::ANDOR: {
1095                const auto& x{subs[0].ss};
1096                const auto& y{subs[1].ss};
1097                const auto& z{subs[2].ss};
1098                return {
1099                    (x.Sat() + SatInfo::If() + y.Sat()) | (x.Dsat() + SatInfo::If() + z.Sat()),
1100                    x.Dsat() + SatInfo::If() + z.Dsat()
1101                };
1102            }
1103            case Fragment::AND_V: {
1104                const auto& x{subs[0].ss};
1105                const auto& y{subs[1].ss};
1106                return {x.Sat() + y.Sat(), {}};
1107            }
1108            case Fragment::AND_B: {
1109                const auto& x{subs[0].ss};
1110                const auto& y{subs[1].ss};
1111                return {x.Sat() + y.Sat() + SatInfo::BinaryOp(), x.Dsat() + y.Dsat() + SatInfo::BinaryOp()};
1112            }
1113            case Fragment::OR_B: {
1114                const auto& x{subs[0].ss};
1115                const auto& y{subs[1].ss};
1116                return {
1117                    ((x.Sat() + y.Dsat()) | (x.Dsat() + y.Sat())) + SatInfo::BinaryOp(),
1118                    x.Dsat() + y.Dsat() + SatInfo::BinaryOp()
1119                };
1120            }
1121            case Fragment::OR_C: {
1122                const auto& x{subs[0].ss};
1123                const auto& y{subs[1].ss};
1124                return {(x.Sat() + SatInfo::If()) | (x.Dsat() + SatInfo::If() + y.Sat()), {}};
1125            }
1126            case Fragment::OR_D: {
1127                const auto& x{subs[0].ss};
1128                const auto& y{subs[1].ss};
1129                return {
1130                    (x.Sat() + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Sat()),
1131                    x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Dsat()
1132                };
1133            }
1134            case Fragment::OR_I: {
1135                const auto& x{subs[0].ss};
1136                const auto& y{subs[1].ss};
1137                return {SatInfo::If() + (x.Sat() | y.Sat()), SatInfo::If() + (x.Dsat() | y.Dsat())};
1138            }
1139            // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k
1140            // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and
1141            // n itself, and ends with 1 stack element (success or failure). Thus, it net removes
1142            // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with.
1143            case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)};
1144            // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the
1145            // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net
1146            // removes n-1 elements (from n to 1) while reaching n more than it ends with.
1147            case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())};
1148            case Fragment::WRAP_A:
1149            case Fragment::WRAP_N:
1150            case Fragment::WRAP_S: return subs[0].ss;
1151            case Fragment::WRAP_C: return {
1152                subs[0].ss.Sat() + SatInfo::OP_CHECKSIG(),
1153                subs[0].ss.Dsat() + SatInfo::OP_CHECKSIG()
1154            };
1155            case Fragment::WRAP_D: return {
1156                SatInfo::OP_DUP() + SatInfo::If() + subs[0].ss.Sat(),
1157                SatInfo::OP_DUP() + SatInfo::If()
1158            };
1159            case Fragment::WRAP_V: return {subs[0].ss.Sat() + SatInfo::OP_VERIFY(), {}};
1160            case Fragment::WRAP_J: return {
1161                SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0].ss.Sat(),
1162                SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If()
1163            };
1164            case Fragment::THRESH: {
1165                // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions.
1166                auto sats = Vector(SatInfo::Empty());
1167                for (size_t i = 0; i < subs.size(); ++i) {
1168                    // Loop over the subexpressions, processing them one by one. After adding
1169                    // element i we need to add OP_ADD (if i>0).
1170                    auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty();
1171                    // Construct a variable that will become the next sats, starting with index 0.
1172                    auto next_sats = Vector(sats[0] + subs[i].ss.Dsat() + add);
1173                    // Then loop to construct next_sats[1..i].
1174                    for (size_t j = 1; j < sats.size(); ++j) {
1175                        next_sats.push_back(((sats[j] + subs[i].ss.Dsat()) | (sats[j - 1] + subs[i].ss.Sat())) + add);
1176                    }
1177                    // Finally construct next_sats[i+1].
1178                    next_sats.push_back(sats[sats.size() - 1] + subs[i].ss.Sat() + add);
1179                    // Switch over.
1180                    sats = std::move(next_sats);
1181                }
1182                // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both
1183                // cases a push of k and an OP_EQUAL follow.
1184                return {
1185                    sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(),
1186                    sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL()
1187                };
1188            }
1189        }
1190        assert(false);
1191    }
1192
1193    internal::WitnessSize CalcWitnessSize() const {
1194        const uint32_t sig_size = IsTapscript(m_script_ctx) ? 1 + 65 : 1 + 72;
1195        const uint32_t pubkey_size = IsTapscript(m_script_ctx) ? 1 + 32 : 1 + 33;
1196        switch (fragment) {
1197            case Fragment::JUST_0: return {{}, 0};
1198            case Fragment::JUST_1:
1199            case Fragment::OLDER:
1200            case Fragment::AFTER: return {0, {}};
1201            case Fragment::PK_K: return {sig_size, 1};
1202            case Fragment::PK_H: return {sig_size + pubkey_size, 1 + pubkey_size};
1203            case Fragment::SHA256:
1204            case Fragment::RIPEMD160:
1205            case Fragment::HASH256:
1206            case Fragment::HASH160: return {1 + 32, {}};
1207            case Fragment::ANDOR: {
1208                const auto sat{(subs[0].ws.sat + subs[1].ws.sat) | (subs[0].ws.dsat + subs[2].ws.sat)};
1209                const auto dsat{subs[0].ws.dsat + subs[2].ws.dsat};
1210                return {sat, dsat};
1211            }
1212            case Fragment::AND_V: return {subs[0].ws.sat + subs[1].ws.sat, {}};
1213            case Fragment::AND_B: return {subs[0].ws.sat + subs[1].ws.sat, subs[0].ws.dsat + subs[1].ws.dsat};
1214            case Fragment::OR_B: {
1215                const auto sat{(subs[0].ws.dsat + subs[1].ws.sat) | (subs[0].ws.sat + subs[1].ws.dsat)};
1216                const auto dsat{subs[0].ws.dsat + subs[1].ws.dsat};
1217                return {sat, dsat};
1218            }
1219            case Fragment::OR_C: return {subs[0].ws.sat | (subs[0].ws.dsat + subs[1].ws.sat), {}};
1220            case Fragment::OR_D: return {subs[0].ws.sat | (subs[0].ws.dsat + subs[1].ws.sat), subs[0].ws.dsat + subs[1].ws.dsat};
1221            case Fragment::OR_I: return {(subs[0].ws.sat + 1 + 1) | (subs[1].ws.sat + 1), (subs[0].ws.dsat + 1 + 1) | (subs[1].ws.dsat + 1)};
1222            case Fragment::MULTI: return {k * sig_size + 1, k + 1};
1223            case Fragment::MULTI_A: return {k * sig_size + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())};
1224            case Fragment::WRAP_A:
1225            case Fragment::WRAP_N:
1226            case Fragment::WRAP_S:
1227            case Fragment::WRAP_C: return subs[0].ws;
1228            case Fragment::WRAP_D: return {1 + 1 + subs[0].ws.sat, 1};
1229            case Fragment::WRAP_V: return {subs[0].ws.sat, {}};
1230            case Fragment::WRAP_J: return {subs[0].ws.sat, 1};
1231            case Fragment::THRESH: {
1232                auto sats = Vector(internal::MaxInt<uint32_t>(0));
1233                for (const auto& sub : subs) {
1234                    auto next_sats = Vector(sats[0] + sub.ws.dsat);
1235                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ws.dsat) | (sats[j - 1] + sub.ws.sat));
1236                    next_sats.push_back(sats[sats.size() - 1] + sub.ws.sat);
1237                    sats = std::move(next_sats);
1238                }
1239                assert(k < sats.size());
1240                return {sats[k], sats[0]};
1241            }
1242        }
1243        assert(false);
1244    }
1245
1246    template<typename Ctx>
1247    internal::InputResult ProduceInput(const Ctx& ctx) const {
1248        using namespace internal;
1249
1250        // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions