Topic: Possible solution for recovering lost Bitcoin to the "blackhole". (Read 4373 times)

I like the idea of going with the metric system for naming smaller amounts of BTC.

The exact number, assuming we don't extend the unit size beyond 1E-8, will be 20,999,999.9769.

The subsidy shifts out of a 64 bit integer.  If we change to a 128 bit representation, there will be a miniscule extra amount.

I must admit I do not know if it will be 21M on the dot, or some fractional number around it.  But does it really matter if it's 21M, or 20.999M?

Is the system designed so that the total amount of BTC in circulation does not exceed 21m or it will always be below that figure?
From what I've read 21m is an asymptote meaning total BTC will always be nearing this number but never reaching.

Thanks. I have heard of the one-time pad, and understand why it's uncrackable (and why it's rarely used.)

Didn't remember the name of the man (Vernam, thanks Epoch) who co-developed it.

It is a one time pad.  It requires one bit of key for each bit of message, and no key bits are related so all potential decodes are equally likely.  Just make sure that the key bits really are unrelated.  That is, you must a have a real source of randomness like a geiger counter, not just pseudorandomness, otherwise the PRNG seed is the real key.

You might have better luck with 'Vernam cipher'.

Is that known by another name? Searching Google and Wikipedia for "vernon cypher" didn't return useful results.

I don't doubt that the bruteforcing of addresses, as they presently exist, would require a truely astronomical computational ability, and is certainly safe for decades.  That was the point of the design, after all.  However, I think that it's also a bit silly to assume that such astronomical computational abilities will remain out of reach for humanity forever.  The only cryptographic algo that is provablely secure from brute force forever is the simple Vernon Cypher, which has no applications here.

Yes, sorry.  Address keypairs are created by ECDSA, while the hashing is done by SHA256.  The bruteforcing would have to be done by ECDSA hardware to create any address collision.  Basicly a huge rainbow table would have to be built and the list of lost addresses would be compared against it.

Makes more sense. Thank you.

Yes except to say it is SHA256 of the nonce would confuse someone who didn't already know what you were trying to say.

More accurately it is (steps 3 to 7)
SHA256(SHA256(0x00 + RIPEMD160(SHA256(public key))))


Put all together:
base address = 0x00 + RIPEMD160(SHA256(public key))))
checksum = left 4 bytes (SHA256(SHA256(base address)))
full address = (base address) + (checksum)     <- don't add just append

Jebus that is complex. So if I understand correctly, the first seven steps (not including step 2) are like this: SHA256(SHA256(0x00 + RIPEMD160(SHA256(nonce))))
Yay? Nay?

Yes.  Although if you want to get into the weeds generating a single address is a "little" complex (not sure what Satoshi was smoking )
1. Start with a 256 bit nonce (cryptographically secure pseudo-random number).
2. Use ECDSA to generate a corresponding public key.
3. Perform SHA-256 hash of the public key
4. Perform RIPEMD-160 hashing on the result of SHA-256
5. Add network byte in front of RIPEMD-160 hash (0x00 for Main Network)
6. Perform SHA-256 hash on the extended RIPEMD-160 result
7. Perform SHA-256 hash on the result of the previous SHA-256 hash
8. Take the first 4 bytes of the second SHA-256 hash. This is the address checksum
9. Add the 4 checksum bytes from point 7 at the end of extended RIPEMD-160 hash from point 4. This is the 25-byte binary Bitcoin Address.

Of the 3 algorithms used SHA-256 is the most computationally intensive and it is performed 3 times in each key generation which is why I focused on that.  The reason vanity gen can "only" try 20 million private keys (as opposed to 80 trillion) is primarily due to computational "cost" of the SHA-256 steps.

It is possible one or more of the algorithms will be BROKEN due to a flaw but 256 bit is far too large to brute force even with planetary sized super computers.

To put it into perspective.
Number of potential private keys in 256 bit keyspace: 1.15792E+77
Number of atoms in our entire galaxy: 1.25E+69

It would take ~90 million (average sized ) galaxies to have as many atoms as there are keys in a 256 bit keyspace.

PS:
Technically my math above was off because I forgot that due to RIPEMD-160 hash there are potentially 7x10^28 private keys for each public address so the problem is 10^28 times "easier" but still computationally infeasible without a cryptographic flaw.

Thanks, that clears it up for me.

The private key is a 256 bit random number, the public key is derived from that random number.  His discussion is still totally valid, since he is really talking about any 256 bit keyspace.  It is even more valid since you don't have to recover the original private key, just any private key that corresponds to one of the public keys in the chain.

Yup, the subsidy is right-shifted out (without carry).  Which means that the end of the subsidy depends on the size of the integer we are using.  So, unless there is a further code change, the subsidy will last about 128 more years (4 * log₂ 50E+8).  An expansion to 128 bit integers will give roughly 64 more shifts, or about 256 more years.  This would have a negligible impact on the total amount of coins.

Actually, we are really only using the bottom 51 bits right now, so if we are changing formats, we could change the pseudo-mantissa from 10e-8 to 10e-30 rather than 10e-17.  21,000,000 * 10^30 just barely allows exact representation in 127 bits (allowing signed math).  If we want to contemplate projects with costs that are many multiples of the total amount of money in the world (which isn't as silly as it sounds), but still allow them to use 128 bit signed representation, we could pick 10e-24 or 10e-21.

Oh, but the value of the subsidy starting in block 2,310,000 will be different in 128 bits than it is in 64 bits.  So, we really should plan how we want to expand sometime in the next 30 years or so.

Sorry, this is mostly off topic, but interesting.  I sometimes get carried away when I calculate.

Cool story. My understanding is that the blockchain uses SHA256, but the keypairs are ECDSA. Is ECDSA still 2^256, or is it something else?

Unless a cryptographic flaw is found I doubt SHA-256 will ever become insecure.  Any insecurity will be due to a flaw which allows cryptographers to cheat not due to more powerful computers.

Vanity gen brute forces private keys.  A top of the line GPU will handle about 20MH/s.  Now lets assume vanity gen is inefficient and you developed a treasure hunter software which was 10x as efficient at trying random private keys, building public address and checking for value.  Also lets say a SHA-256 28nm (current gen) ASIC came out which was 20x as fast as fastest GPU at the same pricepoint.  Now lets also say Moore's law stays alive for the next century (doubling every 24 months).    In 2112 you would have a chip which is 4.5 YH/s (Yottahashes).

That would be roughly equal to all the computing power (in all forms) on the planet right now in a single chip.  Now say you built a cluster of 100,000 of these (would have equivalent cost as 100,000 GPU today) and hashed SHA-256 private keys for the next millennium (till year 3112).

In that millennium you would be able to check 1.4x10^34 private keys.  Which is roughly 0.00000000000000000000000000000000000000001227% of the SHA-256 keyspace.  Now lets sweeten the pot.  Lets say that there are 10 billion active users and 1 quadrillion active and lost private keys.  You would still have only a roughly a 1 in a quadrillion quadrillion chance of finding any key with value after searching for a 1000 years with 100,000 chips each w/ the computing power of the planet today.

SHA-256 is big.  Far bigger than most people can comprehend.  It won't be brute forced.  Not today, not in a century.   The pysical world equivelent would be like saying we might run out of matter in the universe if we keep building things.  SHA-256 may be BROKEN due to cryptographic flaws but it won't be due to increasing hashing power.

I hadn't thought of that aspect... very true indeed!