Make VerifyWitnessProgram use a Span stack by sipa · Pull Request #18388 · bitcoin/bitcoin

sipa · 2020-03-19T23:25:38Z

Here is a follow-up to #18002, again with the goal of simplifying (potential) BIP341 code.

Instead of passing a begin and end iterator of the initial stack to ExecuteWitnessScript, they are turned into a Span<const valtype>, representing a span of valtypes in memory. This allows VerifyWitnessProgram to operate on that span directly, instead of juggling iterators around (which would be exacerbated by #17977 if trying to avoid copying the stack).

DrahtBot · 2020-03-20T00:12:54Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

BIP-325: Signet [consensus] #18267 (BIP-325: Signet [consensus] by kallewoof)
Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977 ([WIP] Implement BIP 340-342 validation (Schnorr/taproot/tapscript) by sipa)
script: add simple signature support (checker/creator) #16653 (script: add simple signature support (checker/creator) by kallewoof)
Make script interpreter independent from storage type CScript #13062 (Make script interpreter independent from storage type CScript by sipa)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

instagibbs · 2020-03-20T18:54:18Z

utACK c7b0131

wondering if there's some short-hand we could do to "split" the Spans or something like pop_back which also returns the popped element since that seems to be a common use-case of it now and going forward.

sipa · 2020-03-20T18:57:10Z

@instagibbs No reason why a pop_back couldn't be added to Span, but since C++20's std::span doesn't have it, I'd rather not in order to maintain compatibility. Maybe a utility function T& PopSpan(Span<T>& span) is useful (which pops, and returns the popped element).

instagibbs · 2020-03-20T18:59:58Z

@sipa took the words right out of my mouth :) I think the latter is perfect for our use-case

sipa · 2020-03-21T01:30:19Z

@instagibbs Done.

instagibbs · 2020-03-21T12:25:34Z

utACK ef540f7

theStack

Code-Review ACK ef540f7
(By the way, getting used to Span, I'm more and more surprised that such a useful lightweight representation hasn't been in the C++ standard for years.)

elichai

tACK ef540f796adef1f128584bd073076062585f0bd9
Read the code, couldn't spot any logic change.
ran unit tests+functional tests

src/span.h

promag

Code review ACK.

src/span.h

This allows for very cheap transformations on the range of elements that are to be passed to ExecuteWitnessScript.

elichai · 2020-03-23T22:13:50Z

ReACK on the diff 2b0fcff

ajtowns · 2020-03-24T05:06:15Z

ACK 2b0fcff

theStack · 2020-03-24T06:37:52Z

re-ACK 2b0fcff

instagibbs · 2020-03-24T17:37:09Z

re-ACK 2b0fcff

jnewbery

utACK 2b0fcff

jnewbery · 2020-03-24T19:14:30Z

src/span.h

    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]; }


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.

Empact · 2020-03-26T18:24:43Z

ACK 2b0fcff

Summary: 2b0fcff7f26d59fed4bcafd1602325122a206c67 Make VerifyWitnessProgram use a Span stack (Pieter Wuille) Pull request description: Here is a follow-up to #18002, again with the goal of simplifying (potential) BIP341 code. Instead of passing a begin and end iterator of the initial stack to `ExecuteWitnessScript`, they are turned into a `Span<const valtype>`, representing a span of `valtype`s in memory. This allows `VerifyWitnessProgram` to operate on that span directly, instead of juggling iterators around (which would be exacerbated by #17977 if trying to avoid copying the stack). --- Ignored the SegWit stuff but brought in the Span functionality, might be used in the future also less merge conflicts Backport of Core [[bitcoin/bitcoin#18388 | PR18388]] Test Plan: ninja Reviewers: #bitcoin_abc, deadalnix Reviewed By: #bitcoin_abc, deadalnix Differential Revision: https://reviews.bitcoinabc.org/D8495

bitcoin@2b0fcff

bitcoin deleted a comment from bee22193 Mar 19, 2020

fanquake requested a review from ajtowns March 19, 2020 23:37

fanquake added the Validation label Mar 19, 2020

sipa mentioned this pull request Mar 19, 2020

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

Closed

4 tasks

DrahtBot mentioned this pull request Mar 20, 2020

Make script interpreter independent from storage type CScript #13062

Closed

sipa force-pushed the 202003_span_witstack branch from c7b0131 to ef540f7 Compare March 21, 2020 01:26

theStack approved these changes Mar 21, 2020

View reviewed changes

jnewbery mentioned this pull request Mar 22, 2020

Future PRs bitcoin-core-review-club/website#14

Closed

elichai reviewed Mar 22, 2020

View reviewed changes

src/span.h Outdated Show resolved Hide resolved

promag reviewed Mar 23, 2020

View reviewed changes

src/span.h Outdated Show resolved Hide resolved

src/span.h Outdated Show resolved Hide resolved

Make VerifyWitnessProgram use a Span stack

2b0fcff

This allows for very cheap transformations on the range of elements that are to be passed to ExecuteWitnessScript.

sipa force-pushed the 202003_span_witstack branch from ef540f7 to 2b0fcff Compare March 23, 2020 21:45

This was referenced Mar 24, 2020

BIP-325: Signet [consensus] #18267

Merged

script: add simple signature support (checker/creator) #16653

Closed

jnewbery reviewed Mar 24, 2020

View reviewed changes

laanwj added this to the 0.20.0 milestone Mar 26, 2020

fanquake merged commit 5464616 into bitcoin:master Mar 27, 2020

MarkLTZ mentioned this pull request Apr 4, 2020

Bitcoin PR tracking litecoinz-core/litecoinz#14

Closed

kwvg mentioned this pull request Mar 10, 2021

partial merge #13697, #18591, #19387, #18468: update constructors to match c++20 draft spec dashpay/dash#4036

Merged

kwvg added a commit to kwvg/dash that referenced this pull request Apr 23, 2021

Merge bitcoin#18388: Make VerifyWitnessProgram use a Span stack

9304ba2

bitcoin@2b0fcff

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

Conversation

sipa commented Mar 19, 2020

Uh oh!

DrahtBot commented Mar 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

instagibbs commented Mar 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sipa commented Mar 20, 2020

Uh oh!

instagibbs commented Mar 20, 2020

Uh oh!

sipa commented Mar 21, 2020

Uh oh!

instagibbs commented Mar 21, 2020

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

elichai left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

promag left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

elichai commented Mar 23, 2020

Uh oh!

ajtowns commented Mar 24, 2020

Uh oh!

theStack commented Mar 24, 2020

Uh oh!

instagibbs commented Mar 24, 2020

Uh oh!

jnewbery left a comment

Choose a reason for hiding this comment

Uh oh!

jnewbery Mar 24, 2020

Choose a reason for hiding this comment

Uh oh!

Empact commented Mar 26, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

11 participants

DrahtBot commented Mar 20, 2020 •

edited

Loading

instagibbs commented Mar 20, 2020 •

edited

Loading