BLAKE256 Hash Function
BLAKE256 is the hashing algorithm used in Decred. It is an extremely flexible function for hardware and is very fast in software, both of which are desirable properties for a block hashing algorithm. BLAKE is a versatile and useroriented design that performs well on all platforms, from embedded systems to resourceconstrained hardware and requires low resources for implementation ^{1} ^{2} ^{3}.
It is worth noting that BLAKE is a finalist of The National Institute of Standards and Technology (NIST) SHA3 competition, a public competition for alternatives to SHA1 and SHA2 with better efficiency and resilience to future attacks. During the competition, BLAKE was thoroughly analyzed and attacked to identify vulnerabilities by notable cryptanalysts ^{1}. Below sections contain information regarding BLAKE256 components, security and performance in hardware and software.
Algorithm  Word  Message  Block  Digest  Salt  Rounds 

BLAKE256  32bit  64bit  512bit  256bit  128bit  14 
Table 1: Characteristics of the BLAKE256 hash function
BLAKE Components
BLAKE is built on previously analyzed, and reliable components; the hash iterative framework (HAIFA) of Biham and Dunkelman ^{4}, the local widepipe introduced by the LAKE hash function^{6}, and the core function inspired by ChaCha function of Bernstein ^{5}. The use of well understood building blocks makes BLAKE a hash function that is simple to analyze and implement for cryptanalysts and implementers alike.
HAIFA iteration mode
The construction of a hash output is typically done by splitting the input data referred to as a ‘message’, into small blocks of fixed length and processed iteratively using a cryptographic compression function. The combination of calls to a compression function for processing the input data is an iteration mode (also referred to as a Domain Extender). The Merkle–Damgård (MD) construction is the classic iteration mode used by MD5, SHA1, RIPEMD160, and SHA2 hash functions. MD splits the variable length input message into equalsized message blocks x (i.e., 512 bits) of n blocks, the last block is padded as required and appended with the length of the message.
Figure 1: Merkle–Damgård Construction
As shown in Figure 1 above, the output of the compression function f known as a chaining value CV and the initial inputs are the Initialization Vector IV shown as CV_{0}, with h(x) being the output after all message blocks are processed. MD maintains the collision resistance of the compression function however it lacks the preimage and second preimage resistance. As a result generic attacks such as the multicollision, the long message secondpreimage, herding and length extension are possible on MD based hash functions ^{7} ^{8} ^{9} ^{10} ^{11}.
BLAKE uses HAIFA, which maintains the valuable properties of the MD construction and adds to the security and scalability of the transformation. HAIFA is essentially an MD construction but with a mandatory counter (number of bits hashed so far) and an optional salt (random data that used as an additional input).
Figure 2: HAIFA Construction
This iteration mode solves many of the internal collision problems with the MD construction and provides resistance to herding, long message second preimage, and length extension attacks as the additional salt and counter simulate distinct compression functions for each data block processed ^{4} ^{12}. HAIFA is both prefixfree and suffixfree and, as a result, is collisionresistant as well as indifferentiable from a random oracle, assuming the underlying compression function is ideal ^{1} ^{13} ^{14}.
The local widepipe and ChaCha inspired core function
Figure 3: Local widepipe construction of BLAKE’s compression function, inherited from LAKE hash function ^{6}
BLAKE uses the LAKE local widepipe structure for its strong security guarantees against collision attacks ^{1} ^{6} and a core function G inspired by the stream cipher ChaCha for its simplicity and security ^{1}. The compression function takes as input four values: a chaining value, a message block, an optional salt and a mandatory counter. In the case of BLAKE256:
Chaining Value  Message Block  Salt  Counter 

256bit  512bit  128bit  64bit 
The structure then works in three steps:

Initialization of a large internal state represented by 16 words in a 4x4 word matrix.

14 rounds of the G function with each round consisting of eight rounddependent transformations.

Finalization after a series of rounds, a new sequence of values taken from the matrix using sequence of initial values and salt.
A more detailed description can be found in the SHA3 proposal BLAKE.
Security Evaluation Criteria
The security of a cryptographic hash function is determined by the number of queries or guesses required to solve the following problems:

Preimage resistance (oneway): Given the y as an output of the hash function, it is computationally infeasible to find message x such that h(x) = y. ^{4}
Figure 6: Preimage resistance

Second preimage resistance (weak collision resistant): Given x, it is computationally infeasible to find a second preimage x’ ≠ x such that h(x) = h(x’) ^{4}
Figure 7: Second preimage resistance

Collision resistance (strong collisionresistant): It is computationally infeasible to find any two distinct inputs x, x’ that hash to the same output such that h(x) = h(x’) ^{4}
Figure 8: Collision resistance

Lengthextension resistance: Based on the hash of an unknown message h(x) and the length of the message len(x) it is not possible to choose a message x’ to calculate h(x’) such that h(x’) = h(x).
Figure 9: Length extension attack: Since x and x’ share the same first n blocks, the hash value h(x) is the intermediate hash value after first n blocks when computing h(x’) ^{17}
In the first three properties, the phrase computationally infeasible means it would take the fastest computer a long time to solve the problem, e.g., billions of years, making it impossible in practice. Also, the fourth property, resistance to Lengthextension attacks, is an additional requirement outlined in NIST’s evaluation criteria for its SHA3 candidates hash function ^{15}.
BLAKE was subject to a great deal of depth during cryptanalysis, more so than other candidates likely due to its similarity with ARX (modular addition, rotation, and XOR) based hash functions, which meant that many existing techniques and tools existed for beginning the analysis ^{16}.
“Keccak received a significant amount of cryptanalysis, although not quite the depth of analysis applied to BLAKE.”
“BLAKE and Keccak have very large security margins.”
“Skein and BLAKE have no known distinguishing attacks that come close to threatening their fullround versions.”
NIST in ThirdRound Report of the SHA3 Cryptographic Hash Algorithm Competition^{16}
BLAKE256 Security bounds
Attack  NIST’s Security Requirements  BLAKE256 Proven Generic Security 

Preimage  256bit  256bit 
SecondPreimage  256bit  256bit 
Collision  128bit  128bit 
Lengthextension  Should be resistant  Immune 
Indifferentiablity  Not specified  128bit 
Table 3: Minimum Security Requirements for a Hash Function and proven security of BLAKE256 in Bits ^{15} ^{16}
Analysis of BLAKE’s Domain extender proved that BLAKE256 is secure against preimage, secondpreimage, and collision attack up to 2^{256}, 2^{256}, and 2^{128} queries, respectively and is indifferentiable from a random oracle up to 2^{128} queries. Additionally, the counter in BLAKE protects against length extension attacks, as it assures consecutive compressions are different.
Software Performance
A significant amount of data on the performance of BLAKE and other SHA3 finalists is available on the eBASH site with the best comparative presentation of data being the “shootout” graphs. The shootout graphs include data from AMD64 processor models, X86 processor implementations, ARMNEON and 32bit RISC (Reduced Instruction Set Computers). The throughput is stated in machine cyclesperbyte, where fewer cycles indicate better performance. BLAKE256 is notable for its high performance on x8664 microarchitecture, being faster for short messages than SHA256 ^{18} despite being considered to have a much higher security margin at 14rounds.
“Skein and BLAKE have the best overall software performance.”
“On 32bit machines (mainly ARM processors) without vector units, BLAKE256 is the overall leader, although it has only a small throughput advantage over SHA256”
“On small embedded computers, BLAKE256 has the best overall performance. BLAKE256’s throughput is usually at or near the top, although occasionally slightly less than SHA256, while BLAKE256 generally has smaller memory requirements than SHA2 and most of the other candidates.”
NIST in ThirdRound Report of the SHA3 Cryptographic Hash Algorithm Competition^{16}
In the context of Decred, BLAKE256 has excellent support for parallelism in both multicore and singlecore instructionlevel scenarios (e.g. AVX2). This is important because the vast majority of validation takes place in general purpose hardware while mining takes place in specialized hardware.
Hardware Performance
Data on the performance of hardware implementations of Field Programmable Gate Arrays (FPGA) and Application Specific Integrated Circuits (ASIC), for BLAKE256 and other SHA3 finalists is available on the GMU CERG Database similar to the eBASH site. BLAKE was found to provide the best performance of any algorithm for very compact FPGA imlementations, which should also be true for ASIC implementations ^{16}. Highperformance implementations of BLAKE256 in FPGAs or ASICs provide the same throughput as SHA256 but require around twice the size, so BLAKE256 throughput/area ratio is roughly half that of SHA2. However, BLAKE has a significant advantage in hardware due to its high flexibility for hardware implementations ^{2}.
“Reasonably efficient, folded or serial implementations of all of the algorithms seem achievable, but BLAKE and Grøstl seem the most flexible.”
NIST in ThirdRound Report of the SHA3 Cryptographic Hash Algorithm Competition^{16}
In Decred, only a single round of BLAKE256 hashing occurs versus two rounds of SHA256 in Bitcoin due to its technical shortcomings. The combined effect is that it takes much less energy to find a solution for a given hash rate.
References

Aumasson J., Henzen L., Meier W., Phan R. 2010. SHA3 proposal BLAKE ↩↩↩↩↩

Aumasson J., Henzen L., Meier W., Phan R. 2014. The hash function BLAKE ↩↩

Balasch, J., Ege, B., Eisenbarth, T., Gérard, B., Gong, Z., Güneysu, T., Heyse, S., Kerckhof, S., Koeune, F., Plos, T., Pöppelmann, T., Regazzoni, F., Standaert, F.X., Van Assche, G., Van Keer, R., van Oldeneel tot Oldenzeel, L., von Maurich, I.: Compact implementation and performance evaluation of hash functions in ATtiny devices ↩

Eli Biham, Orr Dunkelman. A Framework for Iterative Hash Functions — HAIFA ↩↩↩↩↩

Bernstein, D.J.: ChaCha, a variant of Salsa20 ↩

Aumasson, J.P., Meier, W., Phan, R.C.W.: The hash function family LAKE ↩↩↩

Thai Duong, Juliano Rizzo: Flickr’s API Signature Forgery Vulnerability ↩

Antoine Joux. Multicollisions in iterated hash functions ↩

Richard Drews Dean. Formal Aspects of Mobile Code Security ↩

John Kelsey and Bruce Schneier. Second preimages on nbit hash functions for much less than n 2 work ↩

John Kelsey and Tadayoshi Kohno. Herding hash functions and the Nostradamus attack ↩

Aumasson J., Henzen L., Meier W., Phan R. 2014. The hash function BLAKE Page 118. ↩

Aumasson J., Henzen L., Meier W., Phan R. 2014. The hash function BLAKE Page 149150. ↩

Andreeva, Elena; Mennink, Bart; Preneel, Bart, Security Reductions of the Second Round SHA3 Candidates ↩

National Institute for Standards and Technology. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA3) Family ↩↩

ThirdRound Report of the SHA3 Cryptographic Hash Algorithm Competition ↩↩↩↩↩↩

Denton, Ben & Adhami, R. (2012). Modern Hash Function Construction ↩

Bernstein D. and Lange T. 2013. eBACS: ECRYPT benchmarking of cryptographic systems ↩