FIELD

The present invention relates to the operation of a message scheduler when performing cryptographic hashing in respect of plural different input messages to be hashed. The present invention relates particularly, although not exclusively, to cryptographic hashing when mining for cryptocurrency, such as Bitcoin.

BACKGROUND

Bitcoin mining comprises applying three instances of a SHA256 cryptographic hashing function (referred to herein respectively as “SHA256o,” “SHA256-i” and “SHA2562”) to an input message, which is derived from a Bitcoin Block Header. SHA256o uses a standard initialisation vector IV and is applied to a first part of the Bitcoin Block Header. SHA256i then uses the message digest Ho of SHA256o as an initialisation vector and is applied to a second part of the Bitcoin Block Header plus some padding. Finally, SHA2562 again uses the standard initialisation vector IV and is applied to the message digest of SHA256i plus some padding.

The ultimate aim of Bitcoin mining is to find a SHA2562 message digest or “hash” that is lower than or equal to the current Target. If the Target condition is met, then the Bitcoin Block Header in question is accepted by the Bitcoin Network and the Bitcoin miner receives a mining award. On the other hand, if the Target condition is not met, the Bitcoin miner will need to perform cryptographic hashing in respect of one or more different Bitcoin Block Headers until the specified Target condition is met.

The different Bitcoin Block Headers are generally generated by incrementing a Nonce field in the second part of the Bitcoin Block Header. In this case, since the first part of the Bitcoin Block Header remains unchanged, the output of SHA256o is unchanged and there is no need to re-perform SHA256o for each new Nonce. Once all values for the Nonce have been exhausted, then a Bitcoin Block Header that references different transactions, by way of a different HashMerkleRoot, might be considered. Since the HashMerkleRoot spans both parts of the Bitcoin Block Header, SHA256o then needs to be re-performed to generate a new message digest Ho, and SHA256i then needs to be re-applied to the second part of the Bitcoin Block Header using that new message digest Ho as the initialisation vector.

Bitcoin mining can be extremely computationally expensive and various optimisations have therefore been proposed. For example, Rahul P. Naik, “Optimising the SHA256 Hashing Algorithm for Faster and More Efficient Bitcoin Mining", MSc Information Security Department of Computer Science UCL, 2013, describes various optimisations which make use of the fact that certain portions of the Bitcoin Block Header remain unchanged, or are slow to change, or are merely incremented, for plural different input messages. US 2018/0006808 A1 describes further optimisations which use hardwired values for the portions of input messages that always remain the same.

The above optimisations go some way to reducing the computational burden but further optimisation, particularly relating to message scheduling, is possible. In this regard, when performing the cryptographic hashing, a message scheduler is used to calculate (from distinct portions of the input message) a set of input values for compression by the cryptographic compression function. This process of calculating the input values can contribute significantly to the computational effort required to perform the cryptographic hashing.

EP 3 095 044 A1 accordingly describes an optimisation commonly known as “ASICBoost” in which different input messages are used for SHA256o but in which the last 32 bits of the HashMerkleRoot in the Bitcoin Block Header, which are used to derive the input message for SHA256i, are kept the same. This is achieved either by identifying multiple instances of HashMerkleRoot that collide in the last 32 bits (commonly known as “Covert ASICBoost”) or by incrementing the Version in the Bitcoin Block Header (commonly known as “Overt ASICBoost”). The same message schedule for SHA256i can then be reused for multiple outputs of SHA256o. Pham et al, “Double SHA-256 Hardware Architecture With Compact Message Expander for Bitcoin Mining”. IEEE Access, Volume 8, 2020, pp.139634-139646, also describes avoiding certain message scheduler calculations for SHA256i and SHA2562 where the input values will always have the value 0x00000000.

It is desired to provide further improvements relating to message scheduling for cryptographic hashing. S UM MARY

According to an aspect of the present invention there is provided a method of performing cryptographic hashing in respect of plural different input messages to be hashed, the method comprising: causing a message scheduler to: calculate a set of one or more partially-calculated input values for a cryptographic compression function using one or more values based on one or more invariable portions of an initial input message to be hashed, wherein corresponding ones of the invariable portions do not vary across the plural different input messages to be hashed; and for each of one or more subsequent input messages to be hashed: calculate a set of fully-calculated input values for the cryptographic compression function, wherein calculating the set of fully-calculated input values comprises performing calculations using one or more of the partially-calculated input values and one or more values based on one or more variable portions of the subsequent input message to be hashed, wherein corresponding ones of the variable portions do vary across the plural different input messages to be hashed; and provide the set of fully-calculated input values for use when performing the cryptographic compression function in respect of the subsequent input message. According to another aspect of the present invention there is provided an apparatus for performing cryptographic hashing in respect of plural different input messages to be hashed, the apparatus comprising: a message scheduler having processing circuitry configured to: calculate a set of one or more partially-calculated input values for a cryptographic compression function using one or more values based on one or more invariable portions of an initial input message to be hashed, wherein corresponding ones of the invariable portions do not vary across the plural different input messages to be hashed; and for each of one or more subsequent input messages to be hashed: calculate a set of fully-calculated input values for the cryptographic compression function, wherein calculating the set of fully-calculated input values comprises performing calculations using one or more of the partially-calculated input values and one or more values based on one or more variable portions of the subsequent input message to be hashed, wherein corresponding ones of the variable portions do vary across the plural different input messages to be hashed; and provide the set of fully-calculated input values for use when performing the cryptographic compression function in respect of the subsequent input message.

As will be appreciated, the present invention can greatly increase speed and efficiency when performing cryptographic hashing in respect of plural different input messages which have invariable portions and variable portions. In particular, the Applicant has recognised that certain input values for a cryptographic compression function may vary for plural different input messages to be hashed. This is because those variable input values are derived from message portions which vary across the plural different input messages to be hashed. However, the Applicant has identified that even those variable input values might be calculated at least in part using message portions which do not vary across the plural different input messages to be hashed. The Applicant has then recognised that those variable input values can at least be partially calculated once in respect of an initial input message using the invariable portions, and that those partially-calculated input values can then be reused to calculate fully-calculated input values for one or more subsequent input messages. This can significantly reduce the number of calculations which need to be performed when calculating the variable input values for plural different input messages to be hashed. This in turn can significantly increase the processing speed and/or can significantly reduce the processing burden placed on the apparatus used to perform the cryptographic hashing. This is in contrast to the known optimisations in which only invariable fully-calculated input values are determined in advance and then reused for plural different input messages.

In embodiments, the cryptographic hashing may be performed when mining for cryptocurrency, such as (but not limited to) Bitcoin. However, the techniques disclosed herein may equally be applied in other cryptographic hashing contexts in which plural input messages have invariable portions and variable portions. ln embodiments, the cryptographic compression function may be a SHA256 compression function. The cryptographic compression function may be a first instance cryptographic compression function (referred to herein as “SHA256o“), a second instance cryptographic compression function (referred to herein as “SHA256-T), or a third instance cryptographic compression function (referred to herein as “SHA2562"). Overall, the cryptographic hashing may comprise performing plural (e.g. three) instances of a cryptographic compression function, with a message scheduler for one or more (e.g. each) instance operating in the manner of the present invention.

In embodiments, the plural different input messages to be hashed may each correspond to a different Bitcoin Block Header. The Bitcoin Block Headers may each comprise a Version field, a HashPrevBlock field, a HashMerkleRoot field, a Timestamp field, a Target field, and a Nonce field. The Bitcoin Block Headers may be padded with a Padding + Length field for the purposes of the cryptographic hashing. The one or more invariable portions and/or one or more variable portions may be distinct portions of an input message to be hashed.

In embodiments in which the cryptographic compression function is a first instance cryptographic compression function (SHA256o), the plural different input messages to be hashed may each comprise a Version field, a HashPrevBlock field, and/or a (first) part of a HashMerkleRoot field. The one or more invariable portions may correspond to the HashPrevBlock field and/or to the (first) part of the HashMerkleRoot field. The one or more variable portions may correspond to the Version field. The Version field may be incremented across the plural different input messages. In embodiments in which the cryptographic compression function is a first instance cryptographic compression function (SHA256o), the cryptographic compression function may use the SHA256 standard initialisation vector as the initialisation vector.

In embodiments in which the cryptographic compression function is a second instance cryptographic compression function (SHA256-i), the plural different input messages to be hashed may each comprise a (second) part of a HashMerkleRoot field, a Timestamp field, a Target field, a Nonce field, and/or a Padding + Length field. The one or more invariable portions may correspond to the (second) part of the HashMerkleRoot field, the Timestamp field, the Target field, and/or the Padding + Length field. The one or more variable portions may correspond to the Nonce field. The Nonce field may be incremented across the plural different input messages. In embodiments in which the cryptographic compression function is a second instance cryptographic compression function (SHA256i), the cryptographic compression function may use a message digest (from a first instance cryptographic compression function (SHA256o)) as the initialisation vector.

In embodiments in which the cryptographic compression function is a third instance cryptographic compression function (SHA2562), the plural different input messages to be hashed may each comprise a Message Digest field (from a second instance cryptographic compression function (SHA256i)) and a Padding + Length field. The one or more invariable portions may correspond to the Padding + Length field. The one or more variable portions may correspond to the Message Digest field. In embodiments in which the cryptographic compression function is a third instance cryptographic compression function (SHA2562), the cryptographic compression function may use the SHA256 standard initialisation vector as the initialisation vector.

It will be appreciated that the one or more invariable portions referred to herein will not vary across the plural different input messages to be hashed, i.e. those message portions will be the same in each and every one of the plural different input messages. Moreover, it may be the case that one or more of those invariable portions will always be the same for the cryptographic hashing context (e.g. independent of any Bitcoin Block Header), such as the Padding + Length field. However, it will also be appreciated that one or more of the invariable portions may change for input messages not forming part of the plural different input messages to be processed in the manner of the present invention. For example, one or more of the invariable portions may change if there is an update to the HashPrevBlock field, HashMerkleRoot field, Timestamp field, and/or Target field. In this case, the one or more partially- calculated input values may need to be re-calculated based on a further initial input message for a further set of plural different input messages so as to again be processed in the manner of the present invention.

It will also be appreciated that the one or more variable portions referred to herein will vary across the plural different input messages to be hashed, i.e. those message portions will be different in each and every one of the plural different input messages. For example, as discussed above, those one or more variable portions may be incremented across the plural different input messages. In embodiments, for the initial input message, the calculation of a partially-calculated input value of the set of one or more partially-calculated input values may comprise performing some, but not all, of the operations in a (e.g. SHA256) message scheduling calculation. The message scheduling calculation may comprise performing: a^(W[t-2]) + W[t-7] + ao(W[t-15]) + W[t-16] where: ffi(x) = ROTRi?(x) © ROTRig(x) © SHRio(x) ao(x) = ROTR ₇ (X) ® ROTRI ₈ (X) @ SHR ₃ (x)

ROTRi is a bitwise rotate right for i bits

SHRi is a bitwise shift right for i bits; and

© is a bitwise exclusive OR

Thus, for the initial input message, the calculation of a partially-calculated input value of the set of one or more partially-calculated input values may comprise performing one or more of: an add operation; a bitwise rotate right (ROTR) operation; a bitwise shift right (SHR) operation; and a bitwise exclusive OR (@) operation.

In embodiments, the message scheduler may be configured to store one or more partially-calculated input values (e.g. in electronic storage such as (but not limited to) registers and/or memory). The message scheduler may be configured to retrieve one or more partially-calculated input values (e.g. from the electronic storage) prior to performing calculations using one or more of the partially-calculated input values. In embodiments, for a subsequent input message to be hashed, the calculation of a fully-calculated input value of the set of fully-calculated input values may comprise performing some, but not all, of the operations (e.g. performing the remaining operations) in a (e.g. SHA256) message scheduling calculation. Again, the message scheduling calculation may comprise performing: a^(W[t-2]) + W[t-7] + ao(W[t-15]) + W[t-16] where: ffi(x) = R0TRi?(x) © ROTRig(x) © SHRio(x) ao(x) = R0TR ₇ (X) ® R0TRI ₈ (X) @ SHR ₃ (x)

ROTRi is a bitwise rotate right for i bits

SHRi is a bitwise shift right for i bits; and

© is a bitwise exclusive OR

Thus, for a subsequent input message to be hashed, the calculation of a fully-calculated input value of the set of fully-calculated input values may comprise performing one or more of: an add operation; a bitwise rotate right (ROTR) operation; a bitwise shift right (SHR) operation; and a bitwise exclusive OR (@ operation.

In embodiments, for each subsequent input message to be hashed, the calculation of a fully-calculated input value may also comprise adding a roundspecific constant to the fully-calculated input value. Adding a round-specific constant may be performed by the message scheduler. Alternatively, adding a round-specific constant may be performed by a message compressor that performs the cryptographic compression function in respect of the subsequent input message.

In embodiments, the message scheduler may be further configured to derive a set of one or more incrementable fully-calculated input values for the cryptographic compression function based on one or more incremented portions of the initial input message to be hashed, wherein the one or more incremented portions will be incremented across the plural different input messages to be hashed. The message scheduler may be further configured to store one or more of the incrementable fully-calculated input values (e.g. in electronic storage such as (but not limited to) registers and/or memory). The message scheduler may be further configured to retrieve the one or more incrementable fully-calculated input values (e.g. from the electronic storage). For each of the one or more subsequent input messages, the process of calculating the set of fully-calculated input values may comprise calculating a set of one or more incremented fully-calculated input values for the cryptographic compression function by incrementing the one or more incrementable fully-calculated input values. The set of one or more incremented fully-calculated input values may then be provided for use when performing the cryptographic compression function in respect of the subsequent input message. The set of one or more incremented fully-calculated input values may also be used as the set of one or more incrementable fully-calculated input values for the next subsequent input message.

In embodiments in which the cryptographic compression function is a first instance cryptographic compression function (SHA256o), the one or more incremented portions may correspond to the Version field. In embodiments in which the cryptographic compression function is a second instance cryptographic compression function (SHA256-i), the one or more incremented portions may correspond to the Nonce field.

In embodiments, the message scheduler may be further configured to derive a set of one or more invariable fully-calculated input values for the cryptographic compression function based (e.g. solely) on one or more invariable portions of the initial input message to be hashed, wherein corresponding ones of the invariable portions do not vary across the plural different input messages to be hashed. The message scheduler may be further configured to store one or more of the invariable fully-calculated input values (e.g. in electronic storage such as (but not limited to) registers and/or memory). The message scheduler may be further configured to retrieve the one or more invariable fully-calculated input values (e.g. from the electronic storage). One or more of the invariable fully-calculated input values may, for example, be stored in non-volatile memory. One or more of the invariable fully-calculated input values may also or instead be hardwired, for example in cases where those invariable fully-calculated input values will always be the same for the cryptographic hashing context (e.g. independent of any Bitcoin Block Header). The set of one or more invariable fully-calculated input values may then be provided for use when performing the cryptographic compression function in respect of the subsequent input message.

The Applicants have further identified that, due to the calculation of input values based on an initial input message, certain calculations which are needed when performing full calculation of input values in respect of a subsequent input message can be performed in parallel. This is because some calculations required when calculating the one or more fully-calculated input values for the subsequent input message will already have been performed when calculating the input values for the initial input message. This can allow for parallel calculation of the fully-calculated input values for the subsequent input message.

Thus, in embodiments, calculating the set of one or more fully-calculated input values for a subsequent input message may comprise calculating a first set of fully-calculated input values for the subsequent input message and calculating a second set of fully-calculated input values for the subsequent input message, wherein calculation of the first set of fully-calculated input values is performed in parallel with calculation of the second set of fully-calculated input values. In embodiments, one or more of the first set of fully-calculated input values may be used when calculating one or more of the second set of fully- calculated values and one or more of the second set of fully-calculated input values may be used when calculating one or more of the first set of fully- calculated values. These embodiments can significantly increase the processing speed by introducing parallelism to the message scheduler.

As will be appreciated, where there are variable fully-calculated input values which cannot make use of one or more invariable portions in the manner described herein, calculating the set of fully-calculated input values for a subsequent input message may further comprise fully calculating those variable fully-calculated input values using the full message scheduling calculation. As will also be appreciated, embodiments may further comprise, for each of one or more subsequent input messages, causing a message compressor to perform the cryptographic compression function in respect of the subsequent input message using the set of fully-calculated input values to generate a message digest. The message digest from one instance may be passed to a subsequent instance (in the case of SHA256o and SHA256i) or may be compared to the Target (in the case of SHA2562).

Embodiments can be implemented in any desired and suitable data processing apparatus, such as any suitably configured computer-based, processor-based, and/or circuitry-based, system. Similarly, the various functions of the apparatus described herein can be carried out in any desired and suitable manner. For example, the functions of the apparatus described herein may be implemented in hardware and/or software as desired. Thus, unless otherwise indicated, the various functional elements described herein may, for example, comprise a suitable processor or processors, controller or controllers, functional unit or units, circuitry, processing logic, microprocessor arrangements, etc., that are operable to perform the various functions, etc., such as appropriately dedicated hardware elements (processing circuitry) and/or programmable hardware elements (processing circuitry) that are configured to operate in the desired manner. In embodiments, the apparatus may comprise one or more integrated circuits, such as one or more ASICs (Application-Specific Integrated Circuits) and/or FPGAs (Field-Programmable Gate Arrays). In embodiments, the apparatus may comprise, and/or may be in communication with, one or more electronic storage devices that store the data (e.g. input message data, partially-calculated input values, fully-calculated input values, round-specific constants, initialisation vectors, message digests, etc.) as described herein.

BRIEF DESCRIPTION OF DRAWINGS

By way of example only, embodiments of the present invention will now be described in detail with reference being made to the accompanying drawings in which:

Figure 1 illustrates a cryptographic hashing module according to an embodiment of the present invention;

Figure 2 shows details of a message scheduler for use in the cryptographic hashing module of Figure 1 ;

Figure 3 shows details of a section of the message scheduler of Figure 2;

Figure 4 illustrates cryptographic hashing of a Bitcoin Block Header according to an embodiment of the present invention;

Figure 5 illustrates details of message compression modules for use in the cryptographic hashing module of Figure 4;

Figure 6 shows the operations of computation variants used to derive fully-calculated input values according to an embodiment of the present invention;

Figure 7 illustrates a hardware implementation of a message scheduler for SHA256o according to an embodiment of the present invention;

Figure 8 illustrates a hardware implementation of a message scheduler for SHA256i according to an embodiment of the present invention; Figure 9 illustrates a hardware implementation of a message scheduler for SHA256i according to another embodiment of the present invention; and

Figure 10 illustrates a hardware implementation of a message scheduler for SHA2562 according to an embodiment of the present invention.

DETAILED DESCRIPTION

Figure 1 shows a cryptographic hashing module 102 comprising processing circuitry for performing cryptographic hashing. The cryptographic hashing module 102 may, for example, be implemented using one or more ASICs. In this embodiment, the cryptographic hashing module 102 performs SHA256 to compress a 512-bit input message 104 based on a 256-bit initialisation vector 106 in order to produce a 256-bit message digest or hash 108. The cryptographic hashing module 102 comprises a message scheduler 110 which divides the input message 104 into distinct portions and uses those distinct portions to derive a set of input values for t rounds of message compression performed by message compressor 112.

In SHA256, the message scheduler 110 divides the input message 104 into 16 x 32-bit words M[0]-M[15] and expands those 16 x 32-bit words to derive a set of 64 x 32-bit input values W[0]-W[63] for the message compressor 112 in accordance with the following:

The 8 elements HA-HH of the initialisation vector 106 are stored as working variables A-H in electronic storage 114 as follows:

The message compressor 112 then performs 64 rounds of a SHA256 message compression function using the set of input values W[0]-W[63] provided by the message scheduler 110, together with the working variables A- H stored in electronic storage 114 and a set of 64 x 32-bit round-specific constants K[0]-K[63] in accordance with the following: After the 64 rounds the following calculations are performed:

In SHA256, the standard initialisation vector IV is: and the round-specific constants K[0]-K[63] are:

Figure 2 shows further details of the message scheduler 110. In this embodiment, the message scheduler 110 comprises a resource sharing (rolled) hardware architecture. The message scheduler 110 receives the input message 104 and calculates a set of input values W[0]-W[63] for the compression

5 function as discussed above. In this embodiment, the message scheduler 110 also performs the step of adding the set of round-specific constants K[0]-K[63] respectively to the set of input values W[0]-W[63] to generate a set of constant- modified input values WtOl-W^eS], although in other embodiments this addition could instead be performed by the message compressor 112.

Figure 3 shows details of a section of the message scheduler 110. In this embodiment, the section of the message scheduler 110 comprises a multiplexor 302 for progressively selecting, in respect of an initial input message, the input value W[t] either to be i) M[t] for 0 < t < 15; or ii) <n(W[t-2]) + W[t-7] + o-o(W[t-15]) + W[t-16] for 16 < t < 63. The selected input value W[t] is then progressively passed to circuitry 304 for addition with K[t] to produce the constant-modified input value W[t], which as discussed below may in some cases be stored as a reusable value p’[t]. To enable the calculation of W[t] for 16 < t < 63, the input values W[t] are also progressively moved through a set of 16 x 32-bit registers 306. Circuitry 308 is then used to perform the standard message scheduling calculation: cn(W[t-2]) + W[t-7] + o-o(W[t-15]) + W[t-16], In accordance with embodiments of the present invention, the circuitry 308 can also perform only selected ones of the operations in the message scheduling calculation to produce reusable values p[t]. Those reusable values p[t] can then be stored in electronic storage 310 for later use with subsequent input messages. Using a resource sharing (rolled) hardware architecture for the one-off computations in respect of an initial input message reduces the need for a large chip area and reduces power consumption. The section of the message scheduler 110 as shown in Figure 3 can then be shut down to conserve energy when calculating input values for subsequent input messages. Figure 4 shows cryptographic hashing of a Bitcoin Block Header 402. The Bitcoin Block Header 402 contains: a 32-bit Version field 404 which provides block version information; a 256-bit HashPrevBlock field 406 which provides the message digest of the previous block accepted by the Bitcoin Network which is referenced by the current block; a 256-bit HashMerkleRoot field 408 which provides a message digest of the Merkle Root for the unconfirmed transactions that are selected by the Bitcoin miners to include in the new block; a 32-Bit Timestamp field 410 which provides the current timestamp in seconds since 1970-01-01 00:00 UTC; a 32-bit Target field 412 which provides the current Target to be met for the message digest of the new block (i.e. indicative of a particular minimum number of leading zeros that the message digest must have); and a 32-bit Nonce field 414 which is used to add variation to the block header so as to compute different message digests. A 384-bit Padding + Length field 416 is appended to provide two 512-bit input messages 418 and 420 of suitable size for cryptographic hashing using SHA256. In some embodiments, the Padding + Length may be provided by non-volatile memory or hardwired values since the values in question are always constant.

In order to perform the cryptographic hashing, a first input message 418 is provided to a first cryptographic hashing module 424. The first cryptographic hashing module 424 then performs a first instance cryptographic hashing SHA256o of the first input message 418 using the standard initialisation vector IV 422. SHA256o produces a first message digest Ho which is stored in electronic storage 426. The second input message 420 is provided to a second cryptographic hashing module 428. The second cryptographic hashing module 428 then performs a second instance cryptographic hashing SHA256i of the second input message 420 using the first message digest Ho as the initialisation vector. SHA256i produces a second message digest Hi 430. The second message digest Hi is combined with a Padding + Length 432 to create a third input message 434 of suitable size for cryptographic hashing using SHA256. In some embodiments, the Padding + Length may again be provided by nonvolatile memory or hardwired values since the values in question are always constant. The third input message 434 is provided to a third cryptographic hashing module 438. The third cryptographic hashing module 438 performs a third instance cryptographic hashing SHA2562 of the third input message 434 using the standard initialisation vector IV 436. SHA2562 produces a third, and final, message digest H2440. If the third message digest H2 meets the Target condition, then the Bitcoin Block Header used to create that message digest H2 can be broadcast to the Bitcoin Network. On the other hand, if the third message digest H2 does not meet the Target condition, then one or more different Bitcoin Block Headers will need to be considered. In this embodiment, the one or more different Bitcoin Block Headers are derived by incrementing the Version field 404 and/or by incrementing the Nonce field 414 so as to give plural different input messages (plural different first input messages 418, plural different second input messages 420, and/or plural different third input messages 434) to be hashed.

Figure 5 shows a first message compressor 502 for performing the 64 rounds of compression in SHA256o. The first message compressor 502 receives the set of constant-modified input values Wo’[t] from a message scheduler and the standard initialisation vector IV 422. Also shown is circuitry 504 for adding the outputs of the first message compressor 502 to the elements of the standard initialisation vector IV 422 to produce the first message digest Ho. Also shown is a second message compressor 506 for performing the 64 rounds of compression in SHA256i. The second message compressor 506 receives the set of constant-modified input values Wi’[t] from a message scheduler and Ho as an initialisation vector. Also shown is circuitry 508 for adding the outputs of the second message compressor 506 to the elements of Ho to produce the second message digest Hi. Also shown is a third message compressor 510 for performing the 64 rounds of compression in SHA2562. The third message compressor 510 receives the set of constant-modified input values W2’[t] from a message scheduler (not shown), which are based on Hi, and the standard initialisation vector IV 436. Also shown is circuitry 512 for adding the outputs of the third message compressor 510 to the elements of the standard initialisation vector IV 436 to produce the third, and final, message digest H2. In this embodiment, each of the message compressors comprises a resource sharing (rolled) hardware architecture. Using a resource sharing (rolled) hardware architecture for the message compressors again reduces the need for a large chip area; reducing power consumption.

Figure 6 illustrates computation variants CV1-CV7 that can be used by a message scheduler when calculating fully-calculated input values using partially-calculated input values. Also shown for comparison is the standard computation variant CVo for fully calculating input values, i.e. for the full message scheduling calculation <n(W[t-2]) + W[t-7] + o-o(W[t-15]) + W[t-16], As is apparent from Figure 6, the computation variants CV1-CV7 can provide the following savings each time they are used in place of the standard computation variant CVo:

SHA256o IMPLEMENTATION

Referring again to Figure 4, the first input message 418, which is provided to the first cryptographic hashing module 424 to perform SHA256o, comprises the 32-bit Version field 404; the 256-bit HashPrevBlock field 406; and the first 224 bits of the HashMerkleRoot field 408. As per “ASICBoost”, mentioned above, the Version may be incremented to create multiple instances of Ho. When this happens, M[00] (i.e. corresponding to the 32-bit Version field 404) is incremented, but the other M[t] (i.e. corresponding to the HashPrevBlock field 406 and HashMerkleRoot field 408) do not vary. With this in mind, embodiments of the present invention can make use of the following observations for plural different first input messages 418:

1 . W[03] to W[15] will remain unchanged.

2. cro/i(W[O3]) to cro/i(W[15]) will also remain unchanged in view of observation 1 above.

3. Based on the current Target, W[01] and W[02] will remain unchanged as 0x00000000. Additions of these values can be avoided.

4. <ro(W[O1]) and cro(W[O2]) will also remain unchanged as 0x00000000 in view of observation 3 above. Additions of these values can be avoided.

5. Various reusable values p[t] can be calculated once for an initial value of W[00], such as 0x20000000, using the space-saving rolled hardware of Figure 3.

6. For other values of W[00], the reusable values p[t] can be directly fed into the computation variants CV1-CV7 shown in Figure 6 to obtain the same result as the standard computation variant CVo shown in Figure 6.

7. Constant-modified reusable values p’[t] = p[t] + K[t] can also be computed once for an initial value of W[00], such as 0x20000000, and then reused for other values of W[00] in cases where p[t] = W[t],

8. For other values of W[00], the constant-modified reusable values p’[t] can be directly fed into the message compression function of SHA256o.

9. The reusable values p[t] and p’[t] can be fed into the set of message schedule computation variants in a fully unrolled ASIC hardware implementation 700 to obtain a SHA256o fully unrolled message schedule as shown in Figure 7. Keeping the above observations in mind, the following reusable values p[t] and p’[t] can be stored for an initial input message and reused for subsequent input messages:

Figure 7 shows a message scheduling hardware implementation 700 for

SHA256o that makes use of the table above. As is shown, electronic storage 702 is provided to store and later provide the reusable values p[t] and p'[t], which are derived for an initial input message in accordance with the table above and then reused for one or more subsequent input messages. As is also shown, some of the reusable values p'[t] can be used directly as W[t] for each one of plural input messages having different Version values. Incrementing circuitry (one indicated as 704) is also provided for incrementing ( ⁺⁺ ) the value of some of the incrementable reusable values p[t] and p'[t] for each subsequent input message in accordance with the table above. As is shown, in some cases the incremented reusable values p[t] and p'[t] can also be used as W[t] and W[t] for that subsequent input message. Calculation modules (one indicated as 706) are also provided for performing the appropriate computation variants as shown in Figure 6 for the subsequent input message in accordance with the table above. Further electronic storage 708 is also provided for storing and later providing the resultant fully calculated input values W[t] for the subsequent input message in accordance with the table above.

It is notable from the above that for t=18, 20, 22, 24-30, 32, 34 and 36, the reusable values p[t] are partially-calculated versions of input values W[t] or W[t] for the SHA256o cryptographic compression function which are calculated using invariable portions of the plural input messages to be hashed. Those reusable values p[t] are then reused to calculate the fully-calculated input values W[t] or W[t] for a subsequent input message using values based on one or more variable portions of the input messages to be hashed.

For example, for t=18, the reusable value p[18] = W[11] + cro(W[O3]) is a partially-calculated version of the fully-calculated input value W[18] = W[11] + cro(W[O3]) + W[02] + CTI(W[16]) for the SHA256o cryptographic compression function which is calculated using only the invariable portions W[11 ], W[03] and W[02] of the input messages to be hashed. That reusable value p[18] can then be reused to calculate (using CV3) the fully-calculated input value W[18] = p[18] + CTI(W[16]) for a subsequent input message using a value <n(W[16]) which is based on the variable portion W[00] of the input messages to be hashed. Doing this for t=18 saves 2 add operations, 2 ROTR operations, 1 SHR operation and 2 operations for each subsequent input message to be hashed.

As will be appreciated, the savings for all values of t will accumulate over time to give a significant reduction in the number of operations and thus processing time/resources required when performing SHA256o. In particular, the following overall savings are possible for each subsequent input message:

SHA256i IMPLEMENTATION

Referring again to Figure 4, the second input message 420, which is provided to the second cryptographic hashing module 428 to perform SHA256-I, comprises the last 32 bits of the HashMerkleRoot field 408; the Timestamp field 410; the 32-bit Target field 412; the 32-bit Nonce field 414; and the 384-bit Padding + Length field 416. As mentioned above, the Nonce may be incremented to create multiple instances of Hi. When this happens, M[03] (i.e. corresponding to the 32-bit Nonce field 414) is incremented, but the other M[t] (i.e. corresponding to the HashMerkleRoot field 408, the Timestamp field 410, the Target field 412, and the Padding + Length field 416) do not vary. With this in mind, embodiments of the present invention can make use of the following observations for plural different second input messages 420:

1 . W[00] to W[02] and W[04] to W[15] will remain unchanged. 2. CTO/I(W[OO]) to CTO/I(W[O2]) will also remain unchanged in view of observation 1 above.

3. W[05] to W[14] will remain unchanged as 0x00000000. Additions of these values can be avoided. 4. CTO(W[O5]) to CTO(W[14]) will also remain unchanged as 0x00000000 in view of observation 3 above. Additions of these values can be avoided.

5. The constant-modified reusable values p’[04] = W[04] + K[04] = 0xB956C25B and p'[15] = W[15] + K[15] = 0xC19BF3F4 will forever remain unchanged and independent of any Bitcoin Block Header. They can thus be added to the list of SHA256i round-specific constants stored in non-volatile memory and directly fed from the non-volatile memory into the message compression function of SHA256i.

6. Various reusable values p[t] can be calculated once for an initial value of W[03], such as 0x00000000, using the space-saving rolled hardware of Figure 3.

7. For other values of W[03], the reusable values p[t] can be directly fed into the computation variants CV1-CV7 shown in Figure 6 to obtain the same result as the standard computation variant CVo shown in Figure 6.

8. Constant-modified reusable values p’[t] = p[t] + K[t] can also be computed once for an initial value of W[03], such as 0x00000000, and then reused for other values of W[03] in cases where p[t] = W[t],

9. For other values of W[03], the constant-modified reusable values p’[t] can be directly fed into the message compression function of SHA256i.

10. The reusable values p[t] and p’[t] can be fed into the set of message schedule computation variants in a fully unrolled ASIC hardware implementation 800 to obtain a SHA256i fully unrolled message schedule as shown in Figure 8. 11. The reusable values p[t] and p’[t] also allow the parallel computation of the message schedule. This is because the computation of W[t] no longer needs to be serialised since certain W[t] can be computed without the knowledge of the prior W[t], An example parallel architecture 900 is shown in Figure 9.

Keeping the above observations in mind, the following reusable values p[t] and p’[t] can be stored for an initial input message and reused for subsequent input messages:

Figure 8 shows a message scheduling hardware implementation 800 for SHA256i that makes use of the above table. As is shown, electronic storage 802 is provided to store and later provide the reusable values p[t] and p'[t], which are derived for an initial input message in accordance with the table above and then reused for one or more subsequent input messages. As is also shown, some of the reusable values p'[t] can be used directly as W[t] for each one of plural input messages having different Nonce values. Incrementing circuitry (one indicated as 804) is also provided for incrementing ( ⁺⁺ ) the value of some of the incrementable reusable values p[t] and p'[t] for each subsequent input message in accordance with the table above. As is shown, in some cases the incremented reusable values p[t] and p'[t] can then be used as W[t] and W[t] for that subsequent input message. Calculation modules (one indicated as 806) are also provided for performing the appropriate computation variants as shown in Figure 6 for the subsequent input message in accordance with the table above. Further electronic storage 808 is also provided for storing and later providing the resultant fully calculated input values W[t] for the subsequent input message in accordance with the table above.

Figure 9 shows an alternative message scheduling hardware implementation 900 for SHA256i in which the fully calculated input values W[t] are calculated in parallel rather than in series. As is shown, electronic storage 902 is again provided to store and later provide the reusable values p[t] and p'[t], which are derived for an initial input message in accordance with the table above and then reused for one or more subsequent input messages. As is also shown, some of the reusable values p'[t] can be used directly as W[t] for each one of plural input messages having different Nonce values. Incrementing circuitry (one indicated as 904) is again also provided for incrementing ( ⁺⁺ ) the value of some of the incrementable reusable values p[t] and p'[t] for each subsequent input message in accordance with the table above. As is shown, in some cases the incremented reusable values p[t] and p'[t] can then be used as W[t] and W[t] for that subsequent input message.

In this embodiment, a first set of calculation modules (one module in the first set is indicated as 906a) and a second set of calculation modules (one module in the second set is indicated as 906b) are also provided for performing the appropriate computation variants as shown in Figure 6 for the subsequent input message in accordance with the table above. As will be appreciated, the calculation modules of the first set can operate in parallel with the calculation modules of the second set since the values needed by the modules of one set will already have been calculated by the other set, and vice versa, and so there is no need to run those modules entirely in series. Further electronic storage 908 is also provided for storing and later providing the resultant fully calculated input values W[t] for the subsequent input message in accordance with the table above.

It is notable from the above that for t=18, 20 and 22-32 the reusable values p[t] are partially-calculated versions of input values W[t] or W[t] for the SHA256i cryptographic compression function which are calculated using invariable portions of the input messages to be hashed. Those reusable values p[t] are then reused to calculate the fully-calculated input values W[t] or W[t] for a subsequent input message using values based on one or more variable portions of the input messages to be hashed.

For example, for t=18, the reusable value p[18] = <n(W[16]) + W[02] is a partially-calculated version of the fully-calculated input value W[18] = W[11] + cro(W[O3]) + W[02] + CTI(W[16]) for the SHA256i cryptographic compression function which is calculated using only the invariable portions W[16], W[11] and W[02] of the input messages to be hashed. That reusable value p[18] can then be reused to calculate (using CV2) the fully-calculated input value W[18] = p[18] + cro(W[O3]) for a subsequent input message using a value cro(W[O3]) which is based on the variable portion W[03] of the input messages to be hashed. Doing this for t=18 saves 2 add operations, 2 ROTR operations, 1 SHR operation and 2 operations for each subsequent input message to be hashed.

As will be appreciated, the savings for all values of t will again accumulate over time to give a significant reduction in the number of operations and thus processing time/resources required when performing SHA256i. In particular, the following overall savings are possible for each subsequent input message:

SHA256 ₂ IMPLEMENTATION

Referring again to Figure 4, the third input message 434, which is provided to a third cryptographic hashing module 438 to perform SHA2562, comprises the 256-bit second message digest Hi field 430 and the 256-bit Padding + Length field 432. M[00]-M[07] (i.e. corresponding to the second message digest Hi field 430) will vary, but M[08]-M[15] (i.e. corresponding to the 384-bit Padding + Length field 432) do not vary. With this in mind, embodiments of the present invention can make use of the following observations for plural different third input messages 434:

1. W[08] to W[15] will remain unchanged as 0x00000000. Additions of these values can be avoided.

2. CTO/I(W[O8]) to CTO/I(W[15]) will also remain unchanged as 0x00000000 in view of observation 1 above. Additions of these values can be avoided. 3. The reusable values p[17] = OxOOAOOOOO, p[23] = 0x11002000, and p[30] = 0x00400022 will forever remain unchanged and independent of any Bitcoin Block Header. They can thus be added to the list of SHA2562 round-specific constants stored in non-volatile memory and directly fed from the non-volatile memory into the message compression function of SHA256 ₂ . The constant-modified reusable values p’[08] = W[08] + K[08] = 0x5807 AA98 and p'[15] = W[15] + K[15] = 0xC19BF274 will forever remain unchanged and independent of any Bitcoin Block Header. They can thus be added to the list of SHA2562 round-specific constants stored in non-volatile memory and directly fed from the non-volatile memory into the message compression function of SHA2562. Various reusable values p[t] can be calculated once using the spacesaving rolled hardware of Figure 3. For other input messages (i.e. other values of H-i), the reusable values p[t] can be directly fed into the computation variants CV1-CV7 shown in Figure 6 to obtain the same result as the standard computation variant CVo shown in Figure 6. The reusable values p[t] and p’[t] can be fed into the set of message schedule computation variants in a fully unrolled ASIC hardware implementation 1000 to obtain a SHA2562 fully unrolled message schedule as shown in Figure 10. W[61] to W[63] need not be implemented in a fully unrolled ASIC implementation. This is because these computations do not fall in the critical path since one can assert a winning Nonce by observing the value of the working variable E at round 61 [t=60]. Keeping the above observations in mind, the following reusable values p[t] and p’[t] can be stored for an initial input message and reused for subsequent input messages:

Figure 10 shows a message scheduling hardware implementation 1000 for SHA2562 that makes use of the above table. As is shown, electronic storage 1002 is provided to store and later provide the reusable values p[t] and p'[t], which are derived for an initial input message in accordance with the table 5 above and then reused for one or more subsequent input messages. As is also shown, some of the reusable values p'[t] can be used directly as W[t] for each one of plural input messages. Calculation modules (one indicated as 1006) are also provided for performing the appropriate computation variants as shown in Figure 6 for the subsequent input message in accordance with the table above. 0 Further electronic storage 1008 is also provided for storing and later providing the resultant fully calculated input values W[t] for the subsequent input message in accordance with the table above.

It is notable from the above that for t=17, 23 and 30 the reusable values p[t] are partially-calculated versions of input values W[t] or W[t] for the SHA2562 5 cryptographic compression function which are calculated using invariable portions of the input messages to be hashed. Those reusable values p[t] are then reused to calculate the fully-calculated input values W[t] or W[t] for a subsequent input message using values based on one or more variable portions of the input messages to be hashed. 0 For example, for t=17, the reusable value p[17] = cr1 (W[15]) is a partially- calculated version of the fully-calculated input value W[17] = W[10] + cro(W[O2]) + W[01] + CTI(W[15]) for the SHA2562 cryptographic compression function which is calculated using only the invariable portion W[15] of the input messages to be hashed. That reusable value p[17] can then be reused to calculate (using CVe) the fully-calculated input value W[17] = p[17] + cr0(W[02]) + W[01] for a subsequent input message using values cr0(W[02]) and W[01] which are based on the variable portions W[02] and W[01] of the input messages to be hashed. Doing this for t=17 saves 1 add operation, 2 ROTR operations, 1 SHR operation and 2 operations for each subsequent input message to be hashed.

As will be appreciated, the savings for all values of t will again accumulate over time to give a significant reduction in the number of operations and thus processing time/resources required when performing SHA2562. In particular, the following overall savings are possible for each subsequent input message:

It will accordingly be appreciated from the above that embodiments of the present invention can greatly increase speed and efficiency when performing cryptographic hashing in respect of plural different input messages which have invariable portions and variable portions.