[Deprecated] How does Bitmatrix V1 multiply two integers in the absence of OP_MUL?
Bitmatrix utilizes x * y = k formula for calculating a liquidity pool’s constant value. However, OP_MUL (an opcode for multiplying two integers), is disabled in legacy and witness version 0 scripts. Although OP_MUL is expected to be introduced in Liquid Tapscript, Bitmatrix V1 uses some bitwise trick to achieve the same outcome.
Let’s assume a Bitmatrix pool has a liquidity of 10 L-BTC, paired with 500,000 USDT. Since amount fields in Liquid transactions are represented in bytes instead of endians;
10 Bitcoin is represented = 0x000000003b9aca00 in bytes
And,
500,000 USDT is represented = 0x00002d79883d2000 in bytes
However arithmetic opcodes only accept endian integers, this is so that we need to convert amounts to endian using some data manipulation. On the other hand, due to some other limitations, we can multiply at most a 24-bit integer with a 48-bit integer, 24-bit integer being the L-BTC amount and 48-bit integer being the USDT amount.
Since L-BTC amount must be at most a 24-bit integer, we need to strip out the least significant byte (0x00) and reverse the last three bytes (0x3b9aca), leaving stack with 0xca9a3b:
<0x000000003b9aca00>OP_DUP <6> <1> OP_SUBSTR OP_SWAP OP_DUP <5> <1> OP_SUBSTR OP_SWAP <4> <1> OP_SUBSTR OP_CAT OP_CAT
And just like L-BTC, in order to make USDT amount a 48-bit integer, we need to splice and reverse the last 6 bytes, leaving the stack with 0x00203d88792d:
<0x00002d79883d2000>OP_DUP <7> <1> OP_SUBSTR OP_SWAP OP_DUP <6> <1> OP_SUBSTR OP_SWAP OP_DUP <5> <1> OP_SUBSTR OP_SWAP OP_DUP <4> <1> OP_SUBSTR OP_SWAP OP_DUP <3> <1> OP_SUBSTR OP_SWAP <2> <1> OP_SUBSTR OP_CAT OP_CAT OP_CAT OP_CAT OP_CAT
Now we have two valid script numbers; 0xca9a3b and 0x00203d88792d.
The multiplication between 0xca9a3b and 0x00203d88792d results: 195312500000000000000 in decimal, 0x00407ba5f06381960a in endian.
As we’re not able to calculate this value using OP_MUL, we found a trick combining OP_LSHIFT and OP_ADD to achieve the same result. This entire multiplication operation is divided into 7 parts, where the first 6 parts multiply 0xca9a3b with individual bytes of 0x00203d88792d and the last part adds results together.
Byte multiplication first part
The first part multiplies L-BTC amount (0xca9a3b) with the last byte of USDT amount (0x2d), which is 45 in decimal. The number 45 is made of individual numbers of 32, 8, 4, and 1. These numbers are provided in witness, and their additions are verified like the following:
<0x2d> //last byte<32> <8> <4> <1> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<32> <8> <4> <1> //powers<5> <3> <2> <0> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with 0x82357a0a:
<32> <8> <4> <1> //powers<0xca9a3b> //L-BTC amount<5> <3> <2> <0> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
Byte multiplication second part
The second part multiplies L-BTC amount (0xca9a3b) with the second to last byte of USDT amount (0x79), which is 121 in decimal. The number 121 is made of individual numbers of 128, -4, -4, and 1. These numbers are provided in witness, and their additions are verified like the following:
<0x79> //second to last byte<128> <-4> <-4> <1> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<128> <-4> <-4> <1> //powers<7> <2> <2> <0> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with 0x7a292c1c:
<128> <-4> <-4> <1> //powers<0xca9a3b> //L-BTC amount<7> <2> <2> <0> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
Byte multiplication third part
The third part multiplies L-BTC amount (0xca9a3b) with a third to last byte of USDT amount (0x88), which is -8 in decimal. The number -8 is made of individual numbers of -2, -2, -2, and -2. These numbers are provided in witness, and their additions are verified like the following:
<0x88> //third to last byte<-2> <-2> <-2> <-2> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<-2> <-2> <-2> <-2> //powers<1> <1> <1> <1> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with 0x50d6dc81:
<-2> <-2> <-2> <-2> //powers<0xca9a3b> //L-BTC amount<1> <1> <1> <1> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
If a multiplication result is a negative number like we have now with 0x50d6dc81 (-31250000), this number must be subtracted from 128 * L-BTC amount, leaving stack with 0x503baa1f (531250000):
<0xca9a3b> //L-BTC amount<0x50d6dc81> //Third multiplication resultOP_DUP <0> OP_LESSTHAN OP_IF <1> OP_PICK <7> OP_LSHIFT OP_SWAP OP_SUB OP_ENDIF
Byte multiplication fourth part
The fourth part multiplies L-BTC amount (0xca9a3b) with the third byte of USDT amount (0x3d), which is 61 in decimal. The number 61 is made of individual numbers of 64, -1, -1, and -1. These numbers are provided in witness, and their additions are verified like the following:
<0x3d> //second to last byte<64> <-1> <-1> <-1> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<64> <-1> <-1> <-1> //powers<6> <0> <0> <0> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with 0x22e2330e:
<64> <-1> <-1> <-1> //powers<0xca9a3b> //L-BTC amount<6> <0> <0> <0> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
Byte multiplication fifth part
The fifth part multiplies L-BTC amount (0xca9a3b) with the second byte of USDT amount (0x20), which is 32 in decimal. The number 32 is made of individual numbers of 8, 8, 8, and 8. These numbers are provided in witness, and their additions are verified like the following:
<0x20> //second to last byte<8> <8> <8> <8> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<8> <8> <8> <8> //powers<3> <3> <3> <3> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with 0x40597307:
<8> <8> <8> <8> //powers<0xca9a3b> //L-BTC amount<3> <3> <3> <3> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
Byte multiplication sixth part
The sixth part multiplies L-BTC amount (0xca9a3b) with the first byte of USDT amount (0x00), which is OP_0. This number can be made by adding individual numbers of 1, -1, 1, and -1. These numbers are provided in witness, and their additions are verified like the following:
OP_0 //first byte<1> <-1> <1> <-1> //powersOP_ADD OP_ADD OP_ADD OP_NUMEQUALVERIFY
If this passes, we verify that these four number provided in witness are the power of two, by providing their exponents in witness:
<1> <-1> <1> <-1> //powers<0> <0> <0> <0> //exponents<1> <1> OP_PICK OP_ABS OP_LSHIFT <5> OP_PICK OP_EQUALVERIFY<1> <2> OP_PICK OP_ABS OP_LSHIFT <6> OP_PICK OP_EQUALVERIFY<1> <3> OP_PICK OP_ABS OP_LSHIFT <7> OP_PICK OP_EQUALVERIFY<1> <4> OP_PICK OP_ABS OP_LSHIFT <8> OP_PICK OP_EQUALVERIFY
Then we shift L-BTC amount with each exponent, and add results together, leaving stack with OP_0 that can be interpreted as 0x00:
<1> <-1> <1> <-1> //powers<0xca9a3b> //L-BTC amount<0> <0> <0> <0> //exponents<4> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<5> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<6> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIF<7> OP_PICK <4> OP_PICK OP_LSHIFT
<9> OP_PICK <0> OP_LESSTHAN OP_IF OP_NEGATE OP_ENDIFOP_ADD OP_ADD OP_ADD
Final byte additions:
Now we have 6 multiplication results:
<0x00><0x40597307><0x22e2330e><0x503baa1f><0x7a292c1c><0x82357a0a>Let's concatenate the sixth multiplication result (0x00) with the first byte of the fifth multiplication result (0x40), and keep the remainder three bytes (0x597307) for the next addition, leaving stack with 0x0040:
<5> OP_ROLL <5> OP_ROLL OP_DUP <0> <1> OP_SUBSTR_LAZY OP_SWAP <1> <4> OP_SUBSTR_LAZY OP_TOALTSTACK OP_CATAdd fourth multiplication result (0x22e2330e) with the amount left from alternative stack (0x597307), then split first byte (0x7b) and send remainders (0x553b0e) to alternative stack, and then concatenate top two elements, leaving stack with 0x00407b:
<4> OP_ROLL OP_FROMALTSTACK OP_ADD OP_DUP <0> <1> OP_SUBSTR_LAZY OP_SWAP <1> <4> OP_SUBSTR_LAZY OP_TOALTSTACK OP_CATAdd third multiplication result (0x503baa1f) with amount left from alternative stack (0x553b0e), then split first byte (0xa5) and send remainders (0x76b81f) to alternative stack, and then concatenate top two elements, leaving stack with 0x00407ba5:
<3> OP_ROLL OP_FROMALTSTACK OP_ADD OP_DUP <0> <1> OP_SUBSTR_LAZY OP_SWAP <1> <4> OP_SUBSTR_LAZY OP_TOALTSTACK OP_CATAdd second multiplication result (0x7a292c1c) with amount left from alternative stack (0x76b81f), then split first byte (0xf0) and send remainders (0xe14b1c) to alternative stack, and then concatenate top two elements, leaving stack with 0x00407ba5f0:
<3> OP_ROLL OP_FROMALTSTACK OP_ADD OP_DUP <0> <1> OP_SUBSTR_LAZY OP_SWAP <1> <4> OP_SUBSTR_LAZY OP_TOALTSTACK OP_CATAnd finally, add first multiplication result (0x82357a0a) with amount left from previous step (0xe14b1c), then concatenate top two elements, leaving stack with 0x00407ba5f06381960a:
<1> OP_ROLL OP_FROMALTSTACK OP_ADD OP_CATOur multiplication result 0x00407ba5f06381960a matches our expected constant value.
This entire operation consumes 1200+ in bytes and 600+ in operations. Due to the 520-byte stack element size limit and 201 operations limit, this operation is divided into four parts and is assigned to four total covenants. These four covenants introspect an OP_RETURN output to coordinate the multiplication operation which can ultimately be validated by another covenant.
