Bitcoin Forum
September 17, 2021, 09:28:34 PM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: The «beauty» of probability and pure randomness  (Read 227 times)
BlackHatCoiner
Hero Member
*****
Offline Offline

Activity: 546
Merit: 1266


Not your node, not your rules.


View Profile WWW
January 21, 2021, 10:22:33 AM
Merited by o_e_l_e_o (2)
 #1

I really didn't know where to create this thread, so I chose this place. Even if it doesn't require much discussion I just wanted to do it. I wrote the following php code that once you run it, it counts you the total hashes that begin with zero:

Code:
$count = 0;
$maxtries = 16;
for($i=0; $i<$maxtries; $i++){
$hash = hash('sha256', $i);

if(substr($hash, 0, 1) == "0"){
echo $i . ": " . $hash . "</br>";
$count += 1;
}
}

echo "</br>Total: " . $count;

It starts from number 0 and until 16 it hashes every number. Since hexadecimal characters are 16 in total, then on average it should find 1 hash that starts with "0". If you try the above it'll find no hashes that starts with "0". If I change $maxtries to 32, then I should get on average 2 hashes that start with "0". Again, if you try it with 32, you'll find none.

By changing it to 160 I should find 10 hashes on average and surprisingly I find exactly 10:
Code:
39: 0b918943df0962bc7a1824c0555a389347b4febdc7cf9d1254406d80ce44e3f9
49: 0e17daca5f3e175f448bacace3bc0da47d0655a74c8dd0dc497a3afbdad95f1f
51: 031b4af5197ec30a926f48cf40e11a7dbc470048a21e4003b7a3c07c5dab1baa
55: 02d20bbd7e394ad5999a4cebabac9619732c343a4cac99470c03e23ba2bdc2bc
109: 0fd42b3f73c448b34940b339f87d07adf116b05c0227aad72e8f0ee90533e699
125: 0f8ef3377b30fc47f96b48247f463a726a802f62f3faa03d56403751d2f66c67
146: 0a5b046d07f6f971b7776de682f57c5b9cdc8fa060db7ef59de82e721c8098f4
149: 05ada863a4cf9660fd8c68e2295f1d35b2264815f5b605003d6625bd9e0492cf
152: 043066daf2109523a7490d4bfad4766da5719950a2b5f96d192fc0537e84f32a
156: 0fecf9247f3ddc84db8a804fa3065c013baf6b7c2458c2ba2bf56c2e1d42ddd4

Total: 10

If I change it to 1600 I should get 100, but there are 115:
Code:
39: 0b918943df0962bc7a1824c0555a389347b4febdc7cf9d1254406d80ce44e3f9
49: 0e17daca5f3e175f448bacace3bc0da47d0655a74c8dd0dc497a3afbdad95f1f
51: 031b4af5197ec30a926f48cf40e11a7dbc470048a21e4003b7a3c07c5dab1baa
55: 02d20bbd7e394ad5999a4cebabac9619732c343a4cac99470c03e23ba2bdc2bc
109: 0fd42b3f73c448b34940b339f87d07adf116b05c0227aad72e8f0ee90533e699
125: 0f8ef3377b30fc47f96b48247f463a726a802f62f3faa03d56403751d2f66c67
146: 0a5b046d07f6f971b7776de682f57c5b9cdc8fa060db7ef59de82e721c8098f4
149: 05ada863a4cf9660fd8c68e2295f1d35b2264815f5b605003d6625bd9e0492cf
152: 043066daf2109523a7490d4bfad4766da5719950a2b5f96d192fc0537e84f32a
156: 0fecf9247f3ddc84db8a804fa3065c013baf6b7c2458c2ba2bf56c2e1d42ddd4
178: 01d54579da446ae1e75cda808cd188438834fa6249b151269db0f9123c9ddc61
211: 093434a3ee9e0a010bb2c2aae06c2614dd24894062a1caf26718a01e175569b8
216: 0f4121d0ef1df4c86854c7ebb47ae1c93de8aec8f944035eeaa6495dd71a0678
225: 0e6523810856a138a75dec70a9cf3778a5c70b83ac915f22c33f05db97cb3e68
229: 08490295488a1189099751ebeddb5992313dd2a831e07a92e66d196ddc261777
235: 0a2d643bfd24a028cd236e76575d828424ccffbfa47392bd09d8ca9dc85e2f8d
245: 011af72a910ac4acf367eef9e6b761e0980842c30d4e9809840f4141d5163ede
286: 00328ce57bbc14b33bd6695bc8eb32cdf2fb5f3a7d89ec14a42825e15d39df60
290: 09895de0407bcb0386733daa14bdb5dfa544505530c634334a05a60f161b71fc
305: 090d3859ff6840b2280f4708cf08cdaed873d967183a4d1deedc1a7964a21eee
327: 02cca3803b564ede11ccf9f303c9910b39c532061e7a8c3b773169bc3d3c140b
329: 0791963ca2667a23cf3268ad25d7bb6ca0ed287b192869703cdbcf0e87934c33
331: 0bba869d7f392cbcaca6b8935ddc7fc3a8c50846d884959333fb7da475957511
334: 058d5d43bf485bf78dda1ed4eaf8b78e3106f3c6364c625ead2cc3aeb1908237
342: 023849c38925e2af028a2eb4e1dc41afd7dc7a238195c1c2ae00438d1dae00e1
344: 02e6295d8f522840f09b5194b3f023799ad6ed3306d9296005787e792224df20
348: 06b2d82840e43ed8432b3f444de18b57dbe60637c99379c708aa8e66de83dbc1
351: 04a8708c3a481ced13845a30de522486895de0592222c29326d9139ec2b9df25
354: 09a1b036b82baba3177d83c27c1f7d0beacaac6de1c5fdcc9680c49f638c5fb9
356: 03a3d955b8799a90f1ff5a39479fde8e618f8ca3282d5b187186f2cf361abd32
367: 0788979fc9366e21cd56311511b897a222cf91711481bcd7dc837eac2172d087
374: 01299ac65733b5a3d774265fbfe8396b8611e5e3321855dbc541cd301e71fe5e
394: 04d19fde0a08b17aca69491e714bea43565384d12a63626e08477662cc03780e
399: 0f78540965a86402578f8188c826c1cb6c7ddcb608ae3a3201e532c7cacb6ce3
425: 0dfcddb0440e967f05bb68ca09a5e2188b8abc36bfb5b95b83b88be59c42c6e7
431: 0a1f1256f9bac68e806442aa76455bb761af5414855efa23c1b3fd54477c0ba1
437: 0ef962215cc055786d516355238a80dacc204ecf9b160d0a252190bf5c0cc370
439: 050a010ce24d0896056e9a36a1940738d38f469d644b3682cfcc47569739c525
445: 0e12831a7047f759733b21f028525039607350b1b1b4fe904595427e72ea0d9b
463: 06de973bb45531d52cdbd483c5e50bcddaa2095f9515e03cfad490061cc9831e
471: 064c3e311ef63912b0cc91db9681ce2d301c3e76c447febf8faa303de38cc005
500: 0604cd3138feed202ef293e062da2f4720f77a05d25ee036a7a01c9cfcdd1f0a
519: 0cce0bd361c46fcde41daebc801da75e21320763dc2b1a5a62d9b28e7c3e1d10
520: 0b35b06a22779418f775a804f36485f7bc978071d1709ad263a68f4f18117b11
549: 068814875fcdfb8faf539ef43cf5d109a22b7cfd28770e90b00be8c48bfc722f
559: 0d6f9709edaeba4bebf576d6b886b8c7083374f521f5256bf571add42fc7465c
561: 04edd1d7736883194af3ddb232c337e53d17bc93cfd2140c4f4c4e0d966798b1
570: 085b2a38876eeddc33e3fbf612912d3d52a45c37cee95cf42cd3099d0a3fd8cb
584: 085bcb597bbd610a7f0f955301d0fe3734b92a7144e87f68e8b5beec1a09b55b
610: 01ce4b291ad3ecd240be71870340051b755e74e91e05d5c5baa0d7830c1b75d4
636: 02c000a36dcd047f5738f5abfda07dc3b6d56fc44ea752c8f45b965f6fc04c1e
664: 09eac95eb995b821f45353054da3c7eec5f5171fb061de72f1890679956b12a8
671: 00bebc5be79d19e1b8b3f250dc39aebfa9a054baf5f8d61380438d92394c476a
683: 07bed92aab16ecdd9c886a79e44f0c0b02d70c746c593eaa3b8acf24e687bcd8
719: 02837c1944876b4fa860432c13f2d9b11a7fd94dae707c4143d1217dee66fc43
722: 0ebb3519a0c4044c4571b2408a52e7ed8009564205ca65a69fd43f232352f256
723: 07e46896ba89f88776fed50a1b7895129f9b9af7d3b8b33ca23af478bb818d6c
743: 0df5486b7bca884d5f00c502e216f734b2865b202397f24bca25ac9b8a95ab4a
748: 0c658eb5d61e88c86f37613342bbce6cbf278a9a86ba6514dc7e5c205f76c99f
766: 04222ea3e14cb1209b9726defe3efce5196b7afa0a959854a30401be41f4026d
771: 0fbc9039145b6449a7765dcc00d3bd8377d93ac8cccda9f0292b5976e6d67c75
774: 089ee14b926fabea6dd95890032d1a37e69c1011c710977af774ec3a7b5b39a6
780: 0e78437805639c14d6413de94c031fd1babdb561b7728d31ae06bfc5ff1766d4
791: 0b0fc3be2ee8d1d33518036b0f38402ee7bc022380a0b9653886019d38acd128
801: 096012b7ebcaf56d1d63b2784d2b2bbdeae080d72ad6bd1b9f7018e62a3c37d0
809: 0b06d2ffebd5c025cf444cb95a73e1fff046569238eafd1e80f511ea2a807de3
860: 02f99d2002c703f1669e358989f1663e1e38e96297dcb3bb70fb67b0d74fb877
871: 062f50753b9095ee2eff40f888d93e61f2ffeb661bb126d15229f03e0463bdb4
886: 000f21ac06aceb9cdd0575e82d0d85fc39bed0a7a1d71970ba1641666a44f530
962: 084917af148384c1e8396addcec2fca2a9f2c3918cad9676e12cdaad7dc7dfb2
975: 0aa598c735f77296910c9b61658e9411d38061dc817b9e35b5ea4867d83f7603
1038: 0c1c43111448b131d65b3b380041de26f2edd6264ee1c371184f54d26ab53365
1039: 00037f39cf870a1f49129f9c82d935665d352ffd25ea3296208f6f7b16fd654f
1040: 0d21ae129a64e1d19e4a94dfca3a67c777e17374e9d4ca2f74b65647a88119ea
1047: 025ca19d7b07d7f554fd7cd060b628e628d0f607afa3a6fde17c4488f35716d2
1049: 0c62cc42d6479a691f03083654ab6a7a84229ab156c948ba8d3b6c79ddd95536
1055: 02abf8fa7d9c4db035df33acba2dcd495ae9af91152ea9a135533cb747eb3afc
1063: 0fe39b99b379952df916ed88c169ec63757291bf0c3db2881a4e0e9bf84b1463
1064: 0087cf99a4636ebd9a0f66eaf98fde8bca977e2a274bc832cc903c3561735e9d
1068: 0f0b82fae280ae9fec1905f029b6ee9a9c85bb6cc5151da6dafe38a7902a4a53
1085: 0c0ad5934ba82dd287896d6406d1428b9e9669a995ce7964226aa47ede31d547
1086: 084ae23e6996e701addeeb7dcf33696f32dcb4ab78c0ca2026f8f5dbbe5a81d0
1110: 055f78940c07630352676197ab7c3ed8d5bb204d406e5c6ff101f870bc9b7dd7
1111: 0ffe1abd1a08215353c233d6e009613e95eec4253832a761af28ff37ac5a150c
1146: 0b36980af5c0346a818b88693526bc0deb1e8ed19cba03824cc6db1110c331db
1150: 0eaa69a16d7c358a329a7111a809bd2f9a7ff489596bdda17538705e9e03e05d
1154: 06ec44ccee3b23b9e067e96afb796d3b8d75ac7701185f649c61e405c282bdf8
1172: 02ede7e8caf71df40a5bb6495f5fcbc092cf7c87de6beed5d7813910d82ba3bd
1173: 0e6801798cea548d4bdb92af10e38939f59af24c4558a458707f8c970801a9c7
1181: 0252b081bda70b478f0131b310a93cb8d79086d785fb4ae392a8c5ffc3ddc5fe
1204: 0af7d7158becc6d02dc41536107090e77195cf90c556cadb37866528cc94e8a9
1224: 0d866ba9f9fd0f2cbb2134daf52356d2021a3686352d5c19d967305bf9e4bbdc
1234: 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
1287: 065f4fa6723db9087ba06d66629821913cac0ec250a6e0e8e5e54f736751a132
1289: 0e0c8d9c5fa46e66bd8293289e410bbc9e35da10a211a4d5c3e0b64a373db54f
1301: 0f2cb44170f42cc966535f392a10dcd4499426df69dc476f1bf36609f7fa8c1e
1309: 0c1a70e4512ee6f78c92820756a4026ce1f93872369624f31cf206614b2e231f
1318: 095eaa09cd36d1f1e7a963c9ad618edab13f466882c9027ab81ffc18b0eb727e
1328: 040fe555cb4f5459547ee1da624040b002a012b23af44ff9005e59005b7e62ac
1330: 0546542b90c76d50b3f8480b8b330865f8e5f2a0622a0dc9c3d6d5746cd72a13
1353: 04ad22d7630382dd5ece1410d2d8a131c44bdf54b53eb6b22a0276994b836d53
1370: 07e9bba1c63a7a01f935ee06d931c453e0864fc0fcc11ec445a8af60a36cc6c8
1391: 01d77b0b1bd2fecc8ddd43210d4d10934aa31db043675f53eb46907a031d10d2
1392: 01b23136ea7f9f8b9e72c9e125fd710301baec28662b0de2168967838c79e81a
1415: 0c86f2dfd04b5d52de85408b658cd99e053d9010b38c56da20673c9a891e9746
1418: 0f47caa1afdc7b7c8f1b627e85db55ba2193692e714b9def1df80f5b9be249b4
1438: 0594f04659a605a1a4cf43dce46b70def2ce8f4274adf1c88ae9a56059307c43
1467: 0038263cc90dfa55d621a6425e46020136a318d12b974340f518892a6ef690ff
1498: 0d9653b98d117db68a8977412dc81e8bb7ca6c550bc42d0d2a2f77fc703f923e
1511: 0d0c9bc37ae955b26c8bfecc22fcd072c4ea5ce95947a5051b5ed7399bff4f2e
1538: 0f8e631d28e2a339b435ea55da61c718da28902056ed719e576ff1c1b4cb2baf
1547: 05fb3c9a7f20d8c60ade227ba6ed41510428c5d3e3847eac78eb486b06d2fae4
1562: 0f427d4e1430f8f57221d70dca9854b6bd67c42fda811e0f27939a58a46f25ae
1567: 0651ee70db05737d7195776455175f3f4dbd4755e13e9f87d905a63817e979b8
1587: 0252fa3e9d9c8c2c1cbd742a0ac409dc817c43f5ef23d6c36137f988e64055f7

Total: 115

I know that this is completely misplaced and it's part of the function not to give exactly 100, but I find something odd with possibilities and randomness. I mean it's not random, there are some mathematical operations that the computer does and results on a hash. You just can't know it if you don't perform every possible combination until you find it.

There is no proof that between 1,000,000 and 2,000,000 there is a hash that starts with zero. It's just highly improbable. But let's define what probability means.

Quote
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, 0 indicates impossibility of the event and 1 indicates certainty. The higher the probability of an event, the more likely it is that the event will occur. A simple example is the tossing of a fair (unbiased) coin. Since the coin is fair, the two outcomes ("heads" and "tails") are both equally probable; the probability of "heads" equals the probability of "tails"; and since no other outcomes are possible, the probability of either "heads" or "tails" is 1/2 (which could also be written as 0.5 or 50%).

There is a difference with the coin, though. If you make the calculations that are required to know the final result, you can always win. For example, if you calculate the weight of the coin, the pull of gravity, the wind etc, you can predict it correctly. On the other hand, on hash functions you can't know what input gives the analogous output that is publicly known unless if you successfully brute force it. This concludes that SHA-256 hashes are not probable. But, neither random. If you picture a database that expands through infinity and has two columns, the input, that will have every different combination of text that can ever be created, and the output that has input's SHA256 hash (or any other hash function) you will realize that every result is pre-defined. There is a bunch of characters out there that is unknown and once you perform SHA256 to it, it will give you:

Code:
0000000000000000000000000000000000000000000000000000000000000000

And there are more than one. I don't have the proof, but just like before, it's highly likely.



But wait. Since all possible combinations of a text are infinite, does it make the possibilities infinite too? Yes, here's the proof. Whether I have or don't have the text that prints theses 64 zeros once it's put through SHA256, I can prove you that there is one. And not just one. Infinite texts that return it.

And that's reasonable. On the beginning of this post, I showed that 1 in 16 different hashes start with "0" on average, which also means that 1 in an infinite amount of different texts will return 64 zeros once we hash it.


There is no specific reason why I created this topic beyond that I just wanted to. I don't believe that I've made a mistake somewhere. I think that it's possible to perform SHA-256 to an input no matter its length. If not, if there's a limit of characters, then it's not that important. I just wanted to give the idea. Either way, a database that expands through infinity is by itself impossible.

I hope the title, doesn't mislead. Your thoughts.

1631914114
Hero Member
*
Offline Offline

Posts: 1631914114

View Profile Personal Message (Offline)

Ignore
1631914114
Reply with quote  #2

1631914114
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1631914114
Hero Member
*
Offline Offline

Posts: 1631914114

View Profile Personal Message (Offline)

Ignore
1631914114
Reply with quote  #2

1631914114
Report to moderator
o_e_l_e_o
Legendary
*
Offline Offline

Activity: 1414
Merit: 7139


Wear a mask, slow the spread


View Profile
January 21, 2021, 12:00:43 PM
Last edit: January 21, 2021, 07:52:30 PM by o_e_l_e_o
Merited by aliashraf (1), BlackHatCoiner (1)
 #2

Since all possible combinations of a text are infinite, does it make the possibilities infinite too? Yes, here's the proof. Whether I have or don't have the text that prints theses 64 zeros once it's put through SHA256, I can prove you that there is one. And not just one. Infinite texts that return it.
There are not an infinite number of possible inputs for SHA256.

Then append the 64-bit block that is equal to the number l expressed using a binary representation.

What this means is that any input in to SHA256 must first have the length of the input, expressed as a 64 bit number, appended to the input. Therefore, the input itself cannot be longer than 264 - 1 bits, which works out to 2 exabytes (2 million terabytes).

What this means is that for each of the 2256 possible outputs from SHA256, if the inputs were evenly distributed then there would be 218446744073709551360 possible inputs per output. So although not infinite, the chance of an output having 0 possible inputs is incomprehensibly small.

NotATether
Hero Member
*****
Offline Offline

Activity: 644
Merit: 2034


Cryptographic Crawler


View Profile WWW
January 21, 2021, 01:23:36 PM
Last edit: January 26, 2021, 11:04:59 AM by NotATether
 #3

You are describing pseudorandomness and not pure randomness because SHA256 is just XORing a bunch of numbers shifted to the right together. You know how many rounds it's going to use so you could theoretically count the number of XORs done if you know the input to guess the value of the left-most bit.

Also note that all strings, numbers and so on have to be organized into groups of 4 bytes (a double-word) in order to be fed into SHA256. Each double-word has operations applied to it as a unit. So if you change a group of 32 bits (4 bytes) in the input, you completely change all of the output bytes.

So to convert an integer to bytes you'd group the lowest 8 bits of the integer into a single byte, then the next lowest 8 bits, and so on until you have four bytes. That's one double word. If there aren't enough bytes to make a double-word then 0x00 bytes are put at the end of the double-word. I.e we pad the input with bytes to the right of it.

Let's say for example you wanted to hash 65536 which is 0x010000 in hex. This is turned into bytes as 0x00 0x01 0x00 0x00, using big-endian format, which is the way I spelled out the bytes just now. We never spell them out to SHA256 as little endian (where all of the bytes would be spelled in the reverse order).



There is a peculiarly when hashing strings that doesn't happen in numbers. Sometimes there aren't  enough bytes to form a double-word, say if the number of characters is not divisible by 4, then we put 0x80 0x00 0x00 ... at the end until we can form another a double word (the first bit we spend must always be a 1, hence the 8 in the 0x80.

A consequence of this is that there are some strings that make exactly the same hash, such as "abc\x80" and "abc". But if you're only hashing strings of length N then there isn't a known collision (meaning having the same hash) yet between two such strings.

BlackHatCoiner
Hero Member
*****
Offline Offline

Activity: 546
Merit: 1266


Not your node, not your rules.


View Profile WWW
January 21, 2021, 07:03:16 PM
 #4

What this means is that any input in to SHA256 must first have the length of the input, expressed as a 64 bit number, appended to the input. Therefore, the input itself cannot be longer than 264 - 1 bits, which works out to 2 exabytes (2 million terabytes).

What this means is that for each of the 2256 possible outputs from SHA256, if the inputs were evenly distributed then there would be 272057594037927936 possible inputs per output.
Thanks again, I didn't know that you can't hash something that's more than 2 million terabytes. But why 72057594037927936? How did you come up with that number?

A consequence of this is that there are some strings that make exactly the same hash, such as "abc\x80" and "abc".
On what function they make exactly the same hash? I tried it on SHA256 but they don't collide.

abc:
Code:
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

abc\x80:
Code:
435a2c4c08a230aa3dc9874a02324b03c6ffbedf4e6deacf7226477a28f80133

o_e_l_e_o
Legendary
*
Offline Offline

Activity: 1414
Merit: 7139


Wear a mask, slow the spread


View Profile
January 21, 2021, 07:52:15 PM
 #5

But why 72057594037927936? How did you come up with that number?
Yeah, my bad. I was a bit too quick with my calculations and have divided the exponents instead of subtracting them. The actual number is 218446744073709551360. I've fixed my reply above.

Given that the maximum input can be a message of length 264 bits (we'll forget about the "- 1" for ease of explanation), then there are 2264 possible inputs. We also know that there are 2256 possible outputs.

In the same way that if we know there are 50 outputs and 10 inputs then there would be 50/10 = 5 outputs per input, using our numbers above there are 2264 / 2256 outputs per input. This can be simplified to 2((264) - 256), which works out to 218446744073709551360.

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3542
Merit: 5622



View Profile
January 22, 2021, 10:08:28 AM
Merited by o_e_l_e_o (2)
 #6

What this means is that any input in to SHA256 must first have the length of the input, expressed as a 64 bit number, appended to the input. Therefore, the input itself cannot be longer than 264 - 1 bits, which works out to 2 exabytes (2 million terabytes).

What this means is that for each of the 2256 possible outputs from SHA256, if the inputs were evenly distributed then there would be 218446744073709551360 possible inputs per output. So although not infinite, the chance of an output having 0 possible inputs is incomprehensibly small.

It's worse than that... sha-256 has a 256-bit internal state bottleneck, and so that worst case deviation from uniform is likely massively larger than you estimate (though still extraordinarily tiny).

Basically you just consider your last block of input,  there is 512 bits of input text plus 256 bits of state from the prior block and outputs 256 bits.  Even if you model the 256-bit prior-state as totally uniform,  there is "only" 2^512 possible input values for each output value.

Still, according to this counting argument it's absurdly unlikely for there to be an unreachable output ... just not quite as much as your figures suggested.
j2002ba2
Full Member
***
Offline Offline

Activity: 142
Merit: 139


View Profile
January 22, 2021, 10:57:34 AM
 #7


Still, according to this counting argument it's absurdly unlikely for there to be an unreachable output ... just not quite as much as your figures suggested.


Since bitcoin generally uses double sha-256, there are in fact unreachable outputs.

It's expected, that half of the output values are unreachable (when using dSHA256).

Theoretically it might become a problem in the future, when difficulty is insanely high, no combination of nonce/extranonce would produce a number below target. This might not be true though, it's possible that all low values are reachable.

Long before this happens there will be a hardfork, since sha-256 wouldn't be secure anymore, or a softfork adding additional hash commitment, using something stronger than sha-256.

odolvlobo
Legendary
*
Offline Offline

Activity: 3346
Merit: 2009



View Profile
January 22, 2021, 08:33:26 PM
Last edit: January 22, 2021, 08:45:14 PM by odolvlobo
 #8

...I wrote the following php code that once you run it, it counts you the total hashes that begin with zero.
...It starts from number 0 and until 16 it hashes every number. Since hexadecimal characters are 16 in total, then on average it should find 1 hash that starts with "0".
...If I change $maxtries to 32, then I should get on average 2 hashes that start with "0". Again, if you try it with 32, you'll find none.
...By changing it to 160 I should find 10 hashes on average and surprisingly I find exactly 10
...If I change it to 1600 I should get 100, but there are 115
...

Random is non-deterministic by definition, so it is a mistake to believe that any aspect of randomness is deterministic. You can quote me on that.



Also, has it been proven that all possible 256-bit values can be produced by SHA-256? And we assume that the output is uniform, but is that actually known?

Buy stuff on Amazon with BTC or convert Amazon points to BTC here: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
NotATether
Hero Member
*****
Offline Offline

Activity: 644
Merit: 2034


Cryptographic Crawler


View Profile WWW
January 26, 2021, 10:54:06 AM
 #9

A consequence of this is that there are some strings that make exactly the same hash, such as "abc\x80" and "abc".
On what function they make exactly the same hash? I tried it on SHA256 but they don't collide.

abc:
Code:
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

abc\x80:
Code:
435a2c4c08a230aa3dc9874a02324b03c6ffbedf4e6deacf7226477a28f80133


I thought it should give the same output if you hash with abc + hexadecimal byte 0x80, not the actual "\x80" characters. The backslash and "x" is C/C++ printf notation and I am used to writing hex numbers like that. My reasoning for this was that "abc" was not aligned to 512 bits so you'd have to add 0x80 and then enough 0x00 bytes to make it aligned to 512 bits.

But I think my example was wrong since "abc" is just 3 bytes so the equivalent SHA256 hash would be "abc\x80\x00\x00\x00\x00(this is 8 bytes, we need more zeros to make it 64 bytes = 512 bits)".

You could try making an input with 63 characters and see if it's SHA256 is identical to the same string but with a 64th byte of 0x00.

Also, has it been proven that all possible 256-bit values can be produced by SHA-256? And we assume that the output is uniform, but is that actually known?

According to this, it isn't publicly known whether SHA1/256/512/etc hash functions are uniformly distributed because they were designed behind closed doors.

Pages: [1]
  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!