BTCCollider question

[Kostelooscoin]

Hello I would like to know how BTCCollider works (https://github.com/JeanLucPons/BTCCollider)

how does he manage to find these 2 addresses:

Collision: 60 bits
Priv (WIF): p2pkh:L3K5y3LyKXUCmSmpptJrAG5w6o9r6YbfBQyWATV5gyhQ5dwq8moB
Priv (WIF): p2pkh:L3K5y3LyKXUCmSmpptJrAG5w6o9r6YbfBQxC9tihuggxfWGSwDY6
Add1: 12DgBEott9LiyPWspyZfY7K2EWv79498u2
Add2: 12DgBEott9LpupgZkw1fKKKK8pYPMoPatY6

is it random or does it start from one point to the next?

[NotATether]

Simple TL;DR is that it generates addresses knowing that if all the possible address prefixes that are M characters long M-character long prefix amount to N prefixes in total, it's going to take advantage of the birthday paradox phenomenon to keep generating addresses and it's going to eventually find two addresses that both have the same M-character prefix (one of those N prefixes). The more addresses generated the higher the probability of two having the same prefix becomes.


BTCcollider like most of Jean_Lucs programs have an optimization to reduce the number of addresses searched using something called Distinguished Points.

If you're familiar with Kangaroo it's using the same Distinguished Point method as it to ignore leading bits of two numbers so that they are otherwise identical.

This is Kangaroo's Github page. Replace Kangaroo with BTCcollider because both the "birthday problem" BTCcollider says it solves and Kangaroo's hops are kinds of random walks:

The distinguished point (DP) method is an efficient method for storing random walks and detect collision between them. Instead of storing all points of all kangagroo's btccollider's random walks, we store only points that have an x value starting with dpBit zero bits.

In other words when using DPs you ignore the prefix of two numbers and compare the rest of their parts. A distinguished point = a collision = a solution. This is why discussion about the number of DPs is frequent here because the number of DPs tells how many collisions/solutions there are.

Don't worry about dpBit in the quote above, it's not the number of DPs but it's the number of bits to permanently set to 1 (or 0) in a mask that can then be used to calculate the number of distinguished points there are (in the quote below the DP size causes some bits at the beginning to be permanently set to 1 and not compared):

DP size: 10 [0xFFC0000000000000]
DP size: 5 [0xF800000000000000]
DP size: 2 [0xC000000000000000]
DP size: 1 [0x8000000000000000]
DP size: 0 [0x0000000000000000]

All those zeros represent groups of 4 bits (because these are hex numbers and each one encodes 4 bits) that will be used to search for the rest of the address.

[Kostelooscoin]

all these seem to me super complicated do you have an example has drawn indicative that would better explain this process ?

[NotATether]

all these seem to me super complicated do you have an example has drawn indicative that would better explain this process ?

Sure I made a diagram of it.



As you can see, the more addresses we generate, the more likely that any two of the will have the same prefix (collision).

Depending on the total number of prefixes possible, which the prefix length allows for, we will reach 100% probability slowly, but quicker if there are less combinations of prefixes possible, such as by using a smaller prefix length.



Distinguished points is a technique used for the private key to keep a certain part of it fixed while BTCcollider searches the rest of the prefix. It allows you to find collisions more quickly at the expense that you may miss some solutions (by keeping some bits fixed).

I believe the program actually builds a prefilled table of RIPEMD160s, that is what it is looking to match.

Example 56 bit search result:

Code:

H1=7611B2A2E68C3741824EA64D60EEAFA7F71904A0
H2=7611B2A2E68C378130D2487A10A6F0210B031090
Add1: 1BmHwJS6YxB6eqTaXFFKkGZBs5YMdwqpkk
Add2: 1BmHwJS6YxBhMwVHBcexUtf4WGGsKFPtke

As you can see, the Hash160s (H1, H2) have matching 56 bits but the addresses do not. I've ran it a few times where the addresses didn't match other than the leading "1". So I would just change the top part of your diagram.

Good point. But since the top diagram is mainly to show the birthday paradox and not actual address generation I think I'll just change the prefixes at the beginning of each address to be all different. Something like the code block in your quote should be easy for anybody to understand without a diagram.

[WanderingPhilospher]

I believe the program actually builds a prefilled table of RIPEMD160s, that is what it is looking to match.

Example 56 bit search result:

Code:

H1=7611B2A2E68C3741824EA64D60EEAFA7F71904A0
H2=7611B2A2E68C378130D2487A10A6F0210B031090
Add1: 1BmHwJS6YxB6eqTaXFFKkGZBs5YMdwqpkk
Add2: 1BmHwJS6YxBhMwVHBcexUtf4WGGsKFPtke

As you can see, the Hash160s (H1, H2) have matching 56 bits but the addresses do not. I've ran it a few times where the addresses didn't match other than the leading "1". So I would just change the top part of your diagram.

[Kostelooscoin]

an example of generation ?

[Kostelooscoin]

it starts by generating a private key to the base because without private key no address

[citb0in]

Collision: 60 bits
Priv (WIF): p2pkh:L3K5y3LyKXUCmSmpptJrAG5w6o9r6YbfBQyWATV5gyhQ5dwq8moB
Priv (WIF): p2pkh:L3K5y3LyKXUCmSmpptJrAG5w6o9r6YbfBQxC9tihuggxfWGSwDY6
Add1: 12DgBEott9LiyPWspyZfY7K2EWv79498u2
Add2: 12DgBEott9LpupgZkw1fKKKK8pYPMoPatY6

The distinguished point (DP) method is an efficient method for storing random walks and detect collision between them.
[...]
A distinguished point = a collision = a solution.
[...]
This is why discussion about the number of DPs is frequent here because the number of DPs tells how many collisions/solutions there are.

I see no collision on those examples.
Partly matched string != collission IMHO

[Kostelooscoin]

what is this step by step method
from the private key to the colision
and how does this distinguished point work

[Kostelooscoin]

is there any possibility to create btccollider in python version ?