Is true decentralization possible without true randomness? (Part2)
How dare we speak of the laws of chance? Is not chance the antithesis of all law?
-Joseph Bertrand, Calcul des probabilités, 1889.
So here comes the fundamental questions that need to be asked: What is true randomness, how is it generated and where can we get them?
Before we dive into these questions, a more fundamental question perhaps needs to be asked is: does randomness actually exist? or is it just a misconception of this complex universe due to our lack of intelligence?
In Russian mathematician Andrei Khrennikov’s article “Introduction to foundations of probability and randomness”, he summarizes key features of randomness from Kolmogorov’s proposal:
It might be that randomness is not mathematical, but physical notion. Thus one has to elaborate physical procedures guarantying randomness of experimentally produced sequences and not simply try to construct such procedures mathematically.
In Kolmogorov’s frame of randomness and complex system, randomness is based on three features: 1. Unpredictable 2. Typical 3. Complex.
And randomness itself is either an incomputable measure or a subjective measure.
There is a type of complex system embedded in our universe that is not able to be represented or computed by our current mathematics. According to Stephen Wolfram’s theory, it’s actually impossible to achieve the goal of using mathematics to compute and represent every system in the universe, because otherwise, self-referential paradoxes such as the halting problem would emerge.
The cellular automaton is a perfect example of why randomness is not mathematical or cannot be represented in the current mathematical terms. The basis of Rule 30 is from the random number generator embedded in Mathematica. And as we can tell, as the iteration goes up, the seeming randomness gradually evolves into a regular structure with strong patterns. The cellular automaton probably also implies that all the “randomness” generated in the mathematical level are essentially exceedingly complicated patterned computation with some regular structures hidden inside.
However, based on Kolmogorov’s theory, true randomness does exist in the physical universe. The most reliable and fundamental theory until today — quantum mechanics — is intrinsically probabilistic, which means everything is essentially a state function, and there is no way to predict the outcome.
Randomness is the core of modern cryptography. If an external observer manages to figure out any non-random patterns in the encrypted secret, the encrypted secret is exploitable. Cryptography is like a “factory”, we need to constantly feed-in enough entropy and true randomness as fuel for it to work well. The modern cryptography is strong in terms of the complicated machinery in the “factory”, but it’s hard to find sources of good randomness.
As mentioned earlier, it’s proved by mathematicians that if somebody gives you a seemingly random string, you cannot by any chance ever prove if it’s truly random or if it just appears to be random.
Since cryptography requires a lot of unpredictable randomnesses, scientists have found many sources of true randomness in the natural processes. The laws of physics or chemistry constantly produce highly unpredictable, random results. Unfortunately, all these sources are inconvenient to use, because they require special-purpose hardware or even more cumbersome setups.
In current blockchains, cryptography plays a huge role in encryption, hashing, and consensus mechanisms. All of the mainstream public blockchains are using the pseudorandom way as their “fuel” to power the sophisticated cryptographical mechanisms. While a novel idea — Proof of True Randomness (PoTR) breaks this convention by providing true randomness from the hardware level as the source of randomness.
As mentioned in part1, Proof of True Randomness has natural advantages comparing to existing consensus protocols such as PoW and PoS. Several researchers have introduced proof-of-“something” blockchain techniques to address the challenges faced by Bitcoin. However, it is been proven impossible to design a secure distributed consensus without consuming some resource outside of the system. This is generally called the “costless simulation attack” or “nothing at stake attack”. If it is costless for a block proposer to create valid blocks, then she/he may sell her/his stake in the system and perform a history-rewrite attack.
One of the celebrated proof-of-stake schemes is ALGORAND by Micali and his collaborators. Studies showed that the provable security for ALGORAND does not consider the costless simulation attack and ALGORAND is also vulnerable to costless simulation attacks. The literature recommends the use of “bootstrapping through social consensus” approach to defeating the “costless simulation attack”. In this bootstrapping approach, it is recommended that, for a new node to join the blockchain system, one should manually provide a recent checkpoint blockchain from the set of nodes it can access upon joining. This approach does solve “the cost simulation attack”, but it’s required to manually onboarding new nodes in the network.
A recent project called SperaX, proposed a new consensus protocol assuming the existence of tamper-proof devices that generate truly random sequences from the hardware level by using thermal noise or photoelectrical effect. their protocol can be considered a proof-of-stake protocol where the stake is the possession of these specifically designed hardware modules. Since the tamper-proof hardware modules could be designed in such a way that they contain counters for signed blocks, and this process is truly random, the tamper-proof hardware module based proof-of-stake protocols can defeat costless simulation attacks. Up to my knowledge, their protocol is the first proof-of-stake protocol that is secure against costless simulation attacks (without manual bootstrapping). This is an exciting direction where the entropy in the physics world combines with blockchain — a platform for computation.
