Bitcoin to the MoonWed Apr 05 2017 20:00:00 GMT-0400 (Eastern Daylight Time)
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.
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.
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.
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
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
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
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
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
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!
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.