...by Daniel Szego
"On a long enough timeline we will all become Satoshi Nakamoto.."
Daniel Szego

Tuesday, November 28, 2017

Notes on hash turing machines

Hash functions are basic building blocks of every blockchain or distributed ledger solutions. The blockchain itself is nothing more than a linked list of blocks that store transactions and the links are made photographically more secure with hash functions. There are other hash structures as well, like hash trees, called merkle trees to efficiently store the transaction in the blocks or hash tree algorithms to create a consensus mechanism from a different point of view. 

However, hash pointers should not only be considered only at data structures. Hash might be efficiently considered as a result or internal state of a computation. As an example, let we consider a Turing machine: each state change can be extended by a hash computation that computes a hash value based on the input and output states making sure that the given computation is highly secure and hacking resistance. In this sense, a result of a whole computation can be guaranteed by a hash value that is computed either by the inputs or outputs of the whole computation or by the hashes of the individual computational elements. Certainly, it is a little bit questionable what happens if a given algorithm can be implemented many different ways, implying that there might be several valid hash at the end of the computation.