Bitcoin Forum
May 04, 2024, 08:23:15 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
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 57 58 59 60 »
  Print  
Author Topic: Large Bitcoin Collider (Collision Finders Pool)  (Read 193122 times)
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 07, 2017, 07:19:10 AM
 #821

Greetings,

6 months ago, in post on reddit, Ryan Castellucci referenced his article about analyzing how someone (or a group of someones)
in the course of cracking the puzzle transaction was searching 500 tn keys.

15days ago, I posted on reddit a reference to this, mentioning that the LBC has searched over 1000 tn keys. (Where the above
500 tn keys meant 500 tn addresses, namely just the compressed ones and for LBC it means 2000 tn addresses).

Today, the LBC will have searched 2000 tn keys (4000 tn addresses).

I will refrain from posting that on reddit.  Wink

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
1714810995
Hero Member
*
Offline Offline

Posts: 1714810995

View Profile Personal Message (Offline)

Ignore
1714810995
Reply with quote  #2

1714810995
Report to moderator
According to NIST and ECRYPT II, the cryptographic algorithms used in Bitcoin are expected to be strong until at least 2030. (After that, it will not be too difficult to transition to different algorithms.)
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714810995
Hero Member
*
Offline Offline

Posts: 1714810995

View Profile Personal Message (Offline)

Ignore
1714810995
Reply with quote  #2

1714810995
Report to moderator
1714810995
Hero Member
*
Offline Offline

Posts: 1714810995

View Profile Personal Message (Offline)

Ignore
1714810995
Reply with quote  #2

1714810995
Report to moderator
becoin
Legendary
*
Offline Offline

Activity: 3431
Merit: 1233



View Profile
April 07, 2017, 12:11:31 PM
 #822


Today, the LBC will have searched 2000 tn keys (4000 tn addresses).

I will refrain from posting that on reddit.  Wink

Rico

Excellent.

Can you just post how much money have you made?

icanscript
Hero Member
*****
Offline Offline

Activity: 686
Merit: 502



View Profile
April 07, 2017, 12:20:36 PM
 #823


Today, the LBC will have searched 2000 tn keys (4000 tn addresses).

I will refrain from posting that on reddit.  Wink

Rico

Excellent.

Can you just post how much money have you made?



I don't really think the project is about "making money" but rather a proof of concept continually proving.
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 07, 2017, 12:24:59 PM
 #824

Can you just post how much money have you made?


all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
arulbero
Legendary
*
Offline Offline

Activity: 1915
Merit: 2074


View Profile
April 07, 2017, 09:19:52 PM
Last edit: April 08, 2017, 05:49:37 AM by arulbero
 #825

After a discussion with Rico about probability in this project,  I made some computations to try to understand better the problem.

So: now we are generating many private keys ( from #1 to #2^160 ) to get some collisions in space of addresses. Collision: 2 different keys that "generate" the same address. We want to get a collision to unlock one of the 14M  that we are monitoring. We don't want "bad" collisions, i.e. collision between 2 keys that we generate, because we can't catch them and then we want to avoid them because they are a waste of time (we don't want to compute many times the same addresses ).

Rico tried to avoid useless collisions working on 2^160 keys instead of 2^256. In my opinion there are still bad collisions and overall we can't get all addresses starting from only 2^160 keys.

Theory:

From a private key to the relative address there are 3 steps:

private key (a simple number)  --> public key (a point of a curve, (x,y)) --> sha256 --> ripemd160  --> address

**************************************************************************************************
Let's imagine for a moment that we could generate all the points of the elliptic curve secp256k: there are about 2^256 points.
Each point can be represented in 2 ways: "04xy" (to get the uncompressed public key) or "02-3x" (to get the compressed public key), so there are 2^257 distinct representations (different inputs) for sha256.

Question 1: how many distinct 256 bit strings we could get via sha256 from these 2^257 representations?

If we look at theory** of hash function
Quote
Theorem :  In hashing n items into a hash table with k locations, the expected number of  empty locations is  k*(1−1/k)^n.

the number of strings that we cannot get is then:

                                                                            k (1-1/k) ^n

where n=2^257 (input) and k = 2^256 (output).

The result is: 2^256 * (1 - 1/2^256) ^ (2^257) =  2^256 * ((1 - 1 / 2^256)^(2^256))^(2) = 2^256 * ((1/e)^2) = 0,135 * 2^256      so we can get at this stage the 86,5% of all the 256 bit strings.


Now we pass from 256bit strings to 160 bit strings with ripemd160.

Question 2: how many distinct 160 bit strings we could get via ripemd160 from these 0,865 * 2^256 strings?


Input: 0,865 * 2^256 strings  of 256 bit  -->  Output: ?? strings of 160 bit

If we apply again the formula  k (1-1/k) ^n, with n = 0,865 * 2^256 ,   k = 2^160,

we get 0,865*2^160*((1-1/0,865*2^160)^2^256 )  =  0,865*2^160 * (1/e)^(2^95)  = 0 strings that we cannot obtain.

Substantially we can say that we can get 2^160 strings, i.e. there are 2^160 distinct addresses .
*************************************************************************************************

But what are the numbers in our case? We don't generate 2^257 representations, but only 2^161 (2^160 private keys <--> 2^160 points <-->  2^161 point representations)

Question 1: how many distinct 256 bit strings we could get via sha256 from these 2^161 representations?

If we apply again the formula  k (1-1/k) ^n, with n = 2^161 ,   k = 0,865*2^256, we obtain substantially 2^161 different strings.  


Question 2: how many distinct 160 bit strings we could get via ripemd160 from these 2^161 strings?

the formula  k (1-1/k) ^n, with n = 2^161 ,   k = 2^160, we obtain that there are:

  2^160 * ((1-1/2^160)^(2^161)) =  2^160*(1/e)^2 = 0,135 * 2^160 strings (addresses) that we cannot get in our project.

At the end, we will have a 13,5% of collisions (the first after 2^80 keys), 1 collisions each 7 strings.

So, even if we generated 2^160 private keys, we will never find out the private keys of the 13,5% (1.9M) of our 14M of addresses with bitcoin.

And if we generated only 2^159 private keys (2^160 point representations), then there will be 2^160*(1/e) = 0,37 * 2^160 addresses that we cannot get, i.e. in that case we will never find out the private keys of 5.2 M of our 14M of addresses with bitcoin.




**
https://www.google.it/url?sa=t&rct=j&q=&esrc=s&source=web&cd=7&ved=0ahUKEwivm9eGq5LTAhXDu48KHcIMCHcQFghMMAY&url=https%3A%2F%2Fmath.dartmouth.edu%2Farchive%2Fm19w03%2Fpublic_html%2FSection6-5.pdf&usg=AFQjCNEmK51LFxc1lsDXxHoiTbYKpOHZCg&sig2=rKC2czitmxgO8GRPSNbPTg
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 08, 2017, 08:00:25 AM
Last edit: April 08, 2017, 08:21:31 AM by rico666
 #826

the number of strings that we cannot get is then:

                                                                            k (1-1/k) ^n

where n=2^257 (input) and k = 2^256 (output).

The result is: 2^256 * (1 - 1/2^256) ^ (2^257) =  2^256 * ((1 - 1 / 2^256)^(2^256))^(2) = 2^256 * ((1/e)^2) = 0,135 * 2^256      so we can get at this stage the 86,5% of all the 256 bit strings.

I would have appreciated if we could have given this more time (especially me to wrap my head around it) - but sure, maybe someone else can chime in with some insight.

All these models assume a hash function to behave like a random (or pseudo-random) number generator. Normally, a good hash function - by design - tries to
Quote
map the expected inputs as evenly as possible over its output range.

see https://en.wikipedia.org/wiki/Hash_function#Uniformity

Also

Quote
Note that this criterion only requires the value to be uniformly distributed, not random in any sense. A good randomizing function is (barring computational efficiency concerns) generally a good choice as a hash function, but the converse need not be true.

I had a look at the referenced paper, but I'm still not convinced about the premises to model a hash function as a pseudo-random generator. Please don't forget, that I've been looking at the SHA256 and RIPEMD160 implementation for months! They are both very similar (RIPEMD160 being way more "light-weight") and I cannot see how these would qualify as pseudorandoms.



What's even more important, we have to be aware in the nomenclature about the probability context. Let's even assume for a moment that theorem holds true for both SHA256 and RIPEMD160. When you speak above of
Quote
so we can get at this stage the 86,5% of all the 256 bit strings.

it is not entirely clear whom you reference to with "we". Because it certainly should not be "we" in this project. It should be "we all BTC users". In short: The Bitcoin address generation process uses only 86.5% of the codomain (target space) of the SHA256. But this effectively means, these 86,5% become 100% (*), because this is the reachable codomain for everyone under all circumstances.

The other 13.5% simply do not exist for BTC, as they are unreachable. Not only for our project, but for everyone.
So I actually do not see how you could restrict the target space for our 2^161 strings to 86.5% a priori.

Also, because we generate fewer keys, we have actually less collisions in the SHA256 codomain, meaning "less waste" for the RIPEMD160 domain.

As I said, I have to give it more time and see if this has an effect for our reduced search space or not.


(*) And of course do not take my 100% verbatim as in numerically. It's 100% because it's "the reachable world" for us BTC users.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 08, 2017, 09:05:39 PM
 #827

If I was to have per-user keyrate charts (hourly), would you agree them to be public or not?

https://lbc.cryptoguru.org/stats -> click on username

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 08, 2017, 09:12:01 PM
 #828

What's going on with Unknownhostname? How did he het so many keys? Cheesy

I think Unknownhostname is Jeff Bezos.  Cheesy


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
Gyrsur
Legendary
*
Offline Offline

Activity: 2856
Merit: 1518


Bitcoin Legal Tender Countries: 2 of 206


View Profile WWW
April 08, 2017, 09:17:49 PM
 #829

What's going on with Unknownhostname? How did he het so many keys? Cheesy

I think Unknownhostname is Jeff Bezos.  Cheesy


Rico


pls try to attack SN early bitcoins, noob!

arulbero
Legendary
*
Offline Offline

Activity: 1915
Merit: 2074


View Profile
April 09, 2017, 10:06:17 AM
Last edit: April 09, 2017, 10:43:18 AM by arulbero
 #830

For anyone who's interested in numbers about collisions:

https://download.wpsoftware.net/bitcoin-birthday.pdf

http://preshing.com/20110504/hash-collision-probabilities/


This tool seems very interesting:

Generating partial address collisions

https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/

https://github.com/basil00/pairgen
SlarkBoy
Member
**
Offline Offline

Activity: 114
Merit: 11


View Profile
April 09, 2017, 11:09:15 AM
 #831

Who found this address 1L1TjHQQM75mLYVn9QoFuBvWN7rPPTaio ?
There is other 29 bounty for fun haha

https://blockchain.info/tx/9e781cdb4a4b4782594098c43cbaf7dd4619ded7f4acb27ad28af7ab4628115a
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 09, 2017, 03:29:52 PM
 #832

Who found this address 1L1TjHQQM75mLYVn9QoFuBvWN7rPPTaio ?
There is other 29 bounty for fun haha

https://blockchain.info/tx/9e781cdb4a4b4782594098c43cbaf7dd4619ded7f4acb27ad28af7ab4628115a

#52 search space entered.


0.3 in 30 x 0.01 from SlarkBoy
and the 0.052 for #52

Good Luck!


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 09, 2017, 05:55:20 PM
 #833

The pool shows now a 2h average per user as this is "smoother" than the hourly average.
Given ideal round times of 30-60 minutes, with 1h avg I saw the chart oscillating too much...

The per-user charts are available for everyone who was active in the past week - not just those in the top30.

Just enter in your browser

https://lbc.cryptoguru.org/stats/<yourid>

and you should see the chart. Contrary to this, even those in the top30 who haven't been active in the past week -> "No data" ofc.


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 10, 2017, 05:08:11 AM
 #834


No one found them? No one wants them?
If I understand correctly, the bounties were placed to be found about once a day, but we have a faster search speed since then.
You must have the newest BLF file or your client will not see them.

Also in the News: Welcome "Its_a_Meeeee" in the top30. Your gpuauth has been delivered.  Smiley


Rico

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

Activity: 62
Merit: 10


View Profile
April 10, 2017, 07:42:00 AM
Last edit: April 10, 2017, 08:30:18 AM by unknownhostname
 #835

+2 from https://blockchain.info/tx/9e781cdb4a4b4782594098c43cbaf7dd4619ded7f4acb27ad28af7ab4628115a

Yesterday at 8:42 PM         0a52d50d43c0289dde60c5776c175c54d23d2b0c

Today at 5:16 AM              828e1b5cad75725c2ef95da448242015f8be4657
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 10, 2017, 08:32:51 AM
 #836

+2 from https://blockchain.info/tx/9e781cdb4a4b4782594098c43cbaf7dd4619ded7f4acb27ad28af7ab4628115a

Yesterday at 8:42 PM         0a52d50d43c0289dde60c5776c175c54d23d2b0c

Today at 5:16 AM              828e1b5cad75725c2ef95da448242015f8be4657

You can post the privkeys directly. These bounties are just for fun and will not go on the trophies page.

Code:
0a52d50d43c0289dde60c5776c175c54d23d2b0c:c:priv:000000000000000000000000000000000000000000000000000830c199efffc2
828e1b5cad75725c2ef95da448242015f8be4657:u:priv:00000000000000000000000000000000000000000000000000086109578ffff6

So 28 to go.

@SlarkBoy: Did I understand correctly, that these two were not the 1st ones?

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

Activity: 62
Merit: 10


View Profile
April 10, 2017, 01:34:18 PM
 #837

+1 70704beeb84326fa6e6240df15b6ca01ff084e40:c:priv:000000000000000000000000000000000000000000000000000891b476cff001 + 0xfba
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 10, 2017, 01:46:31 PM
 #838

+1 70704beeb84326fa6e6240df15b6ca01ff084e40:c:priv:000000000000000000000000000000000000000000000000000891b476cff001 + 0xfba

This bounty program is titled "SlarkBoy wants to give some BTC to Unknownhostname"  Smiley

@SlarkBoy - I know you turned off your 150 Mkeys/s machine to not find your own bounties, but you're Number 2 and in case you'd find something - push it to

1LBCPotwPzBvBcTtd7ADGzCWPXXsZE19j6

This is the "LBC Pot" meant to distribute public bounties to all pool members according to their Gkeys weight.
Oh wait - Unknownhostname has 65% of these too  Tongue



Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
doc12
Legendary
*
Offline Offline

Activity: 1284
Merit: 1042


View Profile
April 10, 2017, 04:19:40 PM
 #839

Hi I have a off-topic but LBC related question:

If one addess generated from BIP32-Seed is compromised, are the remaining addresses save or is the whole BIP32-Wallet compromised then?
rico666 (OP)
Legendary
*
Offline Offline

Activity: 1120
Merit: 1037


฿ → ∞


View Profile WWW
April 10, 2017, 05:43:09 PM
 #840

Hi I have a off-topic but LBC related question:

If one addess generated from BIP32-Seed is compromised, are the remaining addresses save or is the whole BIP32-Wallet compromised then?

I am no BIP32 expert, but as far as I understand the specification, you would have to

a) find a BIP32 private key (can happen)
b) You'd have to know it is a BIP32 privkey (LBC cannot know that, but we could assume so)
and finally
c) You'd have to know the master seed to derive any children.

Obviously, c) is the KO-criterion, maybe even the only necessary criterion to break BIP32-Seeds and such a master seed is nothing within the reach of the LBC. LBC just looks at private keys and the hash160 they resolve to.

AFAICS the answer is therefore: no


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  Past BURST Activities
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 57 58 59 60 »
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!