The Truth behind BIP 16 and 17

A huge change to the underlying fundamentals of the bitcoin system are in the pipeline. I strongly recommend everyone to understand the issues before voting in any direction. Do not vote based on personalities but ideas.

Voting is based on mining power.

Doing nothing is voting for the current existing system.

Upgrading to the newest bitcoind or Bitcoin-Qt from git is voting for the BIP 0016 P2SH system.

Merging Luke’s branch or applying one of his patches is voting for BIP 0017 CHV.

Two proposals debated over are up for inclusion into bitcoin; P2SH (Pay To Script Hash) and CHV (CHECKHASHVERIFY). Neither are for transactions owned by multiple people (m-of-n transactions), which are already possible in the current bitcoin system and simply requires re-enabling.

Bitcoin (the word) simultaneously refers to the system, a protocol and one program written by Satoshi. The discussion is over a change to the bitcoin system and is highly fundamental, ergo the most important in the bitcoin system’s development history. It is a mistake that if it goes wrong could be destructive. A serious problem would need a network-wide upgrade of all nodes and would cause a blockchain fork. Bitcoin successfully survived one blockchain fork in its early history (August 2010) due to a serious bug. And it is claimed bitcoin could survive another.

Making a payment is in actuality specifying how that money can be spent. Your program creates a script which specifies how another user can spend those funds. We can group payments that use similar script code for specifying how they are spent into broad categories of payment types. The most common payment type is pubkey-hash which first appeared in block 728. The message of the script says “only the owner of the address <12higDjoCCNXSA95xZMWUdPvXNmkAduhWv> can spend these bitcoins I sent.” – replacing the address with the recipient of your payment.

Sara wants to pay Ash 10 BTC. Her bitcoin program takes 10 BTC from her address 12higDjoCCNXSA95xZMWUdPvXNmkAduhWv, creates a script saying “only the owner of 1PEsXxy7kVSPL3Sqw9q4HPkbM368tGTYcx can spend this 10 BTC.” and sends it to the bitcoin network. When Ash wishes to repeat the process, he can take those 10 BTC (because he owns that address) and specify new script code to tie up those bitcoins with a new address- the address of the recipient.

Script overview

Script consists of a series of operations and data.

enum class opcode{ raw_data = 0, special = 1, pushdata1 = 76, pushdata2 = 77, pushdata4 = 78, nop = 97, drop = 117, dup = 118, sha256 = 168, hash160 = 169, equal = 135, equalverify = 136, checksig = 172, codeseparator, bad_operation // There are other operations, but these are the most used};struct operation{ opcode code; data_chunk data;};typedef std::vector operation_stack;typedef std::vector data_stack;struct script{ operation_stack operations; data_stack stack;};

The script is a mini programming language that theoretically allows creative payment types. It is deliberately Turing incomplete to restrict the dangerous properties such as an attacker consuming resources looping forever.

The most common payment type (pubkey-hash) follows the same scheme of operations as:

DUP HASH160 EQUALVERIFY CHECKSIG

“hash of public key” is what a bitcoin address represents. An address is the human readable form, whereas pubkey-hash is the computer readable form.

For the programmers:

bool is_pubkey_hash_type(const operation_stack& ops){ return ops.size() == 5 && ops[0].code == opcode::dup && ops[1].code == opcode::hash160 && ops[2].code == opcode::special && ops[3].code == opcode::equalverify && ops[4].code == opcode::checksig;}

This means that in order to spent the money sent to me, I have to satisfy the demands- that I own the key to unlock the funds.

The output script (archaic name scriptPubKey) specifies the requisites for how funds will be unlocked:

DUP HASH160 EQUALVERIFY CHECKSIG

The input script (archaically called scriptSig) actually unlocks those funds:

When a transaction attempts to spend an output by pulling in the transaction’s new input, the scripting engine inside the bitcoin program will join the input script with the output script and execute them.

DUP HASH160 EQUALVERIFY CHECKSIGstack: (empty)

A stack is like a list of items. Think of a pile of papers with numbers written on them. You write the number of a friend (data) and put it on top of the stack. As you do things, you take papers off the stack or put new ones onto the stack.

The first two operations push two pieces of data to the stack. After pushing to the stack, our script looks like:

DUP HASH160 EQUALVERIFY CHECKSIGstack:

DUP duplicates the top item on the stack:

HASH160 EQUALVERIFY CHECKSIGstack:

HASH160 hashes the top item on the stack:

EQUALVERIFY CHECKSIGstack:

Next is another piece of data- the bitcoin address reversed into computer readable form. This item is added to the stack and then EQUALVERIFY is executed. If the does not match the one specified by the user who sent the bitcoins then the script will fail. We are now left with the final stage of the script’s execution.

CHECKSIGstack:

Using public-key cryptography, this final stage checks the digital signature of the transaction using the public key we just verified is correct to ensure the correctness of the transaction. If (and only if) this final stage passes, will the payment be accepted. Those interested in the details should examine my implementation of op_checksig(…).

Bitcoin Improvement Proposals

There are four functional fundamental implementations of the bitcoin protocol: the original Satoshi client, BitCoinJ by Mike Hearn, BitcoinJS by Stefan Thomas and libbitcoin by me (Amir Taaki). All the clients derive from or use these four original codebases such as bitcoin-qt (Satoshi), MultiBit (BitCoinJ), SafeBit (BitcoinJS) or subvertx (libbitcoin).

The fear was that the flourishing diversity of the bitcoin ecosystem would lead to many incompatible ad-hoc standards, and a poorly functioning bitcoin network. By having a process for formalised agreements among the implementations, we mitigate fracturing of the system.

The BIP (Bitcoin. Improvement. Proposal.) follows a general process as specified in BIP 0001.

Usually a proposed BIP should be discussed in the forums or mailing list. This step is to save the time for the champion of that BIP (author).The BIP champion requests a number to be reserved from the BIP editor. The editor may specify any optional prerequisites such as prior discussion.The BIP editor has the right to arbitrarily reject BIPs such as if the ideas are too vague or being technically unsound. Once accepted, the BIP is given a Draft status and a number.BIP statuses change depending on community consensus. Particularly important is agreement between the major groups participating in development of the bitcoin system.

The disagreement is between BIP 0016 by Gavin Andresen, and BIP 0017 by Luke Dashjr.

The BIP editor has their own personal thoughts about BIPs, but the BIP process is independent of their personal feelings. The editor should remain objective and gauge how to approve proposals based on the consensus. A standard is only as good as the people willing to implement it, and a large part of a standard is whether the major implementations agree to it.

Motivation

Both BIP 0016 and BIP 0017 are addressing the same issue. The issue is not enabling m-of-n transactions that need multiple people to spend (a common misconception) but barging the bulk of output script code into the input.

Barging the script data allows the usage of specialised bitcoin addresses using BIP 0013. Complex scripts can be represented by a short and more usable bitcoin address rather than having to copy paste a longer bitcoin address. The benefit is 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. Without this change addresses are 70 bytes or more.

Without:
57HrrfEw6ZgRS58dygiHhfN7vVhaPaBE7HrrfEw6ZgRS58dygiHhfN7vVhaPaBiTE7vVhaPaBE7Hr
With:
32higDjoCCNXSA95xZMWUdPvXNmkAduhWv

The longer address is inconvenient compared to the usual commonplace form.

It is generally agreed that the payee of the funds should not be responsible for the costs. Rather the recipient should. If the recipient demands crazy conditions for a payment, then they should bear the costs. It is not agreed whether making this change to bitcoin is worth the cost.

A strong argument for why this kind of change is needed, is that with complex scripts, the code specifying how that output is spent can be long. A transaction sending 1000 BTC and 1 BTC follow the same format, and there are a large number of unspent outputs. If the bulk of the script is in the output then the bulk of the data for a transaction is in the output.

Since most outputs are unspent, there would be blockchain-bloat because outputs would contain more data than needed. These changes attempt to decrease the blockchain size by keeping the data out until the output is spent by putting the bulk of the data in the input. If the script is a large or complicated script, then the burden of paying for it (in increased transaction fees due to more signature operations or transaction size) is shifted from the sender to the receiver.

With a transaction which requires multiple people to spend it (m-of-n transaction) this means high fees for the person who makes the transaction rather than the person who spends the transaction. These changes shift it the other way.

OP_EVAL

The original solution for addressing this was to take an existing operation NOP1 and redefine it to become a new operation in new clients; EVAL. NOP1‘s purpose is as a place-holder for future operations and currently does nothing.

This new operation would take the data on the current top of the stack and executes it as another script. This is dangerous because it allows loops if you make a script that keeps recreating and executing itself. The standard specified that EVAL has a maximum execution depth before it stops. The scripting system would need to keep a record of its execution depth. Russel O’Connor (roconnor) found a bug in the test implementation in late December to circumvent this restriction. A new fix was added.

During a private email discussion among developers on the 1st January, further problems were found out. Stefan Thomas discovered that if the arbitrary script is a piece of data which is the result of script, then what that script will be, is unknown until after the script has been executed. Since the script’s structure will be unknown, it would make it difficult to run static analysis. Stefan actually wrote code to exploit the EVAL proposal.

CHECKSIG operations are expensive. The code for validating transactions deliberately limits the number of CHECKSIGs. An attacker can create a transaction with hundreds of CHECKSIGs and perform a denial of service attack on a bitcoin node through the scripting system. Using static analysis we can predict beforehand the number of CHECKSIG operations and reject invalid insecure transactions. EVAL would make that check impossible.

The scripting system despite being a Turing incomplete system is a huge risk and has to be hugely controlled. IsStandard(…)‘s purpose it to limit the scripting system’s freedom to not be dangerous. EVAL introduced new risks from arbitrary code and had to be shelved.

Viewpoints

Gavin Andresen is the author of a new standard P2SH (BIP 0016). Miners have been asked to place the value of /P2SH/ in their blocks. On the 1st February if 55% of the blocks contain /P2SH/, the change will become live in the Satoshi client. Otherwise the voting date will be pushed back and the blockchain re-checked again later.

Luke Dashjr is the author of a competing proposal CHV (BIP 0017). Miners voting in favour of CHV, should place p2sh/CHV in their blocks.

A number of respectable developers are opposed to any changes. Another matter of contention is the schedule is rushed or too fast since real discussion began mid December. Gavin makes the point that without putting the software into practice, it may never reach fruition because of endless debate and discussion. That pointless discussion will continue endlessly and nothing will get done.

[Tycho] runs the largest pool of bitcoin miners; Deepbit. He will vote against the proposals and not contribute his power. He views the proposal as being too risky without the necessary due diligence.

[Tycho] believes the changes to be immature before they can move into the production environment. He objects on the ground that among developers there is no clear consensus.

I would like to add something about one of the reasons why I don’t want to be the FIRST to adopt P2SH: I don’t like doing beta tests in a production environment.

In last 2 days I already got 3 messages from Gavin about new bugs found in his implementation: one “minor bug” and one “major bug” (“one critical line was dropped in a merge and missed in my testing”). Also some coins were possibly destroyed in the process because a bug caused block fees to be lost.

There is a real chance of risk with these changes that are non-negligible. The question is whether the risk outweighs the reward. The risk is loosing the entire bitcoin market. The return is a better blockchain.

Mike Hearn who authored the BitCoinJ version which is the basis for MultiBit, and the android and iPhone bitcoin versions is against the changes also. Mike is worried that too many rushed through changes to the bitcoin system are going to result in an unmaintainable convoluted future system. A fundamental lesson of computer architecture design is that systems become more complex over time as their feature set expands. The best you can do is to mitigate its degradation by careful planning and caution.

Software architecture does not age gracefully. Software architecture degrades in direct proportion to the number of changes made to the software: bug fixes corrode the layering and new features stress design. … as the architecture degrades, maintenance and development become more difficult and at the end of that path is a legacy piece of software maintainable only by having an army of brute-force testers for every release, because nobody understands how the software works inside.
– The Architecture of Open Source Applications: Berkeley DB

A more complex system that is difficult for the designers to understand, can result in unsuspected bugs and security flaws. When a system is harder to fully comprehend, there is less scrutiny over its internal functioning.

These are both valid viewpoints which is why the decision is not so clear cut.

P2SH (BIP 0016)

We defined earlier that there are certain categories of scripts which make different payment types.

P2SH defines a new payment type that works with old non-P2SH enabled clients. When P2SH-enabled clients see see this payment type they invoke a special behaviour.

The biggest objection to P2SH is that this is special unexpected behaviour and is not elegant. The problem is that trying to deal with old clients while creating a new system is going to involve some form of ugly hacks. Satoshi had a great idea then dumped us with an incomplete system that is now in production with $50 million economy. It’s a delicate situation.

if 10 == 10: print ‘Hello’

The analogy is if a programming language, when running a program comparing 10 == 10 and printing ‘Hello’ instead decided to compute Fibonacci numbers. It recognises the format of the program, then does something completely different.

The actual new payment type scripts look like:

input script: { CHECKSIG}output script: HASH160 <20-byte-hash of data inside the {}s> EQUAL

Upon recognising that particular output script format, bitcoin will interpret that in a unique way. First the script will execute as normal, but then on completion, the top stack item will be popped off and executed as another script. Also the current stack is passed to the subscript when executing. If the subscript passes then the parent script also passes.

Begin:

script: {…data…} HASH160 <20-byte-hash of data inside the {}s> EQUALstack: (empty)

Special part:

Take input script as your stack.Remove top item from stack as script.Execute it.script: CHECKSIGstack:

Note that the input script is no longer treated like a script but a stack. The system will fail if the input script has any operations- it can only contain operations for pushing data.

All the arguments against BIP 0016 boil down to its aesthetic effects on the bitcoin system. Increasingly complex systems are harder to manage- potentially leading to bigger problems and issues down the line.

One bug was found in the P2SH implementation 4 days before voting was complete. No developer writes bug-free code, but [Tycho] sees this as a sign of the standard being premature.

SIGOPS limit

Supporters of P2SH tout its ability to increase the maximum number of SIGOPS (signature operations) in a block over CHV.

These are the possible signature operations:

CHECKSIGCHECKSIGVERIFYCHECKMULTISIGCHECKMULTISIGVERIFY

Scripts have a maximum size which is sufficient with the other operations to stop a denial of service attack. Pack several hundred CHECKSIGs or CHECKMULTISIGs inside scripts in a block and it causes the validating node to do far more work than necessary since it must compute the results of every single CHECKSIG/CHECKMULTISIG operation. A denial of service attack.

Satoshi added a restriction to the number of allowed SIGOPs in a block as a response. 20000 per block is the current limit. It is a huge number, but it may need to be raised in the future once bitcoin is performing several thousand transactions per second.

P2SH provides a way to hide these SIGOPs from Satoshi’s rule to allow a newer more precise method for counting them to be developed. This delays the time until the block level SIGOPs limit is raised from 20000 in the future. Raising the limit will be a blockchain forking event and a very difficult change.

There is a block size limit of 1000000 bytes. Assuming 1 transaction has an average of 10 output spends (high estimate; more usual is 2) and is around 200 bytes (very low estimate). The number of transactions per block is approximately 1000000 / 200 = 1000. Assuming 5000 transactions with 10 outputs, the total number of SIGOPs per block is 5000 * 10 = 50000. That is more the 20000 limit.

When the number of transactions starts reaching the block size limit, the SIGOPs count limit could start being a problem. However the block size limit itself would be an issue, and it is likely that a blockchain fork would be needed for raising the block size anyway.

P2SH does not solve this issue, but it buys more time.

CHV (BIP 0017)

Rather than introducing a new paradigm of executing a piece of data on the stack upon recognising a particular script schema, CHV (BIP 0017) uses an existing operation that seemed to be included for this purpose by Satoshi: CODESEPARATOR.

A new proposed operation CHECKHASHVERIFY (hence the name CHV) replaces NOP2. The NOP* series of operations were reserved by Satoshi for future extensions and new operations. In CHV, one of these reserved operations is adapted into the new operation.

input script: CODESEPARATOR CHECKSIGoutput script: <20-byte-hash of subscript> CHECKHASHVERIFY DROP

Where the subscript is everything from the CODESEPARATOR onwards.

CHECKSIG

There are two main differences with the other P2SH proposal.

CHV uses an existing operation to define a subscript rather than interpreting a piece of data from the script.CHV uses a new operation to define the script’s actions rather than implicitly recognising the schema and behaving in a special unexpected way.

It’s argued that CODESEPARATOR is a bad operation because it breaks the flow of the code. The operation exhibits certain oddities and its own weird corner cases. Before this proposal, there was a general consensus that this operation had no potential use following bugs made in an old Satoshi bitcoin client version.

CHV’s disadvantage over P2SH is nodes will accept any transactions spending an output as valid. To old clients it looks like a transaction that is spendable by anybody while P2SH requires the hashed data.

Note that P2SH will only be accepted by the network if more than 55% of the mining power is in favour. Because miners would not accept invalid transactions, nor build off of blocks containing invalid transactions, this should not be a problem for CHV if the majority of mining power remains in favour of it.

It is not a problem; once a CHV is spent, its security properties become equivalent to P2SH.

A minor issue is that old clients will not propagate CHV payments. The old clients will accept blocks with CHV payments, but they will not pass them onto other nodes in the network. This is not a problem as transaction propagation speed is usually far quicker than confirmation speed (especially with 6 confirms or more).

Rules and practicality

Realistically this divisive issue rests upon personal preference for how developers envision that complex systems are developed.

Special cases aren’t special enough to break the rules.
Although practicality beats purity.
– PEP 20 – The Zen of Python

Summarising:

P2SH introduces a complexity-inducing solution to a tough problem.CHV introduces a new operation code. Unexpected combinations of opcodes have been a problem in the past.Remain where we are with all of bitcoin’s imperfections and problems. Use 70+ character addresses for multiple person transactions instead of 20 character ones.

If Deepbit maintains their current stance of not voting for either P2SH or CHV, then the remaining part of the network will need to muster enough power to overcome Deepbit’s vote. Examining the current blockchain (28 Jan) we see a split of votes among P2SH and CHV. Assuming the current voting proportions remain steady, I predict a rejection of both new schemes.