In 1996 Pascal Koiran showed 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

In 1996 Pascal Koiran showed 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]= f_2[x_1, x_2, \cdots x_n]= \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 achieved this by showing that, assuming GRH, there is a $z$ of order $O(\text{exp}(mn))$ such that there are enough primes $p\le z$ with $S$ satisfiable modulo $p$ iff $S$ is satisfiable over $\mathbb{C}$. Similarly, Koiran 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. Any good cryptographic hash, such as the $\mathsf{sha256}$ hash used in bitcoin, may suffice, as long as the number of consecutive $0$'s is correct.

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 number represented by the first couple of bits of the first hash $H(B)$ such that $S$ is satisfiable modulo $t$, along with the satisfying witness $(a_1, a_2, \cdots a_n)$. The proof-of-work also requires a second hash $H(t)$ begins with the target difficulty $\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, or the next system of polynomials may be decided through some other means.

If $S$ is not actually solvable, then another problem could be worked on if after a while no prime is found.