Sha256 Hashing Algorithm as a Directed Graph

The quick and easy part of bitcoin mining is checking the digital signatures of those spending their coins and then confirming that there hasn't been a double spend. Then comes the slow part. Miners guess a value for a number known as a nuance and then take the (Sha256) Hash of the verified transactions and the nuance. If the result is less than the currently specified threshold, then the miner can announce his block to the community. The vast majority of the nuances guessed lead to a hash that is greater than then threshold and so are rejected.
Miners seek a number called a nuance such that
\[Hash( transactions, nuance) < threshold \]
When the nuance is found, it represents proof that the mining community has done a lot of work. This approach is known as a proof of work algorithm.
Well, suppose someone were to invert the Hash function, they would start with say (threshold - 1) and then work out the nuance that would achieve that. So they could mine bitcoin without doing the work. Bitcoin would be unable to continue using the proof of work algorithm and would very likely collapse. For bitcoin to survive it is important that no one known has to invert the hash function.
The Hash function that bitcoin uses is called Sha256. (For details look at the wikipedia article). For the rest of this blog post, I'm going to focus on the part of the algorithm where we start with 512 bits, they are processed through 16 preliminary iterations and then a further 48 standard iterations, at the end of which we have 256 output bits. The algorithm has the following attributes:

• It is not a secret, anyone who wants can look at the code or indeed write their own code to implement it.
• It is completely deterministic and repeatable. It gives the same answer every time.
• There are no 'if' statements.

One of the operations carried out is integer addition. The inputs are put into groups of 32 bits and then the 32 bits are treated as an integer. Pairs of integers are added. If we go down a level from the integer to the bits that make it up, we can implement the integer addition using the AND operator and an XOR operator on pairs of bits.
The rest of the algorithm can be implemented using:
NOT operator, which takes one bit as an input and has one output bit.
XOR operator, which takes two bits as input and has one output bit.
AND operator, which takes two bits as input and has one output bit.
So the entire algorithm can be represented as a directed graph going from the 512 input nodes to the 256 output nodes. Every node represents one bit. The inputs bits are set and then after that every other node is assigned a value of either 0 or 1. A node is assigned a value just once.
If a NOT operator was used to assign the value, then it has one precedent.
On the other hand if an AND or XOR operator is used then it will have 2 precedents.
However nodes can have any number of dependents. The graph is strictly directed. There are no circular loops.

So now we might ask the question: how might someone invert this algorithm. Suppose the output was fixed or indeed constrained, how could we find appropriate inputs?
Well, lets start with the NOT operator.

Input A	NOT A
1	0
0	1

This is very straight forward to invert. Indeed if you apply the NOT operator to the output, then you'll recover the input.

Now lets move on to the XOR operator. It is also known as the 'exclusive or'. A XOR B is A or B but not both.

Input A	Input B	A XOR B
1	1	0
1	0	1
0	1	1
0	0	0

Suppose: A XOR B = 0
that means that A and B are the same. They could both be 1 or both be 0. We just know that they are not different. So if we are traversing our graph from the outputs to the intputs, (i.e. from right to left in the image above) then A XOR B = 0 imposes the simple relationship between A and B that A=B.
On the other hand: A XOR B = 1
tells us that A and B are different. So if we go from right to left across our graph then that condition needs to be maintained.
So the XOR output will tell us if the inputs are the same or different.

The final operator we need to deal with is the AND operator.

Input A	Input B	A AND B
1	1	1
1	0	0
0	1	0
0	0	0

When A AND B = 1,
that implies that both A and B are 1 and so if we have that condition, then we can take a step back through the graph and set the two inputs to 1.
A more difficult case to deal with is: A AND B = 0
In that case either A or B could be 1, but not at the same time.
So that relationship between A and B is (a little bit) complicated.
The Sha256 algorithm consists of 64 iterations ( 16 preliminary, followed by 48 standard). However on each iteration the bits pass through numerous NOT, XOR and AND operators. In my implemenetation in Java (which is available in github) I had:
NOT operator called 117,248 times.
XOR operator called 58,880 times.
AND operator called 106,240 times.
There are a number of ways those numbers could be reduced. For example we could use an OR operator. But if someone was trying to come up with an algorithm to invert the Sha256, then introducing new operators may make it more complicated. Indeed we could replace the XOR with 5 calls to an AND so then we just have lots of AND's and NOT's to invert.
To successfully invert the Sha256, the run time should not grow exponentially with the number of operators N. Something linear in N would be great. Something quadratic in N may be doable.

One method that might be tried would be a probabilistic approach, assigning each node a value between 0 and 1 (inclusive).
For example if we had: A AND B = 0
then we might set A =1/3 and B=1/3.
Reflecting the fact that they are both more likely to be zero than 1.
We could attempt to traverse the graph from right to left and back again a number of times until we had a stable solution. Perhaps a simulated anealing method could be tried. But the problem is that the values in the graph are not stable. One flipped input bit has a huge cascade effect through the graph. It would be very difficult to get a probabalistic method to work because of that instability.

A very different way of trying to reverse it would be to bring the constraints on the nodes through the graph from the outputs back to the inputs. For example if an output needs to be 0 and it is assigned using an AND operator then we know that the two inputs cannot both be 1. We could then pass that constraint back to their precedents.
However in this case if we are not clever then the constraints would grow exponentially as we go back through the graph. If a node has some contraints, then they are passed on to its two precedents, in many cases each of which will have 2 precedents, which in turn may have 2 precedents. Typically to pass from the outputs to the inputs, bits need to pass through 200 AND operators. \(2^{200}\) is a very big number. Someone would need to be very smart in how they compress the constraints to prevent the exponential explosion.

If we observe the Sha256 calculator as it goes from the input to the outputs we find we just need 512 currently live nodes (bits). After a while the inputs are no longer needed. Later, after the intermediate nodes are used, they too are no longer needed. 512 is a comparatively small number. Similarly, someone going back through the graph (from the outputs to the inputs) just needs to keep track of 512 bits at any given point in time. That's not a lot of memory. How difficult could it be to invert the Sha256?
Well, so far no-one has been able to work out how to do it...

False positives and false negatives

When testing for the presence of a disease, the results obtained are often not 100% reliable. In this article we explain false positives and false negatives in test results. The graphics are dynamic, if you change the input numbers, then they'll update.
Let's start with the prevalence of disease, this is the proportion of positive cases in the population.
Disease prevalence input: %


Light red shows the proportion of the population that have the disease, i.e. are positive.
Light blue shows the proportion of the population that don't have the disease, i.e. are negative.


The false negative rate is the proportion of the positive cases that are incorrectly deemed to be negative.
False negative input: %


Dull red shows the true positives: the proportion of the population that are positive and get positive test results.
Orange shows the false negatives: the population that are positive but get negative test results.


The false positive rate is the proportion of the negative cases that are incorrectly deemed to be positive.
False positive input: %


Yellow shows the false positives: the population that are negative but get positive test results.
Dull blue shows the true negatives: the proportion of the population that are negative and get negative test results.


One challenge when considering an individual positive test result is that it is not clear whether it is a true positive or a false positive. We can look at the likelihood of each:

Dull red shows the true positives: the proportion of the population that are positive and get positive test results.
Yellow shows the false positives: the population that are negative but get positive test results.

Using the values that were input above for prevalence, false positives and false negative,
we find that of the positives:

True positives:
False positives:

When the prevalence is low, it is common to have a situation where there are more false positives than true positives. You can try this out for yourself by reducing the prevalence number above.

The Mathematics of a Ponzi scheme

A Ponzi Scheme is a form of investment where profits are paid to early investors with funds from later investors. It often involves fraud and as a result it is of course illegal.
This article will explore the mathematics of a Ponzi Scheme which has been transparent about its intentions. Suppose someone were to set up a fund that aims to pay investors a return of \(\rho\) (rho).
I.e. for each unit of currency invested, it will aim to return \(1+\rho\).
The fund pays out on a first in, first out basis. Early investor money is returned when (or if) later money arrives.
Suppose, at a point in time, the cumulative money invested is N.
The money that's been paid out is P and the fund has remaining money R.
We known that
(Investment in) = (Payouts made) + (Remaining money)
\[N = P + R\] We can classify the investment so far into two categories. There is the money that has already been settled S, i.e. the early investors that have already received their funds returned with a positive return \(\rho\) .
And there is the balance outstanding B, that remains unsettled as yet.
So we can write:
(Investment in) = (Settled amount) + (Balance outstanding) \[N = S + B\]
The early investors who have received their settlement all got a return of \(\rho\).
So we know that the payout: \[P=S(1+\rho)\] The fund administrator has guaranteed that the maximum loss that could be imposed on an investor is \(\lambda\) (lambda).
So for each unit of currency invested, the worst case scenario for the investor is that \((1-\lambda )\) is returned.
Hence we require the remaining funds (R) to be able to cover a payment of the balance (B) with an imposed loss. \[R= B( 1 - \lambda )\] We now have 4 equations and 4 unknowns (P,R,S,B) along with three knowns (N, \(\rho\), \(\lambda\) ).
If we do the algebra, we can find our unknows:

Settled amount:	\(S = N \frac{\lambda}{\lambda + \rho} \)
Balance outstanding:	\(B=N-S\)
Payouts made:	\(P=S (1+ \rho) \)
Remaining money:	\(R=N-P \)

We can try that out with some numbers:

Inputs
Total invested funds (N)		units of currency
Investment return (\(\rho\))		%
Acceptable loss (\(\lambda\))		%
Outputs
Settled amount (S)	-
Balance outstanding (B)	-
Payouts made (P)	-
Remaining money (R)	-

With such a scheme, any investor would be allowed to demand an immediate repayment of funds at any time, though in that case a loss of \(\lambda\) would be imposed. In other words, for each unit of currency invested, \(1-\lambda\) would be returned.

One problem for early investors is that they don't know how long they will have to wait until they'll be repaid their investment with the positive return (\(\rho\)). But it is not just a question of when they'll be paid, it is uncertain if they'll be paid. When later investors don't arrive, the early investors just wait and wait, until they eventually give up and request a return of funds, in that case they'll just have to accept a loss.

It is also worth noting that this model above ignores any administrative fees that may be imposed on funds on the way in and or the way out.

Plotting dates

Suppose you're plotting some attribute against time and so, on the horizontal axis you have years or dates. You might produce a graph such as the following which is of a currency exchange rate:

However one problem is that a year such as 2021 is an interval of time, indeed it is a full year, but on the graph it is presented as a point in time. When an interval of time is presented as a point in time, it reduces the clarity of the graph.
We could improve matters by displaying years as intervals. For example look at the following graph showing 5 years of data:

Sometimes we show graphs of data and the total interval of time is shorter. The graph below shows 12 months worth of data:

Again we have a familiar problem. A month is an interval in time, but on the graph above it is presented as a point in time.
Similarly we can be a bit more diciplined about showing an interval of time as an interval, rather than a point. For example we could have the following graph:

The aim is to be both precise and to be clear.
We often have a similar issue when we have just a few days of data. In that case we need to remember that a date represents a day which is 24 hours long, it is not a point in time!
There are a few caveats:
If we're showing many years of data, then relatively speaking, one year is short, so it is approximately a point. Similarly if we have hundreds of days of data, then one day is almost just a point.
There are also cases when the data is aggregated over a period. We might show monthly rain-fall in that case it may make more sense to display the month as a point, since it represents one data point and not a segment of the graph.
On the other hand if we are showing data within one day, then a time such as 10am is indeed just a point, it is not an interval. 10am does not last for one hour, it is just a point in time. In that respect it is unlike a date, which represents a full day. A date is not a point in time, it is an interval of 24 hours.
But overall, the moral of the story is: if you're using a time interval (year, month, day) as a label on a graph, then it should be diplayed as a time interval and not a point in time.

Intuitions about exponential growth

Suppose you fold over a sheet of paper, you'll then have something twice as thick as the original. Fold it again and you'll have something 4 sheets thick. With each fold the thickness doubles. This is an exponential growth and unlike linear growth, it accelerates.
Well, what if we start with paper 0.001 meters thick, how high would it be if it were folded 100 times? It turns out the answer is a thickness which is a bit more than the diameter of the universe. When written in meters, the number has 28 digits (before the decimal point).

Initially that may seem rather counter intuitive. However with a little bit of training, it can become intuitive. We actually do have lots of experience in dealing with this kind of dramatic exponential growth. Think about how we represent regular integers. Adding a zero will increase the number by a factor of 10. That's an example of exponential growth. The value of the number increases exponentially with the number of digits. We all know that a number with 4 digits, say 1,000 is much much smaller than a number with 8 digits, say 10,000,000. In this case when we have doubled the number of digits and the value increased by a factor of 10,000.
So, the moral of the story is that our experience with representing numbers using the standard decimal digits, gives us a good understanding of exponential growth.

Coming back to our folding example, we note that 3 foldings, causes 3 doublings, which increases the thickness by a factor of 8, which is pretty close to 10. So as a very rough rule of thumb, we'll almost be adding a new digit to the thickness after every three foldings.
If you want to be a bit more precise, then note that 2 to the power of 10 is 1,024 which is close to 1,000. So ten doublings (2 to the power of ten), causes an increase of just over 1,000, which means we add 3 digits. When we have 100 doublings, that is 10 times 10 doublings: \[2^{100} = (2^{10})^{10} = (1,024)^{10} \approx (10^3)^{10} = 10^{30} \] We started with something \(0.001 m\) thick and ended with something approximately \(10^{27} m\) thick.

Is exponential growth always very fast? Actually no. It depends on how long it takes to double. Suppose you are paid an annually compounding interest rate of 0.1% on your deposits in a bank. That is an form of exponential growth. But it will take 693 years for your money to double. That's the bad news. But the good news is that if you start with one euro it will grow to over a billion after it has doubled 30 times. \[ 2^{30} = (2^{10})^3 = (1,024)^3 \approx (10^3)^3 = 10^9\] But that will take more than 20,000 years.

Removing Systematic Bias in Opinion Polls

For polsters, a challenge that can be difficult to overcome is a systematic bias. There are voters who don't like to admit that they will vote for a particular candidate. Also supporters of a given candidate may be difficult for the polsters to find, but they will come out and vote. If we look at the US presidentail poles in Florida in the weeks before the 2020 US Presidential election, we can see that the vast majority had Biden ahead. According to the pole aggregation by Five Thirty Eight, Biden was leading by 2.5% in the poles. However, in the end, Trump won convincingly. The poles were wrong by about 6%, which is a huge error. Many of the poles were better at predicting the other poles than they were at predicting the actual election result.

One approach to deal with the systematic error would be to ask the respondents how they voted in a previous election. In the run-up to the Presidential 2020 election, the most relevant past election would be the 2016 Presidentail election. We know the result of that past election election, if the polster were to use the results from his respondents to estimate that past election, he could then compare that with the actual result and he could see if he has big error. If a methodology can't predict the past, then it will struggle with predicting the future.

We can make an adjustment to the weighting of each respondent so that we (more or less) recover the previous election result. We can then apply that same adjusted weighting to the respondents' answers about who they will vote for in the next election. This adjustment will work well if for example there are many people who are reluctant to admit that vote for Trump, but when they have anonimity in the real vote, they do so.

A polster may have his own methodology to obtain his results from his data, but the approach outlined here may be useful when working out the confidence interval. Rather than using one model, with its assumptions, to work out the confidence interval, it may be wise to consider more than one set of modeling assumptions and then report a confidence interval that is wide enough to include the results from all the different models.

Now, to delve into some maths. I'm going to use the same notation as I used in my earlier post. After we've carried out a pole. We convert the answers to probabilities. We'll use the notation that P(r,c) is the probability that respondent r voted for candidate c in the given election.

So \( \sum_c P(r,c) \) is the probability that the respondent (r) will vote at all.

When we ask voters about how they voted in the past, most will give a definitive response, either that they voted for a particular candidate or that that didn't vote at all. However in some cases repondents will say (in many cases with honesty) that they can't remember how they voted or indeed if they voted. In the model we'll work with here, we'll use the same probabilities as before (P(r,c)) even though in many cases there will be certainty, in that case we'll have 0's and 1's. But we can stick with the general case, when there may be come uncertainty. Using our data, we'll have a raw election result prediction. The proportion of votes for candidate c will be: \[ V(c) = \frac{ \sum_{r} P(r,c)}{ N } \] and the expected total number of votes that will be cast by our respondents is calculated: \[N = \sum_{r} \sum_{c} P(r,c) \] For a past election, when we have asked people about how they voted, we already know the results. We'll label the actual portion of votes allocated to candidate c: \(A(c) \)
For a given candidate say \( \kappa \) we may find a significant discrepancy between the actual result \(A(c) \) and the raw result, from our data \(V(c) \).
We can introduce an adjustment and use the parameter \(\alpha\) to obtain the adjusted probabilities \(P'(r,c,\alpha)\) and adjusted vote allocation estimates \(V'(c,\alpha)\).
When we have no adjustment \(\alpha=0\) and in that case: \[P'(r,c,0)= P(r,c)\] and \[V'(c,0)=V(c)\] The vote allocation to candidate \(\kappa\) will be zero when \(\alpha=-1\) so \(V'(c,-1)=0\)
and we'll have a full vote allocation to candidate \(\kappa\) when \(\alpha=1\) so \(V'(c,1)=1\)
We can achieve this with adjustments that are linear in \(\alpha\) both in the case when we want to increase the estimate for candidate \(\kappa\) ( \(\alpha\) is positive) and in the case when we want to decrease the allocation for candidate ( \( \alpha \) is negative ).
We'll deal with those two cases separately.
1: When we want to increase the estimate for candidate \( \kappa \).
In this case \[ P'(r,\kappa, \alpha) = P(r, \kappa) + \alpha Q(r,\kappa) \] where \[ Q(r,\kappa) = \left( \sum_c P(r,c) \right) - P(r, \kappa)\] and for \( c \ne \kappa\) \[ P'(r, c, \alpha) = P(r, c) (1 - \alpha ) \] with \[0 \leq \alpha \leq 1 \]

2: When we want to decrease the estimate for candidate \( \kappa \).
In this case we set: \[ P'(r,\kappa, \alpha) = P(r, \kappa) (1 + \alpha) \] with \[-1 \leq \alpha \leq 0 \] and for \( c \ne \kappa \) when \( Q(r, \kappa) > 0 \): \[ P'(r,c, , \alpha) = P(r, c) (1 - \alpha) \frac{P(r, \kappa) }{Q(r, \kappa)} \] and when \( Q(r, \kappa) = 0 \) we have a similar formual for \( P'(r, c, \alpha) \) using \( V(c) \).

We have chosen to adjust the probabilities in such a way that the expected number of votes (N) does not change, i.e. N' = N

We can choose the adjustment \( \alpha \) such that our adjusted vote estimate for candidate \( \kappa \) is equal to the actual (historical) election result.
In that case: \( V'(\kappa,\alpha) = A(\kappa) \) That can be achieved by choosing \[ \alpha = \frac{A(\kappa) - V(\kappa)}{V(\kappa)} \hspace{5mm} when \hspace{2mm} V(\kappa) > A(\kappa) \] and \[ \alpha = \frac{A(\kappa) - V(\kappa)}{A(\kappa)} \hspace{5mm} when \hspace{2mm} V(\kappa) < A(\kappa) \]

This approach could be used as follows, when we have the responses from an opion poll which includes both questions about a historical poll and a future poll:
For each candidate in the historical pole, choose the adjustment \( \alpha \) such that our data will match the historical result. Then apply that same adjustment to the data for the future poll and record the result. Then choose a confidence interval to be wide enough to include all the adjusted results.

Dealing with people's uncertainty in opinion poles

When asked about their voting preferences, some people will answer with honesty that they definitely do intend to vote and that they have absolutely made up their mind who to vote for. Other people will answer that they will probably vote and that they will most likely vote for a given candidate, but could possibly be persuaded to change to another between now and election day. For the polster, it may seem tempting to treat those who say they will most likely vote for a given candidate the same as those who say they will definitely vote for that candidate. However by ignoring that stated uncertainty, some useful information is being thrown away.

Suppose a polster were to ask a member of the public "will you vote in the next election?" The repondent could be given a list of possible answers to chose from: definitely yes, probably yes, probably, may be, definitely not. Those answers in natural language can be converted to apropriate probabilities. When we combine all the answers we can find the expected number of respondents who will vote.

We can also ask the respondents the likelyhood that they would vote for each of the candidates. It would be wise to offer answers in English rather than as probabilities, since some people won't be familiar with probabilities. From the answers, we can then obtain estimates for the probabilities that they will vote for each candidate, conditional on turning up and voting on election day. We can combine (multiply) the probability of voting (at all) with the probability of voting for a given candidate (conditional on voting) to get the overall probability that respondent (r) will vote for a candidate (c), we'll denote this probability P(r,c).

The expected portion of votes for candidate c will be: \[ V(c) = \frac{ \sum_{r=1}^{n} P(r,c)} { N } \] where n is the number of respondents
and the expected total number of votes that will be cast by our respondents is calculated: \[N = \sum_{r} \sum_{c} P(r,c) \]
For example, suppose we examine the answers from a respondent and we deem there to be a 20% chance that she will not vote, a 60% chance that she'll vote for candidate 1 and a 20% chance that she'll vote for candidate 2. Rather than treat her as a full supporter of candidate 1, we can use those probabilities as her contribution to each outcome.