Progress pill
Technical development

The battle for Pay to Script Hash

Bitcoin's Pioneering Era

The battle for Pay to Script Hash

  • Development of Bitcoin-Qt
  • Bitcoin programmability
  • Multisignature
  • OP_EVAL: run a script within a script
  • OP_EVAL's shortcomings
  • Pay to Script Hash
  • Luke-Jr's reaction
  • Debate among developers
  • Miner signaling
  • BIP 30: correction of duplicate transactions
  • Activating Pay to Script Hash
  • The first major disagreement
After Satoshi Nakamoto's departure, software development was taken over by the community, which had to coordinate under Gavin Andresen's supervision. In particular, Bitcoin's programmability had to be improved, as this had been temporarily restricted by the introduction of relay rules on the network.
In the winter of 2011-2012, a controversy arose around the implementation of multisignature in Bitcoin. It concerned, among other things, the scheme known as "Pay to Script Hash", or P2SH. Pete Rizzo and Aaron van Wirdum would call this conflict "the Battle for P2SH". This was the first major dispute over the protocol's evolution, and the first to raise the question of governance.
In this chapter, we look back at this unique episode in Bitcoin's technical history. First, we'll analyze the development of the software and the idea of the multisignature. We'll then look at the various proposals for implementing this technique, starting with OP_EVAL and P2SH. Finally, we'll talk about how Pay to Script Hash was activated, despite the many difficulties encountered.

Development of Bitcoin-Qt

Following the release of version 0.4 of the software on September 23, which marked Gavin Andresen's takeover as main maintainer, development of the main Bitcoin implementation continued. In particular, a new graphical interface for the software appeared: Bitcoin-Qt, which was developed by Wladimir van der Laan from June onwards. It was based on the Qt graphics framework, which replaced the wxWindows library originally used by Satoshi. The interface was included in the main branch of the code on September 26 and became the official graphical appearance of the software in version 0.5, released on November 21. From then on, the software was called Bitcoin-Qt/bitcoind, or even Bitcoin-Qt for short (bitcoind being the daemon).
Capture of Bitcoin-Qt 0.5.2 in February 2012 (source: JimNelin for Wikimedia)
Gavin is still the project leader, but he was helped by several people. As of October 2011, Bitcoin's "titular" developers (i.e. those listed on Bitcoin.org) are Gavin Andresen, Pieter Wuille, Nils Schneider, Jeff Garzik and Wladimir van der Laan. These programmers were supposed to represent Bitcoin on a technical level, and could be contacted by e-mail. They were maintainers, who benefited from write access to the GitHub repository. Gregory Maxwell joined in February 2012, and Nils Schneider stopped contributing in May of the same year. The resulting team of developers would remain in place until 2014.
"The Gavinator": drawing of Gavin Andresen burning bills, made by Shazow in April 2011 (source: archive from BitcoinTalk)
At the same time, the system of Bitcoin improvement proposals, introduced by Amir Taaki in September 2011, was beginning to bear fruit. The first BIPs were written by the end of the year. This is the case, for example, of BIP 10, which was published on October 28 by Alan Reiner, the developer of the Armory wallet.
On January 9, 2012, a certain David Perry, known as Enmaku on the forum, published a visualization of the software's development progress, made using a tool called Gource. It showed the contributions made by developers to the software: it began with the actions of Satoshi Nakamoto and Martti Malmi, continued with the growing role taken by Gavin Andresen from July 2010, and showed the complexification of the code that lead to an explosion of development from April 2011.
Visualization of Bitcoin software contributions between August 2009 and September 2012

Bitcoin programmability

Bitcoin features an internal programming system. As we discussed in the course dedicated to the creation of Bitcoin, Satoshi Nakamoto implemented this system right from the start, considering that his model was "set in stone for the rest of its lifetime". He wrote thus in June 2010:
The design supports a tremendous variety of possible transaction types that I designed years ago. Escrow transactions, bonded contracts, third party arbitration, multi-party signature, etc. If Bitcoin catches on in a big way, these are things we'll want to explore in the future, but they all had to be designed at the beginning to make sure they would be possible later.
This range of possibilities was of deep interest to a number of people, not least Mike Hearn. The latter discussed it with Satoshi in private correspondence in 2011. Over the summer, Mike highlighted "distributed contracts" on Bitcoin's wiki, where he gave several examples such as anti-spam, escrow, collateral contracts, external oracles or atomic exchanges. He also added a reference to Nick Szabo's seminal 1997 article on smart contracts.

Multisignature

Multisignature, is a way of requiring several signatures for an expense. It forms the cornerstone for the deployment of contracts involving several people. This technique would be useful for securing funds, which, with the increase in piracy, is a very important issue these days. It could also be used in escrow contracts, making economic exchanges safer for the seller. Such contracts were indeed in demand by users, as evidenced by the existence of Gavin Andresen's escrow service, ClearCoin, between December 2010 and summer 2011.
Bitcoin's scripting language contains a transaction code, OP_CHECKMULTISIG, which allows M signatures to be required among N participants to authorize an expenditure, with M ≤ N. The public keys of any signatories are written to the transactional output lock script. Any subset of M signatures can unlock the document containing the script.
Interestingly, the OP_CHECKMULTISIG implementation contains a bug. It was discovered on June 30 by a certain Bobby Groff (aka Groffer), who was trying to integrate an escrow mechanism into the software. He wrote that the operator "drops one too many items from the stack", so "to push a dummy value to work around that". However, this bug cannot be corrected without modifying the protocol and branching the chain. This is why it will remain in the code after all.
On August 23, 2011, a few days after the New York conference, Gavin Andresen initiated the discussion about multisignature on the BitcoinTalk forum and on the bitcoin-development list. He wanted to standardize transactions involving multiple signatories, which he described as "the fastest path to very secure, very-hard-to-lose bitcoin wallets". Since December 2010, only two schemes were considered standard: P2PK and P2PKH. The idea was to add a raw multisignature scheme, where the number of participants can reach a maximum of 3.
Gavin would like the public keys involved to be used as addresses (as in the case of P2PKH). But these addresses wouldn't be supported by the clients anyway. So, at the risk of releasing an incompatible client, he proposed to "do things right in the first place, implement or enable opcodes so the new bitcoin addresses can be small, and schedule a block chain split" for a few months later. Driven by a sense of urgency, he favored rapid action, explaining that his "biggest worry" was that people would become complacent in the debate and that "there is still no consensus" after six months.
Following Gavin's message, Casascius proposed to modify the OP_CHECKSIG operator (the one used to check normal signatures) so that it takes multisignature scripts into account. Addresses can then be the hash of the script, and the entire script is provided when spending, just as the public key is in the case of spending a P2PKH output. He reformulated this proposal a month later. On October 1, a certain Jim Babcock, software developer and rationalist, made a similar proposal. Their description inspired the mysterious Nicolas van Saberhagen, alias ByteCoin, who conceived a new operating code called OP_EVAL on the night of October 1 to 2. Gavin Andresen made a relatively equivalent proposal (with BEGIN_DIGEST and END_DIGEST operators) at the same time. However, it's OP_EVAL that came out the winner from this abundance of ideas.

OP_EVAL: run a script within a script

The OP_EVAL operator is used to execute a script within a script. It is executed at the end of the locking script to assess the validity of the script supplied, whose hash is compared with the given fingerprint. This allows any script to be executed.
Technical operation of the OP_EVAL operator (source: ByteCoin on BitcoinTalk)
This involves adding an instruction to the scripting language, which requires a modification to the protocol, and therefore a separation of the network if everyone doesn't update, leading to an eventual chain split. However, on October 2, Gavin discovered a way of avoiding such a situation, and wrote on IRC:
I'm probably reading the code wrong, but I think OP_EVAL wouldn't cause a blockchain split!
His idea is based on a feature of Bitcoin's internal programming language: the OP_NOP operators added by Satoshi in summer 2010, which are silent instructions that don't invalidate the script they're in. These allow "backwards-compatible" protocol modifications to be made for older versions of the software, ensuring that only one string survives, in cases where the computing power applying it is in the majority. These modifications will later be referred to as soft forks. It is thus possible to transform OP_NOP1 into OP_EVAL, and arrange for the change to be applied by mining pools.
Other members of the technical community were quick to validate Gavin's discovery. In particular, Gregory Maxwell explained that "Gavin's point that EVAL can be done without a split blew his mind".
Two weeks later, on October 19, Gavin Andresen wrote three Bitcoin enhancement proposals, which were promptly hosted on the Bitcoin.it wiki:
  • The BIP 11, which describes raw multisignature scripting schemes;
  • The BIP 12, which describes the OP_EVAL instruction and the corresponding script schema;
  • The BIP 13, which describes address formatting for OP_EVAL,: "This BIP describes a new type of Bitcoin address to support arbitrarily complex transactions".
Activation of BIP 12 was scheduled for February 1, 2012, provided that 50% of miners signal their support by inserting the string OP_EVAL in the blocks they produce before January 15. If this threshold was not reached, the rollout would be postponed to a later date. It was to ensure that the upgrade goes smoothly, without a competing branch being created.

OP_EVAL's shortcomings

However, the OP_EVAL operator does have its shortcomings. These were highlighted mainly by Russell O'Connor, a Canadian computer scientist working at Radboud University in Nijmegen, the Netherlands.
On the one hand, the obvious flaw is recursiveness. Bitcoin's scripting system is designed not to loop and to stop cleanly (it's not Turing-complete). A naive implementation makes recursion possible by running the program until the machine can't keep up (the example given by Gavin is <OP_DUP OP_EVAL> OP_DUP OP_EVAL). We therefore need to add a limit to the depth of recursion.
However, the risk of a bug remained. On December 27, 2011, Russell O'Connor did a code review and found a recursion flaw. He added the following remark to his report:
More generally, this OP_EVAL is a very large change that clearly hasn't been vetted nearly enough. It took me all of 70 minutes of looking to find this bug. You guys are not ready to implement this. (...) You guys need to stop what you are doing and really understand Bitcoin.
On the other hand, even if the recursion is fixed, OP_EVAL makes it impossible to analyze the script prior to execution. As a result, one cannot count the signature operators (which are resource-intensive) before executing the script itself.
Russell O'Connor pointed out the lack of analysis capabilities offered by OP_EVAL. On December 29, he wrote that "with the OP_EVAL proposal there is no way to statically analyze the script (say to count the number of uses of OP_CHECKSIG or OP_MULTICHECKSIG or other analysis) without actually executing the script".
On the bitcoin-development list, he asked Gavin to push back the activation date "by two months", pointing out that "OP_EVAL just wasn't ready yet". In the same vein, Alan Reiner reminded developers that they are tinkering with ‘an object in "something worth over $20 million" (original: "I would like to remind everyone that we/you are messing with a $20+ million dollar thing"), referring to the aggregate value of all bitcoins, and that "there's more than just a piece of software at stake".
It was therefore decided to study the other proposals before making any decisions. One was OP_CODEHASH operation code, designed by Russell O'Connor himself, which required the creation of a virtual machine-specific stack to preserve the script. Another was the OP_CHECKEDEVAL instruction, designed by Pieter Wuille.

Pay to Script Hash

The principle behind OP_EVAL is to pay to a script hash and provide the script itself when unlocking the funds. On January 2, 2012, Gavin Andresen came up with the idea to take up this principle, with the exception that the virtual machine would recognize the form of the script. Amir Taaki commented, writing that "the idea is a hack" but that he "likes it". Gavin titled his idea "pay to script hash", a name modeled on the Pay to Public Key Hash (P2PKH) scheme, which is a standard form of script.
The next day, January 3 at 21:00 UTC, a meeting was organized on the IRC channel #bitcoin-dev by Amir Taaki, to get the developers to agree. A large majority were in favor of Pay to Script Hash, including Russell O'Connor. Gavin would describe the proposal as "a simpler, safer-but-less-powerful alternative for creating bitcoin addresses for multisignature and future more-complex transactions".
Gavin Andresen wrote a draft of BIP that evening, and it was put online the following day, as number 16. In the document, he conceded that "recognizing one 'special' form of scriptPubKey and performing extra validation when it is detected is ugly", but explains that "the alternatives are either uglier, are more complex to implement, and/or expand the power of the expression language in dangerous ways". He also changed the reporting process to make it automatic: in the last week of January, if 55% of the computing power reported Pay to Script Hash (including the string /P2SH/ in the blocks produced), then the upgrade will be activated at midnight on February 15. Gavin then made a request to modify the software code on the GitHub repository, which he himself accepted on January 13 as main maintainer. It included the default P2SH flag.
Gavin wanted to move fast, very fast, which inevitably created tensions. So, even though he evoked a "consensus" around Pay to Script Hash, not all developers were unanimously in agreement, and the general community had not been consulted. Opposition was therefore building up.

Luke-Jr's reaction

The slingshot was led by developer Luke-Jr. During the IRC meeting on January 3, 2012, he opposed P2SH, considering that "OP_EVAL was far better than this ugly thing". On the 13th, he created a thread on BitcoinTalk, in which he called for action against BIP 16. He considered P2SH to be "far worse" than OP_EVAL because "it essentially replaces the scripting system on which Bitcoin is built with a single special model". Furthermore, he pointed out that "Gavin is forcing everyone using the latest Bitcoin code to vote for BIP 16", and created consequently a pull request to make this flagging optional, which will be accepted. Finally, he proposed a community vote, directly on the forum, which was overwhelmingly won by P2SH.
This attitude deeply annoyed Gavin Andresen, who responded in this latest thread:
Luke, you try my patience. I'm going to step away from the code for a few days to calm down before I do something stupid because my patience is wearing thin.
Another forum member, a German miner using the pseudonym Nachtwind, wrote that Luke demonstrated a certain "mental instability" through his comments. This miner was disinterested in open source; he admitted to liking "the way bitcoin was handled till now" and to trust Gavin more than Luke "to make the right choice" (original: "i trsut [sic] HIM more than you to make the right choice"). Luke's reply is scathing:
If you want a monarchial currency, why not just use the Fed's USD? Gavin isn't perfect, and this is one example. Sorry you consider making people aware of a problem to be 'mental instability'.
From January 12, Luke developed his own operation code as an alternative to P2SH, which was initially called OP_CODEHASHCHECK (CHC), then changed the name to OP_CHECKHASHVERIFY (CHV). On January 18, he wrote BIP 17, which described this new instruction. It involved executing the script provided during unlocking, hashing it and comparing the result with the fingerprint corresponding to the address. However, his proposal did not take into account the complexities of the virtual machine.

Debate among developers

These various proposals were creating a debate among developers. Amir Taaki, who declared "protocol-conservative implementation-liberal by nature", was particularly cautious about adopting P2SH. He favored a broader decision-making process. On January 28, he wrote on IRC that he prefers "people have a say in the matter even if it makes life tougher for developers to explain their decisions".
On January 29, Amir published a long article on Bitcoin Media, entitled "The Truth behind BIP 16 and 17", in which he summarized the situation and the various proposals. He made the following comment:
My worry is bitcoin someday becomes corrupted. Developers: see this extra scrutiny as an opportunity to build a culture of openness. It is not at all bad.
However, this is not the opinion of Gavin Andresen, who chose to settle the debate in favor of BIP 16 and therefore P2SH. He felt there had been enough discussion, and didn't want developers to continue arguing over details, such as "the color of the bike shed". On January 30, he declared on IRC: "I'm done wasting time on BIP 17".
Luke-Jr created a page on the Bitcoin wiki listing developers' positions, following the suggestion of a certain Userjj. Gavin's rejection of CHV was categorical, and contrasted with the other technicians who approved it or considered it better than nothing.
Developer opinions on the various proposals, February 2, 2012 (source: Bitcoin.it)
On February 1, 2012, Casascius put a piece back into the machine by proposing a BIP (improperly assigned to number 22) that took up his idea of modifying the OP_CHECKSIG opcode. Gavin immediately asked him to stop, pointing out that "BIP 16 has overwhelming support, it will be the solution". He added:
You are proposing a non-backwards-compatible change, which would mean a "hard" blockchain split. **Everyone agrees that is a bad idea. The confusion and potential for hacks if a significant fraction of bitcoin users were on a separate chain is massive; you gloss over all of that in your proposal.
A few days later, Gavin would explain (referring to the TV show Who Wants to Be a Millionaire?):
I used my Phone-a-Friend and Ask the Audience, and I'm locking in BIP 16 as my Final Answer

Miner signaling

Another problem concerned the activation of the upgrade by mining pools. For the change to be backwards compatible, a majority of the hash rate must apply it. But as the end of January approached, hopes of activating P2SH were dwindling.
At the time, computing power was divided among some fifty mining pools, but three stood out: DeepBit, BTC Guild and BitcoinCZ Mining (Slush's pool). In particular, DeepBit remained the dominant pool: at the start of 2012, it alone possessed around 30% of the network's computing power. The other two account for around 10-15%.
Proportion of blocks mined by mining pools during the day of December 19, 2011 (source: Blockchain.info)
On January 25, as the evaluation of the signaling began, a few small pools vote in favor of P2SH. Eligius, Luke-Jr's pool, voted against. However, it appeared that Deepbit's operator, Tycho, refused to deploy P2SH within his co-op, as he explained on IRC. In response, Gavin wrote a long message on the forum, where he explained the situation "in layman's terms", noting in particular:
Right now, it looks like one person/pool (Tycho/deepbit) has enough hashing power to veto any change. I believe Tycho liked, and planned to support, the original OP_EVAL proposal, but doesn't like/support either BIP 16 or BIP 17 (he does like/support BIP 11, the multisignature-as-standard-transactions part of all this), so unless he changes his mind or there is a mass exodus from his pool short, multisignature bitcoin addresses will have to wait.
Tycho responded by writing that this was wrong, that he couldn't block the upgrade with the 32% of computing power at his disposal. He justified his attitude by giving three reasons: that there is no "consensus between devs or miners" on how to implement payment to scripts; that the proposed solution is a bit "hackish"; and that he doesn't wish "to become the single entity to decide on this".
Gavin continued to support the adoption of P2SH by pools. Nevertheless, on January 30, he was forced to admit that activation would not take place immediately. He postponed the notification to the last week of February, and the eventual switchover to March 15.
The role of miners in activating the upgrade gave rise to a special conception: that miners direct the evolution of the protocol using their computing power. This conception was supported by Amir Taaki. For him, decision-making was "exactly and correctly characterized as an election" and "each unit of mining power is a vote" in accordance with the "one-CPU-one-vote" principle set out by Satoshi in the white paper.
This interpretation was widely disputed by Gregory Maxwell, who objected on IRC, then on the forum. He wrote:
The Bitcoin system is NOT up for a majority election. Not a majority of hashpower, not a majority of people, not a majority of money. For example, what happens if a super-majority-even 100%-of the current miners decide that the subsidy should be 50 BTC forever? NOTHING. Miners who change that rule in their software simply stop existing from the perspective of the bitcoin network.

BIP 30: correction of duplicate transactions

At the end of February, the situation still seemed to be at a standstill. The number of miners reporting for P2SH was still in the minority, approaching 40%. Gavin Andresen was forced to postpone the evaluation and activation dates again, by two weeks, so that the switchover could take place on April 1. This time seemed to be the right one: according to Gavin, Tycho intended to support the upgrade after integrating and testing the changes.
But first a more urgent problem had to be solved: as Luke-Jr wrote on March 6, "the priority is to get BIP 30 deployed first". The deployment of P2SH is therefore interrupted by an emergency update: the BIP 30.
The problem was "duplicated transactions" on the blockchain: reward transactions with the same identifier included in different blocks. Four blocks mined in November 2010 contained such transactions: the transaction with identifier d5d27987d2a3dfc724e359870c6644b40e497bdc0589a033220fe15429d88599 was included in both blocks 91 812 and 91 842; and the identifier transaction e3bf3d07d4b0375638d5f1db5255fe07ba2c4cb067cd81b84ee974b6585fb468 was part of both block 91 722 and block 91 880. This problem had been noticed, but had been solved by the miners themselves. Generally speaking, there didn't seem to be any urgent need to resolve this problem, as it wasn't thought to fundamentally disrupt Bitcoin's operation.
However, on February 4, 2012, Russell O'Connor discovered a vulnerability that allowed all transactions that arise from a duplicate reward transaction to be deleted outright via chain reorganization, and described the attack in a blog post the following day. To correct the problem, on February 28 Pieter Wuille wrote a BIP on the subject, BIP 30, which prohibits future blocks from "to contain a transaction whose identifier matches that of an earlier, not-fully-spent transaction in the same chain". The rule was added to the code on March 3. The protocol change was included in software version 0.5.3 and became active at midnight on March 15th. It was also present in a preliminary version of Bitcoin-Qt 0.6, which was supposed to activate P2SH.

Activating Pay to Script Hash

After the hiatus caused by the application of BIP 30 (which required a great deal of effort on the part of the miners), signaling for P2SH was back on track. On March 10, Tycho carried out the first tests to implement signaling within Deepbit. On March 15, he stated that he had "tried to delay P2SH as much as possible", but that "this is not productive already". As a result, he gave up the fight and deployed the change within his pool.
A week later, on March 21, signaling for P2SH exceeded 70%! Gavin Andresen wrote on the forum:
Therefore I'd like to announce that support for BIP16 has acquired a majority of mining support needed to prevent a potential permanent fork and will be activated on April 1st as previously planned. \So if you are a pool operator, solo miner, or p2pool miner you need to upgrade your Bitcoin-Qt/bitcoind before April 1st. Running a version of bitcoind earlier than 0.6 release candidate 3 past this date means running the risk of potentially wasting your hashing power mining invalid blocks since earlier versions will accept invalid spends of BIP16 transactions into their memory pools and will put them into blocks considered invalid by the majority.
Two further preliminary versions were released in the following days, and the official version 0.6 released on March 30. It added the standard raw multisignature scheme (BIP 11), implemented short addresses for P2SH (BIP 13) and applied P2SH itself (BIP 16). The upgrade took place at midnight on April 1, without any major incident. As expected, no chain splitting occurred.

The first major disagreement

The Hash Pay to Script battle was the first major discord in Bitcoin's history. It resulted from an expansion of Bitcoin's technical community, which meant that there were enough developers to fight over. Gavin Andresen, who had a much more consensual approach than Satoshi, finally decided in favor of P2SH over the other proposals. This was the community's first major decision concerning the protocol.
This "battle" demonstrated that the development of Bitcoin was not a smooth ride, due to its open and free nature and the stakes involved. It raised the question of Bitcoin's governance, and presaged a far more violent conflict: the Block War, which took place between 2015 and 2017.
Moreover, the debate over the protocol's evolution was not the only consequence of Bitcoin's open and free nature. It also made possible to implement more or less different versions of Bitcoin, taking over the code or concept, which would soon be called "alternative cryptocurrencies". These alternative cryptocurrencies, which contributed in their own way to the construction of Bitcoin, will be the subject of the next chapter.
Quiz
Quiz1/5
Which Bitcoin developer was vehemently opposed to the Pay to Script Hash upgrade?