4
$\begingroup$

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

  1. 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.
  2. Such converted proof-of-work algorithms can support proof-of-work shortcuts.
  3. 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 relevant for software projects supported by charity as the developers do want the software available to anyone but can encourage donations without needing a separate fairly easy to pirate Freemium edition. The Tragedy of the Commons (freeloading) could be discouraged to a fair extent without guilt-tripping or rat poisoning, by adjusting the proof-of-work cost relative the value of the application or service.

Example 1: A commercial stock market estimation tool licensed per month. If the user forgoes paying for a subscription, the estimation occurs at 1% the normal rate.

Example 2: A free Triple A co-op video game runs twice fast if the user donates some money once a year.

In either example the user must decide between accepting the default speed; spending money on a faster computer/cloud services; or contributing to the upkeep of the product.

Question

Does the hypothesis hold and has anyone attempted to explore or implement this hypothesis?

Any example of an open source library or application that attempts to implement the hypothesis qualifies as a sufficient answer (from my perspective); as I could dissect the code.

* Which has a variety of issues for the Digital Divide, but that's another story

$\endgroup$
  • $\begingroup$ What are you trying to achieve? (The question makes it sound a little like you are starting with a hammer and looking for a nail.) Also, I don't understand the core idea. I'm familiar with what proof-of-work means in the crypto/security community; is that what you're referring to? I don't know what you mean by the first few sentences of the question. Overall, I find the question hard to follow, personally. $\endgroup$ – D.W. Oct 18 '13 at 17:47
  • $\begingroup$ @D.W. I've overhauled and cleaned up the question, now that it's been migrated to the comp.sci stack exchange. $\endgroup$ – LateralFractal Oct 19 '13 at 1:17
  • 1
    $\begingroup$ Ahh, that helped a lot! Thank you for the excellent revision. $\endgroup$ – D.W. Oct 19 '13 at 3:55
3
$\begingroup$

Hypothesis

  1. 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.
  2. Such converted proof-of-work algorithms can support proof-of-work shortcuts.
  3. 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.

$\endgroup$
  • $\begingroup$ Interesting +1. Especially the corollary "and then simply verify that he ran the verifier" which incidentally answers another of my questions on the Information Security stack exchange (some free votes for you over there ;-)). I'll read through the linked articles, but to confirm - Assumption 3 applies in that a freeloader couldn't calculate or extrapolate a more efficient version of the business logic? Remember that server only enhances the client-side app, the app should be able to run without the server. $\endgroup$ – LateralFractal Oct 21 '13 at 8:17
  • $\begingroup$ @LateralFractal yes, though you can run the program faster, if you somehow found a method, you cannot provide the proof that you ran it, if you don't do every step of the given program. I specifically asked Eli Ben-Sasson this myself. Also, yes, you can run the program without the server; if I understand your question. Just keep in mind, that running the program will be a drop slower (I think by a constant, maybe also a logarithmic factor, I don't remember) than a native program, because of the VM/tracer/proof overhead. $\endgroup$ – Realz Slaw Oct 21 '13 at 13:02
  • $\begingroup$ Good. As this then means the entire hypothesis holds and you could create an app runs at one speed alone and another speed if drip-fed shortcut results from a server; while the app can not be reversed into the original non-retarded code; even with a GPU-cluster farm for reverse-compiling. ("retarded" meant in the 'slow-down' sense, not in the Nelson sense) $\endgroup$ – LateralFractal Oct 21 '13 at 13:09
  • $\begingroup$ @LateralFractal I actually just thought of another answer to both questions :D. $\endgroup$ – Realz Slaw Oct 21 '13 at 13:18
  • $\begingroup$ Hate to rain on the parade, but.... This kind of solution is very interesting but not yet anywhere near practical. Even with the state-of-the-art schemes, for general-purpose computation, it's slower for the server to check the proof from the client than to just do the computation himself. Therefore, the server isn't getting any benefit from outsourcing this work. (There are some schemes that do provide a benefit if the computation you want done has a very special form, but you'd have to get really lucky for your application business logic to have that form.) $\endgroup$ – D.W. Oct 21 '13 at 14:33
3
$\begingroup$

Another idea, similar to SCIP, is secure multi-party computation, which can provide a similar ability via secure function evaluation. This is essentially a function that you can run on an untrusted machine, without revealing the input-values. The function can provide an "easy-out" shortcut function via some one-way/trapdoor answer, same as above in my previous answer. Wikipedia lists some implementations.

A related and more powerful idea is fully homomorphic encryption. HElib was released by IBM. hcrypt is an effort to create a project for fully homomorphic encryption called Scarab and a project called Secure Function Evaluation which does what its name suggests.

$\endgroup$
  • $\begingroup$ Can it reveal the outputs to the untrusted machine while not revealing the inputs? If so, this also meets the hypothesis quite well, as the secure function evaluation generates a slow result (say, needless calc loops) if using pre-cached/prepackaged inputs publicly provided to the client, but a fast result if provided one-time-unique inputs from the SaaS. I'm starting to wonder if there was fourth point of the hypothesis that I missed: 4. The client having sent a 'speed up' RPC to the server, can not infer the secret shortcut from the calculation results returned by the server. $\endgroup$ – LateralFractal Oct 21 '13 at 13:46
  • 1
    $\begingroup$ @LateralFractal yes, it needn't reveal outputs or inputs; they are both encrypted, the client doesn't know the data is computing with. I am thinking that the shortcut would simply take an entirely different branch or somesuch, like the program from my other answer. $\endgroup$ – Realz Slaw Oct 21 '13 at 13:56
  • $\begingroup$ Yes, secure multi-party computation and fully homomorphic encryption are "a thing", but they're not helpful for this question because they're much too slow. They're not going to be useful in the setting that the original author had in mind. Even with state-of-the-art schemes, it is much faster to just compute the function yourself than to give it to another party and have them help compute it using one of these schemes. $\endgroup$ – D.W. Oct 21 '13 at 14:30
  • $\begingroup$ @D.W. yes, but it can be useful for POW, where you don't care about the usefulness of the computation. $\endgroup$ – Realz Slaw Oct 21 '13 at 14:40
  • $\begingroup$ @RealzSlaw, maybe, but that's not this question. This question is specifically about POWs where the computation is useful (to the server). This question is asking whether you can convert part of the computation done by the server into a useful POW. If the computation isn't useful for the application, (a) it's out of scope for this question, and (b) at that point you might as well use the standard hash-based POW schemes (e.g., hashcash) rather than anything complicated based upon your application. $\endgroup$ – D.W. Oct 21 '13 at 14:43
1
$\begingroup$

I'm skeptical of the hypothesis. I suspect you'll find it is difficult to make this work, in most applications.

For this to be useful, you need to have a small unit of difficult computation that's needed by the server, and can be safely and efficiently outsourced to a client. Suppose you identify some computation in the server, say computing $y=f(x)$, where $f$ is some function (some computation to be run) on some inputs $x$. You are hoping that you will be able to outsource this computation to clients, by giving a client a value $x$ and having them compute $f(x)$ for you. But let's look at all the requirements that must hold, for this to be a net win for your application:

  1. It has to be cheaper for the server to send $x$ to a client and receive $y$ in response than for the server to just compute $f(x)$ himself. In other words, the computation-to-communication ratio has to be very high (where the computation cost is the cost of computing $f$, and the communication cost is the cost of sending $x$ and $y$ over the network).

  2. The server has to have some way to verify that $y$ was computed correctly. For instance, it has to be easier to verify that $y$ is the right answer than to compute it from scratch -- this is true for some functions $f$, but only in special cases. Alternatively, the server could give the same $x$ to many clients and check that it gets the same answer from all of them (but then it becomes vulnerable to Sybil attacks). Alternatively, the computational process must be chosen so that it doesn't matter if the value $y$ is incorrect (but why would you be doing the computation if that was OK?).

  3. The value $x$ has to be something that isn't confidential and is OK to hand to arbitrary clients.

  4. The computational process has to be a pure mathematical function, with no side effects. $x$ has to include all of the data that the computation might read.

I think what you'll find is that, in most applications, it is difficult to identify computational tasks that satisfy all of these requirements.

For instance, many server operations are data-intensive: they have a large working set of state that could possibly be read in response to any given event, so the size of $x$ would be very large. Those kinds of computations won't be a good fit. That's just one example of a challenge. There are many others.

So, I certainly don't rule out the possibility that in some specific applications you might find an opportunity to outsource work to clients. But, as a general rule, it's harder than it might seem to find opportunities to do so.

$\endgroup$
  • $\begingroup$ I know you gonna love my answer @D.W. $\endgroup$ – Realz Slaw Oct 21 '13 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.