Shannar de Kassal 🐀

It is incorrect to name a truly random byte string (large number) an “entropy” (for instance like the one used to produce cryptographic seed for hierarchical deterministic wallets), since not every byte string with a maximal entropy is truly random! In this tweet I give a proof of the statement (for those who want to skip low level details to more practical question “how to generate and verify that a given string is truly random, just skip to the next tweet). The random byte string must have two qualities: - it must have maximal Kolmohorov complexity, i.e. there must be no program in any language to reproduce the string which will be shorter then the string itself (i.e. string by itself is the shortest program to reproduce itself); - the complexity measure must include programs over any input of any reproducible information available in the external world. (Explanation of the second clause: it can’t be a hash of any text in books or known/which can be written by humans, since the hashing has smaller complexity than truly random string of the size of the hash output). These makes truly random byte string to be a subset of strings with maximal entropy! Computationally, maximal entropy is a state of a system which is the least distinguishable from other states (this definition is equivalent to thermodynamical and informational definitions). Thus, a string of maximal entropy bytes has a property “logarithms of mathematical expectation of each specific consecutive byte (given the prefix) multiplied by the expectation must sum to the least value”. In other words, the string must be a “surprise” for the reader, unpredictable from pure statistical qualities. Truly random byte string always has maximal entropy and maximal Kolmohorov complexity. But not each string of maximal entropy has maximal Kolmohorov complexity! In other words, not each statistically random string is unpredictable. An example is a hash function output: you can sample 32 byte pieces of text from literature and SHA256 hash each sample, selecting one with maximal entropy. Yet, the Kolmohorov complexity will be just 32 bytes instead of the 256 for a truly random string! Another example is cellular automation “rule 30” found by @stephen_wolfram and given on the illustration to the tweet: it generates states which maximize entropy, but which can be reproduced with just two values: rule number instruction and N (number of steps); i.e. it has extremely low Kolmohorov complexity. Thus, while rule 30 is used by PRNGs (pseudo-random number generators), it can’t be used for generating truly random strings, i.e. be a source of seeds or private keys in cryptographic systems. Next tweet will describe how to achieve and verify maximum of Kolmohorov complexity.

It is important to understand that geometry is a form of math on multiple degrees of freedom (dimensions) which present the interaction between degrees of freedoms explicit, while algebra is the very same thing putting these dimensions behind named variables. Some things are easier to understand in geometric way, some in algebraic, but fundamentally they are the same. Euler formula just demonstrates that correspondence.