ProtoStar
ざっくりまとめると
Split accumulation scheme
ProtoStarのIVCの構成方法は、split accumulation schemeに基づいている。split accumulation schemeとは、"PCD by non succinct arguments"(2020) (https://eprint.iacr.org/2020/1618) で導入されたテクニックで、verifierはaccumulationの一部(public input)しか参照しない。元々NARKにしか適応できなかったが、ProtoStarはSpecial Sound Protocolへ拡張することで、Fiat-Schamir変換が含まれたプロトコルが扱えるようになり、permutation argument/custom gate/lookup table を扱える柔軟性を獲得した。 https://scrapbox.io/files/6465cb1f456979001b94bbbc.png
Special sound protocol
Special sound protocolとは、ざっくりいうと「Prover-Verifier間のメッセージを何度か見ると、Proverが使ったwitnessが抽出できるプロトコル」のこと。special soundnessはknowledge soundnessを保証する。
knowledge soundnessよりも証明が簡単なので好んで使われるよう
https://scrapbox.io/files/646513664ac049001b504900.png
例えば、permutation argumentを証明する次のプロトコルはspecial sound
https://scrapbox.io/files/6467d5e1d01324001b3cae54.png
witnessをそのまま送るので、proverとverifier間のやりとりからwitnessが復元できるnunocloth.icon
Accumulation/folding
Protostarの肝となる部分がspecial sound protocolのfolding。これはNovaとほとんど同じ方法で実行できる。 Proverがcross termのcommitmentをverifierに渡すだけ。
https://scrapbox.io/files/6467d6cd9af481001c82e873.png
非均一IVC
HyperNovaでも同様の方法で非均一IVCが構成できる？nunocloth.icon
まとめ
Novaの一般化を行っている印象。HyperNovaはCCSという具体的な制約を導入しているが、ProtoStarではそのような具体的な制約を与えず、一般的な多項式制約の状態で論を進めている。またcompression proofは、HyperNovaの場合は(Super)Spartanを使うという明確な方針があるが、Protostarはそういうものがなく、どうすれば良いのかわからない。 HyperNovaよりも抽象化されていて、理論的にはエレガントであるものの、抽象化されている故にどのように実装するのかが悩ましいプロトコルという感じnunocloth.icon