Title: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions
Post by: cmpeq on December 07, 2023, 11:04:54 AM
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! // 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
Title: Re: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions
Post by: NotATether on December 07, 2023, 12:29:48 PM
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?
Title: Re: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions
Post by: garlonicon on December 07, 2023, 01:09:17 PM
Well, "<signature> 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. 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 "<someScript> <key> 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. 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. 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). 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 <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 <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
Title: Re: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions
Post by: pooya87 on December 08, 2023, 04:30:05 AM
Well, "<signature> 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. 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.
Title: Re: [OP_MUL without OP_MUL] Re-enabling OP_MUL in 908 instructions
Post by: cmpeq on December 08, 2023, 05:38:41 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: 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: // 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: <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 (https://users.utcluj.ro/~baruch/book_ssce/SSCE-Shift-Mult.pdf) 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 <lo 15 bits> <hi 15 bits> to the stack can be accomplished using the script: // 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
|