任意の計算上の問題を作業証明に変換できますか?

cryptocurrencyのマイニングの一見無意味さは有用な選択肢の問題を提起しました。これらの質問は
MO
の作業証明問題。 私は、実用的に任意の計算上の挑戦$ mathcal C
$(その解を効率的に検証することができる)を別のそのような挑戦$ Psi( mathcal
C)$に変換するアルゴリズムが存在するかどうか疑問に思う。 ) そのような

  1. 関数$ Psi $は、(公開)ランダムシーケンス$ r $を使用してランダム化されています。
  2. $ Psi( mathcalC)$を解くことは、 mathcalC
    $を解決するのと同じくらい難しい通常です。
  3. $ Psi( mathcal C)$に対して解$ x $が見つかった場合、元のチャレンジ$ mathcal C
    $に対して解$ Psi ^ { – 1}(x)$を効率的に計算できます。
  4. $ mathcalの解を知るC $は$ Psi( mathcal C)$の解を見つけるのに役立ちません。

コメントにNoahが指摘しているように、前処理は、$ mathcal C
$の前処理でも何も指定しないようにする必要があるという前提条件を強化する必要があります($ {> $ Psi(
mathcal C)$を解く利点があります。

この最後の条件は、$ mathcal C $の解を知っているので誰も有利な位置に置かれないようにするために必要です。
この方法を使うと、人々は解決したい計算上の問題を提出することができ、中央の権威は解決の価値のあるものを選ぶことができます。
問題が解決するまでに1週間もかかる場合(これらのエイリアンは隠れているとは限りません)、解決策に大きな報酬をもたらす可能性があるため、問題ではないように注意してください。
とにかく、これらのトピックは私の理論的な問題の解決には関係しませんが、私はコメント/フォーラムでそれらを議論することはもちろん嬉しいです。

可能な解決策は、$ Psi $が$ mathcal C $を$( mathcal
C、HASH_r)$に写像することです。つまり、$ mathcal C $と計算上困難な問題を解決するためです。
この問題の1つの問題は、$ mathcal C $の解を知ることで、$ Psi( mathcal
C)$をやや簡単に解くことができることです($ HASH_r $の難しさによりますます簡単になります)。 別の問題は、$
Psi( mathcal C)$が$ mathcal C $よりも難しくなったことです。

ベストアンサー

:AndreasBjörklundは、下記の説明よりも優れていると思われるコメントの解決策を提案しました。
http://eprint.iacr.org/2017/203
です。要するに、彼らは硬度のある直交ベクトルのような問題に基づいて作業の証明を与えますそれらのPoWのインスタンス$ Psi(
mathcal {C})$は、最悪のケースの直交ベクトルと同じくらい難しいです。インスタンス$ mathcal {C}
$は簡単なので、以下で説明する解の大きな欠点を避けることができます。

以下に説明する解決策は、その単純さから利益を得るかもしれません—それは非専門家に説明することができますが、理論的にはあまり面白くないようです。)

「$ mathcal {C}
$の最速アルゴリズムが根本的にランダム化されている」という強力な仮定を立てるならば解が可能です(暗号ハッシュ関数をランダムなオラクルとしてモデル化する場合)。これを正式化する1つの方法は、

  1. $ mathcal {C} in mathsf {TFNP} setminus mathsf {FP}
    $(そうでなければ、それは本当に有効な課題ではないと思います。
  2. $ mathcal {C} $の最速ランダム化アルゴリズムは、通常のインスタンスの予想時間$ T
    $で実行されます。
  3. $ {0,1 } ^ k $から$ {0,1 } ^ k
    $までの効率的に計算可能な関数が、常にそこに存在するように$ mathcal {C} $を$ k approx log_2
    T $ $ mathcal {C} $の解である$ f(s)$で {0,1 } ^ k $に s が存在する。

$ k approx log_2 T $という仮定は、$ {0,1 } ^ k
$のブルートフォース探索が本質的に$ mathcal {C}
$の最適アルゴリズムであることを示していることに注意してください。だから、これはかなり強い前提です。一方、$ mathcal
{C} $がこれらのプロパティを満たさない場合、条件(2)と条件(4)の両方を満たすことは想像もつきません。

次に、私たちがランダムなオラクルとしてモデル化するハッシュ関数$ H: {0,1 } ^ * {0,1 } ^
k $が与えられたら、$ Psi_H( mathcal {C} ; r)$ここで、$ { 1,1 } ^ ell
$はいくつかの$ ell gg k $は$ Psi_H $へのランダム入力です。目標は、$ f(H(r、x))$が$
mathcal {C} $の解であるように {0,1 } ^ * $で$ x
を出力することです。つまり、$(r、x)$は、上記のアルゴリズムでは「良いランダムコイン」にハッシュする必要があります。

これがあなたのすべての条件を満たすことを見てみましょう。

  1. “関数$ Psi $は、(公開)ランダムシーケンス$ r $を使用してランダム化されています。”チェック!
  2. 「$ Psi( mathcal {C})$を解くことは、通常、 mathcal {C} $を解くほど難しいです。
    $ Psi_H( mathcal {C}、r)$の単純なランダム化アルゴリズムは、予想される$ 2 ^ k
    $に多項式オーバヘッドを加えて実行され、$ 2 ^ k approx T $は本質的に実行時間$ mathcal {C}
    $の最適なアルゴリズムです。
  3. “解 x Psi( mathcal {C})$に対して解$ x $が見つかった場合、元のチャレンジ$ Psi ^ {
    – 1}(x)$を効率的に計算できます。 mathcal {C} $。 “これは、仮定によって$ mathcal {C}
    $の解である$ f(H(r、x))$を計算することによって行うことができます。
  4. 「$ mathcal {C} $の解を知っていても$ Psi( mathcal
    {C})$の解を見つけるのには役に立たない」定義上、$ Psi_H( mathcal {C}; r)$を解くには、$
    f(H(r、x))$が$ mathcal {C} $の解であるような$ x $を求める必要があります。ランダムなオラクルとして$
    H $をモデル化したので、$ H
    $がブラックボックスによって与えられているクエリ問題の最適な予想されるクエリ複雑度によって、この問題を解決するアルゴリズムの予想実行時間を下げることができます。同じ問題に対する解決策を見つけるように頼んだ。また、$
    H $はランダムなオラクルなので、期待されるクエリの複雑さは、解(一定係数まで)である {0,1 } ^ k
    $の要素の部分の逆数にすぎません。仮定すると、$ mathcal {C} $に対する任意のアルゴリズムの最適な予想実行時間は$ T
    approx 2 ^ {k} $であり、この分数は$ 2 ^ { – k} $を大きく上回ることはできません。 {0,1 }
    ^ ell $の$ ell gg k $と$ r は一様にランダムに選択されているので、これは$ H $と$
    mathcal { C} $(但し、$ r $ではなく)であり、特に$ mathcal {C}
    $の解を事前に知っていても当てはまります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です