Branch data Line data Source code
1 : : // Copyright (c) 2019-2022 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 <string>
6 : : #include <vector>
7 : : #include <script/script.h>
8 : : #include <script/miniscript.h>
9 : : #include <serialize.h>
10 : :
11 : : #include <assert.h>
12 : :
13 : : namespace miniscript {
14 : : namespace internal {
15 : :
16 : 23065200 : Type SanitizeType(Type e) {
17 : 23065200 : int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
18 [ + + ]: 23065200 : if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
19 [ + - ]: 13635408 : assert(num_types == 1); // K, V, B, W all conflict with each other
20 [ + + + - ]: 13635408 : assert(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
21 [ + + + - ]: 13635408 : assert(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
22 [ + + + - ]: 13635408 : assert(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
23 [ + + + - ]: 13635408 : assert(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
24 [ + + + - ]: 13635408 : assert(!(e << "K"_mst) || (e << "u"_mst)); // K implies u
25 [ + + + - ]: 13635408 : assert(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
26 [ + + + - ]: 13635408 : assert(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
27 [ + + + - ]: 13635408 : assert(!(e << "e"_mst) || (e << "d"_mst)); // e implies d
28 [ + + + - ]: 13635408 : assert(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
29 [ + + + - ]: 13635408 : assert(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
30 [ + + + - ]: 13635408 : assert(!(e << "V"_mst) || (e << "f"_mst)); // V implies f
31 [ + + + - ]: 13635408 : assert(!(e << "K"_mst) || (e << "s"_mst)); // K implies s
32 [ + + + - ]: 13635408 : assert(!(e << "z"_mst) || (e << "m"_mst)); // z implies m
33 : 13635408 : return e;
34 : 23065200 : }
35 : :
36 : 23122596 : Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
37 : : size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
38 : : // Sanity check on data
39 [ + + + + ]: 23122596 : if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
40 [ + - ]: 89681 : assert(data_size == 32);
41 [ + + + + ]: 23122596 : } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
42 [ + - ]: 29415 : assert(data_size == 20);
43 : 29415 : } else {
44 [ + - ]: 23003500 : assert(data_size == 0);
45 : : }
46 : : // Sanity check on k
47 [ + + + + ]: 23122596 : if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
48 [ + + + - ]: 189069 : assert(k >= 1 && k < 0x80000000UL);
49 [ + + + + ]: 23122596 : } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
50 [ - + + - ]: 53091 : assert(k >= 1 && k <= n_keys);
51 [ + + ]: 22933527 : } else if (fragment == Fragment::THRESH) {
52 [ - + + - ]: 114361 : assert(k >= 1 && k <= n_subs);
53 : 114361 : } else {
54 [ + - ]: 22766075 : assert(k == 0);
55 : : }
56 : : // Sanity check on subs
57 [ + + + + : 40017493 : if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
+ + + + ]
58 [ + + + + ]: 20235962 : fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
59 [ + - ]: 6303848 : assert(n_subs == 2);
60 [ + + ]: 23122596 : } else if (fragment == Fragment::ANDOR) {
61 [ + - ]: 114222 : assert(n_subs == 3);
62 [ + + + + : 28692779 : } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
+ + + + ]
63 [ + + + + : 12664271 : fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
+ + ]
64 : 11874031 : fragment == Fragment::WRAP_N) {
65 [ + - ]: 6357699 : assert(n_subs == 1);
66 [ + + ]: 16704526 : } else if (fragment != Fragment::THRESH) {
67 [ + - ]: 10232466 : assert(n_subs == 0);
68 : 10232466 : }
69 : : // Sanity check on keys
70 [ + + + + ]: 23122596 : if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
71 [ + - ]: 194947 : assert(n_keys == 1);
72 [ + + ]: 23122596 : } else if (fragment == Fragment::MULTI) {
73 [ - + + - ]: 42425 : assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
74 [ + - ]: 42425 : assert(!IsTapscript(ms_ctx));
75 [ + + ]: 22927649 : } else if (fragment == Fragment::MULTI_A) {
76 [ - + + - ]: 10666 : assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
77 [ + - ]: 10666 : assert(IsTapscript(ms_ctx));
78 : 10666 : } else {
79 [ + - ]: 22874558 : assert(n_keys == 0);
80 : : }
81 : :
82 : : // Below is the per-fragment logic for computing the expression types.
83 : : // It heavily relies on Type's << operator (where "X << a_mst" means
84 : : // "X has all properties listed in a").
85 [ - + + + : 23122596 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
86 : 68358 : case Fragment::PK_K: return "Konudemsxk"_mst;
87 : 69193 : case Fragment::PK_H: return "Knudemsxk"_mst;
88 : 65391 : case Fragment::OLDER: return
89 : 130782 : "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
90 : 130782 : "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
91 : 65391 : "Bzfmxk"_mst;
92 : 66282 : case Fragment::AFTER: return
93 : 132564 : "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
94 : 132564 : "j"_mst.If(k < LOCKTIME_THRESHOLD) |
95 : 66282 : "Bzfmxk"_mst;
96 : 14552 : case Fragment::SHA256: return "Bonudmk"_mst;
97 : 14381 : case Fragment::RIPEMD160: return "Bonudmk"_mst;
98 : 17733 : case Fragment::HASH256: return "Bonudmk"_mst;
99 : 15034 : case Fragment::HASH160: return "Bonudmk"_mst;
100 : 2929798 : case Fragment::JUST_1: return "Bzufmxk"_mst;
101 : 6918653 : case Fragment::JUST_0: return "Bzudemsxk"_mst;
102 : 547183 : case Fragment::WRAP_A: return
103 : 1094366 : "W"_mst.If(x << "B"_mst) | // W=B_x
104 : 1094366 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
105 : 1094366 : (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
106 : 547183 : "x"_mst; // x
107 : 282099 : case Fragment::WRAP_S: return
108 : 564198 : "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
109 : 564198 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
110 : 282099 : (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
111 : 3210973 : case Fragment::WRAP_C: return
112 : 6421946 : "B"_mst.If(x << "K"_mst) | // B=K_x
113 : 6421946 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
114 : 6421946 : (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
115 : 3210973 : "us"_mst; // u, s
116 : 247463 : case Fragment::WRAP_D: return
117 : 494926 : "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
118 : 494926 : "o"_mst.If(x << "z"_mst) | // o=z_x
119 : 494926 : "e"_mst.If(x << "f"_mst) | // e=f_x
120 : 494926 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
121 : 494926 : (x & "ms"_mst) | // m=m_x, s=s_x
122 : : // NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
123 : 494926 : "u"_mst.If(IsTapscript(ms_ctx)) |
124 : 247463 : "ndx"_mst; // n, d, x
125 : 352395 : case Fragment::WRAP_V: return
126 : 704790 : "V"_mst.If(x << "B"_mst) | // V=B_x
127 : 704790 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
128 : 704790 : (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
129 : 352395 : "fx"_mst; // f, x
130 : 190382 : case Fragment::WRAP_J: return
131 : 380764 : "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
132 : 380764 : "e"_mst.If(x << "f"_mst) | // e=f_x
133 : 380764 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
134 : 380764 : (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
135 : 190382 : "ndx"_mst; // n, d, x
136 : 1527204 : case Fragment::WRAP_N: return
137 : 3054408 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
138 : 3054408 : (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
139 : 1527204 : "ux"_mst; // u, x
140 : 2677711 : case Fragment::AND_V: return
141 : 5412866 : (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
142 : 8119299 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
143 : 5412866 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
144 : 5412866 : (x & y & "dmz"_mst) | // d=d_x*d_y, m=m_x*m_y, z=z_x*z_y
145 : 2758355 : ((x | y) & "s"_mst) | // s=s_x+s_y
146 [ + + ]: 2706433 : "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
147 : 5412866 : (y & "ux"_mst) | // u=u_y, x=x_y
148 : 2897550 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
149 [ + + ]: 2897550 : "k"_mst.If(((x & y) << "k"_mst) &&
150 [ + + + + ]: 433850 : !(((x << "g"_mst) && (y << "h"_mst)) ||
151 [ + + ]: 214011 : ((x << "h"_mst) && (y << "g"_mst)) ||
152 [ + + ]: 378877 : ((x << "i"_mst) && (y << "j"_mst)) ||
153 [ + + ]: 186340 : ((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)
154 : 72439 : case Fragment::AND_B: return
155 : 164662 : (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
156 : 164662 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
157 : 246993 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
158 : 164662 : (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
159 : 138554 : (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
160 [ + + + + ]: 82331 : "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
161 : 164662 : ((x | y) & "s"_mst) | // s=s_x+s_y
162 : 164662 : "ux"_mst | // u, x
163 : 136556 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
164 [ + + ]: 136556 : "k"_mst.If(((x & y) << "k"_mst) &&
165 [ + + + + ]: 126802 : !(((x << "g"_mst) && (y << "h"_mst)) ||
166 [ + + ]: 62685 : ((x << "h"_mst) && (y << "g"_mst)) ||
167 [ + + ]: 103580 : ((x << "i"_mst) && (y << "j"_mst)) ||
168 [ + + ]: 50003 : ((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)
169 : 79088 : case Fragment::OR_B: return
170 [ + + ]: 79088 : "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
171 : 128419 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
172 [ + + ]: 79088 : (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)
173 : 158176 : (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
174 : 158176 : "dux"_mst | // d, u, x
175 : 158176 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
176 : 79088 : (x & y & "k"_mst); // k=k_x*k_y
177 : 76149 : case Fragment::OR_D: return
178 : 152298 : (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
179 : 136638 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
180 [ + + ]: 76149 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
181 : 152298 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
182 : 152298 : (y & "ufde"_mst) | // u=u_y, f=f_y, d=d_y, e=e_y
183 : 152298 : "x"_mst | // x
184 : 152298 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
185 : 76149 : (x & y & "k"_mst); // k=k_x*k_y
186 : 39060 : case Fragment::OR_C: return
187 : 78120 : (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
188 : 66260 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
189 [ + + ]: 39060 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
190 : 78120 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
191 : 78120 : "fx"_mst | // f, x
192 : 78120 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
193 : 39060 : (x & y & "k"_mst); // k=k_x*k_y
194 : 3302005 : case Fragment::OR_I: return
195 : 6604010 : (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
196 : 6604010 : "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
197 : 6604010 : ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
198 : 6604010 : (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
199 : 6604010 : ((x | y) & "d"_mst) | // d=d_x+d_y
200 : 6604010 : "x"_mst | // x
201 : 6604010 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
202 : 3302005 : (x & y & "k"_mst); // k=k_x*k_y
203 : 114222 : case Fragment::ANDOR: return
204 : 241180 : (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
205 : 241180 : (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
206 : 241180 : ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
207 : 162315 : (y & z & "u"_mst) | // u=u_y*u_z
208 [ + + ]: 120590 : (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
209 : 162315 : (z & "d"_mst) | // d=d_z
210 [ + + ]: 201817 : (z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_z*(s_x+f_y)
211 [ + + ]: 120590 : (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)
212 : 241180 : (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
213 : 241180 : "x"_mst | // x
214 : 213217 : ((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
215 [ + + ]: 213217 : "k"_mst.If(((x & y & z) << "k"_mst) &&
216 [ + + + + ]: 200848 : !(((x << "g"_mst) && (y << "h"_mst)) ||
217 [ + + ]: 101853 : ((x << "h"_mst) && (y << "g"_mst)) ||
218 [ + + ]: 182044 : ((x << "i"_mst) && (y << "j"_mst)) ||
219 [ + + ]: 88859 : ((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)
220 : : case Fragment::MULTI: {
221 : 42425 : return "Bnudemsk"_mst;
222 : : }
223 : : case Fragment::MULTI_A: {
224 : 10666 : return "Budemsk"_mst;
225 : : }
226 : : case Fragment::THRESH: {
227 : 126775 : bool all_e = true;
228 : 126775 : bool all_m = true;
229 : 126775 : uint32_t args = 0;
230 : 126775 : uint32_t num_s = 0;
231 : 126775 : Type acc_tl = "k"_mst;
232 [ + + + + ]: 359588 : for (size_t i = 0; i < sub_types.size(); ++i) {
233 : 245227 : Type t = sub_types[i];
234 : : static constexpr auto WDU{"Wdu"_mst}, BDU{"Bdu"_mst};
235 [ + + + + ]: 245227 : if (!(t << (i ? WDU : BDU))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
236 [ + + ]: 219400 : if (!(t << "e"_mst)) all_e = false;
237 [ + + ]: 219400 : if (!(t << "m"_mst)) all_m = false;
238 [ + + ]: 219400 : if (t << "s"_mst) num_s += 1;
239 [ + + ]: 219400 : args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
240 : 425883 : acc_tl = ((acc_tl | t) & "ghij"_mst) |
241 : : // Thresh contains a combination of timelocks if it has threshold > 1 and
242 : : // it contains two different children that have different types of timelocks
243 : : // Note how if any of the children don't have "k", the parent also does not have "k"
244 [ + + + + ]: 528700 : "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
245 [ - + + + : 228066 : ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
+ + ]
246 [ + + ]: 111829 : ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
247 [ + + ]: 202671 : ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
248 [ + + ]: 98645 : ((acc_tl << "j"_mst) && (t << "i"_mst))))));
249 [ + + ]: 232813 : }
250 : 265602 : return "Bdu"_mst |
251 : 177068 : "z"_mst.If(args == 0) | // z=all z
252 : 154266 : "o"_mst.If(args == 1) | // o=all z except one o
253 [ + + ]: 154266 : "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
254 [ + + + + ]: 88534 : "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
255 : 177068 : "s"_mst.If(num_s >= n_subs - k + 1) | // s= >=(n-k+1) s
256 : 88534 : acc_tl; // timelock info
257 : 114361 : }
258 : : }
259 : 0 : assert(false);
260 : 23065200 : }
261 : :
262 : 23488022 : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs,
263 : : size_t n_keys, MiniscriptContext ms_ctx) {
264 [ - + + + : 23488022 : switch (fragment) {
+ + + + +
+ + + + +
+ + ]
265 : : case Fragment::JUST_1:
266 : 9935808 : case Fragment::JUST_0: return 1;
267 : 85234 : case Fragment::PK_K: return IsTapscript(ms_ctx) ? 33 : 34;
268 : 76937 : case Fragment::PK_H: return 3 + 21;
269 : : case Fragment::OLDER:
270 [ + - ]: 143235 : case Fragment::AFTER: return 1 + BuildScript(k).size();
271 : : case Fragment::HASH256:
272 : 42363 : case Fragment::SHA256: return 4 + 2 + 33;
273 : : case Fragment::HASH160:
274 : 37792 : case Fragment::RIPEMD160: return 4 + 2 + 21;
275 [ + - + - : 54734 : case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
+ - ]
276 [ + - ]: 12552 : case Fragment::MULTI_A: return (1 + 32 + 1) * n_keys + BuildScript(k).size() + 1;
277 : 2724872 : case Fragment::AND_V: return subsize;
278 : 400054 : case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
279 : : case Fragment::WRAP_S:
280 : : case Fragment::WRAP_C:
281 : : case Fragment::WRAP_N:
282 : : case Fragment::AND_B:
283 : 5225856 : case Fragment::OR_B: return subsize + 1;
284 : : case Fragment::WRAP_A:
285 : 625426 : case Fragment::OR_C: return subsize + 2;
286 : : case Fragment::WRAP_D:
287 : : case Fragment::OR_D:
288 : : case Fragment::OR_I:
289 : 3799667 : case Fragment::ANDOR: return subsize + 3;
290 : 195328 : case Fragment::WRAP_J: return subsize + 4;
291 [ + - ]: 128164 : case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
292 : : }
293 : 0 : assert(false);
294 : 23488022 : }
295 : :
296 : 3288476 : InputStack& InputStack::SetAvailable(Availability avail) {
297 : 3288476 : available = avail;
298 [ + + ]: 3288476 : if (avail == Availability::NO) {
299 : 3166972 : stack.clear();
300 : 3166972 : size = std::numeric_limits<size_t>::max();
301 : 3166972 : has_sig = false;
302 : 3166972 : malleable = false;
303 : 3166972 : non_canon = false;
304 : 3166972 : }
305 : 3288476 : return *this;
306 : : }
307 : :
308 : 185962 : InputStack& InputStack::SetWithSig() {
309 : 185962 : has_sig = true;
310 : 185962 : return *this;
311 : : }
312 : :
313 : 163914 : InputStack& InputStack::SetNonCanon() {
314 : 163914 : non_canon = true;
315 : 163914 : return *this;
316 : : }
317 : :
318 : 84456 : InputStack& InputStack::SetMalleable(bool x) {
319 : 84456 : malleable = x;
320 : 84456 : return *this;
321 : : }
322 : :
323 : 4887210 : InputStack operator+(InputStack a, InputStack b) {
324 [ + - ]: 4887210 : a.stack = Cat(std::move(a.stack), std::move(b.stack));
325 [ + + + + ]: 4887210 : if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size;
326 : 4887210 : a.has_sig |= b.has_sig;
327 : 4887210 : a.malleable |= b.malleable;
328 : 4887210 : a.non_canon |= b.non_canon;
329 [ + + + + ]: 4887210 : if (a.available == Availability::NO || b.available == Availability::NO) {
330 : 3070922 : a.SetAvailable(Availability::NO);
331 [ + - - + ]: 4887210 : } else if (a.available == Availability::MAYBE || b.available == Availability::MAYBE) {
332 : 0 : a.SetAvailable(Availability::MAYBE);
333 : 0 : }
334 : 4887210 : return a;
335 : 0 : }
336 : :
337 : 2509812 : InputStack operator|(InputStack a, InputStack b) {
338 : : // If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one.
339 [ + + ]: 2509812 : if (a.available == Availability::NO) return b;
340 [ + + ]: 1021552 : if (b.available == Availability::NO) return a;
341 : : // If only one of the solutions has a signature, we must pick the other one.
342 [ + + + + ]: 717186 : if (!a.has_sig && b.has_sig) return a;
343 [ + + + + ]: 708816 : if (!b.has_sig && a.has_sig) return b;
344 [ + + - + ]: 698858 : if (!a.has_sig && !b.has_sig) {
345 : : // If neither solution requires a signature, the result is inevitably malleable.
346 : 73068 : a.malleable = true;
347 : 73068 : b.malleable = true;
348 : 73068 : } else {
349 : : // If both options require a signature, prefer the non-malleable one.
350 [ + + + + ]: 625790 : if (b.malleable && !a.malleable) return a;
351 [ + + + + ]: 623136 : if (a.malleable && !b.malleable) return b;
352 : : }
353 : : // Between two malleable or two non-malleable solutions, pick the smaller one between
354 : : // YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE.
355 [ + - - + ]: 694384 : if (a.available == Availability::YES && b.available == Availability::YES) {
356 [ + + ]: 694384 : return std::move(a.size <= b.size ? a : b);
357 [ # # # # ]: 0 : } else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) {
358 [ # # ]: 0 : return std::move(a.size >= b.size ? a : b);
359 [ # # ]: 0 : } else if (a.available == Availability::YES) {
360 : 0 : return a;
361 : : } else {
362 : 0 : return b;
363 : : }
364 : 2509812 : }
365 : :
366 : 13512 : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
367 : : {
368 : 13512 : std::vector<Opcode> out;
369 [ + - + - ]: 13512 : CScript::const_iterator it = script.begin(), itend = script.end();
370 [ + - + + ]: 10303181 : while (it != itend) {
371 : 10291578 : std::vector<unsigned char> push_data;
372 : 10291578 : opcodetype opcode;
373 [ + - + + ]: 10291578 : if (!script.GetOp(it, opcode, push_data)) {
374 : 1799 : return {};
375 [ + + + + ]: 10289779 : } else if (opcode >= OP_1 && opcode <= OP_16) {
376 : : // Deal with OP_n (GetOp does not turn them into pushes).
377 [ + - + - ]: 220371 : push_data.assign(1, CScript::DecodeOP_N(opcode));
378 [ + + ]: 10289779 : } else if (opcode == OP_CHECKSIGVERIFY) {
379 : : // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
380 [ + - ]: 19715 : out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
381 : 19715 : opcode = OP_VERIFY;
382 [ + + ]: 10069408 : } else if (opcode == OP_CHECKMULTISIGVERIFY) {
383 : : // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
384 [ + - ]: 9015 : out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
385 : 9015 : opcode = OP_VERIFY;
386 [ + + ]: 10049693 : } else if (opcode == OP_EQUALVERIFY) {
387 : : // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
388 [ + - ]: 70006 : out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
389 : 70006 : opcode = OP_VERIFY;
390 [ + + ]: 10040678 : } else if (opcode == OP_NUMEQUALVERIFY) {
391 : : // Decompose OP_NUMEQUALVERIFY into OP_NUMEQUAL OP_VERIFY
392 [ + - ]: 3015 : out.emplace_back(OP_NUMEQUAL, std::vector<unsigned char>());
393 : 3015 : opcode = OP_VERIFY;
394 [ + - + + ]: 9970672 : } else if (IsPushdataOp(opcode)) {
395 [ + - + + ]: 209673 : if (!CheckMinimalPush(push_data, opcode)) return {};
396 [ + - + + : 9967551 : } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL || opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
+ + + + +
+ + + + -
+ + ]
397 : : // Rule out non minimal VERIFY sequences
398 : 4 : return {};
399 : : }
400 [ + - ]: 10289669 : out.emplace_back(opcode, std::move(push_data));
401 [ + + ]: 10291578 : }
402 [ + - ]: 11603 : std::reverse(out.begin(), out.end());
403 : 11603 : return out;
404 : 13512 : }
405 : :
406 : 132008 : std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
407 [ + + ]: 132008 : if (in.first == OP_0) {
408 : 71 : return 0;
409 : : }
410 [ + + ]: 131937 : if (!in.second.empty()) {
411 [ + + + - ]: 131768 : if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
412 : : try {
413 [ + + + - ]: 131768 : return CScriptNum(in.second, true).GetInt64();
414 [ + - ]: 583 : } catch(const scriptnum_error&) {}
415 : 583 : }
416 : 752 : return {};
417 : 132591 : }
418 : :
419 : 489145 : int FindNextChar(Span<const char> sp, const char m)
420 : : {
421 [ + + - + : 10600500 : for (int i = 0; i < (int)sp.size(); ++i) {
+ ]
422 [ + + ]: 10111355 : if (sp[i] == m) return i;
423 : : // We only search within the current parentheses
424 [ + + ]: 9647199 : if (sp[i] == ')') break;
425 : 9622436 : }
426 : 24989 : return -1;
427 : 489145 : }
428 : :
429 : : } // namespace internal
430 : : } // namespace miniscript
|
