“Nobody Knows. Some do Say because they are Horrified by the Alternative…”

The Large Bitcoin Collider (LBC) tries to break Bitcoin addresses through a brute force attack. In the few past weeks, the project announced their first success. Is Bitcoin no longer secure? Is their cryptographic core broken? Rico, the head of the LBC, explains in detail, what is happening.

Who Are You and Why do You Have a Domain Called cryptoguru.org?

I’m an experienced computer scientist. I rented the domain cryptoguru.org and a bit hardware infrastructure for a small amount of bitcoin. I liked the domain name, and fortunately, the owner did not need it.

You Develop and Maintain the Large Bitcoin Collider (LBC), a Project with Which You Try to Find Collisions of Bitcoin Addresses. How Did You Come to this Idea – and What do You want to Prove?

In July 2016, I stumbled across the website directory.io, which says it contains every private key of every bitcoin address. I thought this was a funny idea; the message was something like, “Do I find the key to my addresses in the directory? Yes, but nobody will ever find it. Because… math.” This reminded me at similar cases in information science, like that the full number of pi must contain a code for every book of Shakespeare.

So I started to dig deeper and found out that some people try to scrape directory.io and search for addresses with funds. I thought this could be done better. First, just as a thought game, but after some time, I realized, that you do not need to search the entire 256bit space, but only 160bit. Then I thought, “Ok, let’s give it a try.”

All I want to prove is that many humans can be wrong when they say that something is impossible. We all know that this happens, and I think that it might also happen in this case. Since everyone always said that it is impossible, nobody really tried. I just want to take this untested path.

If Understood Correctly, the LBC is a Brute Force Attack on any Possible Bitcoin Address. Can You Explain More Precisely What You Do?

Let us start with how addresses are created; you take a private key, which is a random string of signs with a particular length; starting with this you use the coordinates of an elliptic curve to generate a public key. Then you hash the public key with SHA256, and after another round of RIPEMD160, you have a hash160, basically a Bitcoin address. To make it better readable you encode it with Base58, and here we have the popular Bitcoin address (1something …).

The client of the Large Bitcoin Collider (LBC) knows all hash160 addresses which contain more than zero bitcoin. It just increments the private keys – we are only interested in 2¹⁶⁰ – and use them to calculate the said hash160. Then it compares it with addresses containing bitcoins.

What is the Chance of Finding an Address with Funds?

There are many extrapolations, but the more you look at it, the more unknown variables you find. At some point, it looks like the Drake formula, which aims to estimate the number of intelligent species in the Milky Way, and you have to admit; you do not know anything for certain.

But, let us try an example; there are not more than 2160 possible addresses – not 2256 like many believe. And the 2160 are only possible if RIPEMD160 is surjective, what means that it covers the whole scope of possibilities. We hope this, but do not know for sure.

Currently, we have 15 million addresses with funds (223.8). Assuming these addresses are evenly spread on the possible space, than ONE in 2136.2 addresses is funded. If you assume that we are able to search 236.2 addresses each second, we will need 2100 seconds to find such an address. This equals 40,196,936,841,331 billion years.

Seen this way it is pretty unlikely that you ever find an address with funds. However, we already founded three.

According to Your Website, You currently Generate 587 Megakeys Each Second. That is a Lot. What Hardware is in Use for the LBC?

At the time of writing the answer, the pool reaches 1196.22 MKeys/s (when reading my own answer again; 1238.53 MKeys/s). Most of it is CPU, but also some GPU. The question for the hardware, however, is less interesting and relevant as is the question of the software.

I told you about people who used a script to parse directory.io page by page. They needed 20-30 seconds for one page. Since you have 128 keys on each page and 256 addresses, they started to generate six keys pers second. I tried to improve this rate. With a little experimenting, I was able to increase the key rate extremely.

First I used vanitygen, which enabled me to make 100 keys each second. Then I took the sources from directory.or and parsed them directly, which shot my rate to 13,000 keys/s. Then I thought, why use base58 when hash160 is enough – 40,000 keys/s. After Ryan Castellucci had told me that his Brainflayer is much faster, I tried it out, and, yes; 520,000 keys/s.

Then I started to dig deeper. I studied SHA256 and RIPEMD160 and learned C again. I slowly rebuilt Brainflayer to an HRD-Core and reached a rate of 720,000 keys/s. At this time I already had the fastest RIPEMD160 CPU implementation available. But it was not fast enough. So I took the secp256k1 code and tried to use it for GPU. Since nobody had written a GPU application for it before, I developed it by myself. This was far from perfect but took me to 2.2 million keys/s.

But it does not stop here; the user “arulbero” on bitcointalk made some suggestions, how you could improve elliptic curve arithmetic, and worked on his own library for it. I developed the GPU operation meanwhile, and on March 25, 2017, I threw libsecp256k1 away and integrated arulboro’s EC arithmetics.

The result, right now; 5.5 million keys each second and CPU core. With the pool of the LBC, everybody can spend its hardware and time, since the search can perfectly be paralyzed. So I estimate that some hundred CPU cores are participating at the moment.

On the Same Side, I read that the Probability of Finding a Collision During the Next 24 Hours is around 0.000000-something. Does This Mean You Will Not Find a Collision for the Next 1,000 Years?

You might know the story of the pond and the water lilies:

Day one: One water lily.

Day two: Two water lilies.

Day three: Four water lilies. And so on.

After 27 days half of the sea is covered with water lilies. How many more days are needed to cover the whole sea?

You say 0.0000000-something. Let us have a look at the numbers:

0.00000000000000000045 percent (17.9.2016)

0.00000000000000200548 percent (23.9.2016)

0.00000000002801022860 percent (28.3.2017)

0.00000000016406321697 percent (04.4.2017)

I guess everybody should be able to make his own mind about if we need to think about a period of 1,000 years.

Recently You Found Your First Collisions with Change Addresses. Were you Surprised?

I was 50 percent surprised!

How is it Possible that this Happened Multiple Times? Has Something been Special with the Addresses, Like they Have Been Made with Low Entropy?

Nobody knows. Some say so because the alternative terrifies them. Other doubted that the collisions have been real and claimed we fabricated it. I can guarantee everybody that we found real collisions. If it has been bad entropy or not – we just do not know by now.

On the Addresses You Found the Key For Have Only Been Very Small Funds. What Will You Do if You Find the Keys to Wallets from say BitStamp?

How much bitcoins are on them? [Laughs]

Seriously; as a standard, we transfer the funds on another address and publish it. The “rightful owner” can ask for six months for a return of the funds by showing another key. We have our collision; they have their bitcoins. Everybody is happy.

You Found Several “Trophies” from a so-called “Puzzle Transaction.” What is it all About?

Ryan Castellucci told me about the Puzzle Transaction. It seems like someone built a 33BTC canary to examine how secure Bitcoin P2PKH addresses are. He stored for each Bit entropy of private keys 0.001 bitcoin. Up until number 50 all addresses have been drained until 2015. So you should never use keys with 50 bit. Recently we found Number 51.

There is a Picture with a Sun, and Below you can read that “Even if you Cover the Whole Sun with Perfect Microchips and Burn the Entire Energy of the Sun, you would not be able to Bruteforce a Bitcoin Address.” Is this Just Marketing?

Yes. The pathos of this picture had a great effect on me, when I see it for the first time. But keeping it in perspective the numbers just do not compute.

Bitcoin is secure – currently, I even would say; strongly secure – but not as robust as this picture suggests.

Would it be Possible to Drain Bitcoin Addresses with a Cluster of Supercomputers? Would it even be Possible to Build an ASIC mining Bitcoin by Finding Collisions?

If you have the private keys, you do not even need a calculator to drain Bitcoin addresses. Can a cluster of supercomputers find private keys? Yes. Could you use an ASIC to do what we currently do with CPU and GPU? Yes. When I reach the limit of what can be done with GPU, I will try it with FPGAs.

Sometimes I am surprised how many similarities there are with the evolution of Bitcoin mining. But we pass through it faster.

Could a Quantum Computer Help Find Collisions?

Possibly, but I do not want to speculate. Just this: Earlier as with quantum computers I see a technology which could attack P2PKH/P2PSH addresses faster. But that is said enough. You don’t get more details from me.

How Can a User Protect Themselves Against Collisions? Is There a Method to make them Less Likely?

Unfortunately, the (alleged) correct implementations of SHA256 and RIPEMD160 are the reason why I have to answer this question with “no.”

There have been discussions on a method to protect P2PKH addresses against the LBC; this could maybe be done by using a private key of the range 2159 + rand(2158) – for this key the probability of a collision with other keys is lowest in the first 160bit. The LBC would need more time to “look here.”

What You Say is somehow Worrying. Would You Advise storing Large Values in Bitcoin?

Yes, I own some bitcoin, and the LBC does not change that. What I personally would not do any longer is to store large sums of bitcoin on a single address. By doing so, you take risks, independently of the LBC. I would not trust a chain of 160 ones and zeros with something like $100 million.