Pages:
Author

Topic: Large Bitcoin Collider (Collision Finders Pool) - page 19. (Read 193426 times)

member
Activity: 114
Merit: 11
Who found this address 1L1TjHQQM75mLYVn9QoFuBvWN7rPPTaio ?
There is other 29 bounty for fun haha

https://blockchain.info/tx/9e781cdb4a4b4782594098c43cbaf7dd4619ded7f4acb27ad28af7ab4628115a
legendary
Activity: 2856
Merit: 1520
Bitcoin Legal Tender Countries: 2 of 206
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!
legendary
Activity: 1120
Merit: 1037
฿ → ∞
What's going on with Unknownhostname? How did he het so many keys? Cheesy

I think Unknownhostname is Jeff Bezos.  Cheesy


Rico
legendary
Activity: 1120
Merit: 1037
฿ → ∞
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
legendary
Activity: 1120
Merit: 1037
฿ → ∞
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
legendary
Activity: 1932
Merit: 2077
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
legendary
Activity: 1120
Merit: 1037
฿ → ∞
Can you just post how much money have you made?

hero member
Activity: 686
Merit: 502

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.
legendary
Activity: 3431
Merit: 1233

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?

legendary
Activity: 1120
Merit: 1037
฿ → ∞
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
legendary
Activity: 1100
Merit: 1058
A few days too late: I'm on holidays for the next 2 weeks.
But thanks anyway, will implement it after that.
legendary
Activity: 1120
Merit: 1037
฿ → ∞
And a PLUSONE!!! for automatic updating of either executable and Filter file.
Once a day or so, so we all work with the latest data, even on headless machines.

So I hope you have set up an "Eternal Run" configuration: https://lbc.cryptoguru.org/man/user#eternal-run



Rico

legendary
Activity: 1120
Merit: 1037
฿ → ∞
Search debt from #50 search space:

751927328-999999998 ~240 MBlocks   <--- we are here now ... well 752008095 ... I mean 753478383 ... ah f* it
1000752001-1073740223 ~ 73MBlocks   <-- I'm testing here (so you will see a small 1Mblock jump when done above)

[then sudden jump of 1000 MBlocks Smiley]

Rest of #51 search space:

2004489776-2053318784 ~48 MBlocks
2053937985-2147481087 ~93 MBlocks

Start of #52 search space

2147483649-infinity_and_beyond  Wink


So ~ 450 MBlocks until #52 search space. Let's see if we find something in these. So actually if you get a hit before your client shows 2147483649, it will certainly be a more interesting hit than #52.


Rico

(1 Mblock ~ 1Tkey = 1000 Gkey)
legendary
Activity: 1120
Merit: 1037
฿ → ∞
I would like to look at other keys  (unknownhostname has too much cpu power)

Quote
time ./gen-hrdcore-avx2-linux64 -I 0000000000000000000000000000000000000000000000000000000000000001 -c 10000 -L 8

what stand for options "-c"  and "-L" ?

-c is the challenge. 10000 is for testing purposes (normally you can see the challenges if you look at the process table when LBC is running)

-L is the number of loops = number of times 16,7 Mkeys consecutive blocks search to perform

if you want to check individual keys,  LBC -p is a way better option:

https://lbc.cryptoguru.org/man/user#manual-mode

as you can give them in binary form, LBC correctly "snaps" the key range into block boundary form and you can give a from-to range without having to worry about the loops or challenges. You can even mix hexadecimal and binary from-to parameters. And even key and block numbers. I had an attack of genericity when implementing that. Smiley

If you are afraid not to give away any information about privkeys, either pull the network plug, or simply give the "to" parameter with some more distance and end the LBC hard with Ctrl+C before it ends.

With the -p parameter, LBC does not even send a promise (to do work) to the server and if you end it hard before the work is done, it does not send its PoW -> as if it never happened.

edit: But not sending PoW will of course freeze your stats. So unless you are testing privkeys you do not want to disclose, send the PoW.


Rico
legendary
Activity: 1932
Merit: 2077
I would like to look at other keys  (unknownhostname has too much cpu power)

Quote
time ./gen-hrdcore-avx2-linux64 -I 0000000000000000000000000000000000000000000000000000000000000001 -c 10000 -L 8

what stand for options "-c"  and "-L" ?
legendary
Activity: 1120
Merit: 1037
฿ → ∞
Boh, +1 escaped me  Smiley

ok 1/2^(160-51) but more or less....

More or less?  Smiley

The difference is 1461501637330902918203684832716283019655932542976 keys to search.


Quote
2^160 if you want search for the entire space, 2^136 for the first "real" collision (but unknownhostname wants not a simple collision, but a rich collision) ...

I have the suspicion that more people want that...

By the way: The 6-month grace period for 16cFBcM27DGriyvz5i8SLmd8n5ai8hCTEE will end May, 10th. Then, these funds will go to the LBC pot (= for distribution among clients) and yes, I assume the pot will contain some bonus BTCs also. Smiley


Rico
member
Activity: 62
Merit: 10
If I was to have per-user keyrate charts (hourly), would you agree them to be public or not?


Rico


ofc .. u cant always see that some servers dont work ... or have problems when your keyrate goes down.
legendary
Activity: 1932
Merit: 2077
If I was to have per-user keyrate charts (hourly), would you agree them to be public or not?

Rico


For me it's ok.
legendary
Activity: 1932
Merit: 2077

1/2^(161-51)  =  1/2^(110) =  1/(2^10)^11 =  (0.001)^11 =  0.00000...0001  with 33 zeros  


Why 2^161?


Boh, +1 escaped me  Smiley

ok 1/2^(160-51) but more or less....

2^160 if you want search for the entire space, 2^136 for the first "real" collision (but unknownhostname wants not a simple collision, but a rich collision) ...
Pages:
Jump to: