プルーフ・オブ・ワークとはコンセンサス・アルゴリズムの1つです。

P2P（ピアツーピア）ネットワークにおいて何を発言権として認めるか？という問題に対してのひとつの回答です。古典的なP2PではIPアドレスひとつごと、プロセス1つごとなどに発言権がありましたが、ビットコインではこれをCPUの計算量に応じて発言権を与えることにしました。

具体的には多大な計算量を要する問題（＝特定の条件を満たすハッシュを探す）を最初に解いたものに発言権（＝ブロック）を与えています。

ビットコインネットワークに偽の情報を受け入れさせるためには過半数の発言権を手に入れなければなりませんが、そのためにはネットワーク全体の半分以上のCPUパワーが必要となります。また過去にさかのぼって改変するのは指数関数的に難しくなるためビットコインネットワークに対する攻撃は事実上不可能といえます。

より一般的にプルーフ・オブ・リソースという概念があり、PoWはその一形態といえるでしょう（CPUリソースという意味で）。

アルトコインでよく利用されるのがプルーフ・オブ・ステーク（PoS)です。これは利害関係に基づき発言権を与えるモデルで大まかにいうとコインの保持量に応じて発言権を認めるというのに似ています。PoSではPoWと違って無駄な電力消費を抑えるというメリットがあります。ただPoS単独ではなくPoWやほかの概念と組み合わせて使われることが多いようです。