Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make VerifyWitnessProgram use a Span stack #18388

Merged
merged 1 commit into from
Mar 27, 2020
Merged

Make VerifyWitnessProgram use a Span stack #18388

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
16 changes: 9 additions & 7 deletions src/script/interpreter.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1478,9 +1478,9 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
template class GenericTransactionSignatureChecker<CTransaction>;
template class GenericTransactionSignatureChecker<CMutableTransaction>;

static bool ExecuteWitnessScript(std::vector<valtype>::const_iterator begin, std::vector<valtype>::const_iterator end, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
{
std::vector<valtype> stack{begin, end};
std::vector<valtype> stack{stack_span.begin(), stack_span.end()};

// Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
for (const valtype& elem : stack) {
Expand All @@ -1499,27 +1499,29 @@ static bool ExecuteWitnessScript(std::vector<valtype>::const_iterator begin, std
static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
{
CScript scriptPubKey;
Span<const valtype> stack = MakeSpan(witness.stack);

if (witversion == 0) {
if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
// Version 0 segregated witness program: SHA256(CScript) inside the program, CScript + inputs in witness
if (witness.stack.size() == 0) {
if (stack.size() == 0) {
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
}
scriptPubKey = CScript(witness.stack.back().begin(), witness.stack.back().end());
const valtype& script_bytes = SpanPopBack(stack);
scriptPubKey = CScript(script_bytes.begin(), script_bytes.end());
uint256 hashScriptPubKey;
CSHA256().Write(&scriptPubKey[0], scriptPubKey.size()).Finalize(hashScriptPubKey.begin());
if (memcmp(hashScriptPubKey.begin(), program.data(), 32)) {
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
}
return ExecuteWitnessScript(witness.stack.begin(), witness.stack.end() - 1, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror);
return ExecuteWitnessScript(stack, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror);
} else if (program.size() == WITNESS_V0_KEYHASH_SIZE) {
// Special case for pay-to-pubkeyhash; signature + pubkey in witness
if (witness.stack.size() != 2) {
if (stack.size() != 2) {
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); // 2 items in witness
}
scriptPubKey << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG;
return ExecuteWitnessScript(witness.stack.begin(), witness.stack.end(), scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror);
return ExecuteWitnessScript(stack, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror);
} else {
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
}
Expand Down
14 changes: 14 additions & 0 deletions src/span.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,6 +8,7 @@
#include <type_traits>
#include <cstddef>
#include <algorithm>
#include <assert.h>

/** A Span is an object that can refer to a contiguous sequence of objects.
*
Expand All @@ -27,6 +28,8 @@ class Span
constexpr C* data() const noexcept { return m_data; }
constexpr C* begin() const noexcept { return m_data; }
constexpr C* end() const noexcept { return m_data + m_size; }
constexpr C& front() const noexcept { return m_data[0]; }
sipa marked this conversation as resolved.
Show resolved Hide resolved
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Note for reviewers: these functions front() and back() are no longer used in this PR, but are used in the taproot implementation, so there's no harm in including them here.

constexpr C& back() const noexcept { return m_data[m_size - 1]; }
constexpr std::ptrdiff_t size() const noexcept { return m_size; }
constexpr C& operator[](std::ptrdiff_t pos) const noexcept { return m_data[pos]; }

Expand Down Expand Up @@ -57,4 +60,15 @@ constexpr Span<A> MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
template<typename V>
constexpr Span<typename std::remove_pointer<decltype(std::declval<V>().data())>::type> MakeSpan(V& v) { return Span<typename std::remove_pointer<decltype(std::declval<V>().data())>::type>(v.data(), v.size()); }

/** Pop the last element off a span, and return a reference to that element. */
template <typename T>
T& SpanPopBack(Span<T>& span)
{
size_t size = span.size();
assert(size > 0);
T& back = span[size - 1];
span = Span<T>(span.data(), size - 1);
return back;
}

#endif