BIP: ? Title: Scripting System in Merkelized Abstract Syntax Tree Author: Johnson Lau <jl2012@xbt.hk> Status: Draft Type: Standards Track Created: 2016-04-20
This BIP defines the scripting system in Merkelized Abstract Syntax Tree (BIP114). It re-enables some of the previously disabled opcodes, introduces new opcodes, and defines expandable opcodes for future extension.
Bitcoin uses a script system to specify the conditions for redemption of transaction outputs. It is composed of 186 opcodes, each represented by an one-byte unsigned integer from 0x00 to 0xb9. Since the first release of Bitcoin in 2009, 19 opcodes including VER, VERIF, VERNOTIF, RETURN, CAT, SUBSTR, LEFT, RIGHT, INVERT, AND, OR, XOR, 2MUL, 2DIV, MUL, DIV, MOD, LSHIFT, and RSHIFT, were disabled due to security reasons. Presence of a disabled opcode will terminate the script evaluation immediately and return a failure (even in an unexecuted conditional branch).
Some of the disabled opcodes could be useful, but unfortunately it is impossible to re-enable these in the original scripting system with a softfork. It is also not possible to introduce new stack-manipulating opcodes to the original system with a softfork. For example, new opcodes including CHECKLOCKTIMEVERIFY (BIP65) and CHECKSEQUENCEVERIFY (BIP112) could either return a failure immediately, or do nothing, and are usually followed by an DROP to clean up the stack.
Under the witness program version byte system, it is now possible to introduce completely novel scripting system with a softfork. The new semantics will be confined to a particular version of witness program without affecting any existing scripting system. As part of Merkelized Abstract Syntax Tree (BIP114) softfork, this BIP will:
- re-enable
CAT,SUBSTR,LEFT,RIGHT,INVERT,AND,OR,XOR,LSHIFT, andRSHIFT; - introduce new opcodes:
DUPTOALTSTACK (0xba),DUPFROMALTSTACK (0xbb),SWAPSTACK (0xbc),SWAPCAT (0xbd), andRESIZE (0xbe); - define expandable opcodes for future softforks of stack manipulating opcodes:
EXPAND1 (0xd0)toEXPAND32 (0xef).
In the following, xn represents the top-n item on the stack. For example, x1 is the top stack item, and x2 is the second-to-top item.
CAT and SWAPCAT will remove the top two stack items and push the concantenated string onto the stack. If x2 is "abcd" and x1 is "efgh", CAT will return "abcdefgh" while SWAPCAT will return "efghabcd". The script will fail if the stack has less than two items or the total size of the concantenated string is bigger than TBD bytes.
SUBSTR will remove the top three stack items and push a substring of x3 onto the stack, with x2 as the starting position, and x1 as the length of the substring. For example, if x3 is "abcdefghij", x2 is 3 and x1 is 4, the returned string is "defg". The script will fail if the stack has less then three items, x2 or x3 is negative, x2 is not smaller than the size of x1, and x2 + x3 is bigger than the size of x1.
LEFT will remove the top two stack items and push the x1 leftmost characters of x2 onto the stack. For example, if x2 is "abcdefghij" and x1 is 6, the returned string is "abcdef". An empty vector is returned if x1 is 0, and x2 is returned if x1 is not smaller than the size of x2. The script will fail if the stack has less than two items or x1 is negative.
RIGHT will remove the top two stack items and push the x2 with the x1 leftmost characters removed onto the stack. For example, if x2 is "abcdefghij" and x1 is 6, the returned string is "ghij". x2 is returned if x1 is 0, and an empty vector is returned if x1 is not smaller than the size of x2. The script will fail if the stack has less than two items or x1 is negative.
INVERT will flip the bits of the top stack item. For example, 0xbeef (0b1011111011101111) will become 0x4110 (0b0100000100010000). The script will fail if the stack is empty.
AND, OR, XOR will remove the top two stack items and push the boolean and, or, xor of the two values onto the stack, respectively. For example, if the values are 0xdead (0b1101111010101101) and 0xbeef (0b1011111011101111):
ANDwill return 0x9ead (0b1001111010101101),ORwill return 0xfeef (0b1111111011101111),XORwill return 0x6042 (0b0110000001000010).
LSHIFT will remove the top two stack items. The x2, interpreted as a little-endian string, will be left-shifted by x1 bits and the result (with most significant zero bytes removed) is pushed onto the stack. For example, if x2 is 0xbeef00 (0b101111101110111100000000) and x1 is 11, the result is 0x00f07d07 (0b00000000111100000111110100000111). The script will fail if the stack has less then two items, or x1 is negative, or size of the result is potentially larger than TBD bytes.
RSHIFT will remove the top two stack items. The x2, interpreted as a little-endian string, will be right-shifted by x1 bits and the result (with most significant zero bytes removed) is pushed onto the stack. For example, if x2 is 0xbeef00 (0b101111101110111100000000) and x1 is 11, the result is 0x1d (0b00011101). The script will fail if the stack has less then two items or x1 is negative.
RESIZE will remove the top two stack items. The x2 will be resized to x1 bytes and pushed onto the stack. Zero-padding or truncation will be made at the right hand side. For example, if x2 is 0xdeadbeef, x1 = 6 will return 0xdeadbeef0000, x1 = 4 will return 0xdeadbeef, x1 = 2 will return 0xdead, and x1 = 0 will return an empty vector. The script will fail if the stack has less than two items, or x1 is negative, or x1 is greater than TBD.
DUPTOALTSTACK will copy the top main stack item onto the top of the alt stack. The main stack is not modified.
DUPFROMALTSTACK will copy the top alt stack item onto the top of the main stack. The alt stack is not modified.
SWAPSTACK will swap main stack and alt stack.
EXPAND1 to EXPAND32, when executed, will remove all items in the stack and leave a single TRUE value, terminate the script evaluation and return a success immediately. They are reserved for future softfork of new opcodes.
The following scripts will pass:
EXPAND1 (the empty stack is replaced by a single TRUE value) 0 EXPAND1 (the FALSE stack is replaced by a single TRUE value) 1 2 EXPAND1 (the stack with superfluous items is replaced by a single TRUE value) EXPAND1 RETURN (the script passes before RETURN is executed) EXPAND1 VERIF (the script passes before VERIF is executed) 0 IF RETURN ELSE EXPAND1 ENDIF (RETURN is in an unexecuted branch) 0 IF RETURN ELSE EXPAND1 (IF without ENDIF, EXPAND1 executed)
The following scripts will fail:
RETURN EXPAND1 (script failed before EXPAND1 is executed) 0 IF EXPAND1 ELSE RETURN ENDIF (EXPAND1 is in an unexecuted branch) 0 IF VERIF ELSE EXPAND1 ENDIF (VERIF is executed even in an unexecuted branch) 0 IF EXPAND1 ELSE 1 (IF without ENDIF, EXPAND1 not executed)
It has been proposed that an opcode verifying a pair of private and public key could be useful for improving the privacy of payment networks and facilitating cross-blockchain transactions.[1][2] The same effect could be archived with CAT re-enabled. For example, Bob has the private key X. Alice would like to pay Bob some bitcoins for this private key. They will agree to a random secret nonce k, and calculate R, in the same way as signing a transaction. Alice will pay to the following MAST script:
Branch 1: SIZE <R-length + 1> ADD <0x30> SWAPCAT <0x02|R-length|R> CAT SWAPCAT <X pubkey> CHECKSIGVERIFY <Bob pubkey> CHECKSIG Branch 2: "24h" CHECKSEQUENCEVERIFY DROP <Alice key> CHECKSIG
Bob has to redeem the output within 24 hours using the following signature:
<Bob sig> <0x02|S-length|S|sighashtype>
The script will be evaluated as:
Stack: Operation: <Bob sig> <0x02|S-length|S|sighashtype> SIZE <Bob sig> <0x02|S-length|S|sighashtype> <S-length + 3> <R-length + 1> <Bob sig> <0x02|S-length|S|sighashtype> <S-length + 3> <R-length + 1> ADD <Bob sig> <0x02|S-length|S|sighashtype> <Total length> <0x03> <Bob sig> <0x02|S-length|S|sighashtype> <Total length> <0x03> SWAPCAT <Bob sig> <0x02|S-length|S|sighashtype> <0x03|Total length> <0x02|R-length|R> <Bob sig> <0x02|S-length|S|sighashtype> <0x03|Total length> <0x02|R-length|R> CAT <Bob sig> <0x02|S-length|S|sighashtype> <0x03|Total length|0x02|R-length|R> SWAPCAT <Bob sig> <0x03|Total length|0x02|R-length|R|0x02|S-length|S|sighashtype> <X pubkey> <Bob sig> <X sig> <X pubkey> CHECKSIGVERIFY <Bob sig> <Bob pubkey> <Bob sig> <Bob pubkey> CHECKSIG <1>
With k, S and sighash, Alice (and only Alice) can recover the private key X with the well-known k-reuse exploit.[3]
It may also be done using SUBSTR, but is less space efficient:
DUP <2> <R-length + 2> SUBSTR <0x02|R-length|R> EQUALVERIFY <X pubkey> CHECKSIGVERIFY <Bob pubkey> CHECKSIG
Alice and Bob would like to bet against each other without third party arbitration. Each of them will generate a secret nonce (Secret-A and Secret-B respectively). In one funding transaction, they will create the following outputs, each contributing 2.1BTC:
Output 1 (1.1BTC) Branch 1: HASH160 <Secret-A hash 160> EQUALVERIFY <Pubkey-A> CHECKSIG Branch 2: "24h" CHECKSEQUENCEVERIFY DROP <Pubkey-B> CHECKSIG
Output 2 (1.1BTC) Branch 1: HASH160 <Secret-B hash 160> EQUALVERIFY <Pubkey-B> CHECKSIG Branch 2: "24h" CHECKSEQUENCEVERIFY DROP <Pubkey-A> CHECKSIG
Output 3 (2 BTC) Branch 1: 2DUP HASH160 <Secret-B hash 160> EQUALVERIFY HASH160 <Secret-A hash 160> EQUALVERIFY HASH256 SWAP HASH256 XOR <255> RSHIFT VERIFY <Pubkey-A> CHECKSIG Branch 2: 2DUP HASH160 <Secret-B hash 160> EQUALVERIFY HASH160 <Secret-A hash 160> EQUALVERIFY HASH256 SWAP HASH256 XOR <255> RSHIFT NOT VERIFY <Pubkey-B> CHECKSIG Branch 3: <Pubkey-B> CHECKSIGVERIFY <Pubkey-A> CHECKSIG
Before signing the funding transaction, they will sign a refund transaction using the Branch 3 of Output 3, with a relative lock-time of 48 hours, paying 1 BTC to each.
After the funding transaction is confirmed, they have to reveal the secret nonce within 24 hours.
Based on the secret nonce, only one of the Branch 1 and 2 in Output 3 could be valid. If Bob is the winner, he will redeem the Branch 2 of Output 3 using the following signature within 48 hours:
<Sig-B> <Secret-A> <Secret-B>
Alice and Bob will also redeem his/her 1.1 BTC in Output 1 and Output 2 within 24 hours, using the following signatures:
<Sig-A> <Secret-A> <Sig-B> <Secret-B>
If either one becomes uncooperative and fails to reveal the secret within 24 hours, the other one will be able to redeem totally 2.2 BTC from Output 1 and Output 2, and get the 1 BTC refund from Output 3 after 48 hours. The collateral makes sure that any rational player must be cooperative, without the need of third pary arbitration. Unlimited number of bets may be done inside a payment channel and only the final balance will be recorded in the blockchain.
As a soft fork, older software will continue to operate without modification while not be able to use any of the new opcodes. Non-upgraded nodes, however, will consider MAST programs as anyone-can-spend scripts. Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion.
This BIP should be deployed with BIP114 using version-bits BIP9. Exact details TBD.
Re-enabled opcodes were mostly implemented by the Elements Project: https://www.elementsproject.org/
https://github.com/jl2012/bitcoin/tree/segwit_mast
- ^ https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-February/012436.html
- ^ http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011827.html
- ^ https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
This document is placed in the public domain.