Ringkasan Fflonk

Sistem bukti Plonk, diperkenalkan pada 2019, mengabstraksi rangkaian polinomial lengkap. Nantinya, custom gate dan lookup table ditambahkan di sistem Plonk. Teknik-teknik ini pada dasarnya mengabstraksi lebih banyak polinomial. Kemampuan ekspresi polinomial ini lebih kuat, yang dapat mengabstraksi proses perhitungan yang relatif kompleks menjadi polinomial yang lebih rendah, sehingga menghemat banyak gerbang Plonk. Dengan meningkatnya penggunaan teknologi gerbang khusus dan tabel pencarian, lebih banyak polinomial dan lebih banyak titik terbuka muncul di sistem Plonk.

Untuk satu hal, sistem blockchain sangat sensitif terhadap kerumitan verifikasi. Di sisi lain, sistem komitmen polinomial yang berbeda memiliki kompleksitas verifikasi yang berbeda untuk jumlah polinomial dan jumlah titik terbuka. Oleh karena itu, perlu untuk membandingkan sistem komitmen polinomial.

(1) kompleksitas verifikasi komitmen KZG berhubungan linier dengan jumlah polinomial dan jumlah titik terbuka. Dengan tidak adanya gerbang kustom dan tabel pencarian, sistem Plonk menggunakan komitmen KZG untuk memverifikasi kompleksitas 2 peta bilinear dan 18 operasi multipoint .

(2) kompleksitas verifikasi komitmen Dan hanya terkait dengan jumlah polinomial, bukan jumlah titik terbuka. Dengan tidak adanya gerbang khusus dan tabel pencarian, sistem Plonk menggunakan komitmen KZG untuk memverifikasi kompleksitas 2 peta bilinear dan 16 operasi multipoint.

Untuk komitmen KZG dan komitmen Dan, jika tabel pencarian dan teknik gerbang khusus digunakan, penghitungan poin berganda akan semakin ditingkatkan.

(3) Menggunakan Fflonk untuk menggabungkan beberapa polinomial menjadi satu polinomial, lalu menggunakan komitmen Dan. Sistem plonk hanya membutuhkan 2 peta bilinear dan 5 operasi multipoint . Selain itu, dengan tabel pencarian dan gerbang khusus, kompleksitas verifikasi tidak bertambah dan konstan. Oleh karena itu, teknologi Fflonk yang dipadukan dengan komitmen Dan merupakan solusi optimal dalam sistem Plonk.

Bagaimana itu bekerja

Fflonk mengonversi m polinomial f1(X),…,fm(X) yang membuka n poin a1,…,an menjadi ekuivalen dengan 1 polinomial F(X) yang membuka m*n poin b1,…,b_n*m.

Prinsipnya adalah sebagai berikut: kami mendefinisikan operator dan mengelompokkan bersama dan mendekomposisi polinomial "gaya FFT":

Perhatikan bahwa ini adalah operasi injektif dan invers. Artinya, untuk apa saja

Notasi tentang akar

Lemma sederhana berikut adalah dasar dari skema kita.

Kemudian ubah 1 polinomial F(X) buka n*m poin b1,…,b_n*m. menjadi ekuivalen dengan 1 polinomial L(X) membuka 1 poin a.

Prinsipnya adalah sebagai berikut:

Singkatnya, kami akhirnya menyederhanakan menjadi 1 polinomial L(X) yang membuka 1 poin a, yang dapat dilakukan dengan menggunakan sistem komitmen KZG.

Untuk lebih jelasnya, silakan baca makalah dan video aslinya , dan selamat datang untuk berdiskusi di sini.