OP CHECKSIGEX DRAFT BIP

  BIP: 22
  Title: OP_CHECKSIGEX
  Author: Mike Caldwell <mcaldwell@swipeclock.com>
  Status: Draft
  Type: Standards Track
  Created: 31-01-2012

Abstract

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.

Motivation

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.

This proposal goes out of its way expressly to avoid Turing completeness and to permit easy verification that Turing completeness is absent. In particular, 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.

Specification

The OP_CHECKSIG function is renamed to OP_CHECKSIGEX and termed check signature expression. The current OP_CHECKSIG takes two parameters: a signature and a public key; the redefined OP_CHECKSIGEX is extended such that its arguments are a list of n signatures along with a public key expression that consumes those signatures, and also which supports a subset of interpreted opcodes that are executed strictly on a new, separate sandbox stack known as the expression evaluation stack.

By retaining the same opcode, all existing transactions using OP_CHECKSIG (i.e. the vast majority of Bitcoin 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 the original OP_CHECKSIG, the public key portion is always 65 bytes. Under the extended 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 expression, whether 65 bytes or larger, constitutes an evaluation script that runs in a limited context, and only has access to an evaluation stack. An evaluation script strictly cannot read, push, pop, or otherwise reference anything on the stack(s) used in normal script processing. The evaluation stack shall be empty at the beginning of each execution of OP_CHECKSIGEX, and the OP_CHECKSIGEX operation has exactly two results: complete transaction failure, or validation success (with behavior identical to a successful OP_CHECKSIG as presently defined).

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. (In this context, "uncompressed" means that both the X and Y components of the public key are provided, as opposed to Y being flagged as computable from X and therefore omitted. In Bitcoin, each component is always 32 bytes; two 32-byte components plus the 0x04 prefix add up to 65 bytes.)

The fact that the existing OP_CHECKSIG expects public keys starting with 0x04 is exploited in this proposal, by defining 0x04 in OP_CHECKSIGEX in the context of evaluation to simply mean, "check one ECDSA signature in uncompressed format". Therefore, an existing transaction consisting of a single public key, single signature, and transactions currently utilizing OP_CHECKSIG would become interpreted as an OP_CHECKSIGEX opcode which contains an instruction (0x04) to check a single uncompressed signature - resulting in identical behavior.

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. In addition, these opcodes can be enabled in a context that greatly limits their reach, since they'll be running in an enclosed environment with highly limited data access.

The signature list is a simple binary blob of digital signatures concatenated together, each of which can either be present, or intentionally omitted (leaving a null placeholder entry in the list). As already is the practice in standard Bitcoin transactions, real signatures always begins with 0x30 plus a length byte which can be used to locate the end of the signature. A placeholder is hereby defined as 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.) Any time the evaluation script attempts to check a placeholder, no computational resources are expended on EC operations, but instead, a 0 is immediately pushed to the top of the evaluation stack.

Success of the evaluation script is denoted by a 1 at the top of the private evaluation stack. Once the evaluation script is completed and control returns to the outer script, the contents of the evaluation stack are abandoned.

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_NOP
• 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)

In addition,

• 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). Notably, there is no defined need for objects such as blobs of bytes or big integers, as all of these are provided as explicit parameters to the EVALOP_CHECKSIGU operation. 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

Backwards Compatibility

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).

Notes

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.