Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such that $H(c\Vert D)$ starts with $d$ zero’s. That is to say, Hashcash/Bitcoin Proofs-of-Work appear to find a preimage $c\Vert D$ that partially inverts a hash $H$. Depending on $d$ and the size of the nonce, it may be impossible to find a nonce $c$ without having to change the data $D$. Currently (Aug. 2017) with Bitcoin, the target difficulty $d$ is, I think, 17 consecutive hexadecimal 0's. Given a set $S\subseteq\{0,1\}^m$ and a number $K$, the Goldwasser-Sipser Set Lower Bound Protocol is an Arthur-Merlin protocol for Merlin the prover to show Arthur the verifier that $|S|\geq K$. Letting $k$ be a number such that $2^{k-2}\leq K\leq 2^{k-1}$, Arthur chooses a random hash $H$ from pairwise independent hash function collection, along with a random $y\in\{0,1\}^k$. Merlin’s goal is to find an $x\in S$ such that $H(x)=y$. That is to say, Merlin’s goal in the Goldwasser-Sipser Set Lower Bound Protocol is to find a preimage $x$ that inverts a hash function $H$. The larger the set $S$, the easier it may be to find a preimage. Indeed, if $S\leq \frac{K}{2}$, then Merlin has a much smaller chance of finding a preimage than if $S\geq K$. Thus, Merlin may provide evidence to Arthur that $S$ is large. This may be used, e.g., to show that two graphs are not isomorphic. My question is: can we reinterpret the Hashcash/Bitcoin Proof-of-Work as a Set Lower Bound? In other words, can we consider finding a nonce $c$ in the Bitcoin Proof-of-Work as similar to finding a preimage $x$ in the Goldwasser-Sipser Set Lower Bound, which may show that some (arbitrary) set is large? Or is the similarity between the two not very strong? EDIT Following up on D.W.'s answer, I wonder if $D$ could be considered as the input to a test of membership of $x\in S$. For example, $S$ could be

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

Background A proof-of-work system allows one peer to prove to another peer that a certain amount of computational effort was performed. In a network setting this can be used to throttle peer requests without needing to keep a precise track on the identity of the peers or prior events. The most well known use of proof-of-work is to throttle spam throughput in an email network*. Some proof-of-work systems allow certain roles on the network (say, a mailing list) to calculate the proof of work much faster by using a secret "short-cut" - typically a pre-calculated trapdoor or a private key depending on the proof-of-work system. Hypothesis - Any algorithm or a certain class of algorithms can be converted into a proof-of-work version of that algorithm. That is: A deliberately inefficient and incompressible algorithm. - Such converted proof-of-work algorithms can support proof-of-work shortcuts. - Such converted proof-of-work algorithms can not be converted back to the original algorithm without considerable computational power; if at all. Extrapolation If the hypothesis holds, then selected business logic of an application - specifically that which is unique or value-added by that application vs existing applications - could be converted to proof-of-work equivalents. End-users could then be provided such an application; which will run slowly either generally or for certain premium features. The development team however, possesses a secret PoW shortcut and set up a subscription, donation or advertising(!)-based service - an SaaS - for solving the proof-of-work bottleneck for the end-user. The end-user can now choose to run the application slower without the SaaS or faster with the SaaS. This SaaS needs to process considerably less client-side business logic than a general cloud solution (e.g. Diablo 3 style SaaS); as the goal is the speed of execution rather than no execution - and the SaaS proof-of-work speed ratio is tailored accordingly. This is especially