Paranova

paperは出ていない。supernovaやcyclefoldで言及されているparallel provingやparallel IVCと同じかもしれないしそうじゃないかもしれない。

Novaのfoldingで可能だった2to1のfoldingを4in1などに拡張し、並列性を向上させている。

右の図ではF(F(⋯F(za)))=zbという計算を[a,b)と表記している。[b,c)も同様であり、[a,c)はこれら二つのfoldingである。

[a,b)と[b,c)の部分はfoldingではないただの計算なので区別する必要があり、左図のように四角の部分をbase IWPC, 丸い部分がfold IWPCと呼ぶ。(IWPCについては後述する)

ここで点線の部分はfoldingに際し後で証明する必要がある新しい計算を表している。具体的に以下の検証が必要

verifying that the R1CS in the two squares correctly folds to the R1CS in the new upper left computation;

verifying that indeed b=b so the two computations “match” correctly

verifying that the output of the [a,b) computation equals the input of the [b,c)computation.

IWPC

Base (in Nova, (u,w)):

Folded (in Nova, (U,W))

Paranovaの1ノードはbaseとfoldedのペアである。

さらにParanovaはbase nodeとintermidiate nodeという2種類のノードを使用しbinary IVC treeを構成している。

base nodeは(base,base)のペア、intermidiate nodeは(base,folded)のペアといった具合である。

右の図はNovaのFoldingをIWPCで表現したものであり、左の図は2in1だったNovaを4in1に拡張したbinary IVC treeの構成をIWPCで表している

U,uはNovaの表記と一緒であり、P:Parent, L:Left, R:Rightである。

ではなぜ4in1に拡張ができるのか？そもそもなぜNovaでは2in1が限界だったのか？

参考