In 1996 Pascal Koiran [showed](https://pdfs.semanticscholar.org/d4e6/87c5dc96a0e4fd47465792f7b6f694a85e7a.pdf) that, assuming the generalized Riemmann Hypothesis, Hilbert's Nullstellensatz is in $\mathsf{AM}$ over the complex numbers $\mathbb{C}$.  That is, given a system $S$ of polynomial equations $f_1[x_1, x_2, \cdots x_n]=0, f_2[x_1, x_2, \cdots x_n]=0$, $\cdots,  f_m[x_1, x_2, \cdots x_n]=0$, a powerful Merlin can convince a polynomial Arthur that $S$ is satisfiable over $\mathbb{C}$.  

Koiran showed that, if $S$ is satisfiable, assuming GRH there are enough primes $p\le z\sim \text{exp}^{mn}$ such that $S$ is satisfiable modulo $p$ iff $S$ is satisfiable over $\mathbb{C}$.  Koiran also showed that if $S$ is not satisfiable over $\mathbb{C}$, there are no more than half as many primes $p'$ such that $S$ is satisfiable modulo $p'$.

Koiran's Arthur-Merlin protocol involves:

 - Arthur picking a random hash function $H$, along with a random number $y\le z$, and providing $H$ and $y$ to Merlin,

 - Merlin finding a prime $t$ such that $H(x)=y$, along with a solution $(a_1, a_2, \cdots , a_n)\in (\mathbb{Z}/t\mathbb{Z})^n$, and

 - Arthur verifying $H(t)=y$ and $(a_1, a_2, \cdots , a_n)\in (\mathbb{Z}/t\mathbb{Z})^n$ satisfies $S$.

This may lend itself to a proof-of-work to solve nullstellensatz problems that *partially invert* a hash, similar to the bitcoin proof-of-work.  

If we identify Merlin as the miner and $t$ as the nonce, we may set $y$ to be fixed as a run of consecutive $0$'s in a hash, similar to bitcoin.  The $\mathsf{sha256}$ hash may suffice.

Given a system of polynomial equations $S$ and a payload $B$, where the payload includes the Merkle-root of financial transactions, miner ID's, the previous hashes, and other ways to tie the solution to the block and solver, a proof-of-work might include:
-  Miners calculating a first hash $H(B)$. 

-  Miners competing to find a prime $t$ close to the first hash $H(B)$ such that $S$ is satisfiable modulo $t$, along with a witness $(a_1, a_2, \cdots a_n)$. Miners also require a second hash $H(t)$ begins with $\sim mn$ $0$'s.

- Once found, miners announcing on the P2P network the payload $B$, along with the primes $t$ and the witness $(a_1, a_2, \cdots a_n)$.

- A hash of the present solution may be used to encode a system of polynomial equations $S_{next}$ to be solved for the next block