Bitcoin Forum
December 07, 2019, 03:39:41 AM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Are BTC Private Keys evenly distributed in 256bit space?  (Read 321 times)
Angelo1710
Newbie
*
Offline Offline

Activity: 19
Merit: 0


View Profile
November 13, 2019, 01:52:45 PM
Last edit: November 13, 2019, 02:58:16 PM by Angelo1710
 #1

If we assume that there are ~296 private keys for EACH bitcoin address (2256-160) and we assume that  in cryptography it is considered good property of every hash function if it evenly distributes the values in its co-domain (co-domain of the SHA256 function is the domain of the RIPEMD160).

Does that means that HALF of the ~296 private keys is in first 2159 and other HALF is in 2160 - 2256 space?
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1575689981
Hero Member
*
Offline Offline

Posts: 1575689981

View Profile Personal Message (Offline)

Ignore
1575689981
Reply with quote  #2

1575689981
Report to moderator
1575689981
Hero Member
*
Offline Offline

Posts: 1575689981

View Profile Personal Message (Offline)

Ignore
1575689981
Reply with quote  #2

1575689981
Report to moderator
odolvlobo
Legendary
*
Offline Offline

Activity: 2702
Merit: 1442



View Profile
November 15, 2019, 09:06:19 AM
 #2

If we assume that there are ~296 private keys for EACH bitcoin address (2256-160) and we assume that  in cryptography it is considered good property of every hash function if it evenly distributes the values in its co-domain (co-domain of the SHA256 function is the domain of the RIPEMD160).

Does that means that HALF of the ~296 private keys is in first 2159 and other HALF is in 2160 - 2256 space?

I don't have a definitive answer, but I don't believe that it is necessary that of the 296 values that result in a particular hash, there are 295 values with bit bk = 1 and 295 values with bit bk = 0, for every k.

Buy stuff on Amazon at a discount with bitcoins or convert Amazon points to bitcoins: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
Angelo1710
Newbie
*
Offline Offline

Activity: 19
Merit: 0


View Profile
November 15, 2019, 12:44:10 PM
 #3

Well it appears that 296 keys for each address are uniformly spread by ONE key in every 160 bit block up to FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140. But of course we can't prove that.
Dabs
Legendary
*
Offline Offline

Activity: 2534
Merit: 1329


The Concierge of Crypto


View Profile
November 18, 2019, 05:08:52 PM
 #4

Private keys are randomly generated, they will tend to be evenly distributed after billions have been made. You can try it yourself and use either any wallet, or even use something like vanitygen / vanitysearch to go ahead and generate a billion 1, 3, bc1 addresses.

NeuroticFish
Legendary
*
Offline Offline

Activity: 2058
Merit: 1370


There are no mistakes. Only opportunities wasted.


View Profile
November 18, 2019, 05:32:58 PM
 #5

Does that means that HALF of the ~296 private keys is in first 2159 and other HALF is in 2160 - 2256 space?

I don't think so. An address is a very big number, and there are plenty of programs and algorithms to "pick a number".
I don't know if all of them ensure an uniform spread (especially when human-generated seed is used).

Also, let's say that theory tells that if you have the same chance to roll any number of a dice. If you'll get a dice and roll 12 times, most probably you will not get each number twice. You'll tell that you need to roll 6000 times to get close results and that's right. Although I don't agree with the term "randomly" used by @Dabs, I agree with him: we have so few addresses compared to the possible address space we cannot talk yet about getting even close to an even distribution.

mrxtraf
Member
**
Offline Offline

Activity: 159
Merit: 18


View Profile WWW
November 20, 2019, 11:08:48 PM
Merited by Quickseller (2), vapourminer (1), hugeblack (1)
 #6

Question #1. Why do you need to know?
I can say 100 percent evenly. Each private key from 0 to the end of the range has its own public address. Not even own, but most likely shared with another private key.
Question #2. If we are talking about wallets with balances or wallets used once, and about private keys for them. That is another question.
Different programs create private keys on different algorithms. Some just use a random random generator based on ECDSK, others randomly generate their own set of words, from which only then a private key is created using some algorithm. And also on the basis of seeds and sequences. And also there is a creation based on the brain string and its hash.
Plus, their own programs that can create temporary wallets almost sequentially based on the increment of the private key.

On practice. About well-known private keys from used addresses. There is even a graphic table. Most exist at the beginning and end of the range of possible private keys. But these are those that were known at the moment.

But there is another private-public key.
Full range of private keys in hex.
Code:
00000000000000000000000000000000000000000000000000000000000000
fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140
But all range public hash160 from public address only.
Code:
00000000000000000000000000000000000000
ffffffffffffffffffffffffffffffffffffffff
So in the range of private keys.
Code:
000000000000000000000 10000000000000000000000000000000000000000
000000000000000000000 1ffffffffffffffffffffffffffffffffffffffff
We will have, in 50 percent of the private keys, one public hash160 for two private keys. In some percentages, one public hash160 for three private keys. Etc.
This is the number of zeros that we do not take into account first.
Code:
000000000000000000000
And if in the full range of possible private keys? How many repetitions will there be?
In theory.
Code:
ffffffffffffffffff
Given this factor, we can say that private keys are distributed evenly !!!  Grin Grin Grin
Dabs
Legendary
*
Offline Offline

Activity: 2534
Merit: 1329


The Concierge of Crypto


View Profile
November 21, 2019, 03:25:00 PM
 #7

I have no idea how that all works or adds up, but the space is so big, you can start hashing, as an example, from zero (or 1) going up.

An arbitrary set of sequential strings hashed with SHA256 results in a more or less even distribution once you get past a few billion. There is no discernible pattern that most people can see from this.

I guess the other question to ponder, the OP's real question, is how are private keys generated by all these currently existing wallet software. As a flaw in the RNG would produce an uneven set of private keys which can easily be duplicated.

I believe that happened with some implementations of older core wallets, as well as some on android, but this has since been fixed.

Not related to this topic, but for example, Sony did not use a properly generated random number for their Playstation games, thus they got hacked / modded.

mrxtraf
Member
**
Offline Offline

Activity: 159
Merit: 18


View Profile WWW
November 21, 2019, 04:34:06 PM
 #8

By the way, if we look in this range of private keys.
Code:
000000000000000000000 10000000000000000000000000000000000000000
000000000000000000000 1ffffffffffffffffffffffffffffffffffffffff
Then we will have such a picture.
Currently used purses, which had at least one transaction of about 400 million. Of these, with a balance of about 27 million.
400000000 = 0x17D78400
26000000 = 0x18CBA80
And what do we get from this according to probability theory with a relatively uniform distribution?
Keys will be located with a difference in 0xABCC77118461CEFCFDC20D2B36BA7C3D3  keys or in deceminal 3653754093327257295509212081790707549139.
Well, the exact distribution of addresses will not work, let’s take in the weird 3 percent of the uniform spread.
1 percent 0x1B7CDFD9D7BDBAB7D6AE6881CB5109A3
3 percents 0x52769F8D87393027840B398561F31CE9 X2(range - left-right) 0xA4ED3F1B0E72604F0816730AC3E639D2
Total for the search you need to sort out 0xA4ED3F1B0E72604F0816730AC3E639D2 (in deceminal 219225245599635437730552724907442452946) privat key for one address.
And we considered it for all used addresses, and for addresses with balance there will be 10 times more search ranges.
So the knowledge of how evenly distributed private keys for existing addresses do not give practically any information.
Dabs
Legendary
*
Offline Offline

Activity: 2534
Merit: 1329


The Concierge of Crypto


View Profile
November 25, 2019, 04:52:48 PM
 #9

The seed is still random. The list of addresses from any particular seed are indeed determined, hence why they are called deterministic wallets. But similar to a hash function, you can't know the next address in the sequence without knowing the seed or the extended public key. They are effectively random to anyone else but you.

Dabs
Legendary
*
Offline Offline

Activity: 2534
Merit: 1329


The Concierge of Crypto


View Profile
November 25, 2019, 07:53:31 PM
 #10

Yeah.. and only if you all those addresses were proven to be linked together. That's just for one seed though, I'm sure if the OP or someone else is looking for current distribution of all wallets, they can simply just look at all known addresses.

Maybe look at one or two extended keys or seeds and just let it generate a billion addresses and see how it looks like. I'm almost sure it will look random and more or less evenly distributed, simply due to the vastness of the space.

Dabs
Legendary
*
Offline Offline

Activity: 2534
Merit: 1329


The Concierge of Crypto


View Profile
November 26, 2019, 02:27:06 PM
 #11

I looked at a few million. You can try generating from a seed a few billion and see for yourself. It's kinda pointless.

What am I not grasping here? I'd really like to know. I know I know some things about this, I also know I don't know plenty of other things. And, just in my opinion, some things are better left alone because you know they work well enough, delving into it further does not add much except maybe knowing more about it (which is a good thing.) .. To me, it becomes academic at that point.

After all, I'm just a user of the technology.

BrewMaster
Hero Member
*****
Offline Offline

Activity: 1386
Merit: 850


There is trouble abrewing


View Profile
November 26, 2019, 02:59:10 PM
Merited by vapourminer (1), Heisenberg_Hunter (1)
 #12

this is not a question that you can ever answer without actually computing all hashes and count the collisions to see how evenly they are distributed. because of pseudo-randomness of the result you may get more collisions on one value and less on another and so on.

since 2^256 is too big you can test it with a smaller value. for example i tested with 2^16 and 2^8 or in other words take 2 bytes and hash them to and put it inside 1 byte (truncate the hash digest). it is not the same as using the whole space but it should give you the idea. here is a couple of collisions:
0x00 is repeated 231 times
0x01 is repeated 261 times
0x02 is repeated 248 times
0x03 is repeated 267 times
0x04 is repeated 243 times
...
as the space becomes bigger (<2^256 to 2^80) these collisions distribute more evenly so the numbers should become closer but there still is no guarantee for them to be equal.

so the only answer you can come up with is that there is a chance that when you convert each private keys to address using the 160 bit hash you get an uneven distribution.

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!