US11113676B2 — Block mining methods and apparatus
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
US011113676B2
( 12) United States Patent ( 10) Patent No .: US 11,113,676 B2
Hanke et al . (45) Date of Patent : Sep. 7, 2021
(54) BLOCK MINING METHODS AND ( 56 ) References Cited
APPARATUS
U.S. PATENT DOCUMENTS
( 71 ) Applicant: Top Galore Limited , Tortola ( VG ) 5,892,900 A * 4/1999 Ginter G06F 21/10
726/26
( 72 ) Inventors : Timo Tobias Hanke, Austin , TX (US ); 6,097,811 A * 8/2000 Micali G06F 21/33
Sergio Demian Lerner , Cuidad de 713/158
Buenos Aires (AR ) 7,359,846 B1 * 4/2008 Fernandez G06F 30/3312
703/13
( 73 ) Assignee : Top Galore Limited , Tortola ( VG ) 7,599,489 B1 * 10/2009 Spracklen HO4L 9/0643
380/28
( * ) Notice: Subject to any disclaimer, the term of this 9,495,668 B1 * 11/2016 Juels G06Q 20/06
patent is extended or adjusted under 35 2011/0142228 A1 * 6/2011 Crispin G06F 9/3895
380/28
U.S.C. 154 ( b ) by 514 days . 2011/0145137 A1 6/2011 Driemeyer et al .
( 21 ) Appl . No .: 15 /141,063 ( Continued )
(22) Filed : Apr. 28 , 2016 OTHER PUBLICATIONS
( 65 ) Prior Publication Data Dadda et al. (NPL 2004 ) The Design of a High Speed ASIC Unit for
the Hash Function SHA - 256 ( Year: 2004 ) . *
US 2017/0243176 A1 Aug. 24 , 2017 (Continued )
Related U.S. Application Data
Primary Examiner Zeshan Qayyum
Assistant Examiner Eduardo Castilho
( 63 ) Continuation of application No. (74 ) Attorney, Agent, or Firm Dergosits & Noah LLP ;
PCT/US2014 /066470 , filed on Nov. 19 , 2014 . Todd A. Noah
( 57 ) ABSTRACT
(60 ) Provisional application No. 61 / 906,310 , filed on Nov.
19, 2013 . Block chain mining methods and apparatus. A mid - state
generator develops a plurality, n , of mid - states by selectively
( 51 ) Int . Ci. varying a portion of the block, and , in particular, the block
G06Q 20/06 ( 2012.01 ) header. A single message expander develops a message
G06Q 20/38 ( 2012.01 ) schedule by expanding a message in accordance with a
( 52 ) U.S. Cl . predetermined expansion function ; and the message sched
CPC G06Q 20/0655 ( 2013.01 ) ; G06Q 20/0658 ule is shared with a plurality, n , of compressors, each
(2013.01 ) ; G06Q 20/3827 ( 2013.01 ) ; G06Q developing a result as a function of the message schedule
2220/00 (2013.01 ) and a respective one of the n unique mid - states in accor
(58) Field of Classification Search dance with a predetermined compression function . The
None compressors can be either rolled core or pipelined core .
See application file for complete search history. 12 Claims , 10 Drawing Sheets
Mid - state
Generator Mid -state, Mid - state ,
...
28
Wol
W1 W1
W2 W,
Delay FIFO Compressori Compressor
W 63
63
30 14a 34a 14b 34b
Mid-staten Mid - state1
16
Out-state Out - state ,
US 11,113,676 B2
Page 2
( 56 ) References Cited Pal et al. PARSHA - 256 - A New Parallelizable Hash Function and
a Multi threaded Implementation . International Workshop on Fast
U.S. PATENT DOCUMENTS Software Encryption, Springer, Berlin , Heidelberg, 2003 ( Year:
2003 ) . *
2011/0238636 A1 * 9/2011 Shirai H04L 9/0643 Atighehchi et al . Generic Parallel Cryptography for Hashing Schemes .
707/693 IEEE 12th International Symposium on Parallel and Distributed
2011/0246774 A1 * 10/2011 Phillips , II HO4L 63/0442 Computing, ISPDC 2013 , Bucharest, Romania , Jun . 27-30 , 2013 .
713/168 IEEE 2013 ( Year: 2013 ) . *
2011/0307659 A1 * 12/2011 Hans G06F 3/0613 Dotemoto , Philip. FPGA Based Bitcoin Mining , California Poly
711/114 technic State University, Jun . 2014 ( Year: 2014 ) . *
2012/0158736 A1 * 6/2012 Milby G06F 16/2255 Dev, Jega. Bitcoin Mining acceleration and performance quantification .
707/747 May 1 , 2014. Department of Computer Science and Engineering
2013/0332743 A1 * 12/2013 Gueron HO4L 9/0643 College of Engineering , Guindy, Anna University, Chennai, India
713/189 ( Year: 2014 ) . *
2014/0093069 A1 * 4/2014 Wolrich G09C 1/00 Atighehschi et al . An Efficient Parallel Algorithm for Skein Hash
380/28 Functions Jan. 2010Proceedings of the IASTED International Con
2015/0043729 A1 * 2/2015 Gopal HO4L 9/0643 ference on Parallel and Distributed Computing and Systems 2010
380/29 ( Year: 2010 ) . *
2016/0125040 A1 * 5/2016 Kheterpal G06Q 20/3827 Ho , Calvin . Adaptation of All -Programmable SoC to Hardware
707/776 Bitcoin Miners and Mining Servers. Jan. 2014. California State
University, Northridge ( Year: 2014 ) . *
OTHER PUBLICATIONS International Preliminary Report on Patentability for International
Application No. PCT/US2014 /066470, dated May 14 , 2016 .
Bitcoin : A Peer-to - Peer Electronic Cash System ( Satoshi Nakamoto Written Opinion of the International Searching Authority for Inter
/ NPL Retrieved Jul. 4 , 2010 ) ( Year: 2010 ) . * national Application No. PCT/US2014 /066470 , dated Feb. 23 ,
2015 .
Naik , Raul: Optimising the SHA256 Hashing Algorithm for Faster International Search Report for International Application No. PCT/
and More Efficient Bitcoin Mining Master Thesis UCL Department US2014 /066470 , dated Feb. 23 , 2015 .
of Computer Science / Sep. 2 , 2013 ( Year: 2013 ) . * Office Action for Chinese Patent Application No. 201480073590.9 ,
Xu et al . , “ Half -Fast ” Bitcoin Miner: Open - Source Bitcoin Mining dated Jan. 29 , 2018 .
with FPGA , retrieved from Google Scholar, cached May 15 , 2014 Office Action for Chinese Patent Application No. 201480073590.9 ,
( Year: 2014 ) . * dated Nov. 24 , 2017 .
Hu et al . High Throughput Implementation of MD5 Algorithm on European Search Opinion for European Application No. 14864642 .
GPU Ubiquitous Information Technologies & Applications, 2009 5 , dated Aug. 8 , 2017 .
ICUT’09 . Proceedings of the 4th International Converence on
IEEE, 2009 ( Year: 2009 ) . * * cited by examiner
U.S. Patent Sep. 7, 2021 Sheet 1 of 10 US 11,113,676 B2
Mid - state Message
8 16
1
14 12
Compressor ; Expander
1
+ PRIOR ART
10 Result Fig . 1
Mid - state Round Constants Message
Counter ROM
1
Compressor Expander
W
14 ' 12 '
10 ' PRIOR ART Fig. 2
Mid - state Constants ROM Message
r 14 ' 12 '
bladelfgh wolwal ... w14 W15
10 ' Fig. 3 PRIOR ART
U.S. Patent Sep. 7, 2021 Sheet 2 of 10 US 11,113,676 B2
Mid - state Message Nonce Result
14 12
Compressor Expander ,
PRIOR ART
+
16
Constant State 14
12 Trigger
Expander2 Compressor2 Comparison
Fig. 4
16
Nonce * Nonce
Message IRO
Mid - state Rolled Core Nonce
or
Tag * Pipelined Core Tag *
PRIOR ART Fig. 5
Block [ O ] Block [ 1 ]
Version Hash Merkle Timestamp Target Nonce
4 32 28 4 4 4 4
Fig . 6 : Block Header PRIOR ART
U.S. Patent Sep. 7, 2021 Sheet 3 of 10 US 11,113,676 B2
PRIOR ART
Merkle Root
Hash [o] Hash(1)
Hash (o::0) Hash (0:1) Hash(1:0) Hash 1:1)
Transaction1 Transaction Transactionz Transaction 4
Fig. 7
Block 1 Header Block 2 Header Block 3 Header
Hash of Previous Hash of Previous Hash of Previous
Block Header Block Header Block Header
Merkle Root Merkle Root Merkle Root
Block 1 Block 2 Block 3
Transactions Transactions Transactions
Fig. 8 PRIOR ART
U.S. Patent Sep. 7, 2021 Sheet 4 of 10 US 11,113,676 B2
16
Nonce * Nonce
Message IRO
Mid - state1 Shared Core : Nonce
Mid - statez Rolled or
:
Pipelined Id
Mid -state , Fig . 9
Ethernet
24
IRO 16
MPU
18 Channel Channel
20
Mid - state Precomputed
12 Message Schedule
Semi - hasher
Full - hasher Message Schedule Shift Register
14
Slot 0
: :
Slot 63
Intermediate
Comparison 22 12a
Logic
1 26
Last 32 - bits
Comparison
Logic Fig. 10
U.S. Patent Sep. 7, 2021 Sheet 5 of 10 US 11,113,676 B2
Precompute Mid - states
Create B1
For each Nonce
Store Nonce in B1
Precompute Message
Schedule of B1
For each Mid - state
Extend Mid - state with Hash Function
Using Precomputed Schedule
Evaluate second SHA - 256 Hash on
Extended Mid - state
Compare second SHA - 256 Hash Digest
with Target, if < Generate IRQ
Next Mid - state
Next Nonce
Fig . 11
U.S. Patent Sep. 7, 2021 Sheet 6 of 10 US 11,113,676 B2
Mid -state 1 Message Mid-statez
8 16 8
14a 14b
Compressori Expander Compressor2
12
+ +
Out- state1 10 Fig. 12 Out- state ,
Message Mid -state Mid-state ,
16 8 8
Expander Compressor 1 Compressorn
12 14a 14b
+
10 Out- state1 Out-state ,
Fig. 13
U.S. Patent Sep. 7, 2021 Sheet 7 of 10 US 11,113,676 B2
Mid - state
Generator Mid -staten Mid-state1
..
28
Wo Wo
W1 W1
Delay FIFO Compressor 1 W2 Compressor
W 2
W.63 W.63
30 14a 34a 14b 34b
Mid-staten Mid - state1
+ +
16
Fig . 14 Out-state1 Out- staten
Message Nonce Message Nonce
3 1
W [0 :: 63 ] .
Wo W [ 0 :: 63 ] 1
W.
Rolled Logic W [O :: 63 ] 2
Message W2 [ 0 :: n ]
Expander
W [0 :: 63163
WW63)
32a
32b
Fig. 15a Fig. 15b
U.S. Patent Sep. 7, 2021 Sheet 8 of 10 US 11,113,676 B2
Merkle Root
Hashio] Hash(1)
Transaction Transaction Transaction 4 Transactionz
Fig. 16a
Merkle Root
Hash (0) Hash ( 1)
Generation Transaction1 Transaction2 Transactionz
Hash Index # VI Data Seg #
32 4 1-9 Target:: extraNonce 4.
Fig. 16b
U.S. Patent Sep. 7, 2021 Sheet 9 of 10 US 11,113,676 B2
Input : Q = set of 2 ^ n Transactions
Divide Q into Q1 and Q2 ,
each of size 2 ^ ( n - 1 )
For each Q1
For each Q2
For all x1 in L1
For all x2 in L2
Lx = L::SHA ? ( x1 || x2 )
Next x2
Next x1
Next Q2
Next Q1
Output : L = list of k roots
Fig . 17
U.S. Patent Sep. 7, 2021 Sheet 10 of 10 US 11,113,676 B2
10 ' 12 '
Constants + Expander
ROM
14'a
4
14'b
Compressor 1 Messagen
Compressor 2 Messagen-1
Fig. 18
Mid - state Constants
Generator ROM
14'a
Mid -staten+1 Compressor1 Register +
Message
File Expander
12'a
14'b
Mid -state, Compressor Register +
Message
File Expander
12'b
Fig . 19
10 '
US 11,113,676 B2
1 2
BLOCK MINING METHODS AND behaves practically as a random oracle, no better approach
APPARATUS to finding a valid nonce has yet been discovered than simple
trial - and - error. The mining process is therefore a stochastic
CROSS REFERENCE TO RELATED process. In practice , the chances of a particular miner
APPLICATIONS 5 successfully solving a block are, at any particular point in
time , proportional to the miner's hash rate relative to the
This application is a Continuation of International Appli hash rate of the whole network .
cation No. PCT /US14 /66470 , filed 19 Nov. 2014 ( “ Parent As is known, the U.S. National Security Agency (“ NSA ” )
Application ”) . This application is related to Provisional has designed and published a set of cryptographic hash
Application Ser.No. 61/ 906,310, filed 19 Nov.2013 ( “ Par- 10 functions referred to as Secure Hash Algorithms(“ SHA ” ). In
ent Provisional ” ) , the subject matter of which , in its entirety, particular, the Bitcoin protocol applies the SHA - 256 ,
is expressly incorporated herein by reference, and hereby described in the following pseudocode:
claims benefit of the filing date thereof uant to 37 CFR
$ 1.78 ( a ) ( 4 ) . 15 **********
BACKGROUND OF THE INVENTION Note 1 : All variables are 32 bit unsigned integers and addition is
calculated modulo 232
Note 2 : For each round, there is one round constant k [ i ] and one entry
Field of the Invention in the message schedule array w [i], 0 sis 63
The present invention relates to both methods and appa Note Note 3 : The compression function uses & working variables, a through h
ratus for use in mining a block , e.g. , in a block chain , and, 20 this 4 : Big - endian convention is used when expressing the constants in
pseudocode , and when parsing message block data from bytes to
in particular, to methods and apparatus for use in a crypto words, for example, the first word of the input message “ abc" after
currency system , such as the Bitcoin mining system . padding is 0x61626380
Description of the Related Art Initialize hash values : ( first 32 bits of the fractional parts of the
square roots of the first 8 primes 2..19 )
In general, in the descriptions that follow , we will italicize ho : = Ox6a09e667 ;
the first occurrence of each special term of art that should be 25 hl : = Oxbb67ae85 ;
familiar to those of ordinary skill in this art. In addition, h2 : = 0x3c6ef372;
when we first introduce a term that we believe to be new or h3 : = Oxa54ff53a ;
h4 0x510e527f;
=
that we will use in a context that we believe to be new , we h5 : = 0x9605688c ;
will bold the term and provide the definition that we intend h6 : = 0x1f83d9ab ;
to apply to that term . In addition , throughout this descrip- 30 Initialize
h7 : = Ox5be0cd19 ;
array of round constants : ( first 32 bits of the fractional
tion, we will sometimes use the terms assert and negate
when referring to the rendering of a signal, signal flag, status k [ O..63parts] : =of the cube roots of the first 64 primes 2..311 )
bit , or similar apparatus into its logically true or logically 0x428a2f98, 0x71374491 , Oxb5c0fbcf, Oxe9b5dba5 , 0x3956c25b ,
false state , respectively, and the term toggle to indicate the 0x59f111f1 , 0x923f82a4, Oxab1c5ed5 , Oxd807aa98 , 0x12835601 ,
logical inversion of a signal from one logical state to the 35 Ox243185be , 0x550c7dc3 , 0x72be5d74 , 0x80deblfe , Ox9bdc06a7 ,
Oxc19bf174 , Oxe49b69c1 , Oxefbe4786 , 0x0fc19dc6 , 0x240calcc ,
other. Alternatively , we may refer to the mutually exclusive 0x2de92c6f, 0x4a7484aa , Ox5cb0a9dc , 0x76f988da, 0x983e5152 ,
boolean states as logic_0 and logic_1 . Of course , as is well Oxa831c66d , Oxb00327c8 , Oxbf597fc7, Oxc6e00bf3 , Oxd5a79147 ,
known, consistent system operation can be obtained by OxO6ca6351 , 0x14292967 , 0x27b70a85 , 0x2e1b2138 , 0x4d2c6dfc ,
reversing the logic sense of all such signals, such that signals 0x53380d13 , 0x650a7354 , 0x766a0abb , 0x81c2c92e , 0x92722c85 ,
Oxa2bfe8al, Oxa81a664b , Oxc24b8b70 , Oxc76c51a3 , Oxd192e819 ,
described herein as logically true become logically false and 40 Oxd6990624 , Oxf40e3585 , 0x106aa070 , 0x19a4c116 , Oxle376c08 ,
vice versa . Furthermore, it is of no relevance in such systems 0x2748774c , 0x34b0bcb5 , 0x391c0cb3 , 0x4ed8aa4a , 0x5b9cca4f,
which specific voltage levels are selected to represent each 0x682e6ff3 , 0x748f82ee, 0x78a5636f, 0x84c87814 , 0x8cc70208 ,
0x90befffa , Oxa4506ceb , Oxbef9a3f7 , Oxc67178f2 ;
of the logic states . For convenience of reference , we will use Pre -processing
the term “ set ” to mean a collection of zero , one or more than append the bit : ' 1 ' to the message ;
one items , as the context may require. 45 append k bits ' 0 ' ;
In general, a decentralized network can store and refer- where k is the minimum number >= 0) such that the resulting message
ence common information in a block chain . In a typical append length length (modulo 512 in bits ) is 448
of message ;
block chain , each block contains units of information com (without the ' 1 ' bit or padding) , in bits , as 64- bit big - endian
monly called transactions that arise roughly at the same integer ( this will make the entire post-processed length a
time . Using a predefined protocol, blocks are linked by 50 multiple of 512 bits )
having their hash values inserted into a designated field in Process the message in successive 512 - bit chunks:
the next sequential block in the block chain . break message into 512 - bit chunks;
for each chunk :
The process of block chain mining is designed to allow {
the system to come to a consensus in which all nodes in the create a 64 -entry message schedule array w [ 0..63 ] of 32 - bit words ;
computer network agree to the same block chain . Several 55 ( The initial values in w [ 0..63 ] don't matter, so many
block chain systems have been proposed, and some are implementations zero them here )
copy chunk into first 16 words w [0..15 ] of the message schedule
presently in operation . One of the earliest and , currently, the array:
most widely recognized is the Bitcoin system . According to Expand the first 16 words into the remaining 48 words w [ 16..63 ] of
the Bitcoin protocol, the first miner to successfully compute the message schedule array :
for i from 16 to 63 :
a valid proof-of-work for a block candidate is entitled to add 60 SO : = ( w [ i- 15 ] rightrotate 7 ) xor ( w [ i -15 ] rightrotate 18 ) xor
the block to the block chain ( sometimes referred to as the ( w [i- 15] rightshift 3 ) ;
ledger ), and to generate new units of the crypto currency as sl : = ( w [ i- 2 ] rightrotate 17 ) xor ( w [ i - 2 ] rightrotate 19 ) xor
a reward . ( w [ i- 2 ] rightshift 10 ) ;
The proof -of -work for a block consists of a nonce value w [ i ] : = w [ i - 16 ] + S0 + w [ i - 7 ] + sl ;
Initialize working variables to current hash value :
that, when inserted into a designated field in the block , 65 a := h0 ;
makes the cryptographic hash value of the block meet a b := h1;
certain difficulty target. Since a cryptographic hash function
US 11,113,676 B2
3 4
-continued blocks solved , which is in turn proportional to the hash rate
relative to the hash rate of the entire network . As competi
C : = h2 ;
d = - h3 ;
tion has increased , miners are aggressively seeking even
e := h4 ; small improvements in hash rate . One known approach to
f : = h5 ; 5 improve hash rate is to scatter the hash search across the
g := h6; greatest number of hash engines, each adapted to indepen
h := h7 ;
Compression function main loop :
dently search a respective portion of the entire nonce - space
for i from 0 to 63 : for hashes that satisfy ( i.e. , are below ) the required difficulty
{ target.
S1 := ( e rightrotate 6 ) xor ( e rightrotate 11 ) xor ( e rightrotate 10 Often , when a hash is computed within Bitcoin , the
25 ) ;
ch : = ( e and f ) xor ( (not e ) and g ) ;
message being hashed is of a fixed length. This is the case
templ : = h + S1 + ch + k [ i ] + w [ i ] ; for example for block headers ( 80 bytes ) and whenever a
SO : = (a rightrotate 2 ) xor ( a rightrotate 13 ) xor ( a rightrotate hash value ( 32 bytes ) is itself being hashed . Hash values are
22 ) ; being hashed in all applications of double - SHA . In the
maj : = (a and b ) xor ( a and c ) xor (b and c ) ;
temp2 : = SO + maj;
15 formation of a Merkle tree hash value pairs ( 64 bytes )
h := g; arranged in a tree data structure are being hashed . In general,
f; hash engines adapted to hash fixed length messages may be
f : = e; optimized differently than are hash engines adapted to hash
e : = d + templ; arbitrary length messages .
d := C ;
C := b;
20 When implementing a hash engine in an application
b = a; specific integrated circuit (" ASIC " ), the key design goals are
a : = templ + temp2 ; to improve power, performance and area . When many
}
Add the compressed chunk to the current hash value :
messages of the same short length have to be hashed , a
h0 : = h0 + a ; pipelined implementation of a hash core is possible . By way
h1 : = h1 + b ; 25 of example, FIG . 1 shows one block of such a PRIOR ART
h2 := h2 + c ; pipeline . In a typical ASIC , several such pipeline blocks are
h3 : = h3 + d ;
h4 := h4 + e;
instantiated and adapted to operate, either in parallel or
h5 : = h5 + f; serially, under the control of a central control unit, which
h6 := h6 + g ; may be a conventional microprocessor unit ( “MPU ” ) or a
h7 : = h7 + h ; 30 special controller ( not shown) instantiated on the same
} ASIC .
Produce the final hash value (big -endian ): In block chain mining , many messages (blocks ) are being
digest : = hash : = h0 append h1 append h2 append h3 append h4 append
h5 hashed that differ only in the last chunk (i.e , the portion
append h6 append h7
***********
containing the nonce) . For that specific type of application ,
35 the mid - state of the compressor (i.e. , the hardware compo
nent that performs the compression function ) can be pre
Hereinafter, for convenience of reference, we may refer to computed as far as it does not depend on the nonce . Then ,
aspects of our invention using the terminology set forth for the last application of the compressor that does depend
on the nonce , the pipelined core 10 as in FIG . 1 may be
above in the pseudocode. Also , by way of example, we will 40 employed . In FIG . 1 , we have used conventional notation to
focus our disclosure on the Bitcoin protocol, although we indicate bus widths, with units expressed as 32 -bit double
recognize that other crypto currency systems may benefit words ( “ dwords ” ) . Sometimes , depending on the context,
from our invention .
Many hash functions, including the SHA - 1 , SHA - 2 and the compressor 14 may be referred to as a semi-hasher and
RIPEMD families, share a similar scheme with SHA - 256 . 45 as acombination the
full -hasher .
of the expander 12 and the compressor 14
For the purposes of our invention , we
Each applies an expansion function ( sometimes referred to submit that the core
as an expansion operation ) adapted to expand an input pipelined or rolled form10. can be instantiated in either a
message into a message schedule , and then applies a com We have illustrated in FIG . 2 the basic hardware archi
pression function ( sometimes referred to as a compression tecture of a PRIOR ART rolled core 10 ' . Typically, in such
operation ) adapted to compress the message schedule into a 50 an architecture, approximately 67 cycles are required to
hash value or result ( sometimes referred to as the message compute one SHA - 256 round , comprising 64 computation
digest or simply digest ) . Typically, the compression function cycles plus a few additional cycles to load the registers with
is recursive, compressing one word of the message schedule initial values . Often , the read -only -memory ( “ROM ” ) of
per round . The recursive nature of these functions lends constants is shared among several cores 10 ' . In general, a
itself to known loop unrolling techniques and, when applied 55 PRIOR ART special purpose rolled core 10 ' may be con
to hardware implementations, results in a classic pipelined ceptualized as illustrated in FIG . 3 wherein the hash com
configuration of computational elements . putational hardware is depicted as a cloud of combinational
Usually, when a hash is computed within Bitcoin , it is logic . A more highly structured , PRIOR ART SHA pipe
computed twice, i.e. , a SHA - 256 hash of a SHA - 256 hash lined core 10 is illustrated by way of example in FIG . 4. In
( sometimes referred to as a double -SHA, or simply SHA2 ) . 60 FIG . 5 , we have illustrated a high -level representation of a
Most of the time only SHA - 256 hashes are used , for typical Bitcoin SHA? engine 16 .
example when hashing transactions and block headers . Shown in FIG . 6 is the format of a Bitcoin Block Header
However, RIPEMD - 160 is also used for the second hash wherein the indicated field sizes are expressed in 8 -bit bytes.
when a shorter hash digest is desirable, e.g. , when hashing As can be seen , at offset 36 , the 32 -byte Merkle Root field
a public key to obtain a Bitcoin address . 65 spans the boundary between Block [ 0] ( sometimes referred
Block chain mining is , by design , competitive in nature. to simply as “ Bo ” ) and Block [ 1 ] (“ B ” ) of the block header.
The monetary reward is proportional to the number of By way of example, we have illustrated in FIG . 7 a 3 - level
US 11,113,676 B2
5 6
Merkle tree having a leaf set comprising 4 transactions, FIG . 3 illustrates, in block diagram form , another PRIOR
although it will be recognized that a typical Merkle tree may ART special purpose SHA rolled core ;
have additional hierarchical hash levels depending on the FIG . 4 illustrates, in block diagram form , a PRIOR ART
number of transactions being hashed . In FIG . 8 we have Bitcoin SHA? hash engine having a pipelined core ;
shown , for convenience of reference, a typical 3 -block 5 FIG . 5 illustrates, in block diagram form , a PRIOR ART
sequence within a Bitcoin block chain , wherein each block Bitcoin SHA? hash engine having either a rolled core or a
comprises a block header ( see , FIG . 6 ) and a respective set pipelined core ;
of transactions ( in clear text to facilitate block browsing ). In FIG . 6 illustrates , in tabular form , the format of a Bitcoin
situations where the number of available transactions is less Block Header ;
than a power -of -two, padding , e.g. , duplicate or dummy 10 FIG . 7 , illustrates , in block diagram form , a multi - tier
transactions, is added at the leaf level to complete the Merkle tree as employed in the Bitcoin protocol;
power -of -two tree structure. In accordance with the Bitcoin FIG . 8 illustrates, in block diagram form , the general
protocol, the first transaction of every block is always a format for Bitcoin blocks comprising a block chain ;
generation ( or coinbase) transaction generated by the miner FIG . 9 illustrates, in block diagram form , a Bitcoin SHA?
who added the block to the chain . 15 hash engine constructed in accordance with our invention as
As we explained in our Provisional Application , it has disclosed in our Provisional Application ;
been proposed to partition the 4 -byte Version field in the FIG . 10 illustrates, in block diagram form , one possible
block header ( see , FIG . 6 ) and use , e.g. , the high 2 -byte hardware implementation in accordance with our invention
portion as additional nonce range . Alternatively , the Bitcoin as disclosed in our Provisional Application ;
specification defines an extraNonce field in the format for 20 FIG . 11 illustrates, in logic flow diagram form , one
the coinbase or generation transaction ( see , FIG . 166 ) . possible method for operating the embodiment of FIG . 10 ,
However, the Bitcoin specification recognizes that incre- as also disclosed in our Provisional Application ;
menting the extraNonce field entails recomputing the FIG . 12 illus in block diagram form , one possible
Merkle tree , as the coinbase transaction is the left most leaf parallel, message schedule sharing embodiment in accor
node. In this approach, each time the extraNonce is incre- 25 dance with our invention as disclosed in our Provisional
mented, a full Merkle root is generated, thus requiring the Application ;
full block header to be reprocessed. FIG . 13 illustrates, in block diagram form , one possible
One problem that we perceive with current hardware cascaded , message schedule sharing embodiment in accor
platform designs is the requirement that each hash core be dance with our invention ;
adapted to perform the full SHA - 256 independently of all of 30 FIG . 14 illustrates, in block diagram form , one alternate
the other hash cores in the hardware instantiation . What is parallel, pipelined message schedule pre -computation
needed is a method and apparatus that allows a single embodiment in accordance with our invention;
expander instant to be shared by a plurality of compressor FIG . 15 , comprising FIG . 15a and FIG . 15b , illustrates, in
instants. block diagram form , possible message schedule pre -com
35 putation engines adapted for use , for example, in FIG . 14 ;
BRIEF SUMMARY OF THE INVENTION FIG . 16 , comprising FIG . 16a and FIG . 16b , illustrates, in
block diagram form , several possible forms for the multi - tier
In one embodiment of our invention , we provide a method Merkle tree of FIG . 7 ;
for mining a block comprising a block header, as a function FIG . 17 illustrates, in flow diagram form , one possible
of a selected hash function applied on the block header, the 40 method for generating a plurality of Merkle roots in accor
selected hash function comprising an expansion operation dance with our invention ;
and a compression operation. In accordance with our FIG . 18 illustrates , in block diagram form , one possible
method , we first develop a plurality, m , of mid -states, each cascaded , message schedule sharing embodiment, having
as a function of selectively varying a selected first portion of rolled cores , in accordance with our invention; and
the block header. We then perform the expansion operation 45 FIG . 19 illustrates, in block diagram form , a message
on a selected second portion of the block header to produce schedule pre - computation embodiment, having rolled cores ,
a message schedule . Finally, for each of the m mid - states, we in accordance with our invention .
perform the compression operation on the mid - state and the In the drawings, similar elements will be similarly num
message schedule, to produce a respective one of m results . bered whenever possible . However, this practice is simply
In one other embodiment, we provide apparatus config- 50 for convenience of reference and to avoid unnecessary
ured to perform our block mining method . proliferation of numbers, and is not intended to imply or
In yet another embodiment, our method for block mining suggest that our invention requires identity in either function
can be embodied in a computer readable medium including or structure in the several embodiments .
executable instructions which , when executed in a process
ing system , causes the processing system to perform the 55 DETAILED DESCRIPTION OF THE
steps of our method . INVENTION
BRIEF DESCRIPTION OF THE SEVERAL FIG.9 illustrates, in high - level form , a Bitcoin SHA? hash
VIEWS OF THE DRAWINGS engine 16 constructed in accordance with our invention as
60 disclosed in our Provisional Application. In FIG . 10 , we
Our invention may be more fully understood by a descrip present a basic implementation of our invention as we
tion of certain preferred embodiments in conjunction with disclosed in our Provisional Patent. The preferred embodi
the attached drawings in which : ment is instantiated in the form of an ASIC that instantiates
FIG . 1 illustrates, in block diagram form , a PRIOR ART a hash engine 16 ' containing a selected plurality, e.g. , 200 ,
special purpose SHA pipeline ; 65 SHA - 256 semi -hashers 12 , and a corresponding plurality of
FIG . 2 illustrates, in block diagram form , a PRIOR ART full SHA - 256 hashers 14. Each semi- hasher 12 is pipelined
special purpose SHA rolled core ; with a respective full - hasher 14. Each hasher pipeline , which
US 11,113,676 B2
9
7 8
combines one semi-hasher 12 with one full - hasher 14 , field and recomputing the parent node hashes up the tree to
outputs one SHA’ result per clock tick . Each semi- hasher 12 the root node. One other way is by rearranging the sub - trees
has a 32 - byte mid -state register 18 which contains a pre- of the Merkle tree by swapping child nodes ( e.g. , left with
computed mid -state, and a 64 * 4 byte pre - computed message 5 right ), and recomputing parent nodes until the root node ; this
schedule register 20 which contains a pre -computed mes- approach could include permuting the transaction leafs.
sage schedule ; and all SHA rounds are unrolled and imple- Each time a new candidate root is computed, it's checked
mented in hardware . As is conventional, each full -hasher 14 against the desired pattern , and , if it does not match , the
contains the message schedule creation logic to derive the candidate root is discarded , otherwise it is stored . As we
message schedule from the input block on each clock tick ; 10 noted in our Provisional Application, this technique requires
and, also , rounds are unrolled . A message schedule shift the miner to perform approximately s * 2 * 32 * 1 log 2 ( Q )
register 12a is adapted to perform similar to an expander SHA? hash digests to obtain s elements of equal ending,
pipeline to develop the message schedule of an input block when there are Q transactions to include in the Merkle - tree .
sequentially in a 64 -deep push -down stack of 16 dwords As explained in our Provisional Application, we propose
sliding windows ( sometimes referred to as slots ) , where 15 to achieve greater performance by combining two sets of
each new dword of the message enters at the top and the pre - generated Merkle sub -trees ( although a dynamically
oldest dword is removed at the bottom . In operation, each generated Merkle sub -tree can be combined , we have found
sliding window is pushed down to the next -deeper slot to this to be generally worse ) . Our preparation stage is per
follow the hash round corresponding with the slot . At round formed in three steps :
61 of the full-hasher 14 , we provide a special intermediate
comparison logic module 22 that checks for a solution to the 20 1. node
In the first step of our preparation stage , we develop K?
hashes by selectively rearranging the set of trans
block before all 64 rounds are performed . If the solution is actions in the Merkle - tree , or, perhaps, by choosing
found, an interrupt (“ IRQ ” ) is raised ; optionally, all full different sets of transactions from the pool of all pending
hashers 14 may be allowed to continue searching for addi
tional solutions, or may be stopped to conserve power. An 25 ( K , + 1 ) * log .2This
transactions
( #Q .
can be accomplished in approximately
) SHA ’ operations, where Q , is a set of
external microprocessor ( “MPU ” ) 24 handles the exception , transaction hashes and #Q . the number of transactions
reads the full - hasher 14 outputs , and finds the one that hashes in the set ( i.e. , leaf nodes ), since once a tree for Q1
solved the block . Further, we provide a last - 32 -bits checker transactions has been built , then a new root can be
26 to facilitate reuse of the hasher pipeline for the pre obtained by swapping child nodes, and computing each
computation . 30 parent node requires on average log 2 ( Q1 ) SHA? hash
In accordance with one embodiment of our invention , we digests . Only the parent node hashes need to be saved , and
propose directly to selectively vary the 28 -byte portion of the actual trees can be later removed from memory .
the Merkle root that lies in Block [ 0 ] ( see , FIG . 6 ) . Our
2. In the second step of our preparation stage , we develop a
method requires that the miner first perform a preparation
stage where many different valid Merkle roots are con 35 set sub
of K2 parent node hash digests of a set of node
- trees, where the set of transactions is Q2 and the
structed . However, in contrast with the usual approach , our number of transactions (leaf nodes ) is # Q2 =# Q . ( as noted
goal is to find a number of candidate Merkle roots that end above , this is always possible since Bitcoin Merkle roots
with the same 4 - byte pattern. For example, one way is to use duplicate transaction hashes to fill empty nodes of the
select a predetermined , fixed pattern (e.g. , 4 zero bytes ) . tree ). Note that the sets Qi and Q2 do not intersect, and
Another way is to store the Merkle root candidates for each 40 any ordering of transactions created by the concatenation
pattern until enough candidate roots ending with a desired of an ordering of Q? with any ordering of Q2 must be a
pattern are found . valid ordering of transactions. Note , also , that almost all
The functional flow of operation of our hash engine 16 ' , possible orders of the Q? transactions are generally valid
as we described in our Provisional Application, is illustrated since most miners do not generate blocks which have
in FIG . 11. In pseudocode form (with indentation indicating 45 transactions that depend on other transactions in the block
a for - loop structure ), here is how it works: ( the only exception is that the generation transaction is
always the first ).
?********** For Q? , there are ( #Q. - 1 ) ! number of possible candidate
1. Pre - compute s mid - states MS .... , MS5–1 by applying the first chunk roots of the left sub - trees ( there are 3628800 possible
processing of SHA to a block header modified by setting the Merkle- 50 orderings )
roots field to each of the s Merkle - roots MRO..Mrs - 1. For Q2 , for simplicity , we can assume that there are no
2. Create B1 with the first 32 bits of B1 set to the fixed pattern that repeated transaction hashes ( i.e. , # Q1 + # Q2 is a power of
all MR_i have in common in their respective last 4 bytes . Set the other
fields of B1 ( “ bits ” and “ time ” ) to the appropriate values . two ). It follows therefore that there are ( #Q2 ) ! number of
3. For each nonce v, possible candidate roots of the right sub - trees. If we take
3.1 . Store the nonce in B , and pre - compute the message schedule W
for B1
55 # Q1 =# Qz = 11 , then there are at least 2 46 possible candidate
3.1 . For each i from 0 to s - 1 : roots that can be computed easily by combining an element
3.1.1 . Complete the mid - state MS ; to a full SHA execution using from the left set with an element from the right set . Note that
the pre - computed message schedule W , to obtain the intermediate K and K, need not to be that large, and can represent a small
digest Tiv subset of the possible orderings, and use higher values of
3.1.2 . Apply the second SHA operation to Ti, to obtain the double 60 #Q . and # Q2 :
SHA digest Diy
3. In the third step of our preparation state ( which is
3.1.3 . Compare Diy with target (if last round optimization is in
generally performed , e.g. , by our hash engine 16 ' ) , the
use , the comparison is done within the second SHA execution
engine ) .
*********** hashes of one parent of the first set are iteratively com
bined with a parent of the second set (one left node with
65 a right node ), and then SHA? hashed to obtain the root
To quickly enumerate many valid candidate roots , one node hash . Each combination requires only obtaining 2
way to construct them is by incrementing the extraNonce hashes from tables and performing the SHA’ operations.
US 11,113,676 B2
9
9 10
Shown in FIG . 12 is a core 10 , adapted for use in the root hashes as possible , and then to identify and store those
system of FIG . 9 , comprising one expander 12 adapted to that match in the last dword . In pseudocode form , one
share the same message schedule with a pair of synchro- approach we refer to as divide -and - conquer ( “ D & C ” ) works
nously operating compressors 14a and 14b . As explained like this :
above , each of the compressors 14 starts with a unique 5
mid - state generated using , e.g. , our candidate root genera
tion process. As the hash process progresses synchronously ?**********
D&C Algorithm :
downward through the compressors 14 , the message sched Input: Q set of 2 n transactions ( i.e. , the leaves of the tree ).
=
ule words flow in parallel downward through the expander Output: L list of k root node hash values .
12. Upon completion, each compressor 14 delivers a respec- 10 1. Divide the set of leaves into two sets Q1 , Q2 of size 2 ^ (n - 1 );
tive , unique Out State . As in our basic architecture , the 2. Produce a list Ll of hash digests where each element is the root
mid - states remain constant over a full nonce range , whereas node of a Merkle tree built from Q1 by permuting nodes of the tree
the nonce inside the message schedule words increments at 3. Produce a list L2 of hash digests where each element is the root
node of a Merkle tree built from Q2 by permuting nodes of the tree
the full pipeline clock rate . In distinct contrast to a conven 3.1 . For all x1 in Ll :
tional architecture, our hash engine 16 ' requires only a 15 3.1.1 . For all x2 in L2 :
single, shared expander 12 , thereby significantly reducing 3.1.1.1 . Compute x = SHA2 ( x1 || x2 ) and append to L ;
not just total system hardware but power consumption. 4.**********
Return the list L comprising # L1 * #L2 roots .
Shown in FIG . 13 is a generic, cascaded core 10 , adapted
for use in the system of FIG . 9 , comprising one expander 12
adapted to share the same message schedule with a plurality 20 Notes :
of synchronously operating compressors 14a - 14b . In this 1 ) This flow is illustrated in FIG . 17. In the inner loop step
core 10 , the several compressors 14 are connected in cas- 2.1.1 , we denote the append operation using a “ : :"
cade , with each nessage schedule element being passed symbol.
sequentially from compressor to compressor, one delay 2 ) Our basic transaction swapping mechanism is illustrated
interval ( suitable for the specific hardware implementation ) 25 by way of example in FIG . 16a , wherein Transactionz in
per compressor. Each compressor 14 starts with a unique the right sub - tree, Q2 , has been swapped with Transac
mid - state and , upon completion , delivers a respective unique tion , in the right sub - tree, Q2 .
Out State ; however, the Out States corresponding to the 3 ) In FIG . 16b , we have emphasized that the Generation
same message are delivered sequentially over time one delay transaction must always be the left -most transaction .
interval apart. Note that this arrangement comprises a care- 30 Thus, in step 1 of our D & C Algorithm , the Generation
fully coordinated 2 - dimensional pipeline with work flowing transaction is constrained to remain in Q1 .
from top - down and left- right. In operation, every cycle , all 4 ) Since kl , k2 can be relatively small (requiring on the
of the compressors 14 produce a respective Out State , but for order of about 1 M list elements ), we prefer to implement
different messages . all but the outer recursion of our D & C Algorithm , i.e. ,
In FIG . 14 we have illustrated a generic, cascaded form of 35 step 2 , in the form of a software module residing in the
our message schedule pre - computation method, wherein the MPU 24. Once developed, L1 and L2 may be forwarded
hash engine 16 comprises a mid - state generator 28 adapted to a pipeline of hash cores 10 to produce the root hashes
dynamically to generate unique mid - states for each of the and then search the list L for roots that satisfy our criteria
plurality of compressors 14 , and a 64 - stage delay FIFO 30 ( on the order of about 1 T list elements ).
adapted to delay delivery of the respective mid- states to the 40 One alternate approach for quickly developing a set of
final stage of the corresponding compressors 14. The mid- candidate root hashes is to increment the extraNonce field
state generator 28 must develop a new mid - state every that is available for use in every Generation transaction ( see ,
compressor pipe clock , with each mid - state being passed FIG . 16b ) . Since the extraNonce field is variable length from
down the compressor chain at that same pipe clock rate. In 2 to 100 bytes , a very large pool of candidate root hashes can
this embodiment of our message schedule pre - computation 45 be easily and rapidly generated simply by using the extra
hash engine 16 , the message schedule words, W -W63 , are Nonce field . Although it has heretofore been proposed to use
dynamically developed by a suitable message schedule the extraNonce field to increase the effective nonce range for
pre -computation engine 32 , examples of which we have mining operations, we are not aware of any proposal that the
shown in FIG . 15. In hash engine 16 , both the message resulting set of root hashes be filtered using a predetermined
schedule words and the nonce are constant for a relatively 50 filter function specially adapted to identify those in which
long time . In the embodiment shown in FIG . 15a , the output the last 4 bytes match a given criteria, e.g. , all zeros or any
words are stored in a set of 64 message schedule registers 34 other given value as we have disclosed in our Provisional
associated with each compressor 14. Although we have Application. The essential benefit of our approach is that
illustrated in FIG . 15a a single , shared rolled message only B , is affected , allowing the message schedule of B , to
expander 32a , each compressor 14 has a local rolled mes- 55 be pre -computed . The end goal , remember, is to facilitate
sage expander 32a ( not shown ). In the alternate embodiment our two primary mechanisms: message schedule sharing and
shown in FIG . 15b , each compressor 14 has a cloud of message schedule pre - computation.
combinational logic 32b associated therewith adapted to In FIG . 18 , we have illustrated how we can adapt the
dynamically generate the message schedule words ; there is , rolled core architecture in accordance with our invention to
therefore, no need for the registers 34 in this embodiment. 60 employ our message schedule sharing methodology. In the
Since the message schedule registers 34 update relatively illustrated core 10 ' , the message schedules developed by a
infrequently, there should be sufficient time for the deep single message expander 12 are applied , in parallel, to a
logic 32b to resolve. plurality of synchronously operating compressors 14. As in
In FIG . 16a , we have illustrated , for convenience of the embodiment of FIG . 12 , each of the compressors 14 are
reference, the structure of a simple, 3 - level binary Merkle 65 initialized with different mid - states ; this is effective since
tree having 4 leaf nodes, i.e. , Transactions: : 4] : In accordance new mid - states are required relatively infrequently, gener
with our invention , we seek to produce as many candidate ally after the nonce range has been exhausted .
US 11,113,676 B2
9
11 12
In FIG . 19 , we have illustrated how we can adapt the delaying delivery of the plurality of m mid - states to a final
rolled core architecture in accordance with our invention to stage of the plurality of compressor entities using a
employ our message schedule pre - computation methodol FIFO having a number of stages , the number of stages
ogy. In the illustrated core 10 ' , the pre -computed messages corresponding to the plurality of message schedule
are developed by a single message expander 12 , and applied, 5 elements of the message schedule ;
in parallel, to a plurality of cascaded compressors 14. As in for each of the m mid - states , performing, by one of a
the embodiment of FIG . 14 , the generated mid - states are plurality of compressors of the processing system , the
cascaded down through a respective set of mid - state regis compression operation on a combination of one of the
ters , via a bus operating at a frequency of approximately m mid - states and the message schedule, the plurality of
core frequency /67. In this embodiment, since the message 10 compressors being communicatively coupled to the
schedule updates relatively infrequently, we can add the single shared expander and receiving the message
constants and store the pre - computed sums in the register schedule from the single shared expander, the compres
file .
Although we have described our invention in the context sion for each of the m mid - states producing a respective
of particular embodiments, one of ordinary skill in this art 15 identifying one of m results ;
will readily realize that many modifications may be made in , by the processing system , a block solution
such embodiments to adapt either to specific implementa- from the m results by comparing each of the m results
tions . In the future , if other parts of the Bitcoin block header to a target; and
are made available as expanded nonce space , such as the first providing , by the processing system , the block solution to
32 -bits of the previous block hash , then our methods and 20 the ledger stored on the server.
apparatus can also make use of this extra nonce space for 2. The method of claim 1 wherein the first portion of the
creating the set of mid -states required by our invention . one of the plurality of plurality of candidate roots comprises
Thus it is apparent that we have provided an improved an extraNonce field that includes a selected 4 bytes of the
method and apparatus for mining block chains . In particular, block header.
we submit our new methods and apparatus allow a single 25 3. The method of claim 1 wherein the first portion of the
expander instant to be shared by a plurality of compressor one of the plurality of plurality of candidate roots comprises
instants. Further, we submit that our method and apparatus a digest of a transaction .
provides performance generally superior to the best prior art 4. The method of claim 3 wherein a generation transaction
techniques. comprises one of the plurality of transactions; and wherein
30 the determining each of the plurality of candidate roots is
What we claim is : performed by varying the generation transaction.
1. A method for mining a block , comprising a block 5. The method of claim 3 wherein the determining each of
header, as a function of a predetermined hash function the plurality of candidate roots is performed by varying a
applied on the block header, the predetermined hash func- selected portion of a selected transaction .
tion comprising an expansion operation and a compression 35 6. The method of claim 3 wherein the determining each of
operation, the method comprising the steps of: the plurality of candidate roots is performed by varying an
retrieving, by a processing system comprising a processor order of the plurality of transactions.
and memory , a plurality of transactions associated with 7. The method of claim 1 wherein each candidate root
the block from a ledger stored on a server of a decen- comprises a root of a tree data structure .
tralized network , the processing system comprising a 40 8. The method of claim 7 wherein the tree data structure
single shared expander and a plurality of compressor comprises a Merkle tree .
entities, each being implemented as hardware compo- 9. The method of claim 7 wherein the determining each of
nents in an application specific integrated circuit ; the plurality of candidate roots is performed by executing
determining, by the processing system , a plurality of the steps of:
candidate roots from the received plurality of transac- 45 selecting a left sub - tree hash from a first plurality of
tions associated with the block, each candidate root candidate sub - tree hashes;
including a predetermined pattern ; selecting a right sub -tree hash from a second plurality of
developing, by a mid - state generator entity of the pro candidate sub - tree hashes; and
cessing system , m mid - states , each mid - state being developing the root of the tree data structure from the left
developed from a first portion of one of the plurality of 50 sub - tree hash and the right sub -tree hash .
candidate roots, the mid - state generator developing a 10. The method of claim 1 wherein the determining each
new mid - state of the m mid - states every compressor of the plurality of candidate roots is performed by executing
entity pipe clock , with each mid - state of the m mid- the steps of:
states being passed down a compressor entity chain at determining the plurality of candidate roots by applying a
the pipe clock rate ; 55 filter function to a set of all possible roots , and :
distributing the determined plurality of m mid - states to a when a root of the set of all possible roots fails the filter
beginning stage of the plurality of compressor entities ; function , discarding the root ; but
performing, by the single shared expander of the process- when the root passes the filter function, adding the root
ing system using an input of a message and a nonce , the to the plurality of possible roots , wherein a mid - state
expansion operation on a second portion of each of the 60 is developed for each candidate root to develop the
plurality of candidate roots to produce a message m mid - states .
schedule, the message schedule comprising a plurality 11. The method of claim 10 :
of message schedule elements , the single shared wherein the first portion of the one of the plurality of
expander being provided by a single shared rolled candidate roots comprises a first 28 bytes of a 32 - byte
message expander entity; 65 Merkle root stored within the block and the second
distributing the message schedule to the plurality of portion of each of the plurality of candidate roots
compressor entities via the single shared expander ; comprises a last 4 bytes of the Merkle root ; and
US 11,113,676 B2
9
13 14
wherein the filter function is further characterized as
selecting a candidate root when the second portion does
not comprise the predetermined pattern , the selected
candidate roots being subsequently discarded .
12. The method of claim 1 wherein the message schedule 5
comprises an ordered sequence of message schedule ele
ments and wherein the performing the compression opera
tion step is performed by, for each of the m mid - states ,
compressing the sequence of message schedule elements to
produce a respective one of m results. 10