Bitcoin Forum
April 21, 2018, 07:50:50 PM
 News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [45] 46 47 48 49 50 51 52 53 54 55 56
 Author Topic: Large Bitcoin Collider (Collision Finders Pool)  (Read 163277 times)
Its_a_Meeeee
Newbie

Offline

Activity: 6
Merit: 0

 April 12, 2017, 04:44:11 PM

Regarding wheather we assume 160 bit space or 159 (half of it).

The idea to "only" need to search in half of the 160-bit output space of addresses arises because we generate both,
compressed and uncompressed addresses for each private key guess.

Q: I don't know about that process. Is it more like this:

|

or like this:

I would argue no search-space reduction can be achieved if the process is the later one.
So IMO the statement on the page "X bits of 160bits" is correct.

Regarding the probabilty calculations i guess arulbero is in a higher dimension than me I'll shut up and enjoy the show
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
monsanto
Legendary

Offline

Activity: 1186
Merit: 1002

..like bright metal on a sullen ground.

 April 12, 2017, 04:59:26 PM

(31 + 16,4) - 135,2  -->  -87,8 --> 0,0000000000000000000000000037116

I didn't count the 51 bits of the so far searched space, but i think it is more or less the same ...

2 orders of magnitude...
because %

0.000000000000000000000000003711
0.000000000000000000000000401596% <--- correct number (online)

So to sum up - how is this number going to be bigger?

• With more addresses with funds on them
• In time, as more space is searched
• With higher search speed

From what I can see, the number of addresses with funds has the most effect at the moment.

Rico

As I understand it then the "successes" so far were only possible because the hit addresses lacked true randomness or something? I'm trying to understand how exactly those addresses are found.  I understand how some brain wallets were found but not these. I guess your search algorithm specifically targets certain kinds of addresses.

Keep up the good work.
rico666
Hero Member

Offline

Activity: 910
Merit: 1005

฿ → ∞

 April 12, 2017, 06:11:00 PM

or like this:

I would argue no search-space reduction can be achieved if the process is the later one.
So IMO the statement on the page "X bits of 160bits" is correct.

It is more like

Code:
private_key --*some process*--> uncompressed-pubkey -> *very negligible process* -> compressed-pubkey
|                                             |
hash160 process                                 hash160 process
v                                             v

With the current CPU/GPU hybrid architecture, we would have exact the same keyrate if we just computed one of these.

edit: The CPU clients would be faster computing just one of them (preferably the compressed one), which is what e.g. vanitygen does.
but, they would only be faster nominally (keyrate), not factually, as they would need to perform 2 EC arithmetic computations for 2 addresses. So the overall "address-rate" would be lower.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Real-Duke
Legendary

Offline

Activity: 1162
Merit: 1014

Bitcore (BTX) - Airdrops every Monday

 April 12, 2017, 06:44:04 PM

6a50c257a1e7d3712f035059d7d2bf4809360b46:c:priv:0000000000000000000000000000000000000000000000000008f1ce137ff001+0xfe9
My Bounty found from yesterday morning, just for the records
Thanks to SlarkBoy!

 ▀██▄ ▄██▀            ▐█████▌           ▄███▀███▄         ▄████▄  ▀███▄       ▄███▀ ▀██▄  ▀███▄     ▄███▀  ▄█████▄  ▀███▄   ▄███▀  ▄███▀ ▀███▄  ▀███▄  ███▀  ▄████▌   ▐████▄  ▀███ ███   ██▀  ██▄ ▄██  ▀██   ██████   ███  ███   ███  ███   ██████   ███   ███████   ███   ███ ███   ███▄▄       ▄▄███   ███  ███▄   ▀▀█████████▀▀   ▄███   ▀████▄▄           ▄▄████▀      ▀▀███████████████▀▀ DeepOnion ...▬  TOR INTEGRATED & SECURED  ▬... ★  Anonymity Guaranteed★  Anonymous and Untraceable★  Guard Your Privacy ........★★  JOIN THE NEW  ★★..............✈️ AIRDROP..... ▄▄██████████▄▄    ▄███▀▀      ▀▀█▀   ▄▄   ███▀              ▄███  ███              ▄███▀   ▄▄ ███▌  ▄▄▄▄      ▄███▀   ▄███▐███  ██████   ▄███▀   ▄███▀███▌ ███  ███▄███▀   ▄███▀███▌ ███   ████▀   ▄███▀███▌  ███   █▀   ▄███▀  ███▐███   ███     ▄███▀   ███ ███▌   ███  ▄███▀     ███  ███    ██████▀      ███   ███▄             ▄███    ▀███▄▄       ▄▄███▀      ▀▀███████████▀▀ ...Verified..........with DeepVault......
rico666
Hero Member

Offline

Activity: 910
Merit: 1005

฿ → ∞

 April 12, 2017, 07:09:27 PM

And user Coinpiet found https://blockchain.info/de/address/e426d197698e06bdfe851a873a4a1bbd1f2d726e today.

Lucky newbie: https://lbc.cryptoguru.org/stats/PeterPC_Bitcoin

He is still fighting with claiming the funds.  So privkey later...

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Its_a_Meeeee
Newbie

Offline

Activity: 6
Merit: 0

 April 12, 2017, 08:04:17 PM

Congrats Real-Duke & Newbie^^

Ok Rico, from the way you describe the process I derive following information pieces.

EDIT: for clarity. When I say "have 4 addresses in the filter" I mean 4 unique addresses and 8 representations thereof (2 each)

1) As I assumed the compressed address is simply a way of displaying one uncompressed address in another way.
==> It means that it is a bijective mapping of the address to another encoding / format.
As in: https://en.wikipedia.org/wiki/Bijection

2)
a)It definitely makes sense to calculate both addresses for a private key and check against the filters,
just to make sure we cover 100% of all addresses that are funded (if we should ever get to the end of 160 bits )
b)On the contrary this does not mean that you check two private keys, just two representations(!) of the public key.

->Checking only the compressed or uncompressed address format would allow for a collision to go by undetected,
because you basically have a 50% chance of the original private key being used / funded through either of the formats,
thus not appearing in your bloom filter.

->Now reducing the search space to 159 bits, effectively halving it, reduces the collision amount that you can expect to find accordingly and you

->By checking only one however, and opening up for undetected collisions as mentioned above, you should then only expect about 25% of all addresses to be matched.
(while still having to produce half of all addresses for this lesser gain.)

->In Order to produce all addresses you still have to go through 160 bit of search space.
-->In Order to match all addresses you can not reduce the search space and have to check against both formats.

->The probability of matching just one produce (the next one) to an address in the filter should then (kinda simply) be:

1 / ( (2**159) / 1 ), for the case we have a single address in the filter, in both its representations.

1 / ( (2**159) / 2 ), for the case we have two address in the filter, totaling  4 representations.

1 / ( (2**159) / (2**159) ) = 1/1 = 100% (as logically expected), for the case that we would check against a filter containing all possible entries.

So the needed formula is:
1 / ( (2**159) / (Number_Of_Entries_In_Filter) )
This is then scale able with something like X Mkey/s and 24h, to approximate daily probability.

Important here is that this is plain, without the progressive nature that's built into the LBC.
Again I am not sure about the need for conditional calculations (might arrive at the same result).
Because simply put each done calculation just reduces the remaining search space.
1 / ( (2**159 - Progression_Value) / (Number_Of_Entries_In_Filter) )

Imagine the extreme scenario, we find all (lets say we had only 22 for simplcity) addresses in the very last 4 private keys that we search.
The formula must result in 1 (100%) at the point where only 4 private keys are left and 2**159 - 4 have been searched.
Let's see:
1 / ( (2**159 - (2**159 - 4)) / (4) )
1 / ( 4 / 4 )
= 1 !

Works beautifully!
What do you guys think?

SUMMARY:

I think checking both formats is mandatory since we don't want anything go by undetected, period :-)

Since uncompressed to compressed is an encoding process not evolving the private key it is unrelated to the search space coverage.
But related to collision chance. (on the homepage described as" the effective search space until something is found")

One could also formulate:
"There are 2160 addresses. Each has two representations, which are interchangeable. Making it 2161 representations.
One private key calculation will have a chance of matching one of the representations of 1 / 2160 twice. So probability per private key is 1 / 2159. (non progressive)"

If you want to display the probability of the pool forefront on the page my suggested formula should do the trick.
If you really want to display a good estimation, or even just scaled up from current speed, for a 24h based probability you will need a math professor at your disposal

Phew, brain tingles :-)
Have fun with this mind twister
unknownhostname
Member

Offline

Activity: 61
Merit: 10

 April 12, 2017, 10:30:29 PM

f86b1dd782990bafba34c28c88d4c7ff9ce99641:c:priv:000000000000000000000000000000000000000000000000000a1835db9ff001 + 0xf87
rico666
Hero Member

Offline

Activity: 910
Merit: 1005

฿ → ∞

 April 13, 2017, 05:47:36 AM

Ok Rico, from the way you describe the process I derive following information pieces.

EDIT: for clarity. When I say "have 4 addresses in the filter" I mean 4 unique addresses and 8 representations thereof (2 each)

When we have - as of now - 15.6 mio addresses in the filter, it's 15.6 mio addresses (not 15M x 2, or x 4). Unique addresses some of which are based on compressed and some of which are based on uncompressed public keys.

Now - for brevity - instead of this "is based on", we'll just talk of compressed and uncompressed addresses. All we need to know for now, that there is two P2PKH addresses per private key (said compressed and uncompressed).

If we create these from 2^159 private keys, we get 2^160 addresses. Period. The question (but left for another discussion) is if/how far these are unique addresses.

Now why this magic 160 all the time? Because RIPEMD160. The 160 is the number of bits in its output. As RIPEMD160 is the last piece in the chain of computing an address, it's output matters (and nothing else).

Therefore,

Quote
One could also formulate:
"There are 2160 addresses. Each has two representations, which are interchangeable. Making it 2161 representations.

Nope. There is no way we could generate more than said 2160 addresses. Be it with compressed alone, with uncompressed alone, or with both. In fact, even if we generated compressed and uncompressed for all (nearly) 2^256 private keys, (generating 2^257 hash160 in the process) -> we still would end up with at most 2160 addresses.

So this is the limit. There is no more. This discrepancy between the number of possible private keys and the number of possible addresses is the reason for this "there are about 296 private keys to each address". (Which I now believe is not true, because there are actually 297 private keys to each address, but this is also for another discussion)

If we look at an address (the hash160), we cannot see if it is a compressed (c) or uncompressed (u) one. The information is not there.
Therefore, we may have 4 types of collisions:  c-c, u-u, c-u/u-c

c-c: We generate a compressed address with key x and it collides with a compressed address made from key y
u-u: We generate an uncompressed address with key x and it collides with an uncompressed address made from key y
c-u: We generate a compressed address with key x and it collides with an uncompressed address made from key y
u-c: We generate an uncompressed address with key x and it collides with a compressed address made from key y

At the moment - because we are generating both types and because we have both types in the filter, we are potentially catching all these 4 types of collisions. So yes: doing uncompressed and compressed is mandatory.

And yes, looking at 2159 private keys means we will compute 2160 addresses. They may not be unique though. This is under investigation and not necessarily a bad thing for us. Not unique = there are collisions.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Its_a_Meeeee
Newbie

Offline

Activity: 6
Merit: 0

 April 13, 2017, 05:48:34 AM

I reject and denounce myself

After a night of research I found, that this thread somewhere along the way introduced to me the concept of uncompressed and compressed addresses,
which I've had never heard of before, and really threw me for a loop.

I also found that there are no such addresses.
It is allowed however, to represent/store/use your public key in a compressed version of its full length!

This is shocking to me. It allows every private key to control TWO of all of the 2160 addresses
Another fact I just didn't realize so far.

Now that would also mean there are possible collisions (adding to the ones LBC is already looking for).
private_key_UNO resolves to public_key_uncompressed_A and public_key_compressed_A

Do I understand it correctly, that now there could exist another private key resolving to either one of those?
private_key_DUO resolves to public_key_uncompressed_X and public_key_compressed_A
or
private_key_DUO resolves to public_key_uncompressed_A and public_key_compressed_X

Holy crap! Collision inception.
I feel like I don't know my coins at all right now

EDIT:
Hi Rico seems we posted rather synced ;-)
I will enjoy your post with a nice cup of coffee.
Learning so much in this thread :-)

unknownhostname
Member

Offline

Activity: 61
Merit: 10

 April 13, 2017, 07:07:22 AM

6b2749936df41b73239c1c823642c0a82af74ab6:c:priv:000000000000000000000000000000000000000000000000000a489a332ff001 + 0xfbf
rico666
Hero Member

Offline

Activity: 910
Merit: 1005

฿ → ∞

 April 13, 2017, 07:36:09 AM

Now that would also mean there are possible collisions (adding to the ones LBC is already looking for).
private_key_UNO resolves to public_key_uncompressed_A and public_key_compressed_A

Do I understand it correctly, that now there could exist another private key resolving to either one of those?
private_key_DUO resolves to public_key_uncompressed_X and public_key_compressed_A
or
private_key_DUO resolves to public_key_uncompressed_A and public_key_compressed_X

Not only could, but most certainly does. Actually - on average - as much as

297

private keys could exist that resolve to ONE particular address (no matter if compressed or uncompressed). 296 of these via the compressed route, 296 of these via the uncompressed route.

Quote
Learning so much in this thread :-)

Me too - and then there are people who claim this is not beneficial.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
unknownhostname
Member

Offline

Activity: 61
Merit: 10

 April 13, 2017, 10:27:46 AM

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba
Real-Duke
Legendary

Offline

Activity: 1162
Merit: 1014

Bitcore (BTX) - Airdrops every Monday

 April 13, 2017, 10:41:59 AM

f152befd8c60892eb296e937266bf9f3e38f2c5a:u:priv:000000000000000000000000000000000000000000000000000a78990f8ff001 + 0xfba
And our daily easter egg give us today

 ▀██▄ ▄██▀            ▐█████▌           ▄███▀███▄         ▄████▄  ▀███▄       ▄███▀ ▀██▄  ▀███▄     ▄███▀  ▄█████▄  ▀███▄   ▄███▀  ▄███▀ ▀███▄  ▀███▄  ███▀  ▄████▌   ▐████▄  ▀███ ███   ██▀  ██▄ ▄██  ▀██   ██████   ███  ███   ███  ███   ██████   ███   ███████   ███   ███ ███   ███▄▄       ▄▄███   ███  ███▄   ▀▀█████████▀▀   ▄███   ▀████▄▄           ▄▄████▀      ▀▀███████████████▀▀ DeepOnion ...▬  TOR INTEGRATED & SECURED  ▬... ★  Anonymity Guaranteed★  Anonymous and Untraceable★  Guard Your Privacy ........★★  JOIN THE NEW  ★★..............✈️ AIRDROP..... ▄▄██████████▄▄    ▄███▀▀      ▀▀█▀   ▄▄   ███▀              ▄███  ███              ▄███▀   ▄▄ ███▌  ▄▄▄▄      ▄███▀   ▄███▐███  ██████   ▄███▀   ▄███▀███▌ ███  ███▄███▀   ▄███▀███▌ ███   ████▀   ▄███▀███▌  ███   █▀   ▄███▀  ███▐███   ███     ▄███▀   ███ ███▌   ███  ▄███▀     ███  ███    ██████▀      ███   ███▄             ▄███    ▀███▄▄       ▄▄███▀      ▀▀███████████▀▀ ...Verified..........with DeepVault......
unknownhostname
Member

Offline

Activity: 61
Merit: 10

 April 13, 2017, 06:46:42 PM

f9362f7da717b421680e31a0fdc61b8a6c7118ca:u:priv:000000000000000000000000000000000000000000000000000aaa676bdff001 + 0xfff
TooDumbForBitcoin
Legendary

Offline

Activity: 1344
Merit: 1001

 April 13, 2017, 10:45:56 PM

https://motherboard.vice.com/en_us/article/the-large-bitcoin-collider-is-generating-trillions-of-keys-and-breaking-into-wallets

Next, Oprah!!  (Does she still have a show?)

Hey, Rico, don't forget all us little people.

█████
████████████
█████████████████
██
████████████████
███████████████████
███████████████████████
█████
██████████████████
██████████████████████
██████████████████████
█████████████████████
█████
███████████████████
█████
█████████████████
███████████████████
███
███████████████
████████████
██
█████
cashbet

██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
 The Official Cryptocurrency of Arsenal Football Club ♦ PLAYER PROTECTION ♥ TRUST AND TRANSPARENCY ♠ REDUCED FEES ♣

██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
coinableS
Legendary

Offline

Activity: 1064
Merit: 1000

 April 14, 2017, 12:46:02 AM

Glad to see this is still going. I come to check this thread every so often, it's always a good read. Wondering if Rico is going to start a multisig one next

rico666
Hero Member

Offline

Activity: 910
Merit: 1005

฿ → ∞

 April 14, 2017, 05:57:15 AM

Glad to see this is still going. I come to check this thread every so often, it's always a good read. Wondering if Rico is going to start a multisig one next

All Multisig hash160 have been part of the bloom filter we check against for the past month or so.

@TooDumbForBitcoin

About the Motherboard article: No matter how hard one tries, there's always some precision lost in these articles, so "experts" should take them with a grain of salt. Effectively it's just a superficial introduction to the broader public. It's my contribution so scribes also get something to do for a living.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
unknownhostname
Member

Offline

Activity: 61
Merit: 10

 April 14, 2017, 07:39:42 AM

TooDumbForBitcoin
Legendary

Offline

Activity: 1344
Merit: 1001

 April 14, 2017, 10:55:33 AM

@TooDumbForBitcoin

About the Motherboard article: No matter how hard one tries, there's always some precision lost in these articles, so "experts" should take them with a grain of salt. Effectively it's just a superficial introduction to the broader public. It's my contribution so scribes also get something to do for a living.

Rico

It's usually sobering for me to read a "MSM" article about a subject I know a little more about, relative to the general reading audience.  Extrapolating the inaccuracies one notices in areas of their own expertise to all "MSM" articles makes one realize that "MSM" articles are generally poor sources for unbiased or technically accurate reporting.

█████
████████████
█████████████████
██
████████████████
███████████████████
███████████████████████
█████
██████████████████
██████████████████████
██████████████████████
█████████████████████
█████
███████████████████
█████
█████████████████
███████████████████
███
███████████████
████████████
██
█████
cashbet

██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
 The Official Cryptocurrency of Arsenal Football Club ♦ PLAYER PROTECTION ♥ TRUST AND TRANSPARENCY ♠ REDUCED FEES ♣

██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
██████
██
██████
██  ██
josh5
Newbie

Offline

Activity: 5
Merit: 0

 April 14, 2017, 01:20:43 PM

Quick question, please excuse my ignorance on this ... I've searched everywhere and can't really find an answer.

If (hopefully when) I receive my found.txt with the priv key in hex, how do I convert that to a WIF?
Is there something simple I'm completely missing here? I'm terrible at math so hopefully there's a tool to do this.

Watch out unknownhostname .. I'm coming for ya ... very, very slowly albeit
 Pages: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [45] 46 47 48 49 50 51 52 53 54 55 56