Question about Wt in the SHA-256 algorithm

[w0lverine]

Hi everyone I have recently gotten into trying to understand the math behind Bitcoin and cryptography.
Right now I am concentrating on the SHA-256 process mostly using http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html & https://en.wikipedia.org/wiki/SHA-2#Pseudocode & https://csrc.nist.gov/csrc/media/publications/fips/180/4/final/documents/fips180-4-draft-aug2014.pdf as a starting point

I have trouble understanding the following:
Where does the Wt value comes from, how to calculate it and how it relates to the previous block. I cannot understand the origin of this value at all.


Thank you

Edit:

Basically I am trying to understand this:

W_t =

M_t ⁽ⁱ⁾ for ≤ t ≤ 15

ROTL¹ (W_t−3 ⊕W_t−8 ⊕W_t−14 ⊕W_t−16 ) for 16 ≤ t ≤ 79

[1714181481]

1714181481

[1714181481]

1714181481

[1714181481]

1714181481

[DannyHamilton]

You left out a line of pseudo-code:

It should be:

For i = 1 to N
W_t = {
    M_tⁱ  (when 0 ≤ t ≤ 15)
    ROTL¹ (Wt−3 ⊕ Wt−8 ⊕ Wt−14 ⊕ Wt−16) (when 16 ≤ t ≤ 79)
}


N is the number of blocks in the padded message, so the first line says to loop through all the blocks in the message (this explains where the ⁱ in the M_tⁱ comes from).

W_t is the t^th word of the message schedule, so when processing word #1, that would be W₁, when processing word #2, it would be W₂, and so on.

For each word of the message schedule, you perform one of two processes...

If you are processing any of the first 16 words in a message block (word #0 through word #15), then you simply set W_t to the value of that word:
M_tⁱ is just the t^th word of the i^th message block

If you are processing any of the remaining words in a message block (word #16 through word #79) then you set W_t to the result of the following function:
ROTL¹ (W_t−3 ⊕ W_t−8 ⊕ W_t−14 ⊕ W_t−16)

ROTL¹ means to perform a one bit circular left shift.

The thing that is being shifted is the result of:
W_t−3 ⊕ W_t−8 ⊕ W_t−14 ⊕ W_t−16

Remember that you are processing the t^th word and that this only happens when you are processing words 16 through 79, so for example:
If t is 17 then you perform:
W₁₇₋₃ ⊕ W₁₇₋₈ ⊕ W₁₇₋₁₄ ⊕ W₁₇₋₁₆
complete those subtractions and you find that you are performing:
W₁₄ ⊕ W₉ ⊕ W₃ ⊕ W₁
Since  is the symbol for the EXCLUSIVE OR (XOR) operation, you need to perform an XOR on those 4 words of the message schedule.

This set of instructions is performed for all 80 words in the message block (word #0 through word #79)

[Anti-Cen]

You left out a line of pseudo-code:

It should be:

For i = 1 to N
W_t = {
    M_tⁱ  (when 0 ≤ t ≤ 15)
    ROTL¹ (Wt−3 ⊕ Wt−8 ⊕ Wt−14 ⊕ Wt−16) (when 16 ≤ t ≤ 79)
}

I can see you know your stuff here but with all that maths going on you would expect it to be slow but it's not
really and the same is also true with GZip so these functions must be built at assembly level and not from compiled
C++ or C# using *ptr because they run almost as fast as we can iterate a byte array in Dot.NET without performing any "if" statements
or maths.

Whats your thought on this ?

Would send you a merit but i think the merit routine here is broken because I don't have any left to spend it says

[DannyHamilton]

these functions must be built at assembly level and not from compiled C++

Whats your thought on this ?

Compiled C++ results in machine code binaries.  Most C++ compilers have been optimized, so if the code is well written then it should run just about as fast as it would if it was written in assembler.

That being said, SHA256 is common enough that it is now implemented directly on the hardware.  That's what an ASIC is.  It's hardware that is custom designed for a single purpose.  The SHA256 maths can all be implemented with combinations of circuits.  As such, the entire calculation can be completed in the amount of time that it takes for the electricity to flow through the circuit.

[Anti-Cen]

Compiled C++ results in machine code binaries.  Most C++ compilers have been optimized, so if the code is well written then it should run just about as fast as it would if it was written in assembler.

Well C# results in almost the same assembly code as using C++ in windows I am told and I even tried speeding things
up using un-safe pointer code but that didn't achieve much of a result so maybe hidden within the COM windows is still using
after they told everyone to move over to Dot.Net they kick out to some custom hand crafted machine code.

I even played with un-checked (Maloc in C++ i think you call it) but that didn't result in any gains at all so maybe I will
crank up VC just out of interest and give that a go not that I can remember much C++ and most of that came from Borlands C++

I think the other part of your answer is spot on the money 

[J-N]

Compiled C++ results in machine code binaries.  Most C++ compilers have been optimized, so if the code is well written then it should run just about as fast as it would if it was written in assembler.

Well C# results in almost the same assembly code as using C++ in windows I am told and I even tried speeding things
up using un-safe pointer code but that didn't achieve much of a result so maybe hidden within the COM windows is still using
after they told everyone to move over to Dot.Net they kick out to some custom hand crafted machine code.

You can use inline assembly code in C++ program, for example:

Code:

#include <stdio.h>

int main() {
    /* moves the byte from ch to the memory pointed by ebx */
    __asm__("movb %ch, (%ebx)");

    return 0 ;
}

So SHA256 can be implemented directly in ASM code and the computing will be fast as possible on the CPU.

[Foxpup]

Most C++ compilers have been optimized, so if the code is well written then it should run just about as fast as it would if it was written in assembler.

Even faster, actually, since modern optimising compilers are smarter than nearly all human programmers. Unless you're John Carmack, you should expect hand-optimised code to run even slower than machine-optimised code (not to mention be much harder to debug).

[w0lverine]

You left out a line of pseudo-code:

It should be:

For i = 1 to N
W_t = {
    M_tⁱ  (when 0 ≤ t ≤ 15)
    ROTL¹ (Wt−3 ⊕ Wt−8 ⊕ Wt−14 ⊕ Wt−16) (when 16 ≤ t ≤ 79)
}


N is the number of blocks in the padded message, so the first line says to loop through all the blocks in the message (this explains where the ⁱ in the M_tⁱ comes from).

W_t is the t^th word of the message schedule, so when processing word #1, that would be W₁, when processing word #2, it would be W₂, and so on.

For each word of the message schedule, you perform one of two processes...

If you are processing any of the first 16 words in a message block (word #0 through word #15), then you simply set W_t to the value of that word:
M_tⁱ is just the t^th word of the i^th message block

If you are processing any of the remaining words in a message block (word #16 through word #79) then you set W_t to the result of the following function:
ROTL¹ (W_t−3 ⊕ W_t−8 ⊕ W_t−14 ⊕ W_t−16)

ROTL¹ means to perform a one bit circular left shift.

The thing that is being shifted is the result of:
W_t−3 ⊕ W_t−8 ⊕ W_t−14 ⊕ W_t−16

Remember that you are processing the t^th word and that this only happens when you are processing words 16 through 79, so for example:
If t is 17 then you perform:
W₁₇₋₃ ⊕ W₁₇₋₈ ⊕ W₁₇₋₁₄ ⊕ W₁₇₋₁₆
complete those subtractions and you find that you are performing:
W₁₄ ⊕ W₉ ⊕ W₃ ⊕ W₁
Since  is the symbol for the EXCLUSIVE OR (XOR) operation, you need to perform an XOR on those 4 words of the message schedule.

This set of instructions is performed for all 80 words in the message block (word #0 through word #79)

Thank you very much for your answer Danny, I am still digesting it.
I am not too sure where N comes from in BTC, is it from a previous block (blockchain block)?
What is a block in this equation? is it a 32bit chunk of the padded message?

[DannyHamilton]

I am not too sure where N comes from in BTC, is it from a previous block (blockchain block)?
What is a block in this equation? is it a 32bit chunk of the padded message?

SHA256 is an algorithm that can be applied to any arbitrary binary data.  It isn't exclusive to Bitcoin.

The Wikipedia and NIST links that you provided are generic descriptions about the SHA256 algorithm. There is nothing about Bitcoin at all in either of those links.  Therefore, references to "blocks" in either of those are references to some defined block of data, and not to a "Bitcoin Block".

Specifically, if you actually started reading the NIST document from the top, (instead of jumping straight to the calculation on page 27), then you would have found that:

M is the message to be hashed.  In other words, it is the data that is being hashed.

You would also have found that some pre-processing is required to pad the message separate it into blocks (see page 21).

5. PREPROCESSING
Preprocessing consists of three steps: padding the message, M (Sec.  5.1), parsing the message into message blocks (Sec. 5.2), and setting the initial hash value, H⁽⁰⁾ (Sec. 5.3).

Then you would have discovered that the message M needs to be padded to a multiple of 512 bits before it can be hashed:

5.1 Padding the message
The  purpose  of  this  padding  is  to  ensure  that  the  padded  message  is  a  multiple  of  512  or  1024  
bits, depending on the algorithm.

5.1.1 SHA-1, SHA-224 and SHA-256
Suppose that the length of the message, M, is l bits. Append the bit “1” to the end of the message, followed by k zero bits, where k is the smallest, non-negative solution to the equation (l + 1 + k)mod512 = 448. Then append the 64-bit block that is equal to the number l expressed using a binary representation.

And finally, you would find that the message M needs to be parsed into blocks of data that are each exactly 512 bits long:

5.2 Parsing the message
The message and its padding must be parsed into N m-bit blocks.

5.2.1 SHA-1, SHA-224 and SHA-256
For SHA-1, SHA-224 and SHA-256, the message and its padding are parsed into N 512-bit blocks, M⁽¹⁾, M⁽²⁾,...,M^(N). Since the 512 bits of the input block may be expressed as sixteen 32-bit words, the first 32 bits of message block i are denoted M₀⁽ⁱ⁾, the next 32 bits are M₁⁽ⁱ⁾, and so on up to M₁₅⁽ⁱ⁾.  

So:

Data that is less than 449 bits will be padded out to 512 bits and will be parsed into a single 512 bit block.  In that case N is 1 (there is only 1 block of data to hash).

Data that is more than 448 bits and less than 961 bits will be padded out to 1024 bits and will be parsed into two 512 bit blocks. In that case N is 2 (there are 2 blocks of data to hash).

Data that is more than 960 bits and less than 1473 bits will be padded out to 1536 bits and will be parsed into three 512 bit blocks. In that case N is 3 (there are 3 blocks of data to hash).

This process can be continued for any arbitrary length of data.

Note that the Bitcoin Block header is 80 bytes (640 bits), and therefore must be padded to 1024 bits and parsed into two 512 bit blocks.