Using a proof-of-work system to discourage piracy or encourage donations

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

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.

Surprisingly, this is possible.

Essentially the idea is: you can convert any program into a proof. Add some probabilistic complicated mathematical voodoo, and you can get succinct proof that someone ran a program on his machine, the full program, no cheating. This means you can essentially turn any busy-work algorithm into a POW, or even use useful algorithms as POW, and not have to worry about a shortcut (for example, you can use protein folding as POW, and not have to worry that average-case might not be hard). The proof guarantees that the entire program ran until termination.

For deliberate shortcuts you can simply build in early termination into the program for your deliberate shortcuts. For example:

def P(user_input,hard_coded_n):
  if user_input is not None:
    p,q = user_input
    if p*q = hard_coded_n:
      return True
  protein_fold()
  return True

In this program, you generate and hard-code a semi-prime, $n$, into the program. If you want to provide the user with a shortcut, you give him the p,q that he can use as input for early termination. Then you check his proof that he ran the program, and the proof will guarantee that the output he provides was the output of his program; therefore his POW is to provide "True" as output, and the proof.

This type of system is insanely powerful IMO; you can think of all sorts of things you can do with this; your cheap "DRM" ideas are the least of it :P

Further terminology/keywords:

• Succint Non-interactive Argument of Knowledge (SNARKs) are basically succinct proofs that someone ran some computation.

• SCIP: Succinct Computational Integrity and Privacy, is a practical system being built upon many years of research/complicated mathematics.

There is a large body of research into this, attempting to make it practical. For an actual project (SCIP) (you asked this question at the right time in history) see this talk: Universal and affordable computational integrity - Bitcoin 2013 Conference by Eli Ben-Sasson (another talk if you found that one interesting); though he applies it to bitcoin (it is a talk given at a bitcoin conference), he generally explains the power of the system, it is a good watch, even if you don't care about bitcoin.

However, the application to bitcoin, distributed trust systems, and systems that rely on proof-of-work are very numerous and abstract. Suffice to say, though the practical applications are hard to come by at first, the intuitive power of such a system suggests that they will be numerous.

Wrt. bitcoin, this system magnifies the potential of a distributed currency by orders of magnitude; read through bitcoin forums/mailing lists/proposals on the wiki, and you can find countless applications of being able to guaranteeing secure computation on someone else's machine.

• For example, instead of verifying the entire bitcoin blockchain on your machine, you can have someone else do it, and then simply verify that he ran the verifier!

• Of course arbitrary POW is a big possible win for future bitcoin; perhaps one day we'll see a blockchain doing useful work (now doubly useful, not just guaranteeing the integrity of bitcoin, but also computing something useful), or even a secure distributed computing marketplace, where the lottery of minting the next block is won by one of the participants.

For further reading see SNARKs for C :
Verifying Program Executions Succinctly and in Zero Knowledge
(extended version) (PDF): yes, they are making a C compiler. They designed a virtual architecture, called TinyRam from which they generate the proof and the program to be run. They are also considering an LLVM backend. They have created a website for the SCIP project.

StackExchange Computer Science Q#16188, answer score: 3