June 6, 2016

All articles about the blockchain industry emphasize the cryptographic protection of underlying data records as the main trait of that technology, which makes the underlying ‘database’ (or better said ‘data structure’) completely immutable (virtually impossible to be modified) and safely shareable by all network participants.

I am sure many people wonder, "What does it all mean? How does it all look inside and how is it actually stored? How is this immutability achieved?" That’s why I have decided to provide a very brief primer.

Every known flavor of blockchain technology platform in use today relies on a couple of well-known cryptographic concepts which have been in existence for a long time. People from the payments space should already be very familiar with them (EMV was using them in various ways for a long time), but many enterprise businesses and IT folks may feel disadvantaged, simply because they haven’t been exposed intensively to those concepts.

The two key concepts underlying the blockchain are __Cryptographic Hashing__ and __Digital Signatures__. Creatively combined, these two cryptography capabilities achieve everything that’s making blockchain a unique and potentially exciting technology. Let’s take a quick look at each one. I will bravely try to explain these at the highest possible level and rely mainly on words (and maybe some diagrams), and avoid complex mathematical notation and proofs (which really do not matter much in this context).

A cryptographic hash function is a mathematical function that is implemented in software, which must have following important properties:

- It must be able to take input of any type/any size data block and then produce a fixed size output.

- It must be ‘constant’ – meaning that it always produces exactly the same output from the same supplied input.

- It must be ‘collision resistant’ – meaning that the probability of generating the same output from two different inputs is close to zero (i.e., it is virtually impossible)

- It must be ‘one way’ – meaning that despite knowing the hashing algorithm and the output, the input data can not be figured out.

- It must be efficiently computable - meaning that for a given input string, it produces the output in a reasonable amount of time on an average computer.

In order to implement a cryptographic hash function that would work on data block inputs of arbitrary lengths, we usually use a simpler ‘helper’ function (called the Compression Function'), which only needs to be able to work on fixed-length inputs. We then chop input data message into fixed size blocks and repeatedly reuse the compression function as many times as required until all blocks of the original input get processed. NOTE: This extremely important and convenient capability of implementing a cryptographic hash function for handling inputs of any size (by reusing the simpler Compression Function capable of only processing fixed size inputs) is called the Merkle-Damgard transform.

SHA-256 is commonly used hash function in blockchain implementations that take advantage of the Merkle-Damgard transform. SHA-256 uses a Compression Function that takes fixed-length 768-bit inputs and produces 256-bit outputs. See below for a graphical explanation of how the SHA-256 works.

Basically, the original message is first divided into ‘n’ blocks of 512 bits (blue boxes on the diagram). Then the SHA-256 Compression Function is reused iteratively. The first iteration of SHA-256 Compression Function receives as inputs 512 bits of the original message’s Block #1 and 256 bits of Initialization Vector. Every next iteration of SHA-256 Compression Function (from 2 to n) receives next 512-bit Block of the original message and the 256 bits-long output of the previous SHA-256 Compression Function. The output of the n-th SHA-256 Compression Function iteration is the final SHA-256 hash value (256 bits long) of the whole original message.

Since SHA-256 satisfies all of the above properties of the cryptographic hash functions, it can be used to produce something called ‘message digest’ of any type/size input data block. The message digest is basically a __safe__ and __unique__ hash of the input data block. All that is the consequence of the ‘constant’, ‘one way’ and ‘collision free’ properties of the SHA-256 cryptographic hash function. As such, the message digest can be the used as a reliable proof of ‘immutability’ of the original input data block. For example, if you store the data block together with its SHA-256 ‘message digest’ you can always verify later (when you read it), whether it was modified while at rest, by running SHA-256 on the read block and comparing it to the stored message digest. They MUST BE THE SAME.

The hash pointer is simply a pointer to an arbitrary data block record location (in memory or disk storage), together with the message digest of the content of that particular data block record. It gives the programmer the ability to locate and read the data block together with the ability to verify it’s immutability.

On diagrams, hash pointer is usually represented as: **H()->.**

A digital signature is considered being the digital analog to a handwritten signature on a paper document. We require two properties from digital signatures to be able to mimic the handwritten signature analogy well:

- The only signer should be able to make his/her signature, but anyone who sees it should be able to easily verify that it’s valid.

- The digital signature needs to be tied to a particular document so that it can be used to signify signer’s agreement / endorsement of the document.

Public key cryptography satisfies both of these properties. The signer has a pair of complementary keys: __secret key__ or ‘sk’ (that he/she keeps protected) and __public key__ or ‘pk’ (that he/she shares with the general public). The electronic documents are always signed using the signer’s secret key and can be verified by anyone using the signer’s corresponding public key.

To improve the efficiency of execution, instead of digitally signing the whole message, implementations usually chose to sign the message digest of the original message.

All blockchain implementations basically represent a tamper-evident linear list (log) of data block records, linked using previously described concept of hash pointers. Each hash pointer points to the previous data block record and also contains the message digest of that data block. Each of the linked data block records contains the set of transaction messages (digitally signed by the transaction initiator using his/her ‘sk’), which are grouped together, primarily for more efficient ‘mining’ (out of the scope of this article).

Inside the data block, all of the grouped transaction messages are organized in a kind of binary tree, called Merkle Tree, which is also implemented using the hash pointers for the record linking. The binary tree structure is chosen for as efficient as a possible method of finding (or not) individual transaction messages inside the data block.

As you can see, the blockchain maintains immutability of the data at two levels. The immutability of data blocks is preserved by hash pointers used for their linear linking, but also immutability of each of the transaction messages stored inside the data block is preserved by hash pointers used for implementing the Merkle Tree data structure.

Since the picture is worth a thousand words, the diagram below shows final typical (still high-level) blockchain data structure, where one of the data blocks is further expanded to show the nature of the Merkle Tree data structure (the internal tree hash pointers are marked as HL()-> and HR()->.

This is by no means a complete description of everything that is stored and managed inside a typical blockchain database. It also doesn’t elaborate nor touch on the implementation of mining and/or consensus algorithms implemented in the various blockchain products on the market. That’s a whole separate subject in itself.

However, my hope is that this article provides enough detail for everyone interested in the subject, but not fully familiar with cryptography and blockchain technology internal storage mechanisms. Ideally, articles like this can equip and enable many more decision makers for making better and informed decisions going forward with eyes wide open.

DEEP DIVESExclusive to Strategy Plans