BIP draft: 64-bit arithmetic opcodes

Christewart commented at 8:44 pm on January 10, 2024: contributor

This BIP describes a soft fork to add 64-bit arithmetic op codes to bitcoin

Implementation: https://github.com/bitcoin/bitcoin/pull/29221

WIP d0aafd9001

Add section on overflows 54350b53c5

Add credit to Sanket and Andrew b11e06e1e8

fix code formatting 8bbf62764d

Fix hyperlinks 5d52ff3212

Add link to elements impl 464ce8eb4d

Add helper methods 9da332cefd

Add conversion opcodes b5d0fe5bbd

Remove push4_le as its not used in reference impl 571390589b

Add specifics for OP_DIV64 1c8a5af1d1

Remove BIP number 243db3fc67

Remove uncessary sequence requirement d1c90b0f0a

Christewart renamed this:
~~64bit arithetmic op codes~~
64bit arithmetic op codes
on Jan 10, 2024

Christewart marked this as ready for review on Jan 10, 2024

khademreza5 approved

EthanHeilman commented at 4:54 pm on January 17, 2024: contributor

Why not push the overflow amount and the result back on the stack?

Rather than $2^{64}-1 + 3 = \mbox{FALSE}$, do $2^{64}-1 + 3 = 2, 1$. Where $2 = 2^{64}-1 + 3 \mod 2^{64}$ is the result and 1 is the overflow.

This would simply doing 256-bit math from 64-bit stack elements and I don’t see any downsides for 64-bit operations.

Remove OP_DIV64 from other opcodes 5bebdd18d4

Christewart commented at 9:01 pm on February 1, 2024: contributor

Why not push the overflow amount and the result back on the stack?

Rather than 264−1+3=FALSE, do 264−1+3=2,1. Where 2=264−1+3mod264 is the result and 1 is the overflow.

This would simply doing 256-bit math from 64-bit stack elements and I don’t see any downsides for 64-bit operations.

Sorry I don’t understand this. Could you maybe give a more concrete example, perhaps on delvingbitcoin? We have a thread going here: https://delvingbitcoin.org/t/64-bit-arithmetic-soft-fork/397/25

in bip-0364.mediawiki:7 in 5bebdd18d4 outdated

0@@ -0,0 +1,302 @@
1+<pre>
2+  BIP: TBD
3+  Layer: Consensus (soft fork)
4+  Title: 64 bit arithmetic operations
5+  Author: Chris Stewart <stewart.chris1234@gmail.com>
6+  Comments-Summary: No comments yet.
7+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0364

murchandamus commented at 7:21 pm on May 1, 2024:

Please refrain from issuing your own BIP numbers.

in bip-0364.mediawiki:4 in 5bebdd18d4 outdated

0@@ -0,0 +1,302 @@
1+<pre>
2+  BIP: TBD
3+  Layer: Consensus (soft fork)
4+  Title: 64 bit arithmetic operations

murchandamus commented at 7:21 pm on May 1, 2024:

Maybe:

0  Title: 64-bit arithmetic operations

murchandamus changes_requested

murchandamus commented at 7:28 pm on May 1, 2024: contributor

I just did a light first pass. I noticed that this document may be missing a Rationale Section that describes design decisions, alternate approaches, and related work, and a Backwards Compatibility section.

You may want to add the “Post-History” header to the preamble to link to discussions of this proposal on the mailing list or forums.

murchandamus added the label New BIP on May 8, 2024

murchandamus added the label PR Author action required on May 8, 2024

murchandamus commented at 8:47 pm on November 14, 2024: contributor

Hey @Christewart, are you still working on this?

Christewart commented at 10:49 pm on November 14, 2024: contributor

Hey @Christewart, are you still working on this?

Yep i’m going to give it another go. I’ll update soon.

bitcoin deleted a comment on Nov 14, 2024

jonatack renamed this:
~~64bit arithmetic op codes~~
BIP draft: 64-bit arithmetic opcodes
on Dec 17, 2024

Remove 64bit specific arithmetic opcodes in favor of just repurposing existing airthmetic opcodes bc417cbd88

in bip-0364.mediawiki:18 in bc417cbd88

13+
14+==Abstract==
15+
16+This BIP re-enables two opcodes: OP_MUL and OP_DIV.
17+
18+This BIP also expands supported precision for valid operands from `-2^31 +1` to `2^31 -1` to `-2^63 +1...2^63 -1`.

EthanHeilman commented at 3:07 pm on February 3, 2025:

I want to make sure I understand, this isn’t proposing new opcodes that handle 64-bit arithmetic is it redefining the existing opcodes. Is that correct? It’s probably on your TODO list, but what is the mechanism you are using to make this a softfork? Script versioning?

In the future we may wish to increase the supported precision again. What about adding a precision commitment to make soft-forking precision upgrades easier? For instance OP_PUSH x, OP_PRECIS, if x >64 then P_PUSH x OP_PRECIS is an OP_SUCCESSx. Then if we soft precision to 128 bits, OP_PUSH x, OP_PRECIS becomes a NOP.

Christewart commented at 10:48 pm on February 3, 2025:

Hi Ethan thanks for your continued interest in this topic.

I want to make sure I understand, this isn’t proposing new opcodes that handle 64-bit arithmetic is it redefining the existing opcodes. Is that correct?

:+1:

It’s probably on your TODO list, but what is the mechanism you are using to make this a softfork? Script versioning?

My latest thinking for the upgrade mechanism is allocating a new tap leaf version to indicate the precision of arithmetic operations for Script. This was suggested by @sipa here. You can read about how this works on delving bitcoin and see my implementation of it here inside the bitcoin c++ code base.

I personally think this makes Scripts easier to reason about as the leaf version indicates the precision of all numeric operations during this Script’s execution. If we want to increase precision again in the future, we can allocate a new leaf version and extend the underlying precision of CScriptNum and expose that functionality as I’ve done here

https://github.com/Christewart/bitcoin/blob/20fe67b5e4f2db7326ba5b8771c4516a7010861e/src/script/interpreter.cpp#L257

In the future we may wish to increase the supported precision again. What about adding a precision commitment to make soft-forking precision upgrades easier?

Committing to arbitrary precision seems hard, but i think this BIP lays the groundwork for extending precision in the future by making the precision of arithmetic operations linked with new tapleaf versions.

I pushed to this branch staged changes in a haphazard state, apologies. I’m working on a BIP currently to disallow 64 byte transactions in the bitcoin blockchain as I think that is more likely to be widely accepted by the community, and then will be coming back to this work.

murchandamus marked this as a draft on Feb 6, 2025

murchandamus commented at 6:57 pm on February 6, 2025: contributor

Hi @Christewart, it’s my understanding that this document is currently not ready for BIP Editor review, so I have labeled the pull request as Draft. Please let us know when you would like us to take a look by returning it to “Ready for Review” when it has been updated.

in bip-0364.mediawiki:54 in bc417cbd88

49+
50+Refer to the reference implementation, reproduced below, for the precise
51+semantics and detailed rationale for those semantics.
52+
53+<source lang="cpp">
54+class CScriptNum

Roasbeef commented at 1:13 am on February 7, 2025:

Big thumbs down at the idea of just pasting a blob of C++ code vs actually specifying the semantics of the new op codes.

Christewart commented at 9:27 pm on March 2, 2025: contributor

I’m closing this PR for now as the proposals I have in my mind differentiate materially from this original PR.

I envision having 2 BIPs in the future to hopefully make this proposal more consumable.

This BIP would expand the arithmetic operations precision from -2^31 +1 to 2^31 -1 to -2^63 +1...2^63 -1. This propsal may also redefine behavior in arithmetic operations such as overflow handling, supporting signed vs unsigned numbers, and potentially number encoding.
Re-enabling opcodes. This BIP would build on the first BIP and re-enable a set of opcodes based on the foundation laid in the first BIP.

Hopefully if we ever decide to expand precision again in the future, we can heavily rely on (1) to lay the groundwork for safe precision expansion in future soft forks.

If you are interested in working on either of these with me, please reach out on delving, twitter, irc, email etc.

Christewart closed this on Mar 2, 2025

BIP draft: 64-bit arithmetic opcodes #1538