baro77
Jr. Member
Offline
Activity: 45
Merit: 41


October 17, 2019, 03:26:34 PM 

Hi everybody! Is it possible to express SHA256 output bits as MATHEMATICAL function of input bits? If so, which is the minimum subset of needed mathematical operators? Over which numeric set (e.g. Real or Complex field instead of binary to exploit more freedom degrees)? Any news about it already out there on the Internet?
Thanks!







Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.




DiamondCardz
Legendary
Offline
Activity: 1134
Merit: 1098


October 18, 2019, 12:19:08 AM 

I'm not sure what you're really asking? That is what SHA256 is, a oneway function that maps any arbitrary data to a fixedsize bit string. Whether you call that 'mathematical' or not is up to debate on what you consider that term to mean, I consider it mathematical because I consider all algorithms/functions to be mathematical. To be honest, I consider pretty much anything descended from Computer Science theory mathematical.
There isn't an 'equation' that will map the input to the output. There is a long series of steps  an algorithm  but that doesn't seem to be what you're asking for.




BitcoinFX
Legendary
Offline
Activity: 2366
Merit: 1525
https://youtu.be/FYLxX6uu0Q ... Proofof Work :o


October 18, 2019, 02:22:44 AM 

Hi everybody! Is it possible to express SHA256 output bits as MATHEMATICAL function of input bits? If so, which is the minimum subset of needed mathematical operators? Over which numeric set (e.g. Real or Complex field instead of binary to exploit more freedom degrees)? Any news about it already out there on the Internet?
Thanks!
I'm also not 100% clear on what you are referring to exactly, so please provide some clarification and further examples. However, useful proofofwork and mathematical problem solving / function does already exist in several Bitcoin based alt. coin chains ... See: gapcoin.club ... "So the difficulty will simply be the length of the prime gap?
Not exactly. The average length of a prime gap with the starting prime p, is log(p), which means that the average prime gap size increases with lager primes. Then, instead of the pure length, we use the merit of the prime gap, which is the ratio of the gap's size to the average gap size.
Let p be the prime starting a prime gap, then m = gapsize/log(p) will be the merit of this prime gap.
Also a pseudo random number is calculated from p to provide finer difficulty adjustment.
Let rand(p) be a pseudo random function with 0 less than rand(p) less than 1. Then, for a prime gap starting at prime p with size s, the difficulty will be s/log(p) + 2/log(p) * rand(p), where 2/log(p) is the average distance between a gap of size s and s + 2 (the next greater gap) in the proximity of p.
When it actually comes to mining, there are two additional fields added to the Blockheader, named “shift” and “adder”. We will calculate the prime p as sha256(Blockheader) * 2^shift + adder. As an additional criterion the adder has to be smaller than 2^shift to avoid that the PoW could be reused."The gapcoin blockchain has been producing results and actually breaking world records since late 2014 ...  gapcoin.club/newprimegapofmaximumknownmeritpressrelease.php  en.wikipedia.org/wiki/Prime_gap Unfortunately the original developer passed away in 2017. Also see Primecoin and Riecoin. ... Can Bitcoin technology / blockchain be utilized to solve and/or calculate other mathematical solutions ... most likely yes ... take your pick ... ?  en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics




odolvlobo
Legendary
Online
Activity: 3108
Merit: 1763


October 20, 2019, 02:03:37 AM 

Hi everybody! Is it possible to express SHA256 output bits as MATHEMATICAL function of input bits? If so, which is the minimum subset of needed mathematical operators? Over which numeric set (e.g. Real or Complex field instead of binary to exploit more freedom degrees)? Any news about it already out there on the Internet?
The are many explanations of the SHA256 algorithm. Here is one: https://steemit.com/cryptocurrency/@f4tca7/introductiontothesha256hashfunctionKeep in mind that the input is arbitrary and unbounded. I suppose that it might be possible to describe each bit of the output as an explicit function of the inputs in some standard mathematical notation, but I doubt it would be practical or even insightful.

Buy stuff on Amazon with BTC or convert Amazon points to BTC here: Purse.ioJoin an antisignature campaign: Click ignore on the members of signature campaigns. PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt



baro77
Jr. Member
Offline
Activity: 45
Merit: 41


October 20, 2019, 09:44:41 AM 

Thank you everybody replying, and sorry to:
 have originally posted in the wrong forum section (Mining)
 haven't been clear enough
what I was trying to say was:
given SHA256 output bits: O_1, O_2, ..., O_256 and input bits: I_1, I_2, ..., I_n
is it possible to obtain:
O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
where the f* functions are math equations and not algorithms? I mean, for example, given x,y belonging to [0,1]:
XOR = x(1y)+y(1x) AND = xy OR = x+yxy NOT = 1x
but I don't know for shifts, rotations, modadditions...
I'm also thinking if recursive structure of SHA256 (deriving from input being unbounded) can in some way be substituted by Series, Infinite Product, or other math stuff like that
And maybe considering operators working on binary field is not the best choice, in the same sense complex numbers are sometimes easier to work with than real numbers even when both math function domain and codomain are real.
I'm thinking about those things because I wonder if this "mapping" of SHA256 algorithm into math objects with more workable properties could permit easier hash analysis and optimizations in its computation
Thanks everybody




DiamondCardz
Legendary
Offline
Activity: 1134
Merit: 1098


October 20, 2019, 12:17:31 PM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
I might be wrong but surely if you could get neat functions for the mapping between input and output bits it would be relatively straightforward to reverse the hashing process? I don't believe there is anyway to produce a neat set of 256 functions like you're asking, no.




aliashraf


October 20, 2019, 10:44:01 PM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
where the f* functions are math equations and not algorithms?
Sure you can! SHA256 is a deterministic function of input bits, undisputable, but: Firstly, it is not a set of 256 functions, but a series of such functions for n ranging from 1 to infinity (size of the string). Secondly, Although bitcoin block header is fixed size (80 bytes) and a fixed set of functions hypothetically exist for hashing it, those functions are not feasible to be written down or saved or implemented as circuits like actual "formula"s, because such formulas, each, will be infeasibly long. I've not made a close assessment but I think it would be interesting to prove such an infeasibility in terms of the number of operations/gates it takes to be represented.




pooya87
Legendary
Offline
Activity: 2240
Merit: 3475
Remember tonight for it's the beginning of forever


October 21, 2019, 03:35:03 AM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
i don't think it is mathematically possible to come up with such a formula because of how hash algorithms work. SHA256 like all hash algorithms don't work on individual bits, they take a block of them and work on all the bits at the same time then use the result in calculation of next block. in other words f1, f2, ... are all the same exact "formula" and O_1, O_2,... are bits of the final chunk. One iteration in a SHA2 family compression function from wikipedia: so for example to calculate O_1 you have to first calculate small_sigma0 and small_sigma1 for that block to build the 256 bit working vector then perform the permutation (big_sigma0, big_sigma1, CH, MAJ, ROR) on its words 64 times and get A (word) out and get its first bit. there is no math to simplify that.




aliashraf


October 21, 2019, 04:38:03 AM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
i don't think it is mathematically possible to come up with such a formula because of how hash algorithms work. SHA256 like all hash algorithms don't work on individual bits, they take a block of them and work on all the bits at the same time then use the result in calculation of next block. ... It is possible but just not in polynomial time and space to come up with such a formula. For example, having an input string with length 1 (one byte), you can feasibly deduct 256 functions each with a maximum of O(2 ^{8}) complexity (maximum number of operations), I suppose, but for 80 bytes block headers it is very different because you have O(2 ^{640}) as the ceiling unless you could find heuristic optimizations and/or analytic solutions which are not feasible because of the algorithm and what you have said above. So, what makes it ultimately infeasible is the length of the input to an NPlike problem: find a mathematical presentation for SHA256 hash of strings with arbitrary length.




pooya87
Legendary
Offline
Activity: 2240
Merit: 3475
Remember tonight for it's the beginning of forever


October 21, 2019, 05:10:36 AM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
i don't think it is mathematically possible to come up with such a formula because of how hash algorithms work. SHA256 like all hash algorithms don't work on individual bits, they take a block of them and work on all the bits at the same time then use the result in calculation of next block. ... It is possible but just not in polynomial time and space to come up with such a formula. For example, having an input string with length 1 (one byte), you can feasibly deduct 256 functions my point is that all the functions that you could come up with will be the same exact function. the most thing you could do is to skip a very small number of operations in the end. for example to get the first bit the only thing you can skip is the final addition after the 64th step of b to h. this that kind of addition could be done in one CPU register, it is not really a big deal to skip them.




aliashraf


October 21, 2019, 06:18:03 AM 

O_1 = f1(I_1, I_2, ..., I_n) O_2 = f2(I_1, I_2, ..., I_n) ... O_256 = f256(I_1, I_2, ..., I_n)
i don't think it is mathematically possible to come up with such a formula because of how hash algorithms work. SHA256 like all hash algorithms don't work on individual bits, they take a block of them and work on all the bits at the same time then use the result in calculation of next block. ... It is possible but just not in polynomial time and space to come up with such a formula. For example, having an input string with length 1 (one byte), you can feasibly deduct 256 functions my point is that all the functions that you could come up with will be the same exact function. the most thing you could do is to skip a very small number of operations in the end. for example to get the first bit the only thing you can skip is the final addition after the 64th step of b to h. this that kind of addition could be done in one CPU register, it is not really a big deal to skip them. Now I get your point and you are absolutely right but it reduces the complexity with a constant 256 factor which is negligible compared to exponential complexity growth with input length. Briefly speaking, this is theoretically possible to represent O_i with a mathematical expression but the complexity of such expression grows exponentially with input string length.




baro77
Jr. Member
Offline
Activity: 45
Merit: 41


October 23, 2019, 03:02:41 PM 

interesting replies, thank you very much So, you have restated the problem as: "peroutputbit" mathematical formula/equation could exist (maybe in the form of a vectorial function to calculate all the output bits at the same time as well), but it would be as long and difficult to be expressed as the number of inputs increase (aka length of hashed string)and that as... as... wouldn't be polynomial, but exponential at least... from an algorithmic point of view this complexity explosion comes from the recursive nature of SHA256 over unbound input... that's why I'm wondering if in your opinion (but I guess the answer is "no" ) any insomewaycyclic mathematical operator like Series or Infinite Products (or something else, maybe in a superset of binary field) could introduce any reduction in formulas, or if you know if this idea has ever been explored. Thanks!




fillippone


October 24, 2019, 04:37:36 PM 

If I understand correctly your question, what you are asking is if it is actually possible to break the POW Bitcoin algorithm, using a mathematical function to find the nonce to be used in the block header, instead of random guesses, to get the desidered hash value. Then I second your request, as a bitcoin enthusiast (and might be investor), but I have a very strong feeling the answer is NO.




baro77
Jr. Member
Offline
Activity: 45
Merit: 41


October 25, 2019, 05:14:59 PM 

If I understand correctly your question, what you are asking is if it is actually possible to break the POW Bitcoin algorithm, using a mathematical function to find the nonce to be used in the block header, instead of random guesses, to get the desidered hash value. Then I second your request, as a bitcoin enthusiast (and might be investor), but I have a very strong feeling the answer is NO.
Well "to break" maybe is too strong let's say I'm interested in SHA256 analysis:  to understand what makes an HASH effective against collisions  to understand if its computation can be optimized in particular circumstances.. a sort of new ASICboostlike optimization let's say I think the first step is to write SHA256 in an alternative form.. algebraical? over which field? as set of relations in graphdb? I don't' know.. I just wanted to explore if someone has already thought about it too




aliashraf


October 26, 2019, 08:46:28 PM 

interesting replies, thank you very much So, you have restated the problem as: "peroutputbit" mathematical formula/equation could exist (maybe in the form of a vectorial function to calculate all the output bits at the same time as well), but it would be as long and difficult to be expressed as the number of inputs increase (aka length of hashed string)and that as... as... wouldn't be polynomial, but exponential at least... from an algorithmic point of view this complexity explosion comes from the recursive nature of SHA256 over unbound input... that's why I'm wondering if in your opinion (but I guess the answer is "no" ) any insomewaycyclic mathematical operator like Series or Infinite Products (or something else, maybe in a superset of binary field) could introduce any reduction in formulas, or if you know if this idea has ever been explored. Thanks! Good question, but I am afraid it wouldn't be easy to give a rigid answer. My guess is obviously "NO" but proving it is another issue. The point is if there is any proof for this problem it would be a breakthrough: the security of SHA256 is not proved mathematically because it is adhoc and does not belong to the socalled Provably Secure Hash Functions. Once I got enough time, I'll check it myself but for now, I'm curious if there is any chance to study the security of adhoc hash functions by testing the feasibility of such reducibility? My guess is any hash function that is reducible to mathematical functions that their size grows polynomially (instead of exponentially) with the length, is not ultimately secure.




pooya87
Legendary
Offline
Activity: 2240
Merit: 3475
Remember tonight for it's the beginning of forever


October 27, 2019, 04:55:46 AM 

 to understand what makes an HASH effective against collisions  to understand if its computation can be optimized in particular circumstances.. a sort of new ASICboostlike optimization let's say
have you studied SHA1? i think it would be a good idea to first check what happened to SHA1 and how they were able to increase the efficiency of their collision attack so much that it could happen in a much smaller space than 2^80 (i think there was a scientific article about how they could reduce to 2^50). check these articles out and see their approach, it could give you a lot of good information.




baro77
Jr. Member
Offline
Activity: 45
Merit: 41


November 04, 2019, 06:32:32 PM 

Thanks for replies, suggestions, and @aliashraf for the "merit".. really appreciated and sorry for me being late, but I'm involved in a lot of stuff lately I was thinking that as underlined by aliashraf the general problem for sure is huge (stated it seems to still rest unsolved), but I'm in some way confident "that reduction" perhaps could be less impossible if we consider the mining problem... I mean, if for sake of simplicity we consider:  a fixed order of transactions in the block (so fixed merkle root)
 no misuse of timestamp and version fields from their original meaning
then the only remaining freedom degrees are the nonce's 32 bits.. still many but not the whole 640 bit header Ok ok, I know the block hash is the SHA256 applied TWO TIMES to the block header, nevertheless the "whole function" would still apply to just 32 bits input... And for the PoW we "only" need the beginning 0s, so we would not be interested in all the 256 bits outputs (so we would handle a smaller vector function/system) When I'll have time I'll try to write a symbolic SHA256 able to mill the numbers and to passthrough variables.. just to check what happen.... ..but it won't be soon , for sure




pooya87
Legendary
Offline
Activity: 2240
Merit: 3475
Remember tonight for it's the beginning of forever

then the only remaining freedom degrees are the nonce's 32 bits.. still many but not the whole 640 bit header
the thing about hash algorithms is that they have a property called "avalanche effect"[1] which means that if you change even a single bit inside a message, the final hash result should change completely. wikipedia has an interesting example: The quick brown fox jumps over the lazy dog d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592 The quick brown fox jumps over the lazy cog e4c4d8f3bf76b692de791a173e05321150f7a345b46484fe427f6acc7ecc81bemy suggestion is that you should start by debugging the SHA256 algorithm. find an unoptimized SHA256 code and go through it step by step and see how all the intermediate values are being calculated. then change 1 bit and see the effects once again. that can give you a pretty good idea what is going on under the hood and you can see places where you can actually "optimize" things. [1] https://en.wikipedia.org/wiki/Avalanche_effect




SapphireSpire
Member
Offline
Activity: 125
Merit: 22


November 06, 2019, 01:12:40 PM 

I'm no expert but I believe the SHA256 algorithm involves nonmathematical operations, such as summing or multiplying the lower and upper halves of intermediate values, followed by appending arbitrarily bitmasked derivatives to the upper or lower ends, and this is why it's irreversible.




