Punctul cheie este că folosesc un circuit universal acolo:
Când construim un SNARK pentru circuitul SAT, folosim un QSP pentru a circuit universal, care are dimensiune $O(|C| \log |C|)$ Unde $|C|$ este dimensiunea maximă a circuitelor din problema satisfacabilității.
Un circuit universal este unul care poate calcula orice alt circuit. Această generalizare este locul în care intervine factorul logaritmic suplimentar. Acest lucru este explicat la începutul secțiunii 3:
Pentru a compara direct cu Groth, ne putem descurca $u$ fiind un circuit ales adaptiv prin construirea $R$ [(o relație)] din a
circuit universal. În acest caz, dimensiunea circuitului de calcul $R$ poate fi mai mare
decât $|u|$ printr-un factor logaritmic, care crește în mod corespunzător dimensiunea CRS și calculul probei la $\tilde{O}(|u|)$. Dacă $u$ ... poate fi ales neadaptativ, schema noastră devine mai eficientă.
The $\tilde{O}$ notația ascunde factori logaritmici. La final se menționează că cunoașterea circuitului specific $u$ ar fi mai eficient - asta ai in vedere. Motivul corectitudinii adaptive este că aceasta modelează mai corect modul în care protocolul ar fi probabil utilizat în situații reale - de multe ori v-ați aștepta ca probatorul să vadă CRS-ul înainte de a începe demonstrația, astfel încât să poată alege afirmația care este (poate în mod fals). încercând să demonstreze pe baza CRS (adaptiv).
Această hârtie explică o construcție eficientă a circuitelor universale și oferă o explicație a modului în care funcționează astfel de circuite în preliminarii (de exemplu, vezi paginile 4-7). Intuitiv, factorul logaritmic este introdus deoarece aceste circuite tind să fie construite recursiv, fiecare sub-problemă având aproximativ jumătate din dimensiune, deci avem factorul logaritmic obișnuit pe care îl obținem atunci când avem de-a face cu arbori binari. Pentru o explicație mai bună, cred că lucrarea în sine este cel mai bun lucru de citit.
