Given a cryptographic hash $H:\{0,1\}^*\mapsto\{0,1\}^N$ and data $D\in\{0,1\}^*$, the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $x$ such that $H(x\Vert D)$ begins with $d$ leading zeros, for some difficulty target $d$.
Given a family of pairwise-independent hash functions $h:\{0,1\}^m\mapsto\{0,1\}^n$, a random string $y\in\{0,1\}^n$, a number $K$, along with a set $\mathcal{S}$ whose membership can be certified, with a promise that either $|\mathcal{S}|\ge K$ or $|\mathcal{S}|\le\frac{K}{2}$, the Goldwasser-Sipser Set Lower Bound protocol is an Arthur-Merlin public-coin protocol that allows Merlin to prove to Arthur that $|\mathcal{S}|\ge K$. Merlin does this by finding a preimage $x$ such that $y=h(x)$, along with a certification $\pi$ that $x\in \mathcal{S}$. If $\mathcal{S}$ is large, then Merlin will have an easier time of finding a preimage.
The Goldwasser-Sipser Set Lower Bound protocol may be used by Merlin to prove to Arthur certain decision problems in $\text{coNP}$, for example, that two finite (groups, graphs, rings, etc?) are not isomorphic.
Hashcash/Bitcoin mining is famously energy-intensive. A significant amount of energy is consumed to, essentially, solve a the problem to partially invert a hash.
The Goldwasser-Sipser Set Lower Bound Protocol famously makes Merlin work harder, for example, to show that two graphs are not isomorphic, by essentially solving an exponential problem of finding preimage of a hash, while, even before the recent (2015) breakthrough of Babai, it was hard to find instances of $\text{GI}$ that took near exponential time.
However, following up on this question and the answer given, I think, in a certain sense, Hashcash/Bitcoin mining has been doing "quasi-useful" work all along. For example, finding a nonce $x$ such that a cryptographic hash $H(x\Vert D)$ begins with $d$ leading zeros indicates that for a set $\mathcal{S}\subseteq\{0,1\}^*$, if $x\Vert D \in \mathcal{S}$, then it is likely that $|\mathcal{S}|\ge 2^{d-1}$ ($\text{BIG}$) and it is not likely that $|S|\le 2^{d-2}$ ($\text{SMALL}$). But we don't know a-priori how $x\Vert D$ tests for membership in $\mathcal{S}$. In other words, I don't know if we can backtrack to determine what $x\Vert D$ encodes.
But then can we put the Goldwasser-Sipser Set Lower Bound Protocol to good use in designing (forking) a Proof-of-Work in a cryptocurrency, to show that some set is $\text{BIG}$ and not $\text{SMALL}$?
For example, could we, by design, let a random string $D$ representing merkle-nodes of a series of financial transactions also represent an encoding such as the adjacency matrices of two $n$-vertex graphs $G_1$ and $G_2$ (i.e. $D=G_1\Vert G_2$), and have miners compete to find a permutation $\pi\in S_n$, equating the permutation of one of the two graphs as the "nonce" such that for $i\in \{1,2\}$ and $j\le |S_n|=n!$, we have $H(\pi_j(G_i)\Vert G_1\Vert G_2)$ begins with $d$ leading zeros?
Rather than a miner increment a nonce from $0$ to $2^d$, a miner runs through all permutations of the vertices, for two graphs $G_1$ and $G_2$.
If $G_1$ and $G_2$ are isomorphic, then there are permutations $\pi_{j1}$, $\pi_{j2}$ such that $\pi_{j1}(G_1)=\pi_{j2}(G_2)$. Thus, if the graphs are isomorphic, there is a smaller chance that a preimage may be found, as the proof-of-work goes through all of the elements of $S_n$.
Right now (summer 2017) the Bitcoin target is, I believe, set to be searching for a nonce that, when hashed with the payload $D$, leads to 17 consecutive hexadecimal 0's in a SHA256 hash. Note that $2^{17\times 4}\approx 2\times 21!\approx 1e20$, which means I think we can explore all permutations of a pair of $21$- vertex graphs by running through all $\pi\in S_{21}$ in the time used to validate typical transactions in Bitcoin.
Showing that two random $21$-vertex graphs are not isomorphic is trivially done by decent tests for invariants, even with the technology/algorithms used before the 2015 breakthrough of Babai. I believe similar questions can be asked about whether two groups are isomorphic, with a group order roughly $2^{d-2}$; e.g. whether a random set of permutations generates the alternating group, or other word-like problems in matrix groups.
But to me finding a preimage of a SHA256 hash that secures a blockchain and shows that two graphs are not likely to be isomorphic, or answers some marginally interesting question about a perumutation group or a matrix group, seems like an incremental improvement over finding a preimage of a SHA256 hash for the sole purpose of finding a preimage that secures a blockchain.
