Inefficient outsourceability

[kushti]

Non-outsourceability, so a infeasibility or impossibility to outsource work to external players (usually, from a pool to a miner) is desirable property to tackle with the problem of few(or one) mining pools controlling most of mining power.

We can not hope for a strong non-outsourceable scheme (e.g. http://soc1024.ece.illinois.edu/nonoutsourceable_full.pdf) because of its inefficiency. Weak non-outsourceable scheme from the Permacoin paper also not suitable for our needs probably.

As an initial attempt, as we would like miners to prove possession of a state N blocks ago, we combine a proof of possession (which is basically a proof of (non)membership for nonce value used in PoW) with a zero-knowledge proof of knowledge for nonce commitment. We require "coinbase" transaction to be protected by the following script:

proof_of_(non)membership(stateroot(-N), nonce) /\ proof_of_knowledge(c, nonce),

where c is a Pedersen commitment c = g^nonce * h^R

Thus a pool for every nonce needs to calculate a proof of (non)membership and make at least 1 exponentiation, then update roots for state and transaction and send the header to the worker. Hopefully, computations and interactions needed for that are prohibitively high.

What are weaknesses of this scheme? How to adopt it to Equihash?

[catena2w]

Miners may fix nonce and change some transaction (possibly to themselves) in a block

[catena2w]

Will be done in #390