Verifiable Computation

例えば、laptopでは厳しい大量の計算をcloud probiderに代わりに計算を行ってもらって計算結果を受け取る。

ただし、この時、移譲した計算が正しくcoud providerに行われたという保証がないという問題。

全てのデータが計算されたのか？

計算結果はあっているのか？

そもそも不正なcloudではないのか

Verifiable Computationの理想としては、

ユーザー（検証者）はそのinput dataを読み込むだけ。

検証作業の最小化

cloud（証明者）はその問題をただ解くだけ。

証明作業の最小化

approach

interactive proofs

GKR protocol

argument systems

PCPs(probabilistically chekable proofs)が源泉

front-end

どのくらいexpressiveか

プログラミングはどのように行うか

どのようにしてtranslationを行うか

異なるプログラム構造のコスト

プログラムはどのように外部stateを参照するか

circuits with repeated structure

circuits without repeated strucutre

circuit with non-deteministic input : ↑ASIC

universal circuits : CPU

back-end

どんなタイプのcircuitを扱うことができるか

なんの仮定を必要とするか

zkなどの性質を必要とするのか

messageの数はどのくらいか

コストはどのくらいかかるのか

コストは分割できるのか

どのような機構か（抽象化可能か）

interactive proof : より仮定が強くなる

interactive argument

cs-proof

snarg

snark

stark

https://gyazo.com/c50f53b5951f76a009159d3068c9a38b

https://gyazo.com/b5441b0a26647b7d70008d13d4b03cb4

open problems

expensiveでない標準的仮定に基づいたZK

より効率的なprogramからcircuitへのreduction

より効率的なexecution traceのencoding

circuitを必要としない確率的証明プロトコル

expensiveでない方法でpreprocessingを避ける手段

circuitの検証を統合した計算のアウトソースのためのspecial-purpose アルゴリズム

STARKs vs Hyrax vs ZKB++

STARKs

Reed-Solomon codesに基づいた非標準的仮定

state-machine transitionsのsequenceとして表現されたcircuitの検証に最適化している

Hyrax

quantum-susceptible

verifier is not scalable

ZKB++ , Ligero

verifier is not scalable

MPCs

proverのcircuitのmemoryがボトルネックに

10^7 -> x100 : DIZK

https://gyazo.com/115cbe2ba0fed1b2fa9534e377b57920

https://gyazo.com/cb16b3ededea91c75e654b45c95859f0

Modern Verifiable Computation

A Survey of Verifiable Computation

https://youtu.be/qiusq9R8Wws