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:
<20>
<124214124>
OP_MUL
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:
// 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
<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:
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