I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site.
Question
Because of the nature of a blockchain, a large number of publicly agreeable coin flips may be generated - namely, the hashes of previous blocks may be agreed by the network to be randomly drawn from $\{0,1\}$.
Accordingly, has anyone attempted to create a solution to the Byzantine Generals' Problem for a blockchain, where a proof-of-work is a decision problem in $NEXP$ or $PSPACE$, and the proof is checked probabilistically, using hashes of previous blocks as public coin flips?
Motivation
I’ve seen discussions online attempting to make a proof-of-work for cryptocurrencies "better," by, for example, finding witnesses to $NP$ problems.
A prover who finds a witness to an $NP$ problem may publicly announce the witness to prove that she did the work.
If there were a common, static pool of $NP$ problems, say $TSPs$ of subsets of the $n$ largest cities on Earth, then announcing the witness to secure block $i$ means that anyone can take that same witness and attach the work to another chain, which does not secure the chain.
If the verification were a zero-knowledge proof, the world (apart from the prover) may never need to know what the witness actually was.
However, as noted by others, because cryptocurrencies are trustless peer-to-peer systems, attempting to keep such a witness zero-knowledge may be difficult in a trustless peer-to-peer system.
For example, if a prover finds a solution to one of the $TSP$ problems from a static pool, and announces a $ZKP$ proof, she may still be tempted to sell her witness to fraudster if the price was right. That fraudster may attach the work to another fraudulent chain.
The witness to an $NP$ problem may not secure a blockchain, which is one of the purposes of a proof-of-work.
Similar Proposals
Converting the problem space from a static pool of $NP$ problems to a dynamic pool of problems may help, and I’ve seen a proposal that, I think, dynamically generates subgraph isomorphism problems as proofs-of-work. However, as far as I can tell, the above proposal verifies the witness deterministically.
I’ve also seen attempts to use PCP’s to verify outsourced computations, although I don’t think the outsourced work is connected to a cryptocurrency blockchain. Maybe that work comes close.
History
In [GMR85], the authors introduce interactive proof systems. In [GS86], the authors show a public coin protocol for graph nonisomorphism. In [Sha91], the author proves $IP=PSPACE$.
In [BFL91], the authors prove that $MIP=NEXP$. In [BFLS91], the authors envisioned extending those ideas to transforming formal mathematical proofs into transparent proofs checkable in polylogarithmic time.
In [AS92], the authors characterized the above works as implying that mathematical statements can be checked in polylogarithmic time by reading only $poly(logn)$ bits in a proof of a theorem of Peano arithmetic, with a proof of size $n$ (which they reduced to a sublogarithmic number of bits, and was reduced contemporaneously to $O(1)$ queries in the hallowed PCP theorem).
E.G., quoting from [AS92], they envision statements:
$$\{(T,1^n):T\:is\:a\:theorem\:of\:Peano\:arithmetic\:with\:a\:proof\:of\:size\:\leq n\}$$
as languages in $NP$, with witnesses that can be probabilistically checked with a sublogarthmic number of bits.
Note that it is undecidable to find an easy relation between $|T|$, the length of the theorem proved, with $|\pi|=n$, the size of the proof. Simple provable statements may have long proofs, or long provable statements may have short proofs.
That is, by the Incompleteness Theorem, $n$ grows faster than any computable function of $|T|$. Accordingly, one may consider a bounded version of the above, say $n=O(exp |T|)$, and find exponential size proofs of small theorems. Thus, statements such as:
$$\{(T,1^n):T\:is\:a\:theorem\:of\:Peano\:arithmetic\:with\:a\:proof\:of\:size\:O(exp(|T|))\}$$
may be viewed as languages in $NEXP$, with inputs of size $|T|$.
[AS92] states “we suspect this result is largely of theoretical (as opposed to practical) interest” (emphasis added.)
In [Kil92] the author describes a prover committing to a probabilistically checkable proof of $\pi$ as a Merkle root of a tree, and answering public questions about bit $i$ of the proof by revealing the path of $i$ to the publicly committed Merkle root.
In [Nak08] the author’s solution of the Byzantine Generals' Problem entails requiring proofs-of-work.
The proof-of-work in [Nak08] involves partially inverting cryptographic hashes – for example, given a cryptographic hash $h(x)\in\{0,1\}^N,x\in\{0,1\}^*$, a block $i\in\mathbb{N}$, and (a Merkle root of) financial transactions $B_i\in\{0,1\}^N$, finding a nonce $n$ such that $$h(n\Vert B_i)$$ begins with a number $d$ of leading $0s$.
The proof-of-work in [Nak08] has some advantages – it secures the transactions, relying on the well-established SHA256 hash ($N=256$), etc. The difficulty of finding a nonce grows as $O(2^{kd})$ for some $k$. The proof-of-work in [Nak08] is immediately checkable by all nodes in time $O(d)$, and verification is very fast.
Likewise, there may be disadvantages to partially inverting SHA256 – a lot of energy is spent on a problem that is essentially a random, somewhat artificial puzzle. Additionally, all those who attempt the proof-of-work are working on the same problem, while there will on be one "winner."
Examples
NEXP
Consider, for block $i$, a prover committing to a Merkle-root, as in [Kil92], of a proof $\pi$ of some statement $T$ of Peano arithmetic in probabilistically checkable format, as in [AS92]. She may use in the proof the Peano axioms and other rules of inference. She may also use other theorems proved in previous blocks as lemmas to speed up the proof of her own theorem. The first miner to announce proofs of statements where $\sum2^{-|T|}>d$ for some difficulty threshold $d$ "wins" the block.
She then uses the hash of block $i-1$ as the random coin tosses used by the verifier in [Kil92] to query $O(1)$ bits of $\pi$.
As her reward for mining, she is granted a profit of $\sum2^{-|T|}$ units of currency. Hence she is encouraged to find proofs of small theorems (as they are worth more).
This also keeps the total amount of minted currency finite, and bounded below by I think $1/2$ (because $1/2$ of all well-formed formulae are true and $1/2$ are false, and not all of them can be proved.)
I also think this encourages $|T|$ to grow only as $O(log\:i)$, where $i$ is the block number, because miners only look at smaller statements.
This also shows that a miner who proves a statement $T$ can also announce $\sim\sim T$, and $\sim\sim\sim\sim T$, etc., and still only be rewarded $2^{-O(|T|)}$ units of currency.
Eventually the world may learn that some small statement of Peano arithmetic is true, although no one person or miner may have access to the entire proof. Some miners may have proved individual lemmas, which are used by others to finish off the proof. Those other miners may never need to have their proofs verified deterministically.
PSPACE
As another example for a proof-of-work, consider adding a number of randomly spawned quantified Boolean formula ($QBF$) to a “pool” of open problems. Say, upon mining block $i$, $O(1)$ $QBF$ problems with an average of $l=O(log\:i)$ literals are spawned and added to the “pool.”
The problems added to the pool may be randomly generated based on the previous blocks’ hash.
Provers (miners) compete to find proofs that one or more of the problems in the “pool” are true or false. The first prover to find a number $d$ of statements in the "pool" wins the mining profit. Upon finding a proof, a prover engages in a public-coin interactive proof of the truth or falsity of the statements that they proved. I think they can engage in the Fiat-Shamir heuristic in their announced proof.
Provers are not, necessarily, required to prove that the most recently spawned problems are true or false, only that some of the problems in the pool are true or false. For example, a problem added $10$ or $100$ blocks ago may still be worked on and proved for this block.
Hence a problem that has been “in the pool” for a long time will manifest itself as a harder problem because it’s been “in the pool” for longer.
The provers may be rewarded $2^{-l}$ units of currency. Hence there is an encouragement to find true QBF's with a smaller number of literals. This also keeps the total currency finite. Because some QBF's with a large number of literals may be easier than others with a small number of literals, it might be easier for miners to work on newly added, easier problems with a larger number of literals than older, harder problems with a fewer number of literals, although the profit may be lower.
Unlike inverting SHA, provers $P_1$ and $P_2$ do not need to be working on the same position at the same time. Whoever finds a proof first merely announces her proof, relying on the random bits from the hash of the previous block to verify probabilistically. The loser for this block may still continue searching for her proof, and may win the next round.
Because $PSPACE$ can be considered as games between $\exists$ and $\forall$, mining may be considered as solving games. Eventually the world may find out that chess (or whatever game) is solved. However, no one prover has access to the entire proof, because no one prover will be able to store the entire proof.
References
[AS92] S. Arora, S. Safra. Probabilistic Checking of Proofs: A new characterization of NP. link
[BFL91] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive proofs. link
[BFLS91] L. Babai, L. Fornow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. link
[GMR85] S. Goldwasser, S. Micali, C. Rackoff. The Knowledge complexity of interactive proofs. link
[GS86] S. Goldwasser, M. Sipser. Private coins vs. public coins in interactive proof systems. link
[Kil92] J. Killian. A note on efficient zero-knowledge proofs and arguments. link
[Nak08] S. Nakomoto. Bitcoin: a Peer-to-Peer Electronic Cash System. link
[Sha92] IP=PSPACE link
