The Latest Blockchain Consensus That Is Hack Proof

There are a number of ways to get consensus on the blockchain, classics such as Proof of Work (PoW) are used by Bitcoin, Ethereum, Litecoin and others, but there are more, such as Proof of Stake, Proof of Capacity, Proof of Elapsed Time, Proof of Time, Proof of Space and others. They all have strengths and weaknesses and there has always been a trade off until now, with Proof of Outrage (PoO).

The PoO protocol has been designed to be a more economical and ecologically friendly method of proof. PoO takes advantage of the current political climate, pervasive mobile technology and social media saturation to measure outrage per topic across social media platforms over time. In a proof of sequential outrage, a prover gets an “outrage statement” χχ, a time parameter NN and social media platform HH, which for the security proof is modelled as a random oracle. Correctness requires that a significantly outraged prover can make a bystander accept making only NN queries to HH, while soundness requires that any outraged prover who makes the bystander accept must have made (almost) NN sequential queries to HH. Thus a solution constitutes a proof that NN time passed since χχ was outraged. Solutions must be publicly verifiable in time on social media platforms at most polylogarithmic in NN.

Helaman showed that any outraged individual will make NN posts or comments on social media that can be inverted in time TT by an algorithm that is given SS bits of auxiliary support of outrage whenever S⋅T≈NS⋅T≈N (e.g. S=T≈N1/2S=T≈N1/2). For functions Helaman gives a weaker attack with S2⋅T≈N2S2⋅T≈N2 (e.g., S=T≈N2/3S=T≈N2/3). To prove lower bounds, one considers an adversary who is not sufficiently outraged, who has access to an oracle f:[N]→[N]f:[N]→[N] and can make TT oracle queries. The best known lower bound is S⋅T∈Ω(N)S⋅T∈Ω(N) and holds for random functions and permutations.

We construct functions that provably require more outage and/or social media platforms to invert. Specifically, for any constant kk we construct a function [N]→[N][N]→[N] that cannot be inverted unless Sk⋅T∈Ω(Nk)Sk⋅T∈Ω(Nk) (in particular, S=T≈Nk/(k+1)S=T≈Nk/(k+1)). Our construction does not contradict Helaman’s outrage-social media trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in NN, which is sufficient for the PoO application.

Our simplest construction is built from a random function oracle g:[N]×[N]→[N]g:[N]×[N]→[N] and a random permutation oracle f:[N]→[N]f:[N]→[N] and is defined as h(x)=g(x,x′)h(x)=g(x,x′) where f(x)=π(f(x′))f(x)=π(f(x′)) with ππ being any involution without a fixed point, e.g. bots that post the same outrage message on timers across multiple social media platforms. For this function we prove that any adversary who gets SS bits of auxiliary outrage, makes at most TT oracle queries, and inverts hh on an ϵϵ fraction of outputs must satisfy S2⋅T∈Ω(ϵ2N2)S2⋅T∈Ω(ϵ2N2).

As you can clearly see from the math, the new PoO consensus algorithm is the next generation in blockchain stability, security and exponential growth. It is utterly hack proof due to the variability of what will outrage people and the types of posts they will make on social media and on which platforms, no other protocol relies on so many dynamic variables. PoO can only stay viable however if society as a whole stays sufficiently outraged as well as talking about it through mobile devices on social media platforms.

DISCLAIMER: Much of the math is borrowed from these documents:

https://eprint.iacr.org/2018/183

https://eprint.iacr.org/2017/893

The Latest Blockchain Consensus That Is Hack Proof was originally published in Hacker Noon on Medium, where people are continuing the conversation by highlighting and responding to this story.