[OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions

cmpeq

copper member

Activity: 33

Merit: 152

Quote from: NotATether on December 07, 2023, 07:29:48 AM

Wow, that is very impressive!

Although what are the limits for the bit lengths of the multiplicands? This does not look like arbitrary-precision multiplication, and the integer constants sprinkled in the code seem to indicate that it can handle 64-bit word sizes.

How does it handle overflow, since you can't directly program the script interpreter itself? Does it wrap around, or does it perform some other behavior?

I tried to mimic OP_MUL's behavior as best as possible since this is supposed to be something like a polyfill for OP_MUL.
For example, consider the script below with OP_MUL running in the original bitcoin implementation:

Code:

<20>
<124214124>
OP_MUL

The result of running the script is a single item on the stack, <0x7024139400>, which is the same result you get with the polyfill.

The polyfill does not, however, work when the first multiplicand is more than 15 bits, but this can be fixed if we do a limb decomposition:
a = w*2^15 + x
b = y*2^15 + z
--- where w,x,y,z are all less than 2^15

We then can perform a*b by noticing that:
a*b = (w*y)*2^30 + (w*z + x*y)*2^15 + x*z
(ensuring to properly handle the carry of w*z + x*y)

On your point about arbitrary precision, we can achieve this for larger integers by decomposing the number into limbs and handling the carries as we go.

For example, here is OP_ADD_U255, an operation which adds two 255 bit unsigned integers, each of which is decomposed into 17 15-bit limbs:

Code:

// add 4201337318233461266421127527930416761106284784989888161287540051441282761337 + 17686905553605813955825278217326858327442079615426146182410664135134525734280

/*

4201337318233461266421127527930416761106284784989888161287540051441282761337 = 2377 * 2^240 + 28595 * 2^225 + 3588 * 2^210 + 25430 * 2^195 + 3044 * 2^180 + 28258 * 2^165 + 12937 * 2^150 + 9487 * 2^135 + 15672 * 2^120 + 27272 * 2^105 + 10294 * 2^90 + 17021 * 2^75 + 16961 * 2^60 + 16915 * 2^45 + 2004 * 2^30 + 13225 * 2^15 + 17017

17686905553605813955825278217326858327442079615426146182410664135134525734280 = 10010 * 2^240 + 14214 * 2^225 + 10823 * 2^210 + 20655 * 2^195 + 4000 * 2^180 + 5067 * 2^165 + 10108 * 2^150 + 23969 * 2^135 + 8175 * 2^120 + 12139 * 2^105 + 27111 * 2^90 + 29872 * 2^75 + 18130 * 2^60 + 23804 * 2^45 + 20091 * 2^30 + 11350 * 2^15 + 15752

*/

// OP_ADD_U255 => A+B
// start A
<2377>
<28595>
<3588>
<25430>
<3044>
<28258>
<12937>
<9487>
<15672>
<27272>
<10294>
<17021>
<16961>
<16915>
<2004>
<13225>
<17017>
// end A

// start B
<10010>
<14214>
<10823>
<20655>
<4000>
<5067>
<10108>
<23969>
<8175>
<12139>
<27111>
<29872>
<18130>
<23804>
<20091>
<11350>
<15752>
// end B

// start OP_ADD_U255
<17>
OP_ROLL
OP_ADD
OP_DUP
<32767>
OP_LESSTHANOREQUAL
OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <16>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <15>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <14>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <13>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <12>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <11>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <10>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <9>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <8>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <7>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <6>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <5>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <4>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <3>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <2>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_ADD
  <1>
  OP_ROLL
  OP_ADD
  OP_DUP
  <32767>
  OP_LESSTHANOREQUAL
  OP_IF
  OP_0
OP_ELSE
  <32768>
  OP_SUB
  OP_1
  OP_ENDIF
  OP_SWAP
  OP_TOALTSTACK
  OP_DROP
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK
  OP_FROMALTSTACK

//end OP_ADD_U255

If you compute the result in python, you will find that it is 21888242871839275222246405745257275088548364400416034343698204186575808495617, and indeed if we run our script we will find the following items on the stack:

Code:

<12388>
<10041>
<14412>
<13317>
<7045>
<557>
<23046>
<688>
<23848>
<6644>
<4638>
<14126>
<2324>
<7951>
<22095>
<24576>
<1>

Which is the 15 bit decomposed representation of 21888242871839275222246405745257275088548364400416034343698204186575808495617 as:

21888242871839275222246405745257275088548364400416034343698204186575808495617 = 12388 * 2^240 + 10041 * 2^225 + 14412 * 2^210 + 13317 * 2^195 + 7045 * 2^180 + 557 * 2^165 + 23046 * 2^150 + 688 * 2^135 + 23848 * 2^120 + 6644 * 2^105 + 4638 * 2^90 + 14126 * 2^75 + 2324 * 2^60 + 7951 * 2^45 + 22095 * 2^30 + 24576 * 2^15 + 1

For big int multiplication we have a few options:
1. Bitwise multiplication (giant scripts), for example here is a script which multiplies two u128 bit vectors in the stack:
https://gist.github.com/cf/16072ca8efcafce5fcf9412565c9e469
This uses a basic shift and add design to handle the multiplication

2. 15-bit decomposition (the largest number bitcoin script numbers can represent is 2**31-1, so using 15 bit limbs is convenient since we can add and multiply them without fear of overflowing).
This produces much smaller scripts, but is a bit more involved as, whenever we multiply, we also have to split the products back into 15 bit limbs

For #2, we can split a 30 bit uint result from a multiplication into two 15 bit limbs with the following script:

Code:

OP_0
OP_TOALTSTACK
OP_DUP
<536870912>
OP_LESSTHAN
OP_IF
OP_ELSE
  <16384>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <536870912>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <268435456>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <8192>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <268435456>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <134217728>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <4096>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <134217728>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <67108864>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <2048>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <67108864>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <33554432>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <1024>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <33554432>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <16777216>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <512>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <16777216>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <8388608>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <256>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <8388608>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <4194304>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <128>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <4194304>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <2097152>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <64>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <2097152>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <1048576>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <32>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <1048576>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <524288>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <16>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <524288>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <262144>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <8>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <262144>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <131072>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <4>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <131072>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <65536>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <2>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <65536>
  OP_SUB
  OP_ENDIF
  OP_DUP
  <32768>
  OP_LESSTHAN
  OP_IF
OP_ELSE
  <1>
  OP_FROMALTSTACK
  OP_ADD
  OP_TOALTSTACK
  <32768>
  OP_SUB
  OP_ENDIF
  OP_FROMALTSTACK

Hence multiplying 2 15 bit uints and pushing to the stack can be accomplished using the script:

Code:

// mul x * y => push lo and hi limbs to stack where x,y,lo,hi are all 15 bit script numbers

// Example multiply 13379 * 12345
<13379>
<12345>

// start OP_MUL_15_HI_LO
OP_DUP
<16384>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<16384>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<8192>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<8192>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<4096>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<4096>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<2048>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<2048>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<1024>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<1024>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<512>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<512>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<256>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<256>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<128>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<128>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<64>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<64>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<32>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<32>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<16>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<16>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<8>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<8>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<4>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<4>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<2>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<2>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
<15>
OP_ROLL
OP_SWAP
OP_IF
OP_DUP
OP_ELSE
OP_0
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_NIP
OP_0
OP_TOALTSTACK
OP_DUP
<536870912>
OP_LESSTHAN
OP_IF
OP_ELSE
<16384>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<536870912>
OP_SUB
OP_ENDIF
OP_DUP
<268435456>
OP_LESSTHAN
OP_IF
OP_ELSE
<8192>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<268435456>
OP_SUB
OP_ENDIF
OP_DUP
<134217728>
OP_LESSTHAN
OP_IF
OP_ELSE
<4096>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<134217728>
OP_SUB
OP_ENDIF
OP_DUP
<67108864>
OP_LESSTHAN
OP_IF
OP_ELSE
<2048>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<67108864>
OP_SUB
OP_ENDIF
OP_DUP
<33554432>
OP_LESSTHAN
OP_IF
OP_ELSE
<1024>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<33554432>
OP_SUB
OP_ENDIF
OP_DUP
<16777216>
OP_LESSTHAN
OP_IF
OP_ELSE
<512>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<16777216>
OP_SUB
OP_ENDIF
OP_DUP
<8388608>
OP_LESSTHAN
OP_IF
OP_ELSE
<256>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<8388608>
OP_SUB
OP_ENDIF
OP_DUP
<4194304>
OP_LESSTHAN
OP_IF
OP_ELSE
<128>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<4194304>
OP_SUB
OP_ENDIF
OP_DUP
<2097152>
OP_LESSTHAN
OP_IF
OP_ELSE
<64>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<2097152>
OP_SUB
OP_ENDIF
OP_DUP
<1048576>
OP_LESSTHAN
OP_IF
OP_ELSE
<32>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<1048576>
OP_SUB
OP_ENDIF
OP_DUP
<524288>
OP_LESSTHAN
OP_IF
OP_ELSE
<16>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<524288>
OP_SUB
OP_ENDIF
OP_DUP
<262144>
OP_LESSTHAN
OP_IF
OP_ELSE
<8>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<262144>
OP_SUB
OP_ENDIF
OP_DUP
<131072>
OP_LESSTHAN
OP_IF
OP_ELSE
<4>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<131072>
OP_SUB
OP_ENDIF
OP_DUP
<65536>
OP_LESSTHAN
OP_IF
OP_ELSE
<2>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<65536>
OP_SUB
OP_ENDIF
OP_DUP
<32768>
OP_LESSTHAN
OP_IF
OP_ELSE
<1>
OP_FROMALTSTACK
OP_ADD
OP_TOALTSTACK
<32768>
OP_SUB
OP_ENDIF
OP_FROMALTSTACK

// end OP_MUL_15_HI_LO

// stack result <13035> (lo) <5040> (hi)
// 13379*12345 == 165163755 == (5040<<15) | 13035

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: garlonicon on December 07, 2023, 08:09:17 AM

Well, " OP_SWAP OP_CHECKSIG" can handle addition and multiplication on 256-bit numbers. And Schnorr signatures can be used to handle similar things on a single public key.

It's not the same concept though. OP_CHECKSIG handles ECDSA that is a fixed formula and on fixed integer types. What OP has in mind is arbitrary arithmetic being performed on arbitrary integers.

Quote

This does not look like arbitrary-precision multiplication, and the integer constants sprinkled in the code seem to indicate that it can handle 64-bit word sizes.

Well, the Script supports 32-bit chunks by default, so yes, if you multiply two 32-bit values, you can get one 64-bit value, splitted into two chunks.

The final result doesn't need to be split into chunks, you can push a 64-bit integer result to the stack. It is only invalid when you pop it and want to interpret a >4 byte data as integer in arithmetic OPs.

garlonicon

copper member

Activity: 821

Merit: 1992

Well, " OP_SWAP OP_CHECKSIG" can handle addition and multiplication on 256-bit numbers. And Schnorr signatures can be used to handle similar things on a single public key. But of course, without OP_CAT, that kind of things are hard.

Quote

Although what are the limits for the bit lengths of the multiplicands?

1. If you assume unlimited Script size (which is kind of true, because you can have pre-signed transactions with " OP_CHECKSIG", and you can create a chain of transactions), then it is potentially unlimited.
2. If you think about the code of OP, then it is limited to 32-bit values.
3. If you use signatures, then it is limited to 256-bit values.

Quote

This does not look like arbitrary-precision multiplication, and the integer constants sprinkled in the code seem to indicate that it can handle 64-bit word sizes.

Well, the Script supports 32-bit chunks by default, so yes, if you multiply two 32-bit values, you can get one 64-bit value, splitted into two chunks.

Quote

How does it handle overflow, since you can't directly program the script interpreter itself?

You can use opcodes like OP_LESSTHAN, and similar ones, to decide, what exactly do you want. By the way, if you have addition, then only the last bit is different in that case, so the code with overflow is very similar to the code without it. If you add two 32-bit values, then you can reach some 33-bit number, or drop the most important bit, and reach an equivalent modulo 2^32 (it can be useful in hash functions).

Quote

Does it wrap around, or does it perform some other behavior?

You can decide, both solutions are possible.

Edit: And of course, there is also Homomorphic Encryption: https://duo.com/labs/tech-notes/2p-ecdsa-explained

Which means, you can use "first=randomA*1337" and "second=randomB*123456", and then make a signature in a way, where by knowing the result of "1337*123456", you will unlock it, and where some combination of "randomA" and "randomB" will protect it from being cracked by the outside observers.

Edit: If you want to multiply by some constant, then you can factor your number. For example, if 1337 is constant, then it means you need 7*191 multiplication. And also note that you can multiply by two or three, and then make squares or cubes.

1337=7*191
123456=2^6*3*643

Also, if you can find a simple sequence, then you can use it. For example, Fibonacci can be achieved by repeating "OP_TUCK OP_ADD". So, it is possible to find some sequence, where your magic number will be present, and then just calculate N-th value of that sequence.

Edit: Multiplication by 7: OP_DUP OP_2DUP OP_ADD OP_ADD OP_DUP OP_ADD OP_ADD

Code:

<123456>
<123456> <123456>
<123456> <123456> <123456> <123456>
<123456> <123456> <123456*2>
<123456> <123456*3>
<123456> <123456*3> <123456*3>
<123456> <123456*6>
<123456*7>

Multiplication by 10: OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD

Code:

<123456>
<123456> <123456>
<123456*2>
<123456*2> <123456*2>
<123456*2> <123456*2> <123456*2>
<123456*2> <123456*4>
<123456*2> <123456*4> <123456*4>
<123456*2> <123456*8>
<123456*10>

Multiplication by 100: OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD
Multiplication by 1000: OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD OP_DUP OP_ADD OP_DUP OP_DUP OP_ADD OP_DUP OP_ADD OP_ADD
Multiplication by 1337: OP_DUP OP_MUL1000 OP_OVER OP_MUL100 OP_MUL3 OP_ADD OP_OVER OP_MUL10 OP_MUL3 OP_ADD OP_OVER OP_MUL7 OP_ADD

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Wow, that is very impressive!

Although what are the limits for the bit lengths of the multiplicands? This does not look like arbitrary-precision multiplication, and the integer constants sprinkled in the code seem to indicate that it can handle 64-bit word sizes.

How does it handle overflow, since you can't directly program the script interpreter itself? Does it wrap around, or does it perform some other behavior?

cmpeq

copper member

Activity: 33

Merit: 152

A project I have been working on recently required the use of OP_MUL, and I implemented a shim that works... but unfortunately is 908 instructions long.

I imagine someone has come up with something more efficient, and would very much appreciate if anyone is willing to share!

Code:

// multiply 1337*123456
<1337>
<123456>

// (Start) OP_MUL
OP_DUP
<1073741824>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<1073741824>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<536870912>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<536870912>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<268435456>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<268435456>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<134217728>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<134217728>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<67108864>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<67108864>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<33554432>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<33554432>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<16777216>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<16777216>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<8388608>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<8388608>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<4194304>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<4194304>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<2097152>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<2097152>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<1048576>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<1048576>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<524288>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<524288>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<262144>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<262144>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<131072>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<131072>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<65536>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<65536>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<32768>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<32768>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<16384>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<16384>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<8192>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<8192>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<4096>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<4096>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<2048>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<2048>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<1024>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<1024>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<512>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<512>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<256>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<256>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<128>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<128>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<64>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<64>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<32>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<32>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<16>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<16>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<8>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<8>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<4>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<4>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
OP_DUP
<2>
OP_LESSTHAN
OP_IF
OP_0
OP_SWAP
OP_ELSE
<2>
OP_SUB
OP_1
OP_SWAP
OP_ENDIF
<31>
OP_ROLL
OP_SWAP
OP_IF
OP_DUP
OP_ELSE
OP_0
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_SWAP
OP_DUP
OP_ADD
OP_SIZE
OP_5
OP_EQUAL
OP_IF
OP_DROP
OP_0
OP_ENDIF
OP_ROT
OP_IF
OP_DUP
OP_ROT
OP_ADD
OP_ELSE
OP_SWAP
OP_ENDIF
OP_NIP
// (END) OP_MUL
// the result is now at the top of the stack

Topic: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions (Read 174 times)