How would I be able to tell if one of my addresses was collided?
I believe they will move your Bitcoins for you. Correct? 
Topic: Large Bitcoin Collider Thread 2.0 - page 12. (Read 57143 times)
How would I be able to tell if one of my addresses was collided?
New client 1.192 (see News in my sig for changes);
User 735912756 blacklisted for insane spamming. Note from the author: "If you start using AWS for your LBC efforts, please make sure your config is right or bear the consequences."
also, the block forfeiture script ran, result can be inspected here: https://lbc.cryptoguru.org/static/logs/171110-forfeiture_run.log
The acquired blocks are kept separate from the blocks you delivered (done by your work).
You can see them in the "acquired"-field when doing ./LBC -q
LBC Pot payout
User 735912756 blacklisted for insane spamming. Note from the author: "If you start using AWS for your LBC efforts, please make sure your config is right or bear the consequences."
also, the block forfeiture script ran, result can be inspected here: https://lbc.cryptoguru.org/static/logs/171110-forfeiture_run.log
The acquired blocks are kept separate from the blocks you delivered (done by your work).
You can see them in the "acquired"-field when doing ./LBC -q
Code:
{
...
"done" : 12345,
"acquired" : 768
}
LBC Pot payout
Code:
# lbcadmin payout
__rico666__ would be eligible by activity, but has no BTC address set!
kknd2017 would be eligible by activity, but has no BTC address set!
testing123 would be eligible by activity, but has no BTC address set!
Total blocks of eligible users: 2264937133
Satoshi in LBC Pot: 12274528
Distribution as follows:
5b8f5562ac3873408d26852d74434040 (0.00528064104991650556333565131231392990721) -> 64817.37642514954519931922543123407743608654688 Satoshi
5dcb3e5d07a8ccdbc00912773ca806dd (0.001196988631825305501757606620510115500853) -> 14692.470477021403489877791676436786998454172384 Satoshi
UnimatrixONE (0.3679931177144950804248216632509949670201) -> 4516941.8271938658705367254005809087505472940128 Satoshi
__ac0v__ (0.3891475852279207610130166027879768087144) -> 4776602.9310124997628355806553858994019155468032 Satoshi
_maxairz_ (0.002621289533160742258889002019818975699579) -> 32175.091770888459357516304184324572155802023712 Satoshi
b8a357e43e373ac086bed2c374085298 (0.03876699212560439751508105103771990655071) -> 475846.53032151069422199278323192204911407331488 Satoshi
cagrund_ (0.1335338785317181693272190261715312696054) -> 1639065.3309861735575156910988751933716470312512 Satoshi
likizjucdordvd (0.06145950718535903839587939679913402700171) -> 754386.44181289070684329674063408099018524544288 Satoshi
At 10:48 PM Thursday (UTC), Rico announced on Discord that we crossed into the 54 bit search space.
There are a lot of dead/dormant accounts, who seem to just have tested LBC and then stopped colliding. And this is perfectly ok.
On the other hand, I don't think it makes sense to keep these accounts around indefinitely as most of them have some single-digit Gkeys, but everyone started out small, so an automated cleanup mechanism should not immediately reap small accounts.
This is what will happen:
Starting with 53bit search space (which is due in about a month given current speed), accounts that have been inactive for (7 + Gkeys_delivered) days will be reaped and their Gkeys will be added proportionally to the other active accounts. Consider it a kind of Proof of Stake.
e.g.
Account has delivered 5 Gkeys and is inactive. This account can be inactive for 12 days before it is reaped.
Account has delivered 1000 Gkeys and is inactive. This account can be inactive for 1007 days before it is reaped.
It's clear that accounts that did some serious colliding in the past with several thousand Gkeys do not have to fear to be reaped anytime soon.
But I should point out that as speed of colliding rates changes over time, we may change this rule at some point in the future. (Imagine if the hardware/software in 5 years can give you 1Gkey/s then probably 1 Gkey will buy you 1 hour idle time. Or something like that)
For now, 7 days idle time is ok for everyone, above that: 1Gkey = 1 day.
On the other hand, I don't think it makes sense to keep these accounts around indefinitely as most of them have some single-digit Gkeys, but everyone started out small, so an automated cleanup mechanism should not immediately reap small accounts.
This is what will happen:
Starting with 53bit search space (which is due in about a month given current speed), accounts that have been inactive for (7 + Gkeys_delivered) days will be reaped and their Gkeys will be added proportionally to the other active accounts. Consider it a kind of Proof of Stake.
e.g.
Account has delivered 5 Gkeys and is inactive. This account can be inactive for 12 days before it is reaped.
Account has delivered 1000 Gkeys and is inactive. This account can be inactive for 1007 days before it is reaped.
It's clear that accounts that did some serious colliding in the past with several thousand Gkeys do not have to fear to be reaped anytime soon.
But I should point out that as speed of colliding rates changes over time, we may change this rule at some point in the future. (Imagine if the hardware/software in 5 years can give you 1Gkey/s then probably 1 Gkey will buy you 1 hour idle time. Or something like that)
For now, 7 days idle time is ok for everyone, above that: 1Gkey = 1 day.
The 53bit search space is nearing completion, and see below for the current forfeiture list.
So in probably less than 24 hours accounts worth ~1300 Gkeys are going to be reaped and redistributed.
If anyone sees an old account of his and wants it to be merged, ping me (Discord).
Code:
07012014 - merits (13) < inactive days (61)
07784296c5953af2050fa559e232d3ce - merits (21) < inactive days (83)
27f9e8cdd9bee45f6d943b04d724fbda - merits (8) < inactive days (78)
2ebafbde0b5046923e7c63ea7f085719 - merits (13) < inactive days (26)
3f28ef225fd629b144789cd7b6396019 - merits (14) < inactive days (66)
4a35b30adba2af2ba2c3e543176b3bf2 - merits (8) < inactive days (76)
4d0262b4d8587eaff46cd76a142b9f7d - merits (8) < inactive days (83)
5279ffedcc725c89c21eef937c9b1f1b - merits (12) < inactive days (77)
53734e6a8ae7ca7cef9c9ca2d26b6989 - merits (8) < inactive days (62)
5428f3d893b44cf06cd9e3a23fb684d4 - merits (27) < inactive days (65)
54bff9f1f6ebc70f75500306174379e1 - merits (8) < inactive days (77)
55983aa8ec125415ef295bb6181d2376 - merits (36) < inactive days (98)
56183636ede39effd426430665e29ab1 - merits (8) < inactive days (67)
5adef64d5f5f26f9bb61b5dc1e51ae80 - merits (8) < inactive days (9)
7318cd5b2c9a2bccb63ee749008d1464 - merits (10) < inactive days (78)
7a5e0c4959a68cc0b4abb6cabde3d8cc - merits (8) < inactive days (78)
82b80cce73915a6825c64f806e649ac6 - merits (13) < inactive days (77)
8a4b86be2a3157a53c82aaffebf62ef9 - merits (8) < inactive days (77)
EasterZombieJStar - merits (161) < inactive days (206)
HereticalSauce - merits (133) < inactive days (148)
K1LLY0UALL - merits (104) < inactive days (163)
MarinaSG - merits (26) < inactive days (50)
OoOooOoO - merits (59) < inactive days (118)
RobinJonson - merits (129) < inactive days (192)
Twolklefarmeur - merits (9) < inactive days (17)
ZellDincht - merits (55) < inactive days (203)
__george__ - merits (10) < inactive days (12)
a7520deb0d51f0c5ea5821731834b9df - merits (24) < inactive days (65)
br123456 - merits (8) < inactive days (185)
cfc3b9abae26b0d43b49dba79ad82c39 - merits (9) < inactive days (90)
dddba64d0bbf5f0fdd392ea65772179b - merits (8) < inactive days (78)
depachlbc - merits (97) < inactive days (133)
e026c2d3c48d36b830ebc9d69120bed3 - merits (42) < inactive days (81)
e8427d71a63040e3ac8b11941fd5e651 - merits (8) < inactive days (77)
edae837b39e05377674b20ba9804ae39 - merits (23) < inactive days (79)
f0f13a3775adf04d79fa568f68295a8e - merits (10) < inactive days (64)
f68a5fe027b2d395551b507e3d9ba4ed - merits (15) < inactive days (28)
f829f754fafc9d588a12041c814b1580 - merits (15) < inactive days (28)
f88af2215c8106bc6a43669d799ab1d8 - merits (8) < inactive days (77)
floppyjohn - merits (103) < inactive days (148)
iamback12 - merits (8) < inactive days (92)
ilovebtc00777 - merits (16) < inactive days (93)
ishortbitcoin - merits (77) < inactive days (92)
jazzjazz - merits (72) < inactive days (164)
merror1203 - merits (22) < inactive days (26)
morantis - merits (8) < inactive days (121)
oootah123 - merits (122) < inactive days (188)
skywalker - merits (8) < inactive days (34)
slaingerz - merits (42) < inactive days (180)
someonenewwho - merits (29) < inactive days (206)
tester397564 - merits (21) < inactive days (25)
wanwandrew - merits (8) < inactive days (49)
wanwanwan - merits (9) < inactive days (49)
Total forfeited Gkeys: 1329.98752593994140625
On Rico's advise just now, I added a hook-find file because I am running in the cloud.
https://github.com/dcw312/lbc-client-docker/commit/15874d4dc14fdb48e92b3288ff98bd9645172c26
Rico suggested:
Mine sends to a queue that I would prefer not to share.
https://github.com/dcw312/lbc-client-docker/commit/15874d4dc14fdb48e92b3288ff98bd9645172c26
Rico suggested:
Code:
#!/bin/bash
mail -s 'LBC FOUND' [email protected] < FOUND.txt
Mine sends to a queue that I would prefer not to share.
If it were so, at the moment there would be only a few people currently active that could get the LBC Pot (at least in the top 30, from what I can see).
it is so, and at the moment would look something like that:
Eligible users:
5b8f5562ac3873408d26852d74434040
b8a357e43e373ac086bed2c374085298
kknd2017
__rico666__
likizjucdordvd
UnimatrixONE
_maxairz_
cagrund_
__ac0v__
5dcb3e5d07a8ccdbc00912773ca806dd
amthenia
Rexikonn
735912756
Total blocks of eligible users: 2677768070
Satoshi in LBC Pot: 12274528
Distribution as follows:
userid (share in total eligible blocks) -> share in LBC Pot in Satoshi
Code:
5b8f5562ac3873408d26852d74434040 (0.003923506340114063724719818621184769000551) -> 48159.188429907598382857705820653840270795264928 Satoshi
5dcb3e5d07a8ccdbc00912773ca806dd (0.0009264790434221586636515536612549121926008) -> 11372.0929598985023374335776585759348456199124224 Satoshi
735912756 (0.001599170610769139539407533528473210900599) -> 19629.064438662904812364873706183224449307642272 Satoshi
Rexikonn (0.01046480474315312901613618837422316414431) -> 128450.53883436589039617609601267670653792913568 Satoshi
UnimatrixONE (0.3025223849950529882896094134097281995001) -> 3713319.4852485577662444828539612842571535634528 Satoshi
__ac0v__ (0.3143228935432036875396755328403030812149) -> 3858165.1578370728724089984387632196988585640672 Satoshi
__rico666__ (0.03241580104433764497012618422924133231598) -> 397888.65756115166463987301185498115226980135744 Satoshi
_maxairz_ (0.001672999260163707904695420466343823421571) -> 20535.276262858717260005269985910318215129043488 Satoshi
amthenia (0.004009046235285044682753275193097660620025) -> 49209.1502683008689397061934493826420149942232 Satoshi
b8a357e43e373ac086bed2c374085298 (0.02908196302452736319318349329634063490794) -> 356967.36943952580628090019760374542071528695232 Satoshi
cagrund_ (0.1118683112835832716460765028092966990976) -> 1373130.7191630588081513721238747909933810659328 Satoshi
kknd2017 (0.1366251536489491414392733422951002623614) -> 1677009.2739683284071723209396547924331623504192 Satoshi
likizjucdordvd (0.05056748622743865939069174127541225032234) -> 620692.02558831019297350871765380337812457135552 Satoshi
Now, this is only to demonstrate the Sub-Satoshi accuracy of the distribution script and which/how many users currently actually are eligible.
The numbers may change, because I see users who still can make it into the list of eligible users as e.g.
https://lbc.cryptoguru.org/stats/testing123
and also, I will let run the "Gkeys forfeiture reaper" script before the distribution script.
While the Gkeys gained by the forfeiture of others will be recorded in a separate place, they will count for share computation.
edit:
And of course you need to have a BTC address set for payout, else cry (holy crap):
UnimatrixONE would be eligible by activity, but has no BTC address set!
__ac0v__ would be eligible by activity, but has no BTC address set!
__rico666__ would be eligible by activity, but has no BTC address set!
amthenia would be eligible by activity, but has no BTC address set!
kknd2017 would be eligible by activity, but has no BTC address set!
Total blocks of eligible users: 562942816
Satoshi in LBC Pot: 12274528
Distribution as follows:
Code:
5b8f5562ac3873408d26852d74434040 (0.01869944815140868588684503258675566791495) -> 229526.8999190141543612841841470448749807553936 Satoshi
5dcb3e5d07a8ccdbc00912773ca806dd (0.004413265307572554580748038180844286677956) -> 54170.748589227933232920055595842260468597904768 Satoshi
735912756 (0.007620468505987649019043525728197586591104) -> 93537.654049863565538422289769481666144930598912 Satoshi
Rexikonn (0.04979600627854890326906667550403556442223) -> 611222.47335422431254545044234119864849646595744 Satoshi
_maxairz_ (0.007998254657538786319639257995256129176716) -> 98174.800745090243766429022161995224751217490048 Satoshi
b8a357e43e373ac086bed2c374085298 (0.1385989158799390380709645648981867458452) -> 1701236.2737379563610951205388506103611057910656 Satoshi
cagrund_ (0.5322046493617568431675305365296641426542) -> 6532560.8703210665006514622614883853496049722176 Satoshi
likizjucdordvd (0.2406689918572475396861623685770598767176) -> 2954098.2792835569288089112056454416144467292928 Satoshi
Unknown, what the heck are you running this project on?!
Join our Discord Chat and find out. (Mostly cloud services, pretty big iron machines with 80 - 220 Mkeys/s)
Unknown, what the heck are you running this project on?!
Pool has 1.2 Gkeys/s already.
The "one week before bit boundary" was exactly this. You can never know when you are "just one week before the bit boundary".
Interestingly, if Unknownhostname overdoes it, he will not be eligible for LBC Pot distribution himself.
The "one week before bit boundary" was exactly this. You can never know when you are "just one week before the bit boundary".
Interestingly, if Unknownhostname overdoes it, he will not be eligible for LBC Pot distribution himself.
If it were so, at the moment there would be only a few people currently active that could get the LBC Pot (at least in the top 30, from what I can see).
And besides, If we could mantain a 1.5 Gkeys/s speed for 1 year, we would find #54, #55 and #56 by the end of 2018.
EDIT: now we are almost at 2 Gkeys/s, #54 by the end of this year!
And we will hit the next bit boundary in less than 4 days! At this speed, in the next 50 days we will generate as many addresses as we have been generating from the beginning of this project so far. I feel like we are going to reach the next bit boundary of the search space. Maybe we are already in the week before the end of the 53 bits. Thanks to Unknownhostname.
It's very well possible. Last time he managed to push pool performance to 2.5 Gkeys/s with CPUs only.
This time he's back and has weapons of mass collision at his hands.
Pool has 1.2 Gkeys/s already.
The "one week before bit boundary" was exactly this. You can never know when you are "just one week before the bit boundary".
Interestingly, if Unknownhostname overdoes it, he will not be eligible for LBC Pot distribution himself.
Every time the LBC reaches a bit boundary in the search space (53 bits, 54 bits, ...) the current LBC pot will be distributed proportionally according to the Gkeys delivered among those who were active in the week before the LBC hits this boundary. This means, if you look at your Per-User statistics (e.g. https://lbc.cryptoguru.org/stats/__rico666__) at the time the LBC crosses this boundary, there can be no single 2h average point with 0 Mkeys/s or else you are not eligible - no matter how many Gkeys you have submitted so far. On the other hand, the speed in there (as long as it is above 0 Mkeys/s) does not have any influence on the payout - only your Gkeys delivered so far do.
I feel like we are going to reach the next bit boundary of the search space. Maybe we are already in the week before the end of the 53 bits. Thanks to Unknownhostname.
in the next days I will add a section called "Probability & LBC".
I was able to find this formula:
p(different) ~ e^(n^2 / -2 * T)
https://betterexplained.com/articles/understanding-the-birthday-paradox/
Which calculates the probability of avoiding a collision for a given search size (2^x) as:
Code:
search_range p_different
70 0.999999523163
72 0.999992370635
74 0.999877937138
76 0.998048781107
78 0.969233234476
79 0.882496902585
80 0.606530659713
81 0.135335283237
82 0.000335462627903
83 1.26641655491e-14
84 2.57220937264e-56
with the following python code
Code:
import numpy as np
def print_different(bit):
T = np.float128(2 ** 160)
n = np.float128(2 ** bit)
f1 = np.power(n, 2)
f2 = np.divide(f1, T)
f3 = np.divide(f2, -2)
print bit, np.exp(f3)
search = range(70, 85, 2)
print 'search_range', 'p_different'
for x in search:
print_different(x)
From the LBC website: In the rare event of a collision, the funds on the address in question would become accessible to the collision finder.
I was confused about this earlier but I found my point of confusion. I'll add here in the hope it saves others some time.
The public key is exposed when the sender (Alice) lists it as an input to a transaction. I thought that the public key could be compared to the previous transaction or another transaction. While there may be another transaction from Alice that identifies the full public key from her address, there is no verification that the same public key is being used for all transactions from her address. So if we find a key pair X2 that hash160(X1) == hash160(X2), the finder could transfer the money .
https://en.bitcoin.it/wiki/Transaction#Principle_example_of_a_Bitcoin_transaction_with_1_input_and_1_output_only
I was confused about this earlier but I found my point of confusion. I'll add here in the hope it saves others some time.
The public key is exposed when the sender (Alice) lists it as an input to a transaction. I thought that the public key could be compared to the previous transaction or another transaction. While there may be another transaction from Alice that identifies the full public key from her address, there is no verification that the same public key is being used for all transactions from her address. So if we find a key pair X2 that hash160(X1) == hash160(X2), the finder could transfer the money .
Code:
Input:
Previous tx: f5d8ee39a430901c91a5917b9f2dc19d6d1a0e9cea205b009ca73dd04470b9a6
Index: 0
scriptSig: 304502206e21798a42fae0e854281abd38bacd1aeed3ee3738d9e1446618c4571d10
90db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d5d6cc8d25c6b241501
Output:
Value: 5000000000
scriptPubKey: OP_DUP OP_HASH160 404371705fa9bd789a2fcd52d2c580b65d35549d
OP_EQUALVERIFY OP_CHECKSIG
Has anyone seen a calculation on how many attempts it should take to have a high chance of finding a collision? (The binomial probably) I tried calculating it but the library I used wasn’t able to handle the large numbers.
This is a very interesting question, in the next days I will add a section called "Probability & LBC".
I like where you are going with expanding the search space because it puts the focus on proving the likelihood of collision. I think this is the interesting question.
Looking at all used addresses seems the simplest way to expand the search space because those addresses are publicly available.
Has anyone seen a calculation on how many attempts it should take to have a high chance of finding a collision? (The binomial probably) I tried calculating it but the library I used wasn’t able to handle the large numbers.
Looking at all used addresses seems the simplest way to expand the search space because those addresses are publicly available.
Has anyone seen a calculation on how many attempts it should take to have a high chance of finding a collision? (The binomial probably) I tried calculating it but the library I used wasn’t able to handle the large numbers.
I want to make some comments on how LBC works. I take inspiration from this Wuille's comment: https://bitcoin.stackexchange.com/questions/54841/birthday-attack-on-p2sh/54844
The aim of the following considerations is to help bitcointalkforum's users to understand better what (and why) LBC is doing.
For this reason, I will make some simplifications, like 20M = 2^24 instead of 20M = 2^24.2535 and so on. In this context above all I care about the concepts.
*************************************************************************************************************************************************************************************************
THE THEORY
The theory:
1) Preimage search: given a hash H, find X such that Hash(X) = H.
2) Collision search: find an X and a Y, such that X != Y and Hash(X) = Hash(Y).
These 2 problems look similar, but they are actually very different. In our context, X is a public key, H = hash160(X) is a bitcoin address:
1) Preimage search: given a particular address H, find a public key X such that hash160(X) = H.
2) Collision search: find two public keys X and Y, such that X != Y and hash160(X) = hash160(Y) .
A preimage search for a 160-bit hash function needs 2^160 steps. A collision search however only needs 2^80 steps.
Example of a preimage search:
You choose a particular address H.
Then you generate:
2^160 public keys Xi and store the corresponding addresses Hi = hash160(Xi)
in a list L= {H1, H2, H3, .....H2^160}
If they are all different, you will get surely a match between an Hi and the H you chose (Hi = H). So we say that there are needed 2^160 steps to find an Xi (a pre-image) of H=Hi.
Note: Xi is only one preimage, since we don't know how H was generated, we can't say we have found a collision (we don't have two different public keys but only one that produces for sure H)
Example of a collision search:
Your purpose here is to find a couple ("collision" implies always at least two) of public keys X and Y that generate the same address H, any address H, you can't choose it.
You generate:
a list L1 of 2^80 random addresses Hi => L1= {H1, H2, H3, .....H2^80} where Hi = Hash160(Xi)
and
a list L2 of other 2^80 random addresses Aj => L2= {A1, A2, A3, .....A2^80} where Aj = hash160(Yj)
"You sort both lists. Then you go through both lists, and find a hash that exists in both in a single iteration. This is the critical point. It is likely that such a collision exists,
because even though there are only 2^80 entries in each list, there are 2^160 combinations of entries. Each of those has a 2^(-160) chance to be a collision.
This is also the explanation of the Birthday Paradox, and such an attack is therefore called a birthday attack." (Wuille)
So we say that there are needed 2^80 steps to find an Xi and Yj (a collision) such that Hi=Aj.
If you noted, the difference between the first case (preimage) and the second one (collision) is that in the first case we are looking for something we chose, a particular address (in LBC we have the UTXO data set, we are assuming now for the sake of simplicity it is always the same during the research) and we get only one preimage (one public key), in the second case we find two public keys that correspond to a random address.
To sum up, we can think at these 2 problems using 2 lists:
preimage search:
L1 = {H1, H2, H3, .....H2^160} --> you have to generate randomly 2^160 addresses -> 2^160 steps
L2 = {H} --> H is the particular prefixed address you chose
collision search:
L1 = {H1, H2, H3, .....H2^80} --> you have to generate randomly 2^80 addresses
L2= {A1, A2, A3, ..... A2^80} --> you have to generate randomly 2^80 addresses -> 2^80 steps (2^81 at the most)
The fact that the number of the elements of the 2 lists in the second case is the same (this number is equal - more or less - to the square root of the number of the elements in L1 in the first case) makes less expensive to perform a collision search.
This point is very important.
A metaphor to visualize the difference between a preimage search (looking for a prefixed target using randomly generated elements) and a collision (a chance "encounter" between two elements of two random sequences):
imagine you are in a room.
1) In that room there is a fixed target (a single point). If a fly moves randomly, what are the chances that it hit the target? Very low (this is a preimage, to hit a specific target using randomly generated addresses).
2) Now imagine that the target turns into another fly.
Then we have two flies that move randomly in the room. What are the chances that one hit the other one? Much more. This is a collision.
*************************************************************************************************************************************************************************************************+
*************************************************************************************************************************************************************************************************
THE CURRENT LBC APPROACH
Ok, now how is the LBC's approach in relation to these two problems?
To start, LBC performs a preimage search, where L2 contains not only 1 but 20M = (about) 2^24 addresses taken from the UTXO data set:
preimage search:
L1 = {H1, H2, H3, .....H2^160} --> we can think that it is randomly generated
L2 = {A1, A2, ......, A2^24} --> UTXO data set, it is not randomly generated!!!
in this case you can note that there are 2^160 * 2^24 combinations of entries, then we can reduce L1 from 2^160 to 2^136 addresses:
L1 = {H1, H2, H3, .....H2^136} --> the addresses we have to generate to get a single preimage
L2 = {A1, A2, ......, A2^24} --> the UTXO data set, these are "data", we don't have to compute these
I repeat: we are taking care of a preimage search problem. In LBC project we call "collision" what actually is a "preimage". Infact our difficulty is nearer to 160 bit than 80 bit. We want to find preimages (public keys) only of some particular hashes (addresses from UTXO).
Now imagine we find a preimage, i.e. we find a public key Xi such that Hi = Aj for some Aj in L2 (remember: Hi = hash160(Xi))
Then, only if we can prove that the public key Xi is different from the public key Yj that produces Aj, we can claim to have found a real collision too (usually we don't have Yj, how to get this information is a real problem)
Only in this case we can go from a single preimage to two preimages and then get a real collision.
*************************************************************************************************************************************************************************************************
*************************************************************************************************************************************************************************************************
SOME IDEA FOR THE FUTURE
Can we improve the odds to find a preimage/collision?
My guess: we should extend the L2 list (and extend the corresponding bloom filter to not rise the false positive rate, but this is a technical issue)
Remember: if L2 becomes bigger, then L1 becomes smaller, and L1's size is the difficulty of our task (because: size_of_L1 = 2^160 / size_of_L2).
L2's elements can be collected and stored easily, those of L1 don't, L1 is too big.
To extend L2, we have these possibilities:
1) we wait for bitcoin's net grows up naturally
2) we generate a few random millions of addresses (but in this way we shift from a preimage search to a purely random collision search task)
3) we use addresses already generated and stored in blockchain even if they have no more bitcoin (always interesting for me; besides, if we find a preimage of one of these addresses, then we will know for sure if we have a collision too, because all the addresses with at least an output transaction have already exposed their public key)
Narrow down the list L1 is a way to speedup our search, on the other hand we need to rise the speed at which we generate the list L1. Any idea is welcome.
To speedup my ECC library I need to realize a couple of assembly functions. I don't know so much about assembly. If someone is able to help me, I will be happy.
*************************************************************************************************************************************************************************************************
The aim of the following considerations is to help bitcointalkforum's users to understand better what (and why) LBC is doing.
For this reason, I will make some simplifications, like 20M = 2^24 instead of 20M = 2^24.2535 and so on. In this context above all I care about the concepts.
*************************************************************************************************************************************************************************************************
THE THEORY
The theory:
1) Preimage search: given a hash H, find X such that Hash(X) = H.
2) Collision search: find an X and a Y, such that X != Y and Hash(X) = Hash(Y).
These 2 problems look similar, but they are actually very different. In our context, X is a public key, H = hash160(X) is a bitcoin address:
1) Preimage search: given a particular address H, find a public key X such that hash160(X) = H.
2) Collision search: find two public keys X and Y, such that X != Y and hash160(X) = hash160(Y) .
A preimage search for a 160-bit hash function needs 2^160 steps. A collision search however only needs 2^80 steps.
Example of a preimage search:
You choose a particular address H.
Then you generate:
2^160 public keys Xi and store the corresponding addresses Hi = hash160(Xi)
in a list L= {H1, H2, H3, .....H2^160}
If they are all different, you will get surely a match between an Hi and the H you chose (Hi = H). So we say that there are needed 2^160 steps to find an Xi (a pre-image) of H=Hi.
Note: Xi is only one preimage, since we don't know how H was generated, we can't say we have found a collision (we don't have two different public keys but only one that produces for sure H)
Example of a collision search:
Your purpose here is to find a couple ("collision" implies always at least two) of public keys X and Y that generate the same address H, any address H, you can't choose it.
You generate:
a list L1 of 2^80 random addresses Hi => L1= {H1, H2, H3, .....H2^80} where Hi = Hash160(Xi)
and
a list L2 of other 2^80 random addresses Aj => L2= {A1, A2, A3, .....A2^80} where Aj = hash160(Yj)
"You sort both lists. Then you go through both lists, and find a hash that exists in both in a single iteration. This is the critical point. It is likely that such a collision exists,
because even though there are only 2^80 entries in each list, there are 2^160 combinations of entries. Each of those has a 2^(-160) chance to be a collision.
This is also the explanation of the Birthday Paradox, and such an attack is therefore called a birthday attack." (Wuille)
So we say that there are needed 2^80 steps to find an Xi and Yj (a collision) such that Hi=Aj.
If you noted, the difference between the first case (preimage) and the second one (collision) is that in the first case we are looking for something we chose, a particular address (in LBC we have the UTXO data set, we are assuming now for the sake of simplicity it is always the same during the research) and we get only one preimage (one public key), in the second case we find two public keys that correspond to a random address.
To sum up, we can think at these 2 problems using 2 lists:
preimage search:
L1 = {H1, H2, H3, .....H2^160} --> you have to generate randomly 2^160 addresses -> 2^160 steps
L2 = {H} --> H is the particular prefixed address you chose
collision search:
L1 = {H1, H2, H3, .....H2^80} --> you have to generate randomly 2^80 addresses
L2= {A1, A2, A3, ..... A2^80} --> you have to generate randomly 2^80 addresses -> 2^80 steps (2^81 at the most)
The fact that the number of the elements of the 2 lists in the second case is the same (this number is equal - more or less - to the square root of the number of the elements in L1 in the first case) makes less expensive to perform a collision search.
This point is very important.
A metaphor to visualize the difference between a preimage search (looking for a prefixed target using randomly generated elements) and a collision (a chance "encounter" between two elements of two random sequences):
imagine you are in a room.
1) In that room there is a fixed target (a single point). If a fly moves randomly, what are the chances that it hit the target? Very low (this is a preimage, to hit a specific target using randomly generated addresses).
2) Now imagine that the target turns into another fly.
Then we have two flies that move randomly in the room. What are the chances that one hit the other one? Much more. This is a collision.
*************************************************************************************************************************************************************************************************+
*************************************************************************************************************************************************************************************************
THE CURRENT LBC APPROACH
Ok, now how is the LBC's approach in relation to these two problems?
To start, LBC performs a preimage search, where L2 contains not only 1 but 20M = (about) 2^24 addresses taken from the UTXO data set:
preimage search:
L1 = {H1, H2, H3, .....H2^160} --> we can think that it is randomly generated
L2 = {A1, A2, ......, A2^24} --> UTXO data set, it is not randomly generated!!!
in this case you can note that there are 2^160 * 2^24 combinations of entries, then we can reduce L1 from 2^160 to 2^136 addresses:
L1 = {H1, H2, H3, .....H2^136} --> the addresses we have to generate to get a single preimage
L2 = {A1, A2, ......, A2^24} --> the UTXO data set, these are "data", we don't have to compute these
I repeat: we are taking care of a preimage search problem. In LBC project we call "collision" what actually is a "preimage". Infact our difficulty is nearer to 160 bit than 80 bit. We want to find preimages (public keys) only of some particular hashes (addresses from UTXO).
Now imagine we find a preimage, i.e. we find a public key Xi such that Hi = Aj for some Aj in L2 (remember: Hi = hash160(Xi))
Then, only if we can prove that the public key Xi is different from the public key Yj that produces Aj, we can claim to have found a real collision too (usually we don't have Yj, how to get this information is a real problem)
Only in this case we can go from a single preimage to two preimages and then get a real collision.
*************************************************************************************************************************************************************************************************
*************************************************************************************************************************************************************************************************
SOME IDEA FOR THE FUTURE
Can we improve the odds to find a preimage/collision?
My guess: we should extend the L2 list (and extend the corresponding bloom filter to not rise the false positive rate, but this is a technical issue)
Remember: if L2 becomes bigger, then L1 becomes smaller, and L1's size is the difficulty of our task (because: size_of_L1 = 2^160 / size_of_L2).
L2's elements can be collected and stored easily, those of L1 don't, L1 is too big.
To extend L2, we have these possibilities:
1) we wait for bitcoin's net grows up naturally
2) we generate a few random millions of addresses (but in this way we shift from a preimage search to a purely random collision search task)
3) we use addresses already generated and stored in blockchain even if they have no more bitcoin (always interesting for me; besides, if we find a preimage of one of these addresses, then we will know for sure if we have a collision too, because all the addresses with at least an output transaction have already exposed their public key)
Narrow down the list L1 is a way to speedup our search, on the other hand we need to rise the speed at which we generate the list L1. Any idea is welcome.
To speedup my ECC library I need to realize a couple of assembly functions. I don't know so much about assembly. If someone is able to help me, I will be happy.
*************************************************************************************************************************************************************************************************
Hereticalsauce is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
GPUAuth set now.
Thank you, sir.
So, Google wants $140 before they auth me GPU use.
Might just as well buy a video card and run this locally; time to dust off the ol' 5970.
Id like to try these once my GPU is authed.
5b8f5562ac3873408d26852d74434040 is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
6fdafb1d737ef98bcbdceaaff16b2a9c is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
Hereticalsauce is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
QWERTYUIOP555 is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
YorikBlin is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
___vh___ is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
cyberguard is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
ddosddos is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
ffchampmt is over 3000 Gkeys and has no gpuauth.
GPUAuth set now.
IMO a 2h timeframe is too short. Probability of power outage/ network downtime lasting over 2hr is quite high.
A number between 6hr to 12hr average point would be more reasonable.
A number between 6hr to 12hr average point would be more reasonable.
2h is fine. You can have multiple colliders, even geographically distributed, working for the same id.
Also, I need to be efficient about any functional changes I make to the LBC because of time constraints
taking the individual stats as validation dataset is such an efficiency.
And therefore as announced. It may be a problem if your collider infrastructure is not reliable:
https://lbc.cryptoguru.org/stats/Unknownhostname
But that is - intentionally - your problem you either solve or not.
@arulbero
I may re-think the assignment of forfeited Gkeys. Either assign them to some "Dummy account", or into a separate value of the clients, because I agree that the information what were your Gkeys and what were foreign Gkeys should not be dilluted.
Jump to: