メモリ読み込み・書き込みの一貫性

メモリ読み込み・書き込みの一貫性

概要(WIP)

Memory Consistency Checks (MCC)は、zkVMのread/write operationにおける一貫性を証明する重要なパーツです。

M: Memory Size N: Number of Memory Access

Note: SpiceとNebulaのfixed costsは回路上で行う必要があるWSとRSのInitializeとFinalizeのコストで、Joltの方はGKRにこのコストがかかるはず。

Paper	Access Efficiency	Fixed Costs	Space Efficiency	IVC	Techniques	Proof System
TinyRAM ..etc	O(log M)	-	O(M)	△	MerkleTree	Only R1CS, CCS, ..etc
Spice	O(1) hash	O(M) hash	O(1)	○	Multiset Hash	Only R1CS, CCS, ..etc
Nebula	(O1) filed ops	O(M) filed ops	O(1)	◎	Multiset Fingerprinting	Two-Layered IVC + Commitment-Carrying IVC
Jolt/Lasso	(O1) filed ops	?	O(N)	×	Multiset Fingerprinting + Ground Product	LogUp Optimisation + GKR
Proofs for Deep Thought	(O1) filed ops	?	O(1)	◎	Updating Lookup Table using differential Δ in LogUp	ProtoStar + IVC-Friendly GKR