Branch data Line data Source code
1 : : // Copyright (c) 2019-present The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <limits>
6 : : #include <vector>
7 : :
8 : : #include <primitives/transaction.h>
9 : : #include <script/miniscript.h>
10 : : #include <script/script.h>
11 : : #include <script/solver.h>
12 : : #include <span.h>
13 : : #include <util/check.h>
14 : : #include <util/vector.h>
15 : :
16 : : namespace miniscript {
17 : : namespace internal {
18 : :
19 : 22474374 : Type SanitizeType(Type e) {
20 [ + + ]: 22474374 : int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
21 [ + + ]: 22474374 : if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
22 [ - + ]: 14476937 : assert(num_types == 1); // K, V, B, W all conflict with each other
23 [ + + - + ]: 14476937 : assert(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
24 [ + + - + ]: 14476937 : assert(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
25 [ + + - + ]: 14476937 : assert(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
26 [ + + - + ]: 14476937 : assert(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
27 [ + + - + ]: 14476937 : assert(!(e << "K"_mst) || (e << "u"_mst)); // K implies u
28 [ + + - + ]: 14476937 : assert(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
29 [ + + - + ]: 14476937 : assert(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
30 [ + + - + ]: 14476937 : assert(!(e << "e"_mst) || (e << "d"_mst)); // e implies d
31 [ + + - + ]: 14476937 : assert(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
32 [ + + - + ]: 14476937 : assert(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
33 [ + + - + ]: 14476937 : assert(!(e << "V"_mst) || (e << "f"_mst)); // V implies f
34 [ + + - + ]: 14476937 : assert(!(e << "K"_mst) || (e << "s"_mst)); // K implies s
35 [ + + - + ]: 14476937 : assert(!(e << "z"_mst) || (e << "m"_mst)); // z implies m
36 : 14476937 : return e;
37 : : }
38 : :
39 : 25311164 : Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
40 : : size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
41 : : // Sanity check on data
42 [ + + ]: 25311164 : if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
43 [ - + ]: 27176 : assert(data_size == 32);
44 [ + + ]: 25283988 : } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
45 [ - + ]: 27428 : assert(data_size == 20);
46 : : } else {
47 [ - + ]: 25256560 : assert(data_size == 0);
48 : : }
49 : : // Sanity check on k
50 [ + + ]: 25311164 : if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
51 [ - + ]: 110449 : assert(k >= 1 && k < 0x80000000UL);
52 [ + + ]: 25200715 : } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
53 [ + - - + ]: 49572 : assert(k >= 1 && k <= n_keys);
54 [ + + ]: 25151143 : } else if (fragment == Fragment::THRESH) {
55 [ + - - + ]: 487052 : assert(k >= 1 && k <= n_subs);
56 : : } else {
57 [ - + ]: 24664091 : assert(k == 0);
58 : : }
59 : : // Sanity check on subs
60 : 25311164 : if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
61 [ + + + + ]: 25311164 : fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
62 [ - + ]: 8631480 : assert(n_subs == 2);
63 [ + + ]: 16679684 : } else if (fragment == Fragment::ANDOR) {
64 [ - + ]: 469103 : assert(n_subs == 3);
65 : 16210581 : } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
66 [ + + ]: 16210581 : fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
67 : : fragment == Fragment::WRAP_N) {
68 [ - + ]: 4968551 : assert(n_subs == 1);
69 [ + + ]: 11242030 : } else if (fragment != Fragment::THRESH) {
70 [ - + ]: 10754978 : assert(n_subs == 0);
71 : : }
72 : : // Sanity check on keys
73 [ + + ]: 24824112 : if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
74 [ - + ]: 162813 : assert(n_keys == 1);
75 [ + + ]: 25148351 : } else if (fragment == Fragment::MULTI) {
76 [ - + ]: 38979 : assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
77 [ - + ]: 38979 : assert(!IsTapscript(ms_ctx));
78 [ + + ]: 25109372 : } else if (fragment == Fragment::MULTI_A) {
79 [ - + ]: 10593 : assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
80 [ - + ]: 10593 : assert(IsTapscript(ms_ctx));
81 : : } else {
82 [ - + ]: 25098779 : assert(n_keys == 0);
83 : : }
84 : :
85 : : // Below is the per-fragment logic for computing the expression types.
86 : : // It heavily relies on Type's << operator (where "X << a_mst" means
87 : : // "X has all properties listed in a").
88 [ + + + + : 25311164 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + - ]
89 : 98016 : case Fragment::PK_K: return "Konudemsxk"_mst;
90 : 64797 : case Fragment::PK_H: return "Knudemsxk"_mst;
91 : 57530 : case Fragment::OLDER: return
92 : 57530 : "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
93 [ + + ]: 57530 : "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
94 [ + + ]: 115060 : "Bzfmxk"_mst;
95 : 52919 : case Fragment::AFTER: return
96 : 52919 : "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
97 [ + + ]: 52919 : "j"_mst.If(k < LOCKTIME_THRESHOLD) |
98 [ + + ]: 105838 : "Bzfmxk"_mst;
99 : 11971 : case Fragment::SHA256: return "Bonudmk"_mst;
100 : 13934 : case Fragment::RIPEMD160: return "Bonudmk"_mst;
101 : 15205 : case Fragment::HASH256: return "Bonudmk"_mst;
102 : 13494 : case Fragment::HASH160: return "Bonudmk"_mst;
103 : 3222438 : case Fragment::JUST_1: return "Bzufmxk"_mst;
104 : 7155102 : case Fragment::JUST_0: return "Bzudemsxk"_mst;
105 : 519904 : case Fragment::WRAP_A: return
106 : 519904 : "W"_mst.If(x << "B"_mst) | // W=B_x
107 [ + + ]: 519904 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
108 : 1039808 : (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
109 [ + + ]: 778827 : "x"_mst; // x
110 : 294072 : case Fragment::WRAP_S: return
111 : 294072 : "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
112 [ + + ]: 294072 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
113 [ + + ]: 345562 : (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
114 : 1526070 : case Fragment::WRAP_C: return
115 : 1526070 : "B"_mst.If(x << "K"_mst) | // B=K_x
116 [ + + ]: 1526070 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
117 : 3052140 : (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
118 [ + + ]: 1648796 : "us"_mst; // u, s
119 : 352298 : case Fragment::WRAP_D: return
120 : 352298 : "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
121 [ + + ]: 352298 : "o"_mst.If(x << "z"_mst) | // o=z_x
122 [ + + ]: 352298 : "e"_mst.If(x << "f"_mst) | // e=f_x
123 [ + + ]: 352298 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
124 : 704596 : (x & "ms"_mst) | // m=m_x, s=s_x
125 : : // NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
126 [ + + + + ]: 682932 : "u"_mst.If(IsTapscript(ms_ctx)) |
127 : 704596 : "ndx"_mst; // n, d, x
128 : 377664 : case Fragment::WRAP_V: return
129 : 377664 : "V"_mst.If(x << "B"_mst) | // V=B_x
130 [ + + ]: 377664 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
131 : 755328 : (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
132 [ + + ]: 631353 : "fx"_mst; // f, x
133 : 453129 : case Fragment::WRAP_J: return
134 : 453129 : "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
135 [ + + ]: 453129 : "e"_mst.If(x << "f"_mst) | // e=f_x
136 [ + + ]: 453129 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
137 : 906258 : (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
138 [ + + ]: 906258 : "ndx"_mst; // n, d, x
139 : 1445414 : case Fragment::WRAP_N: return
140 : 1445414 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
141 : 1445414 : (x & "Bzondfems"_mst) | // B=B_x, z=z_x, o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
142 : 1445414 : "ux"_mst; // u, x
143 : 3332991 : case Fragment::AND_V: return
144 [ + + + + ]: 6865574 : (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
145 [ + + ]: 3332991 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
146 [ + + ]: 3332991 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
147 [ + + ]: 3332991 : (x & y & "dmz"_mst) | // d=d_x*d_y, m=m_x*m_y, z=z_x*z_y
148 [ + + ]: 3332991 : ((x | y) & "s"_mst) | // s=s_x+s_y
149 [ + + ]: 388008 : "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
150 [ + + ]: 3332991 : (y & "ux"_mst) | // u=u_y, x=x_y
151 [ + + ]: 3332991 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
152 [ + + + + ]: 3332991 : "k"_mst.If(((x & y) << "k"_mst) &&
153 [ + + + + : 399270 : !(((x << "g"_mst) && (y << "h"_mst)) ||
+ + + + ]
154 [ + + + + : 200992 : ((x << "h"_mst) && (y << "g"_mst)) ||
+ + ]
155 [ + + + + ]: 199404 : ((x << "i"_mst) && (y << "j"_mst)) ||
156 [ + + + + ]: 3530455 : ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
157 : 402079 : case Fragment::AND_B: return
158 : 402079 : (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
159 [ + + + + ]: 568254 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
160 [ + + ]: 402079 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
161 [ + + + + ]: 423350 : (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
162 [ + + ]: 402079 : (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
163 [ + + + + ]: 388596 : "f"_mst.If(((x & y) << "f"_mst) || (x << "sf"_mst) || (y << "sf"_mst)) | // f=f_x*f_y + f_x*s_x + f_y*s_y
164 : 804158 : ((x | y) & "s"_mst) | // s=s_x+s_y
165 [ + + ]: 402079 : "ux"_mst | // u, x
166 [ + + ]: 402079 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
167 [ + + + + ]: 402079 : "k"_mst.If(((x & y) << "k"_mst) &&
168 [ + + + + : 87966 : !(((x << "g"_mst) && (y << "h"_mst)) ||
+ + + + ]
169 [ + + + + : 44230 : ((x << "h"_mst) && (y << "g"_mst)) ||
+ + ]
170 [ + + + + ]: 43037 : ((x << "i"_mst) && (y << "j"_mst)) ||
171 [ + + + + ]: 444405 : ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
172 : 440136 : case Fragment::OR_B: return
173 [ + + ]: 511887 : "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
174 [ + + + + ]: 626191 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
175 [ + + ]: 45388 : (x & y & "m"_mst).If((x | y) << "s"_mst && (x & y) << "e"_mst) | // m=m_x*m_y*e_x*e_y*(s_x+s_y)
176 : 880272 : (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
177 [ + + ]: 440136 : "dux"_mst | // d, u, x
178 [ + + ]: 440136 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
179 [ + + ]: 880272 : (x & y & "k"_mst); // k=k_x*k_y
180 : 419311 : case Fragment::OR_D: return
181 : 419311 : (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
182 [ + + + + ]: 531774 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
183 [ + + ]: 47126 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
184 : 838622 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
185 : 838622 : (y & "ufde"_mst) | // u=u_y, f=f_y, d=d_y, e=e_y
186 [ + + ]: 419311 : "x"_mst | // x
187 [ + + ]: 419311 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
188 [ + + ]: 838622 : (x & y & "k"_mst); // k=k_x*k_y
189 : 399486 : case Fragment::OR_C: return
190 : 399486 : (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
191 [ + + + + ]: 495066 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
192 [ + + ]: 21781 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
193 : 798972 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
194 [ + + ]: 399486 : "fx"_mst | // f, x
195 [ + + ]: 399486 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
196 [ + + ]: 798972 : (x & y & "k"_mst); // k=k_x*k_y
197 : 3637477 : case Fragment::OR_I: return
198 : 3637477 : (x & y & "VBKufs"_mst) | // V=V_x*V_y, B=B_x*B_y, K=K_x*K_y, u=u_x*u_y, f=f_x*f_y, s=s_x*s_y
199 : 3637477 : "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
200 [ + + ]: 3637477 : ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
201 [ + + ]: 3637477 : (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
202 : 7274954 : ((x | y) & "d"_mst) | // d=d_x+d_y
203 [ + + ]: 3637477 : "x"_mst | // x
204 [ + + ]: 3637477 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
205 [ + + ]: 7274954 : (x & y & "k"_mst); // k=k_x*k_y
206 : 469103 : case Fragment::ANDOR: return
207 [ + + ]: 588109 : (y & z & "BKV"_mst).If(x << "Bdu"_mst) | // B=B_x*d_x*u_x*B_y*B_z, K=B_x*d_x*u_x*K_y*K_z, V=B_x*d_x*u_x*V_y*V_z
208 : 938206 : (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
209 [ + + + + ]: 617473 : ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
210 [ + + ]: 469103 : (y & z & "u"_mst) | // u=u_y*u_z
211 [ + + + + ]: 469103 : (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
212 [ + + ]: 469103 : (z & "d"_mst) | // d=d_z
213 [ + + + + ]: 469103 : (z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_z*(s_x+f_y)
214 [ + + ]: 70840 : (x & y & z & "m"_mst).If(x << "e"_mst && (x | y | z) << "s"_mst) | // m=m_x*m_y*m_z*e_x*(s_x+s_y+s_z)
215 : 938206 : (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
216 [ + + ]: 469103 : "x"_mst | // x
217 [ + + ]: 469103 : ((x | y | z) & "ghij"_mst) | // g=g_x+g_y+g_z, h=h_x+h_y+h_z, i=i_x+i_y+i_z, j=j_x+j_y_j_z
218 [ + + + + ]: 469103 : "k"_mst.If(((x & y & z) << "k"_mst) &&
219 [ + + + + : 160295 : !(((x << "g"_mst) && (y << "h"_mst)) ||
+ + + + ]
220 [ + + + + : 81121 : ((x << "h"_mst) && (y << "g"_mst)) ||
+ + ]
221 [ + + + + ]: 79674 : ((x << "i"_mst) && (y << "j"_mst)) ||
222 [ + + + + ]: 547702 : ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*k_z* !(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
223 : 38979 : case Fragment::MULTI: {
224 : 38979 : return "Bnudemsk"_mst;
225 : : }
226 : 10593 : case Fragment::MULTI_A: {
227 : 10593 : return "Budemsk"_mst;
228 : : }
229 : 487052 : case Fragment::THRESH: {
230 : 487052 : bool all_e = true;
231 : 487052 : bool all_m = true;
232 : 487052 : uint32_t args = 0;
233 : 487052 : uint32_t num_s = 0;
234 : 487052 : Type acc_tl = "k"_mst;
235 [ + + ]: 739366 : for (size_t i = 0; i < sub_types.size(); ++i) {
236 [ + + ]: 650659 : Type t = sub_types[i];
237 : 650659 : static constexpr auto WDU{"Wdu"_mst}, BDU{"Bdu"_mst};
238 [ + + + + ]: 650659 : if (!(t << (i ? WDU : BDU))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
239 [ + + ]: 252314 : if (!(t << "e"_mst)) all_e = false;
240 [ + + ]: 252314 : if (!(t << "m"_mst)) all_m = false;
241 [ + + ]: 252314 : if (t << "s"_mst) num_s += 1;
242 [ + + + + ]: 252314 : args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
243 : 252314 : acc_tl = ((acc_tl | t) & "ghij"_mst) |
244 : : // Thresh contains a combination of timelocks if it has threshold > 1 and
245 : : // it contains two different children that have different types of timelocks
246 : : // Note how if any of the children don't have "k", the parent also does not have "k"
247 [ + + + + ]: 252314 : "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
248 [ + + + + : 186639 : ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
+ + + + ]
249 [ + + + + : 94417 : ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
+ + ]
250 [ + + + + ]: 92901 : ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
251 [ + + + + ]: 257795 : ((acc_tl << "j"_mst) && (t << "i"_mst))))));
252 : : }
253 : 177414 : return "Bdu"_mst |
254 : 88707 : "z"_mst.If(args == 0) | // z=all z
255 [ + + + + ]: 99354 : "o"_mst.If(args == 1) | // o=all z except one o
256 [ + + + + : 88707 : "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
+ + ]
257 [ + + + + ]: 88707 : "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
258 [ + + + + ]: 153190 : "s"_mst.If(num_s >= n_subs - k + 1) | // s= >=(n-k+1) s
259 : 88707 : acc_tl; // timelock info
260 : : }
261 : : }
262 : 0 : assert(false);
263 : : }
264 : :
265 : 22807216 : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs,
266 : : size_t n_keys, MiniscriptContext ms_ctx) {
267 [ + + + + : 22807216 : switch (fragment) {
+ + + + +
+ + + + +
- + ]
268 : : case Fragment::JUST_1:
269 : : case Fragment::JUST_0: return 1;
270 [ + + ]: 112748 : case Fragment::PK_K: return IsTapscript(ms_ctx) ? 33 : 34;
271 : 74213 : case Fragment::PK_H: return 3 + 21;
272 : 120127 : case Fragment::OLDER:
273 [ - + ]: 120127 : case Fragment::AFTER: return 1 + BuildScript(k).size();
274 : 34922 : case Fragment::HASH256:
275 : 34922 : case Fragment::SHA256: return 4 + 2 + 33;
276 : 34734 : case Fragment::HASH160:
277 : 34734 : case Fragment::RIPEMD160: return 4 + 2 + 21;
278 [ - + + - ]: 96038 : case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
279 [ - + ]: 12068 : case Fragment::MULTI_A: return (1 + 32 + 1) * n_keys + BuildScript(k).size() + 1;
280 : 3022373 : case Fragment::AND_V: return subsize;
281 : 408543 : case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
282 : 3430417 : case Fragment::WRAP_S:
283 : 3430417 : case Fragment::WRAP_C:
284 : 3430417 : case Fragment::WRAP_N:
285 : 3430417 : case Fragment::AND_B:
286 : 3430417 : case Fragment::OR_B: return subsize + 1;
287 : 578701 : case Fragment::WRAP_A:
288 : 578701 : case Fragment::OR_C: return subsize + 2;
289 : 3912559 : case Fragment::WRAP_D:
290 : 3912559 : case Fragment::OR_D:
291 : 3912559 : case Fragment::OR_I:
292 : 3912559 : case Fragment::ANDOR: return subsize + 3;
293 : 450936 : case Fragment::WRAP_J: return subsize + 4;
294 [ - + ]: 122951 : case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
295 : : }
296 : 0 : assert(false);
297 : : }
298 : :
299 : 3908050 : InputStack& InputStack::SetAvailable(Availability avail) {
300 : 3908050 : available = avail;
301 [ + + ]: 3908050 : if (avail == Availability::NO) {
302 : 3797078 : stack.clear();
303 : 3797078 : size = std::numeric_limits<size_t>::max();
304 : 3797078 : has_sig = false;
305 : 3797078 : malleable = false;
306 : 3797078 : non_canon = false;
307 : : }
308 : 3908050 : return *this;
309 : : }
310 : :
311 : 176274 : InputStack& InputStack::SetWithSig() {
312 : 176274 : has_sig = true;
313 : 176274 : return *this;
314 : : }
315 : :
316 : 136654 : InputStack& InputStack::SetNonCanon() {
317 : 136654 : non_canon = true;
318 : 136654 : return *this;
319 : : }
320 : :
321 : 69906 : InputStack& InputStack::SetMalleable(bool x) {
322 : 69906 : malleable = x;
323 : 69906 : return *this;
324 : : }
325 : :
326 : 5904274 : InputStack operator+(InputStack a, InputStack b) {
327 [ + - ]: 5904274 : a.stack = Cat(std::move(a.stack), std::move(b.stack));
328 [ + + + + ]: 5904274 : if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size;
329 : 5904274 : a.has_sig |= b.has_sig;
330 : 5904274 : a.malleable |= b.malleable;
331 : 5904274 : a.non_canon |= b.non_canon;
332 [ + + + + ]: 5904274 : if (a.available == Availability::NO || b.available == Availability::NO) {
333 : 3704444 : a.SetAvailable(Availability::NO);
334 [ + - - + ]: 2199830 : } else if (a.available == Availability::MAYBE || b.available == Availability::MAYBE) {
335 : 0 : a.SetAvailable(Availability::MAYBE);
336 : : }
337 : 5904274 : return a;
338 : : }
339 : :
340 : 2981878 : InputStack operator|(InputStack a, InputStack b) {
341 : : // If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one.
342 [ + + ]: 2981878 : if (a.available == Availability::NO) return b;
343 [ + + ]: 1229896 : if (b.available == Availability::NO) return a;
344 : : // If only one of the solutions has a signature, we must pick the other one.
345 [ + + + + ]: 862890 : if (!a.has_sig && b.has_sig) return a;
346 [ + + + + ]: 856044 : if (!b.has_sig && a.has_sig) return b;
347 [ + + + - ]: 846632 : if (!a.has_sig && !b.has_sig) {
348 : : // If neither solution requires a signature, the result is inevitably malleable.
349 : 68294 : a.malleable = true;
350 : 68294 : b.malleable = true;
351 : : } else {
352 : : // If both options require a signature, prefer the non-malleable one.
353 [ + + + + ]: 778338 : if (b.malleable && !a.malleable) return a;
354 [ + + + + ]: 776062 : if (a.malleable && !b.malleable) return b;
355 : : }
356 : : // Between two malleable or two non-malleable solutions, pick the smaller one between
357 : : // YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE.
358 [ + - + - ]: 843084 : if (a.available == Availability::YES && b.available == Availability::YES) {
359 [ + + ]: 873392 : return std::move(a.size <= b.size ? a : b);
360 [ # # # # ]: 0 : } else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) {
361 [ # # ]: 0 : return std::move(a.size >= b.size ? a : b);
362 [ # # ]: 0 : } else if (a.available == Availability::YES) {
363 : 0 : return a;
364 : : } else {
365 : 0 : return b;
366 : : }
367 : : }
368 : :
369 : 27250 : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
370 : : {
371 : 27250 : std::vector<Opcode> out;
372 [ + + ]: 54500 : CScript::const_iterator it = script.begin(), itend = script.end();
373 [ + + ]: 11275725 : while (it != itend) {
374 : 11249512 : std::vector<unsigned char> push_data;
375 : 11249512 : opcodetype opcode;
376 [ + - + + ]: 11249512 : if (!script.GetOp(it, opcode, push_data)) {
377 : 961 : return {};
378 [ + + ]: 11248551 : } else if (opcode >= OP_1 && opcode <= OP_16) {
379 : : // Deal with OP_n (GetOp does not turn them into pushes).
380 [ + - ]: 250979 : push_data.assign(1, CScript::DecodeOP_N(opcode));
381 [ + + ]: 10997572 : } else if (opcode == OP_CHECKSIGVERIFY) {
382 : : // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
383 [ + - ]: 19726 : out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
384 : 19726 : opcode = OP_VERIFY;
385 [ + + ]: 10977846 : } else if (opcode == OP_CHECKMULTISIGVERIFY) {
386 : : // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
387 [ + - ]: 6876 : out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
388 : 6876 : opcode = OP_VERIFY;
389 [ + + ]: 10970970 : } else if (opcode == OP_EQUALVERIFY) {
390 : : // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
391 [ + - ]: 71298 : out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
392 : 71298 : opcode = OP_VERIFY;
393 [ + + ]: 10899672 : } else if (opcode == OP_NUMEQUALVERIFY) {
394 : : // Decompose OP_NUMEQUALVERIFY into OP_NUMEQUAL OP_VERIFY
395 [ + - ]: 2896 : out.emplace_back(OP_NUMEQUAL, std::vector<unsigned char>());
396 : 2896 : opcode = OP_VERIFY;
397 [ + + ]: 10896776 : } else if (IsPushdataOp(opcode)) {
398 [ + - + + ]: 234905 : if (!CheckMinimalPush(push_data, opcode)) return {};
399 [ + + + + : 10661871 : } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL || opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
+ + ]
400 : : // Rule out non minimal VERIFY sequences
401 : 6 : return {};
402 : : }
403 [ + - ]: 11248475 : out.emplace_back(opcode, std::move(push_data));
404 : 11249512 : }
405 : 26213 : std::reverse(out.begin(), out.end());
406 : 26213 : return out;
407 : 27250 : }
408 : :
409 : 137255 : std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
410 [ + + ]: 137255 : if (in.first == OP_0) {
411 : 70 : return 0;
412 : : }
413 [ + + ]: 137185 : if (!in.second.empty()) {
414 [ + + - + ]: 137022 : if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
415 : 137022 : try {
416 [ + + ]: 137022 : return CScriptNum(in.second, true).GetInt64();
417 [ - + ]: 667 : } catch(const scriptnum_error&) {}
418 : : }
419 : 830 : return {};
420 : : }
421 : :
422 : 419822 : int FindNextChar(Span<const char> sp, const char m)
423 : : {
424 [ + + ]: 11293595 : for (int i = 0; i < (int)sp.size(); ++i) {
425 [ + + ]: 11293269 : if (sp[i] == m) return i;
426 : : // We only search within the current parentheses
427 [ + + ]: 10893622 : if (sp[i] == ')') break;
428 : : }
429 : : return -1;
430 : : }
431 : :
432 : : } // namespace internal
433 : : } // namespace miniscript
|
