Make script interpreter independent from storage type CScript #13062

sipa · 2018-04-23T23:11:37Z

This introduces versions of GetScriptOp, EvalScript, and VerifyScript that operate on scripts represented by Span<const unsigned char>. This makes it possible to use different representation types for scripts, as Spans can be used to refer to scripts stored in any continuous fashion in memory, regardless of the container.

This is also a step towards reducing the consensus-criticalness of CScript, but not entirely. The interpreter code still uses CScript internally for a few purposes (notably DecodeOP_N, and operator<<).

Longer term, the goal is removing the need for all scripts to share the same representation. Currently CScript is a prevector with 28 preallocated bytes - a choice we need because it's favorable for scriptPubKeys in the UTXO cache, but it's pretty terrible for storing scriptSigs. With this change, separate (or even custom) data structures can be used for UTXO scriptPubKeys, and scriptPubKeys/scriptSigs in transactions. One possibility for the latter is storing all scripts in a transaction concatenated in a single allocated area, rather than using separate allocations for each.

promag

Looks good, will look more closely later.

promag · 2018-04-23T23:54:52Z

src/span.h

    constexpr std::ptrdiff_t size() const noexcept { return m_size; }
+    constexpr C& operator[](std::ptrdiff_t pos) const noexcept { return m_data[pos]; }
+
+    constexpr Span<C> subspan(std::ptrdiff_t offset) const noexcept { return Span<C>(m_data + offset, m_size - offset); }


Note, equivalent to count = std::dynamic_extent in std::span.

Which is the default, so I think it's fine. Generally all methods here mimic a subset of the behaviour of std::span, but sometimes with optional arguments/types omitted.

laanwj · 2018-04-25T13:51:27Z

Makes interpreter.cpp more self-contained, that's good.
Verified that:

Consensus IsPayToScriptHash matches CScript::IsPayToScriptHash: copy-only apart from variable names
Consensus IsWitnessProgram matches CScript::IsWitnessProgram:
- a size_t becomes ptr_diff_t: not an issue as only positive values are possible (unsigned char + 2)
- std::vector<unsigned char>(this->begin() + 2, this->end()) becomes script.subspan(2): should be ok, it's defined as Span(m_data + offset, m_size - offset)
Consensus IsPushOnly matches CScript::IsPushOnly:
- pc becomes Span instead of a const_iterator: effective behavior is the same
- GetOp becomes GetScriptOp: GetOp is already defined in that way, so should be fine

Other changes look straightforward.

utACK 91c12000dd97d7b9b9c82d1bbc92c7bbadd3d6ed

TheBlueMatt · 2018-04-27T16:40:27Z

This seems to be lacking a bunch of motivation. Can you clarify why you want to run a script stored in a span?

sipa · 2018-04-27T16:51:25Z

@TheBlueMatt They're not stored in a Span; a Span is just a way to refer to a script stored anywhere (vector, array, prevector, whatever custom structure that can hold a continuous sequence of bytes).

I'll add some more motivation.

TheBlueMatt · 2018-04-27T16:55:43Z

Suresure, I was asking for motivation of where we want to do this in the immediate future (do you have any branches that run scripts in non-prevector form?). The only place I can think of it being useful is in libbitcoinconsensus.

sipa · 2018-04-27T17:02:53Z

@TheBlueMatt No code to show, but I added some thoughts to the PR description.

TheBlueMatt · 2018-04-27T17:12:33Z

Ah, the scriptPubKey/scriptSig distinction seems like a reasonable idea. Would love to see a branch with that implemented to see the feasibility of using this in the short-term after a merge.

src/script/script.cpp

src/script/interpreter.cpp

ryanofsky · 2018-05-11T14:08:02Z

Related discussion in IRC: https://botbot.me/freenode/bitcoin-core-dev/msg/99929791/

src/span.h

sipa · 2018-05-31T18:53:29Z

Rebased.

src/script/script.cpp

achow101 · 2018-06-11T22:58:16Z

utACK 6ae8a5d

src/span.h

jb55 · 2018-06-21T01:04:20Z

utACK ae8df82ad34a6baaf883411308255e6c6d093c53

promag · 2018-06-21T19:01:35Z

utACK ae8df82.

achow101 · 2018-06-29T22:05:54Z

re-utACK ae8df82ad34a6baaf883411308255e6c6d093c53

sipa · 2018-08-01T18:42:13Z

Rebased.

… witness programs 34d0e07 Test that OP_1-OP_16 (but not lower/higher) start witness programs (Pieter Wuille) Pull request description: Cherry-picks one of the commits adding test coverage from #13062. As [pointed out by aj](https://github.com/bitcoin/bitcoin/pull/13062/files#r492723037): > could move the test additions to the first commit, since they're testing things that are already true Pull the additional test code into master earlier. ACKs for top commit: laanwj: Code review ACK 34d0e07 Tree-SHA512: ff0ab2a54613ea6e8246b443363b362dd41b5e464faba4d11be6003aa6588a626cf56e142a3b94465cd37dd3ac4debea08455db96bade336171b6c30ea894950

…) start witness programs 34d0e07 Test that OP_1-OP_16 (but not lower/higher) start witness programs (Pieter Wuille) Pull request description: Cherry-picks one of the commits adding test coverage from bitcoin#13062. As [pointed out by aj](https://github.com/bitcoin/bitcoin/pull/13062/files#r492723037): > could move the test additions to the first commit, since they're testing things that are already true Pull the additional test code into master earlier. ACKs for top commit: laanwj: Code review ACK 34d0e07 Tree-SHA512: ff0ab2a54613ea6e8246b443363b362dd41b5e464faba4d11be6003aa6588a626cf56e142a3b94465cd37dd3ac4debea08455db96bade336171b6c30ea894950

This introduces a version of GetScriptOp that is independent from the script storage type.

The CScript methods IsPayToScriptHash, IsWitnessProgram, and IsPushOnly are currently consensus critical, and dependent on the storage type (CScript). This creates new consensus-critical versions inside interpreter that operate on the more efficient Span<const unsigned char> type, independent from the script storage. The CScript methods remain, but are no longer consensus-critical.

This introduces a version of EvalScript that is independent from the storage type.

sipa · 2022-04-05T19:02:08Z

Rebased.

w0xlt

Code Review ACK f5ad705

DrahtBot · 2022-07-22T07:57:01Z

🐙 This pull request conflicts with the target branch and needs rebase.

_{Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft".}

ajtowns · 2022-10-05T02:31:24Z

I think rebasing this to current master only requires:

+++ src/script/interpreter.cpp
-+    return (CHashWriter(HASHER_TAPLEAF) << leaf_version << COMPACTSIZE(script.size()) << script).GetSHA256();
++    return (HashWriter(HASHER_TAPLEAF) << leaf_version << COMPACTSIZE(script.size()) << script).GetSHA256();

+++ src/psbt.h
@@ -889,7 +889,7 @@ struct PSBTOutput
                     } else if (key.size() != 33) {
                         throw std::ios_base::failure("Output Taproot BIP32 keypath key is not at 33 bytes");
                     }
-                    XOnlyPubKey xonly(uint256({key.begin() + 1, key.begin() + 33}));
+                    XOnlyPubKey xonly(Span<const unsigned char>(key).subspan(1, 32));

achow101 · 2022-10-12T17:54:36Z

Closing this as it has not had any activity in a while. If you are interested in continuing work on this, please leave a comment so that it can be reopened.

promag reviewed Apr 24, 2018

View reviewed changes

laanwj added Refactoring Consensus labels Apr 24, 2018

theuni reviewed Apr 27, 2018

View reviewed changes

src/script/script.cpp Show resolved Hide resolved

src/script/script.cpp Outdated Show resolved Hide resolved

src/script/interpreter.cpp Outdated Show resolved Hide resolved

sipa force-pushed the 201804_spaninterpret branch from 91c1200 to de61601 Compare April 28, 2018 00:04

sipa mentioned this pull request May 12, 2018

BIP 158: Compact Block Filters for Light Clients #12254

Merged

martinus reviewed May 31, 2018

View reviewed changes

src/span.h Outdated Show resolved Hide resolved

sipa force-pushed the 201804_spaninterpret branch from a76a044 to 6ae8a5d Compare May 31, 2018 18:53

promag reviewed Jun 11, 2018

View reviewed changes

src/script/script.cpp Outdated Show resolved Hide resolved

src/script/script.cpp Outdated Show resolved Hide resolved

sipa force-pushed the 201804_spaninterpret branch from 6ae8a5d to ae8df82 Compare June 18, 2018 22:45

jb55 reviewed Jun 21, 2018

View reviewed changes

src/span.h Outdated Show resolved Hide resolved

DrahtBot mentioned this pull request Jun 28, 2018

Remove unused function arguments #13554

Merged

DrahtBot mentioned this pull request Jul 22, 2018

Support output descriptors in scantxoutset #13697

Merged

DrahtBot added the Needs rebase label Jul 30, 2018

sipa force-pushed the 201804_spaninterpret branch from ae8df82 to 5fae0f4 Compare August 1, 2018 18:41

DrahtBot removed the Needs rebase label Aug 1, 2018

sipa force-pushed the 201804_spaninterpret branch from 5fae0f4 to 2537e8a Compare August 1, 2018 21:54

fanquake mentioned this pull request Feb 10, 2022

test: test that OP_1-OP_16 (but not lower/higher) start witness programs #24309

Merged

maflcko added Needs rebase Waiting for author labels Feb 14, 2022

DrahtBot removed the Needs rebase label Feb 14, 2022

DrahtBot added the Needs rebase label Apr 5, 2022

sipa and others added 8 commits April 5, 2022 14:45

Make uint{160,256} support construction from Span

4d905a7

Support pushing Spans onto CScript

1bf6f3a

Make GetScriptOp operate on Span

2da0be9

This introduces a version of GetScriptOp that is independent from the script storage type.

Make EvalScript operate on Span

bef9b40

This introduces a version of EvalScript that is independent from the storage type.

Make VerifyScript operate on Span

9732fdd

Avoid a few instances of CScript in interpreter

356791d

Make CountWitnessSigOps operate on Span

f5ad705

sipa force-pushed the 201804_spaninterpret branch from 690bc61 to f5ad705 Compare April 5, 2022 19:01

DrahtBot removed the Needs rebase label Apr 5, 2022

w0xlt approved these changes Apr 5, 2022

View reviewed changes

DrahtBot mentioned this pull request Jun 10, 2022

Add HashWriter without ser-type and ser-version and use it where possible #25331

Merged

DrahtBot added the Needs rebase label Jul 22, 2022

maflcko removed the Waiting for author label Aug 1, 2022

maflcko mentioned this pull request Aug 19, 2022

refactor: Do not use CScript for tapleaf scripts until the tapleaf version is known #25877

Merged

achow101 closed this Oct 12, 2022

fanquake added the Up for grabs label Oct 13, 2022

bitcoin locked and limited conversation to collaborators Oct 13, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Make script interpreter independent from storage type CScript #13062

Make script interpreter independent from storage type CScript #13062

sipa commented Apr 23, 2018 •

edited

promag left a comment

promag Apr 23, 2018

sipa May 22, 2018

laanwj commented Apr 25, 2018

TheBlueMatt commented Apr 27, 2018

sipa commented Apr 27, 2018

TheBlueMatt commented Apr 27, 2018

sipa commented Apr 27, 2018

TheBlueMatt commented Apr 27, 2018

ryanofsky commented May 11, 2018

sipa commented May 31, 2018

achow101 commented Jun 11, 2018

jb55 commented Jun 21, 2018

promag commented Jun 21, 2018

achow101 commented Jun 29, 2018

sipa commented Aug 1, 2018

sipa commented Apr 5, 2022

w0xlt left a comment

DrahtBot commented Jul 22, 2022

ajtowns commented Oct 5, 2022

achow101 commented Oct 12, 2022

Make script interpreter independent from storage type CScript #13062

Make script interpreter independent from storage type CScript #13062

Conversation

sipa commented Apr 23, 2018 • edited

promag left a comment

Choose a reason for hiding this comment

promag Apr 23, 2018

Choose a reason for hiding this comment

sipa May 22, 2018

Choose a reason for hiding this comment

laanwj commented Apr 25, 2018

TheBlueMatt commented Apr 27, 2018

sipa commented Apr 27, 2018

TheBlueMatt commented Apr 27, 2018

sipa commented Apr 27, 2018

TheBlueMatt commented Apr 27, 2018

ryanofsky commented May 11, 2018

sipa commented May 31, 2018

achow101 commented Jun 11, 2018

jb55 commented Jun 21, 2018

promag commented Jun 21, 2018

achow101 commented Jun 29, 2018

sipa commented Aug 1, 2018

sipa commented Apr 5, 2022

w0xlt left a comment

Choose a reason for hiding this comment

DrahtBot commented Jul 22, 2022

ajtowns commented Oct 5, 2022

achow101 commented Oct 12, 2022

sipa commented Apr 23, 2018 •

edited