ZK protocols use special hash functions that are algebraically simple. But if our proof system supported lookup tables, could we do better? Introducing Polocolo: a new ZK-friendly hash function for PlonKup, co-authored by Zellic Cryptographer @baaaaaarkingdog.
Bei ZK-freundlichen Hash-Funktionen sind die Funktionen algebraisch einfach, um die Effizienz zu gewährleisten. Ein Angriff auf eine ZK-freundliche Hash-Funktion konzentriert sich also auf das Problem der eingeschränkten Eingabe und Ausgabe (CICO), da die Lösung des Gleichungssystems in der Regel der effektivste Angriff auf ZK-freundliche Hash-Funktionen ist. Obwohl die Designer ihre Strukturen und Parameter sorgfältig mit diesen Angriffsvektoren im Hinterkopf wählen, ist es dennoch häufig, dass ZK-freundliche Hash-Funktionen angegriffen werden.
Wenn das ZK-Beweissystem nur Additions- und Multiplikationsgatter zulässt, erfordern Operationen, die algebraisch nicht dargestellt werden können, einfach eine große Anzahl von Einschränkungen. Aber wenn das ZK-Beweissystem Lookup-Gatter unterstützt, wird die erforderliche Anzahl von Gattern dramatisch reduziert. Der Hauptvorteil der Verwendung von Lookup-Gattern in ZK-freundlichen Hash-Funktionen besteht darin, dass sie nicht auf einfache algebraische Weise ausgedrückt werden, was Widerstand gegen algebraische Angriffe bieten kann.
Reinforced Concrete ist die erste lookup-basierte ZK-freundliche Hash-Funktion, die aus Schichten von Ziegeln, Beton und Stangen besteht (hier werden Lookup-Tabellen verwendet). Ein wesentlicher Nachteil ist jedoch die hohe Kosten für die Auswertung der Stangen-Schicht in einem ZK-Setting. Von den 15 Schichten in Reinforced Concrete ist nur eine die Stangen-Schicht. Es ist wünschenswert und natürlich, eine einfache Schicht über mehrere Runden zu iterieren, da die Reduzierung der Kosten der Stangen-Schicht und die Iteration über mehrere Runden die Sicherheit erhöhen und einen Kompromiss zwischen Effizienz und Sicherheit ermöglichen kann. Dies motiviert das Design von Polocolo.
Um die hohen Kosten in der Bars-Schicht zu adressieren, wurde ein alternativer Ansatz vorgeschlagen, der als Power Residue-Methode bezeichnet wird. Polocolo ist eine lookup-basierte ZK-freundliche Hash-Funktion mit einer anderen Design-Rationale. Der Name Polocolo leitet sich von Power Residue für kostengünstigere Tabellenabfragen ab.
Die Methode der Potenzreste wendet effizient Lookup-Tabellen auf Fp-Elemente für eine große Primzahl an: p(≈2^256). Die S-Box, die mit der Methode der Potenzreste erstellt wurde, hat einen hohen Grad und benötigt nur 14 PLONK-Gatter, was erheblich weniger ist als die 94 Gatter, die für die Bar-Funktion aus Reinforced Concrete erforderlich sind. Mit dieser S-Box schlagen wir Polocolo vor, eine neue Lookup-basierte ZK-freundliche Hash-Funktion.
Polocolo wurde von dem Zellic-Kryptographen @baaaaaarkingdog, einem Mitglied des KAIST CryptLab, zusammen mit anderen Forschern aus demselben Labor entworfen. In Teil 2 werden wir die detaillierten Spezifikationen und die Kryptoanalyse von Polocolo vorstellen, zusammen mit einem Leistungsvergleich mit anderen ZK-freundlichen Hash-Funktionen.
224