Hard Problems in Cryptocurrency: Five Years Later

making the proof of work function something which is simultaneously useful; a common candidate is something like Folding@home, an existing program where users can download software onto their computers to simulate protein folding and provide researchers with a large supply of data to help them cure diseases.

Status: Probably not feasible, with one exception.

The challenge with useful proof of work is that a proof of work algorithm requires many properties:

Hard to compute

Easy to verify

Does not depend on large amounts of external data

Can be efficiently computed in small "bite-sized" chunks

Unfortunately, there are not many computations that are useful that preserve all of these properties, and most computations that do have all of those properties and are "useful" are only "useful" for far too short a time to build a cryptocurrency around them.

However, there is one possible exception: zero-knowledge-proof generation. Zero knowledge proofs of aspects of blockchain validity (eg. data availability roots for a simple example) are difficult to compute, and easy to verify. Furthermore, they are durably difficult to compute; if proofs of "highly structured" computation become too easy, one can simply switch to verifying a blockchain's entire state transition, which becomes extremely expensive due to the need to model the virtual machine and random memory accesses.

Zero-knowledge proofs of blockchain validity provide great value to users of the blockchain, as they can substitute the need to verify the chain directly; Coda is doing this already, albeit with a simplified blockchain design that is heavily optimized for provability. Such proofs can significantly assist in improving the blockchain's safety and scalability. That said, the total amount of computation that realistically needs to be done is still much less than the amount that's currently done by proof of work miners, so this would at best be an add-on for proof of stake blockchains, not a full-on consensus algorithm.

有用なプルーフ・オブ・ワーク

一般的な候補は、Folding@homeのようなものである。Folding@homeは、ユーザーが自分のコンピュータにソフトウェアをダウンロードして、タンパク質の折り畳みをシミュレーションし、研究者に大量のデータを提供して病気の治療に役立てることができる既存のプログラムである。

現状：一つの例外を除いて、おそらく実現不可能であろう。

有用なプルーフ・オブ・ワークの課題は、プルーフ・オブ・ワーク・アルゴリズムが多くの特性を必要とすることである：

計算が難しい

大量の外部データに依存しない

小さな "一口サイズ "の塊で効率的に計算できる。

残念ながら、これらの特性をすべて備えた有用な計算はそれほど多くなく、これらの特性をすべて備えた「有用な」計算のほとんどは、暗号通貨を構築するにはあまりにも短い期間しか「有用」ではない。

しかし、ゼロ知識証明生成という例外もある。ブロックチェーンの有効性（簡単な例ではデータの可用性ルーツなど）のゼロ知識証明は計算が難しく、検証も簡単です。高度に構造化された」計算の証明が簡単になりすぎると、ブロックチェーンの状態遷移全体の検証に切り替えるだけでよくなるが、仮想マシンとランダムメモリアクセスをモデル化する必要があるため、非常に高価になる。

ブロックチェーンの有効性に関するゼロ知識証明は、チェーンを直接検証する必要性を代替することができるため、ブロックチェーンのユーザーにとって大きな価値を提供する。このような証明は、ブロックチェーンの安全性とスケーラビリティの向上に大きく貢献する。とはいえ、現実的に必要とされる計算の総量は、現在プルーフ・オブ・ワークのマイナーによって行われている量よりもはるかに少ないため、これはせいぜいプルーフ・オブ・ステーク・ブロックチェーンのアドオンであり、完全なコンセンサス・アルゴリズムではないだろう。