OP CHECKSIGEX DRAFT BIP
BIP: 22 Title: OP_CHECKSIGEX Author: Mike Caldwell <firstname.lastname@example.org> Status: Draft Type: Standards Track Created: 31-01-2012
This BIP describes a new "standard" transaction type for the Bitcoin scripting system, and defines additional validation rules that apply only to the new transactions.
The purpose of this proposal is to address some of the perceived shortcomings in BIP 0016 and BIP 0017, as well as objections that have been raised with respect to the difficulty in statically analyzing all of the potential scenarios that could arise. If adopted, it would be a complete replacement for both BIP 16 and BIP 17.
Like BIP 16, this proposal keeps the burden for supplying the conditions to redeem a transaction on the redeemer.
Like BIP 16 and BIP 17, this proposal ensures that payments to multisig addresses can be accomplished with addresses in the customary format. In other words, this proposal provides the benefit of allowing a sender to fund any arbitrary transaction, no matter how complicated, using a fixed-length 20-byte hash that is short enough to scan from a QR code or easily copied and pasted.
Unlike BIP 16 and BIP 17, this proposal creates no new transaction types.
Unlike BIP 16 and BIP 17, this proposal is believed to create no new scenarios where a "stealing bot" could be implemented to grab transactions created under the new standard from the view of the old clients.
Unlike BIP 16, this proposal creates no new types of script that must be recognized as a special case by design (referred to in BIP 16 as "ugly").
Unlike BIP 17, this proposal requires no reliance on the redefinition of OP_NOP opcodes to operations that must trigger failure, where they would never trigger failure under their prior definitions.
It is expected to be fairly easy to conclude at a glance that this proposal does not accidentally afford Turing-completeness to scripts, because it proposes creation of an extra sandbox stack whose access is exclusive to evaluation functions. This evaluation stack is a completely new stack that is independent of the regular and "alt" stacks defined in the Bitcoin scripting system.
In this proposal, all existing transactions become normal cases of an extended opcode. No changes are made to the way new transactions are sent, only how they are redeemed.
The OP_CHECKSIG function is renamed to OP_CHECKSIGEX and termed check signature expression, and extended such that its arguments are a list of signatures along with a public key expression which supports a subset of opcodes that are executed on a separate sandbox stack known as the expression evaluation stack.
By retaining the same opcode, all existing transactions become OP_CHECKSIGEX transactions. Specifically, they become a specific case of OP_CHECKSIGEX: one which happen to contain exactly one signature and one public key to be validated. Thus, they retain identical behavior as before the redefinition.
As OP_CHECKSIGEX, the function will continue to pop two parameters from the stack: one representing public key(s), and the other representing signature(s). Under OP_CHECKSIG, the public key portion is always 65 bytes. Under OP_CHECKSIGEX, the public key portion may be greater than 65 bytes, this would represent the multi-signature formula supplied at redemption.
A public key portion greater than 65 bytes is a script that only has access to an evaluation stack, and cannot read or reference anything on the stack(s) used in normal script processing. The evaluation stack shall be empty at the beginning of the execution of OP_CHECKSIGEX.
It shall be noted that in Bitcoin, all 65-byte public keys begin with the byte 0x04, which is a constant that denotes an uncompressed public key. This fact is exploited in this proposal, by defining 0x04 in the context of evaluation to simply mean, "check one signature in uncompressed format". Therefore, an existing transaction consisting of a single public key, single signature, and OP_CHECKSIG would become interpreted as an OP_CHECKSIGEX opcode which contains an instruction (0x04) to check a single uncompressed signature.
By including a subset of opcodes specifically turned on for OP_CHECKSIGEX, the multi signature functionality can be included in a reduced "expression" context without the risk of adding Turing-completeness to the scripting engine, nor the risk of the ability of scripts to modify themselves.
The signature list is a simple heap of signatures, each of which can either be present, or intentionally omitted (leaving a null placeholder entry in the list). A real signature always begins with 0x30 plus a length byte which is used to establish the end of the signature. A placeholder is a single 0x00 byte. A placeholder is used to denote that a particular signature is absent and not needed. (For example, an (A AND B) OR C transaction, where only C is provided, would have two placeholders in the list to represent A and B.)
Proposed opcodes to be supported in evaluation environment
The following opcodes would be supported in an evaluation environment. They would not necessarily need to be enabled in the environment of regular script processing (and in fact ought not to be). Thus, they have been prefixed as EVALOP_ instead of OP_, to show they are different, even if the same constants are chosen to represent these as the corresponding OP_ version.
- EVALOP_CHECKSIGU (opcode strictly defined as 0x04) - Check a single uncompressed ECDSA signature. The U stands for uncompressed. The next 64 bytes are the X and Y coordinates of the public key, and one signature is pulled from the signature list. Push 1 or 0 on the stack to denote success or failure.
- EVALOP_INVERT - turn a 1 on top of the eval stack to a 0 and vice versa.
- EVALOP_AND - pop two items off eval stack, if both 1 then push 1, else push 0.
- EVALOP_OR - pop two items off eval stack, if either 1 then push 1, else push 0.
- EVALOP_ADD - pop two items off eval stack, push sum.
- EVALOP_DUP - duplicate top item on stack.
- Comparison operators (equality, less than, greater than, etc.)
- Ability to push constants 0-75 (with the exception of the repurposed opcode 0x04, which must be handled via a replacement opcode or via EVALOP_PUSHDATA1)
- Operations expecting a 1 or 0 on the top of the stack shall cause transaction failure if the stack does not contain these elements or if they are not 1 or 0.
- Operations shall be explicitly defined as unsigned 32-bit arithmetic, with overflows explicitly defined as causing transaction failure.
- Note that none of the operations defined thus far involve stack operations involving anything other than scalar 32-bit unsigned integers (assuming "true" and "false" are denoted as 1 and 0). In the absence of a well-articulated need to utilize any other data type in this limited evaluation context, it is advisable to limit the functionality of the evaluation stack such that it only holds 32-bit unsigned integers.
Examples of use cases
All of these use cases assume the standard transaction format which is recited as follows, but modified such that pubKeyHash is called pubKeyExHash (public key expression hash), and pubKey is called pubKeyEx (public key expression).
Sending funds: OP_DUP OP_HASH160 <pubKeyExHash> OP_EQUALVERIFY OP_CHECKSIGEX Redeeming funds: <sigs> <pubKeyEx>
A standard transaction as is known now. This transaction leaves the evaluation environment with a 1 on the top of the evaluation stack, resulting in OP_CHECKSIGEX returning true.
<sigs> - contains a single signature. <pubKeyEx> - contains a single public key, i.e. 0x04 + xy i.e. EVALOP_CHECKSIGU + xy
A two party, A and B transaction.
<sigs> - contains two signatures, binary concatenated together <pubKeyEx> contains: EVALOP_CHECKSIGU + x1y1 + EVALOP_CHECKSIGU + x2y2 + EVALOP_AND
An (A AND B) OR C, redeemed using signatures A and B
<sigs> - contains two signatures and one placeholder <pubKeyEx> contains: EVALOP_CHECKSIGU + x1y1 + EVALOP_CHECKSIGU + x2y2 + EVALOP_AND + EVALOP_CHECKSIGU + x3y3 + EVALOP_OR
An (A AND B) OR C, redeemed using only signature C
<sigs> - contains two placeholders and one signature <pubKeyEx> contains: EVALOP_CHECKSIGU + x1y1 + EVALOP_CHECKSIGU + x2y2 + EVALOP_AND + EVALOP_CHECKSIGU + x3y3 + EVALOP_OR
An m-of-n transaction, requiring (for example) 5 out of 10 signatures
<sigs> - contains 10 items, a combination of signatures and placeholders <pubKeyEx> contains: EVALOP_CHECKSIGU + x1y1 + 9 repetitions of: EVALOP_CHECKSIGU + xnyn + EVALOP_ADD + (constant 5) + EVALOP_GREATERTHANOREQUAL
New transactions are non-standard to old implementations. But old implementations will generate transactions that are fully compatible with the new format. Regardless, old implementations will be rendered incompatible once such extended transactions appear on the network.
A suggested implementation is to program the client such that the functionality is enabled only on Testnet, and on the main Bitcoin network once a certain level of voting consensus has been established into the block chain. So long as the functionality is disabled, OP_CHECKSIG shall fail so long as the expected parameters of one single signature and one single private key are provided.
Avoiding Turing completeness surprises
In order to minimize the possibility of a later discovery of a Turing complete script engine, the following implementation details are recommended and/or required for implementers.
The implementation of the evaluation script processor SHOULD be implemented as a simple nested loop within the outer script processor. The evaluation script processing SHOULD NOT be implemented as a recursive call to the same loop that handles the outer script operations.
The inner evaluation script processing loop SHOULD NOT contain any references or use any pointers to the stacks belonging to the outer loop. The inner evaluation script processing loop MUST NOT provide any access whatsoever to the stacks used by the outer loop - not read access, not write access. The inner processing loop MUST receive as its sole inputs the two binary blob parameters (sigs and pubKeyEx) that were popped off the stack, along with any information incidental to validating signatures (i.e. the computed hash of the transaction script). The inner processing loop MUST NOT be able to return any data to the outer loop that invoked it - other than transaction failure (which terminates script processing) or validation success (identical in behavior to the current implementation of OP_CHECKSIG returning success).
This was once informally proposed by Casascius.
As it was understood by Casascius, the proposal was informally rejected, mainly on the notion that it would be silly or unclean to have a script interpreter of one type embedded within a script interpreter of another type.
This proposal is being reintroduced as a BIP simply because, due to heightened concern regarding Turing completeness surprises - where a script may be able to modify its own behavior - having separate partitioned storage and operations for two different types of script content may be seen as a viable answer to the concern. The partitioning, of course, referring to the main script - which has access to control flow operations (if/then/else), as well as the ability to modify scripts run in the "evaluation context" and then that separate "evaluation" context - consisting solely of code that has access to nothing beyond its own private data, the signature validation function, and basic arithmetic options.
It is believed that implementation of this BIP would be relatively easy, with changes to code being confined strictly to the addition of a single new loop that runs with in the OP_CHECKSIG[EX] portion of the script interpreter.