Hacker News Reader

Comment by frisco | Hacker News Reader

This raises a really interesting question. Though it’s essentially impossible to figure out the key for any given wallet… if you download the blockchain and generate private keys as fast as you can, how often do you find one that has a balance? Will there just be some ongoing very low but decidedly nonzero risk of all of your assets vanishing some day if you’re not using multisig?

View on HN

One thing you can do that's quite lucrative for someone is to generate all the keys corresponding to common dictionary words like "dog" and "cat". The way I know someone is doing this is I was testing some transactions and somehow whatever I was sending was immediately vanishing. So someone out there has taken a dictionary and done this already.

Introducing the Large Bitcoin Collider: https://lbc.cryptoguru.org/about

If you check 1 billion addresses a second, and there are 100 million addresses with a balance, then it would take on average roughly (2^256 / 10^8) * 10^-9 seconds, which is 36717430630808027468154168254911183362909051 billion years.

EDIT: Only 463439129036942 billion years, taking into account that there are effectively only 2^160 addresses.

You could shorten that by recognising the address space is more like 2^160 in BTC, due to the address generation process, more than one private key can spend from a given address, technically.

This reduces that number of years by 28 digits, afaiu, and that is still a pretty big number of billions of years.

Is that the average time until the first collision, or the time it will take to generate all possible private keys?

Average time until collision.

Now that it looks like a phone number, one could unleash a horde of telemarketers at it.

Feels like a Hitchhiker’s quote:

"""Coincidentally, 2276709 is also the telephone number of a flat in Islington where Arthur once went to a party, met a nice girl, and lost her to a party-crasher. While the flat and telephone have been demolished along with Earth, they are forever linked to the fact that Arthur Dent and Ford Prefect—against all odds—are rescued 29 seconds after being ejected from the Vogon spaceship."""

You could check a lot more than 1B address per second.

Not easily, as you need to do an elliptic curve point x scalar multiplication, which takes tons of cycles on a CPU and even tons of gates on an ASIC. Please provide a link to hardware that can do it much faster...

Two or more of whatever you are using to perform the calculations? I mean it won't appreciably shorten the search time but it would double the processing rate.

There's kind of a reason you don't count the coefficient in big O notation etc. It doesn't really matter.

If you can't exponentially increase the amount of power / transactions you don't really have a chance of figuring out a collision.

100x machines with a computation that takes 100 billion years is still 1 billion years.

I'd guess a GPU at 2Ghz (2. Billion per second) might run parallel enough to compensate for the number of cycles required for a given point.

I doubt whether this would get far past 1 billion a second though.

Hashing hardware capability is typically measured in trillions per second (TH/s) so the math might be better using trillion instead of billion. As I understand it, the rental cost of 1 PH/s (which I think is one-thousand-trillion?) is about $10/hour. From that I think you could work out an actual cost to generate a collision!

Even taking the smaller value of 463439129036942 billion years at 1 billion/second (and therefore 463439129036942000 years at a quadrillion/second), at $10 / hour / PH/s, that’s $4.06e22, or ≈ 480 million years of Earth’s 2020 global nominal GDP.

This assumes a uniform key space. If PRNGs used to generate keys are biased, then there may be a way to exploit that bias.

Human-generated brainwallets are notoriously guessable: https://www.reddit.com/r/Bitcoin/comments/1zti1p/17956_hacke...

I wonder if you could cut this down by focusing on know implementations and their random number generation. That is trying to figure out if weaker random number generation at any point was prevalent...

It did happen, and bitcoins were stolen. https://tradeblock.com/blog/javascript-random-number-flaw-le...

its like asking if you had a rocketship that traveled at the speed of light, how long until you find earth given you're on some random galaxy

Not really because if you are travelling at the speed of light time isn't passing...

does that technical mistake hinder the point of my comment?

Yes. You can't, technically, find earth while passing in speed of light. If you are travelling in light-speed, you'll reach destination in no time.

Not a physicist, but I don’t imagine you can turn while going light speed

I can do whatever I want, I’m going light speed!

It is for earth though, which might be swallowed up by the sun at the spacetime you arrive.

Miniscule, not zero of course but zero for any practical purpose. The search space is just that much bigger.

With every supercomputer working for 100 years, you can have 0.01% of all accounts, maybe.

... not even close.

2^256 is a very large number. If you could build a computer that required a single atom, and could test the balance of a single account in a single nanosecond, and then converted the entirety of the earth into such computers, it would take ~2.8 million years for you to check 0.01% of all accounts.

Brute-forcing modern cryptography isn't something that can happen. The magnitude of 2^256 is close to the count of atoms in the entire observable universe.

This reminds me of a discussion a few years ago where someone was extremely adamant that you'd have to handle the chance of a key collision in a random 256-bit key for the system to be secure :)

I might agree with them because your random process could be weaker than you think without having any indication until you hit the colision.

Anything past detection and panicking might be overkill tho.

> The magnitude of 2^256 is close to the count of atoms in the entire observable universe.

I've always heard that even 2¹²⁸ is significantly larger than that number (which is closer to 2⁸⁰). This page seems to support that:

https://en.wikipedia.org/wiki/Observable_universe#Matter_con...

Nope, the rough approximation of atoms in the universe is O(10^80). Big difference!

Quickly checking with Python...

2^265 < 10^80 > 2^266

So it's only 0.1% of the number of atoms in the universe?

“Only”.

Look more carefully, the estimation according to Wikipedia is 10^80, which is roughly 2^266.

(BTW, when converting 10^x to 2^x, times 3 is what I use for very rough back of the envelope estimations. Times 10/3 is actually almost precise, as log2(10) = 3.32…)

Ah, so it's just me being stupid, as usual. Thanks, at least now I know.

> log2(10) = 3.32

or, to put it in simpler terms,

10^3 = 1000 ≈ 1024 = 2^10

The best quote for this is from Bruce Schneier:

"... brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space."

https://security.stackexchange.com/a/82412

It's a large number but not close to the count of atom:

https://www.wolframalpha.com/input/?i=2%5E256 > ≈ 0.0012 × the number of atoms in the visible universe (≈ 10^80)

Reply on news.ycombinator.com