1// Copyright (c) 2009-2010 Satoshi Nakamoto
2// Copyright (c) 2009-present The Bitcoin Core developers
3// Distributed under the MIT software license, see the accompanying
4// file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6#include <script/interpreter.h>
7
8#include <crypto/ripemd160.h>
9#include <crypto/sha1.h>
10#include <crypto/sha256.h>
11#include <prevector.h>
12#include <pubkey.h>
13#include <script/script.h>
14#include <serialize.h>
15#include <span.h>
16#include <tinyformat.h>
17#include <uint256.h>
18
19#include <algorithm>
20#include <cassert>
21#include <compare>
22#include <cstring>
23#include <limits>
24#include <stdexcept>
25
26typedef std::vector<unsigned char> valtype;
27
28namespace {
29
30inline bool set_success(ScriptError* ret)
31{
32    if (ret)
33        *ret = SCRIPT_ERR_OK;
34    return true;
35}
36
37inline bool set_error(ScriptError* ret, const ScriptError serror)
38{
39    if (ret)
40        *ret = serror;
41    return false;
42}
43
44} // namespace
45
46bool CastToBool(const valtype& vch)
47{
48    for (unsigned int i = 0; i < vch.size(); i++)
49    {
50        if (vch[i] != 0)
51        {
52            // Can be negative zero
53            if (i == vch.size()-1 && vch[i] == 0x80)
54                return false;
55            return true;
56        }
57    }
58    return false;
59}
60
61/**
62 * Script is a stack machine (like Forth) that evaluates a predicate
63 * returning a bool indicating valid or not.  There are no loops.
64 */
65#define stacktop(i) (stack.at(size_t(int64_t(stack.size()) + int64_t{i})))
66#define altstacktop(i) (altstack.at(size_t(int64_t(altstack.size()) + int64_t{i})))
67static inline void popstack(std::vector<valtype>& stack)
68{
69    if (stack.empty())
70        throw std::runtime_error("popstack(): stack empty");
71    stack.pop_back();
72}
73
74bool static IsCompressedOrUncompressedPubKey(const valtype &vchPubKey) {
75    if (vchPubKey.size() < CPubKey::COMPRESSED_SIZE) {
76        //  Non-canonical public key: too short
77        return false;
78    }
79    if (vchPubKey[0] == 0x04) {
80        if (vchPubKey.size() != CPubKey::SIZE) {
81            //  Non-canonical public key: invalid length for uncompressed key
82            return false;
83        }
84    } else if (vchPubKey[0] == 0x02 || vchPubKey[0] == 0x03) {
85        if (vchPubKey.size() != CPubKey::COMPRESSED_SIZE) {
86            //  Non-canonical public key: invalid length for compressed key
87            return false;
88        }
89    } else {
90        //  Non-canonical public key: neither compressed nor uncompressed
91        return false;
92    }
93    return true;
94}
95
96bool static IsCompressedPubKey(const valtype &vchPubKey) {
97    if (vchPubKey.size() != CPubKey::COMPRESSED_SIZE) {
98        //  Non-canonical public key: invalid length for compressed key
99        return false;
100    }
101    if (vchPubKey[0] != 0x02 && vchPubKey[0] != 0x03) {
102        //  Non-canonical public key: invalid prefix for compressed key
103        return false;
104    }
105    return true;
106}
107
108/**
109 * A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
110 * Where R and S are not negative (their first byte has its highest bit not set), and not
111 * excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
112 * in which case a single 0 byte is necessary and even required).
113 *
114 * See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
115 *
116 * This function is consensus-critical since BIP66.
117 */
118bool static IsValidSignatureEncoding(const std::vector<unsigned char> &sig) {
119    // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
120    // * total-length: 1-byte length descriptor of everything that follows,
121    //   excluding the sighash byte.
122    // * R-length: 1-byte length descriptor of the R value that follows.
123    // * R: arbitrary-length big-endian encoded R value. It must use the shortest
124    //   possible encoding for a positive integer (which means no null bytes at
125    //   the start, except a single one when the next byte has its highest bit set).
126    // * S-length: 1-byte length descriptor of the S value that follows.
127    // * S: arbitrary-length big-endian encoded S value. The same rules apply.
128    // * sighash: 1-byte value indicating what data is hashed (not part of the DER
129    //   signature)
130
131    // Minimum and maximum size constraints.
132    if (sig.size() < 9) return false;
133    if (sig.size() > 73) return false;
134
135    // A signature is of type 0x30 (compound).
136    if (sig[0] != 0x30) return false;
137
138    // Make sure the length covers the entire signature.
139    if (sig[1] != sig.size() - 3) return false;
140
141    // Extract the length of the R element.
142    unsigned int lenR = sig[3];
143
144    // Make sure the length of the S element is still inside the signature.
145    if (5 + lenR >= sig.size()) return false;
146
147    // Extract the length of the S element.
148    unsigned int lenS = sig[5 + lenR];
149
150    // Verify that the length of the signature matches the sum of the length
151    // of the elements.
152    if ((size_t)(lenR + lenS + 7) != sig.size()) return false;
153
154    // Check whether the R element is an integer.
155    if (sig[2] != 0x02) return false;
156
157    // Zero-length integers are not allowed for R.
158    if (lenR == 0) return false;
159
160    // Negative numbers are not allowed for R.
161    if (sig[4] & 0x80) return false;
162
163    // Null bytes at the start of R are not allowed, unless R would
164    // otherwise be interpreted as a negative number.
165    if (lenR > 1 && (sig[4] == 0x00) && !(sig[5] & 0x80)) return false;
166
167    // Check whether the S element is an integer.
168    if (sig[lenR + 4] != 0x02) return false;
169
170    // Zero-length integers are not allowed for S.
171    if (lenS == 0) return false;
172
173    // Negative numbers are not allowed for S.
174    if (sig[lenR + 6] & 0x80) return false;
175
176    // Null bytes at the start of S are not allowed, unless S would otherwise be
177    // interpreted as a negative number.
178    if (lenS > 1 && (sig[lenR + 6] == 0x00) && !(sig[lenR + 7] & 0x80)) return false;
179
180    return true;
181}
182
183bool static IsLowDERSignature(const valtype &vchSig, ScriptError* serror) {
184    if (!IsValidSignatureEncoding(vchSig)) {
185        return set_error(serror, SCRIPT_ERR_SIG_DER);
186    }
187    // https://bitcoin.stackexchange.com/a/12556:
188    //     Also note that inside transaction signatures, an extra hashtype byte
189    //     follows the actual signature data.
190    std::vector<unsigned char> vchSigCopy(vchSig.begin(), vchSig.begin() + vchSig.size() - 1);
191    // If the S value is above the order of the curve divided by two, its
192    // complement modulo the order could have been used instead, which is
193    // one byte shorter when encoded correctly.
194    if (!CPubKey::CheckLowS(vchSigCopy)) {
195        return set_error(serror, SCRIPT_ERR_SIG_HIGH_S);
196    }
197    return true;
198}
199
200bool static IsDefinedHashtypeSignature(const valtype &vchSig) {
201    if (vchSig.size() == 0) {
202        return false;
203    }
204    unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));
205    if (nHashType < SIGHASH_ALL || nHashType > SIGHASH_SINGLE)
206        return false;
207
208    return true;
209}
210
211bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, script_verify_flags flags, ScriptError* serror) {
212    // Empty signature. Not strictly DER encoded, but allowed to provide a
213    // compact way to provide an invalid signature for use with CHECK(MULTI)SIG
214    if (vchSig.size() == 0) {
215        return true;
216    }
217    if ((flags & (SCRIPT_VERIFY_DERSIG | SCRIPT_VERIFY_LOW_S | SCRIPT_VERIFY_STRICTENC)) != 0 && !IsValidSignatureEncoding(vchSig)) {
218        return set_error(serror, SCRIPT_ERR_SIG_DER);
219    } else if ((flags & SCRIPT_VERIFY_LOW_S) != 0 && !IsLowDERSignature(vchSig, serror)) {
220        // serror is set
221        return false;
222    } else if ((flags & SCRIPT_VERIFY_STRICTENC) != 0 && !IsDefinedHashtypeSignature(vchSig)) {
223        return set_error(serror, SCRIPT_ERR_SIG_HASHTYPE);
224    }
225    return true;
226}
227
228bool static CheckPubKeyEncoding(const valtype &vchPubKey, script_verify_flags flags, const SigVersion &sigversion, ScriptError* serror) {
229    if ((flags & SCRIPT_VERIFY_STRICTENC) != 0 && !IsCompressedOrUncompressedPubKey(vchPubKey)) {
230        return set_error(serror, SCRIPT_ERR_PUBKEYTYPE);
231    }
232    // Only compressed keys are accepted in segwit
233    if ((flags & SCRIPT_VERIFY_WITNESS_PUBKEYTYPE) != 0 && sigversion == SigVersion::WITNESS_V0 && !IsCompressedPubKey(vchPubKey)) {
234        return set_error(serror, SCRIPT_ERR_WITNESS_PUBKEYTYPE);
235    }
236    return true;
237}
238
239int FindAndDelete(CScript& script, const CScript& b)
240{
241    int nFound = 0;
242    if (b.empty())
243        return nFound;
244    CScript result;
245    CScript::const_iterator pc = script.begin(), pc2 = script.begin(), end = script.end();
246    opcodetype opcode;
247    do
248    {
249        result.insert(result.end(), pc2, pc);
250        while (static_cast<size_t>(end - pc) >= b.size() && std::equal(b.begin(), b.end(), pc))