Cryptography

This section is dedicated to the prerequisite cryptography (and related topics) involved in blockchain technology, and contains more math than any other section. Since this site is dedicated to blockchains, the cryptography sections are provided at the level of detail useful to blockchain developers; they do not delve into the mathematics beyond what is necessary to understand and safely implement/use the various cryptographic concepts covered.

 

Trap Door Functions
Informally: A trap door (or one-way) function is a manipulation of data in such a way that, given only the result of applying the function, it is very difficult to get back to the original data. Conceptually, they are similar to mixing ingredients (like eggs and flour) together: mixing them is easy, separating them afterwards is incredibly difficult.

Formally: A trap door function H(x) = y is a function for which the output y is easy to find given x, but for which recovering x is difficult given y. Trap door functions include hash functions, multiplying vs factoring numbers, and discrete logarithms. In blockchains, they are used to summarize/represent other data (in a way where forging the original data is made impossible) and to sign messages/prove identity.

 

Hash Functions
Informally: A hash function ‘scrambles’ data of any size and squeezes it into a representation or fingerprint of the data. Changing the input data even slightly will reduce in drastic changes to the output, and given the output it is incredibly difficult to reverse the function to restore the original data. It is a form of trap door function.

Formally: A hash function H(x) is a function which takes input x (of arbitrary size) and outputs a fixed-size representation y of the input data. Well-designed hash functions evenly distribute the outputs in the possible output space, and create a hash which cannot be reversed (other than brute-forcing) back to the original input data. They are considered a trapdoor function, a property which makes them ideal for proof-of-work mining. Their ability to create a unique identifier for any input data (ignoring the theoretical possibility of a collision generally unobserved in practice, a mathematical inevitability as per the Pigeon Hole theorem) also makes them useful for summarizing data and proving presence of a piece of data in a set using Merkle Trees.

An example of the hashing algorithm SHA256. Note that small changes to the input data have an avalanche effect, causing the output to be entirely different.

 

Signature Algorithms
Informally: Signature algorithms allow parties to prove that they are who they say they are, and to endorse or agree to a message (like a statement endorsing a candidate, or a contract). They are analogous to real-life signatures, in that they should be impossible to forge by any other party and prove that the expected party saw and endorsed with the message.

Formally: A signature algorithm is a type of asymmetrical cryptography wherein a public/private keypair is employed and which allows a party to prove access to the private key (as well as approval of something, like transferring funds or voting for a candidate) in a way which doesn’t reveal the private key, but can be verified as valid by any party who knows the public key. For example, an entity with the public identity a can sign a message (like “I, a, endorse candidate x”) producing a signature b. Anyone who knows of the public identity a can verify that the signature b is valid, but cannot create a signature c which correctly signs any other message for a (like, “I, a, endorse candidate y”).

 

Merkle Trees
Informally: A Merkle Tree is a tree data structure which uses hash functions to represent multiple individual pieces of data. Their construction makes it possible to prove to any party who knows only the tree’s fingerprint that a certain piece of data is contained within the tree without revealing any other pieces of the original data and in a manner which scales incredibly well (with regards to computation time and size) relative to the number of individual pieces of data that the tree represents.

Formally: A Merkle Tree (often referred to as a ‘hash tree’) is a data structure which summarizes a set of data S = {d0, d1, …, dn} in such a way that it is easy to prove to anyone who knows the Merkle Root (a fixed-length representation of the tree) that an element dx is present in (in other words, dx ∈ S) with a proof whose size follows O(ceiling(log2(n)) + c) where n is the number of elements in the set. In tabular form, here is a guide to the relative size of the proofs (where c is a reasonably constant overhead consisting of the index of the proven element in the tree):

Number of Elements in Tree Relative Size of Proof
2 1 + c
4 2 + c
8 3 + c
16 4 + c
32 5 + c
64 6 + c
128 7 + c
256 8 + c
512 9 + c
n ceiling(log2(n)) + c

Merkle trees are made by concatenating two adjacent elements in one layer and hashing this concatenation to create a single corresponding entry in the layer above. The process is repeated until a layer is created which contains only one entry. This single entry is known as the Merkle Root, and serves as a fingerprint of the entire tree.

 

Here, there are four pieces of data: ‘AB’, ‘CD’, ‘EF’, and ‘GH’ from which a Merkle Tree has been created.