Bitcoin to the Moon

Wed Apr 05 2017 20:00:00 GMT-0400 (EDT)

Behold, this is rather unusual post for this blog. Instead of exploring vastness of technical wonders, this post will concentrate on discussion and explanation of recent events in Bitcoin community.

Prerequisites

Statement

Recently I got involved in the initiative related to my past interest in Bitcoin technology. This effort is lead by Christopher Jeffrey (JJ) from purse.io, Joseph Poon from Lightning Network, Stephen Pair from bitpay.com. To make it clear from the start, my contribution to this project was rather small and limited to providing superficial technical review.

The initiative is based off the Auxillary Block proposal that is slightly older than the bcoin project. It was modified to accommodate the use of Lightning, and (although, it is incompatible with BIP 141) Segregated Witness (SEGWIT).

The main advantage over Segregated witness is that the block size is no longer tied to the number of transactions in it. Many transactions could be stored outside of the canonical blocks in so called Extension blocks. There are pros and cons to this approach that better be discussed on github.

The most important thing is that it attempts to solve the contention between miners and bitcoin core. It has been known for some time that many miners were willing to switch to Bitcoin Unlimited (BU) (or in other words do a hard-fork) because of the block size limitation. Not only BU is a hard fork, but it also prone to bugs that already brought it down once. Obviously, given this information one has to be very careful when considering it. SEGWIT, on other hand, is a fantastic effort and a soft-fork alternative to BU. However it still caps the block size, and thus is not acceptable for miners for the very same reason as the current version of Bitcoin.

Given this context, a proposal has been created to address this once and for all. Purse.io has reached out to the companies involved in Bitcoin to collect their feedback and feature requests. All in all, it appears to me that "To the Moon" proposal should address the needs of everyone without much compromise of our ideals and Bitcoin ideology.

ASICBOOST

Almost at the same time as "To the Moon" proposal was published, Greg Maxwell has sent an email about ASICBOOST and his findings about usage of this optimization in "particular mining chip" (quoting Greg).

Given the timing this email has sprawled the discussion of miner's reasons to "love" "To the Moon" and "hate" BIP 141. It turned out that "To the Moon" was compatible with ASICBOOST's optimization, while SEGWIT is not.

I can't resist diving into the technical details of this optimization, but before I'll walk this road with you let me quickly reassure you. As of this commit "To the Moon" is no longer compatible with ASICBOOST, and, although it is an open question whether this kind of optimization is permissible or not, this proposal is on the same grounds with SEGWIT now.

This means that reasons for conspiracy about relationship between "To the Moon" and miners no longer holds.

If you have any additional prevention measures in mind - please do not hesitate to open an issue on github.

Technical details!

Finally :)

The most of the content below relies on some understanding of this ASICBOOST paper. This paper is not to hard to follow, so please take a look.

It is a normal practice in Bitcoin mining to pre-compute as much as possible to make mining possible. ASIC's mostly do double SHA256 hashes, thus this pre-computation relies heavily on splitting SHA256 into phases and sharing data for inputs that do not change.

The way Bitcoin is mined is by brute-forcing the 32-bit nonce in the block header until the hash of the header will match current complexity of the Blockchain (read, number of leading zeroes in the hash). Trying all 32 bits is of course not enough to generate such fancy looking block hashes, and almost in every case some additional modifications to the block header are needed.

Given the structure of the block header:

02000000 ........................... Block version: 2

b6ff0b1b1680a2862a30ca44d346d9e8
910d334beb48ca0c0000000000000000 ... Hash of previous block's header
9d10aa52ee949386ca9385695f04ede2
70dda20810decd12bc9b048aaab31471 ... Merkle root

24d95a54 ........................... Unix time: 1415239972
30c31b18 ........................... Target: 0x1bc330 * 256**(0x18-3)
fe9f0864 ........................... Nonce

(Source of the data)

The only field that miners has control of (other than timestamp, which can't be changed too much for obvious reasons) is root of the Merkle tree with block's transactions (TX) as leafs. This is usually approached by modifying the first TX (coinbase) in the block.

Now as the Merkle root changes - it will practically invalidate any SHA256 pre-computation that could have been made, since the changes will span both of the two 64-byte chunks (including padding) forming the 80-byte block header. (SHA256 operates on 64-byte chunks).

What can one do about it? Second 64-byte chunk starts from the last 4 bytes of the merkle root... Does it ring the bell yet?

The answer is: collisions!

The pre-computation is still partially possible if the second 64-byte chunk is the same during mining. One doesn't have to keep it always the same, generating few of such colliding chunks is enough to get the benefits of the optimization.

Now how this collision may be generated? The answer is brute-force.

(The rest of the post is basically elaboration upon Greg's email which I hope you already checked).

How many brute-force attempts has to be done? Applying Birthday Paradox gives the number of tries around 2^16 (size of whole problem space is 2^32, since we need to collide just 4 bytes) for two colliding block headers. Four of them will take approximately 2^24 tries. Quite a lot, but not too much if you can optimize it. Let's now consider how this brute-force could work.

The most straightforward way of doing it would be changing the coinbase, but this is rather expensive for regular blocks. If block has around 1500 TXs this means re-computing the Merkle tree branch of length 10. Thus 10 double-SHA256 per brute-force attempt. Very inefficient!

Can we do less? Yes - we can!

Transactions can be re-arranged in the block to change the Merkle root, each different permutation will yield a different hash and thus will count as a try. Permuting 7 branches to the right of the Merkle root yields 5040 combinations with 7 double-SHA526 hashes per try. Changing the coinbase to the left of the root can produce 4096 more combinations. Combining these two together gives us just 2^24 tries that we was looking for! Now since we pre-cached various choices for both left and right branches the only thing that is left is compute double-SHA256 of both of them for every combination. To conclude: just 1 double-SHA256 per try! Now this sounds quite good.

SEGWIT and "To the Moon"

This optimization is possible with "classical" Bitcoin, but is not feasible with SEGWIT for a very simple reason. Coinbase in SEGWIT includes the Merkle root over the rest of transactions (ignoring technical details), which means that it is not possible to combine left and right branches without changing the coinbase which brings us back to 10 double-SHA256 per try.

Initial version of "To the Moon" has a Merkle tree in coinbase too, but it had to be computed only over transactions that are not present in classical/canonical block. Meaning that it is easier to do ASICBOOST optimization on "To the Moon" than on SEGWIT.

Given this description, it is easy to see that the recent change in "To the Moon" spec makes it non-susceptible to ASICBOOST optimization.

I hope this answers all or at least some of your questions about it.

Thank you for reading!

Credits

I'd like to thank:

  • Greg Maxwell for doing a quick review of the change to "To the Moon" proposal, and for helping me understand the details of his discovery
  • Christopher Jeffrey (JJ) for inviting me to the initiative
  • Guillermo Rauch for reviewing/proof-reading this post.