Perkenalan

Pada postingan kami sebelumnya, kami memperkenalkan konsep SNARK dan properti dasar yang diperlukan. Dengan mengingat tujuan utama dari seri posting ini, yaitu: bagaimana membangun zk-SNARK untuk perhitungan apa pun, kami memperkenalkan dalam posting ini pembuatan SNARK untuk membuktikan pengetahuan tentang polinomial. Kami akan melakukannya langkah demi langkah berangkat dari satu konstruksi yang tidak akan memenuhi semua persyaratan dan mengakhiri protokol yang akan menjadi SNARK tanpa pengetahuan “penuh”.

ZK-SNARKs untuk polinomial

Kami akan membangun zk-SNARK selangkah demi selangkah, mulai dari konstruksi yang lebih sederhana yang bukan SNARK, dan kemudian memperbaikinya dengan teknik baru hingga kami mencapai tujuan kami.

Langkah pertama: lemma Schwartz — Zippel

Kami ingin membuat protokol yang memungkinkan pembukti P untuk meyakinkan pemverifikasi V tentang pengetahuan tentang polinomial tertentu dengan derajat n dengan koefisien dalam bidang terbatas F. Dengan kata lain, P ingin meyakinkan V bahwa dia mengetahui polinomial dalam bentuk

Mari kita asumsikan bahwa a_1, a_2, … , a_n ∈ F adalah n akar dari polinomial ini, sehingga p(x) dapat ditulis sebagai

Mari kita asumsikan bahwa V mengetahui d < n akar polinomial p(x).

Kemudian kita dapat merumuskan kembali masalah kita: sekarang P ingin membuktikan kepada V bahwa ia mengetahui polinomial h(x) sehingga

Polinomial t(x) akan disebut polinomial target. Perhatikan bahwa ia memiliki bentuk

Versi pertama zk-SNARK kita didasarkan pada lemma Schwartz — Zippel: misalkan F adalah bidang dan f: F^m → F polinomial multivariabel dengan derajat n. Maka, untuk sembarang himpunan berhingga S ⊆ F:

Apa yang ditunjukkan oleh lemma adalah bahwa jika kita mengambil u ∈ Sm secara acak secara seragam, peluang u menjadi himpunan akar dari f paling banyak adalah n / |S|. Amati bahwa probabilitas ini sangat kecil jika kita menganggap S sebagai bidang terbatas F. Ukuran bidang akan sangat besar dibandingkan dengan n.

Ini mungkin tampak kontradiktif tetapi lemma ini memungkinkan kita untuk membuktikan pengetahuan polinomial f. Kita tidak perlu membuktikan bahwa kita mengetahui semua koefisien dari p tetapi hanya kita yang mengetahui bagaimana menghitung pasangan (s, f(s)) untuk sembarang s ∈ Fm. Schwartz — lemma Zippel memberikan efisiensi yang diperlukan dalam zk-SNARK kami.

Protokol pertama

Kita ingat bahwa P mengetahui polinomial p(x) dan V mengetahui d < n akar dari p(x) atau, ekuivalennya, V mengetahui polinomial target t(x). P juga mengetahui t(x).

Pendekatan pertama kami adalah sebagai berikut:

1. V mengambil nilai acak s dan menghitung t = t(s). V mengirim s ke P.
2. P menghitung polinomial

4. V memeriksa apakah persamaan p = t · h.

Protokol ini benar karena jika P mengetahui polinomial p(x), dia dapat menghitung h(x) dan oleh karena itu P juga dapat menghitung nilai h dan p sehingga p = h · t. Di sisi lain, protokol ini juga efisien, karena lemma Schwartz-Zippel.

Namun demikian, protokol ini tidak kuat karena pembukti dapat menghitung t = t(s) menggunakan polinomial target, bahkan jika P tidak mengetahui p(x),. Dia dapat mengambil h acak dan menghitung p = h · t dan mengirim pasangan (h, p) ke V yang akan menerima pasangan sebagai valid.

Kami mengamati bahwa titik kritis yang memungkinkan P untuk mengelabui V adalah bahwa P mengetahui titik evaluasi s. Trik ini tidak mungkin dilakukan jika P dapat mengevaluasi p tanpa mengetahui titik evaluasi s. Ini membawa kita ke langkah kedua: kebingungan homomorfik, atau persembunyian homomorfik.

Langkah kedua: kebingungan homomorfik

Untuk membuat protokol kami kuat, kami harus dapat mengevaluasi polinomial pada suatu titik, tanpa mengetahui titik tersebut.

Kami akan melakukannya dengan mengandalkan kekerasan masalah logaritma diskrit. Untuk komputer klasik, masalah logaritma diskrit tidak layak secara komputasi: dalam grup siklik G, berorde p dan dihasilkan oleh elemen g, menentukan elemen a sehingga = ga (mod p) untuk yang diketahui.

Jadi dengan asumsi kekerasan polinomial logaritma diskrit, kita dapat mengaburkan nilai a dengan menghitung = ga (mod p). Penerima saja tidak dapat mempelajari nilai a. Hal yang menarik dari teknik ini adalah eksponensial memiliki beberapa sifat homomorfik:

Produk dari dua nilai yang dikaburkan sama dengan kebingungan dari penambahan nilai terkait secara jelas.

Jika kita ingin mengevaluasi polinomial

pada titik x = s tanpa memberi tahu evaluator titik yang tepat, kita perlu mengaburkan seluruh polinomial:

Kita juga perlu menghitung pangkat, dari 1 sampai derajat polinomial, dari semua nilai yang disamarkan untuk x = r, yaitu:

Perhatikan bahwa dengan semua elemen ini, kita sekarang dapat menghitung evaluasi polinomial p yang dikaburkan pada titik x = r. Memang:

Contoh persembunyian homomorfik

Mari pertimbangkan medan hingga F = ℤ127 dan g = 3 sebagai generator. Misalkan P mengetahui polinomial p(x) = 4x2 + 3x + 1 dan bahwa V ingin P mengevaluasi polinomial pada titik x = 2 tanpa membiarkan P mengetahui titik tersebut. Kita dapat melakukannya melalui langkah-langkah berikut:

1. V menghitung semua kekuatan x = 2 dari 0 hingga derajat polinomial, n = 2:

1.b. 32 (mod 127) = 9

1.c. 34 (mod 127) = 81

dan mengirimkan pasangan (9, 81) ke P.

2. P dapat menghitung evaluasi p(x) pada x = 2 tanpa mengetahui nilai x, memang, dengan menggunakan informasi yang diterima dari V ia dapat menghitung:

Protokol kedua

Sekarang kita tahu bagaimana mengaburkan poin sehingga pembukti dapat mengevaluasi polinomial pada titik yang disamarkan itu, kita akan meningkatkan protokol pertama. Kita ingat bahwa P mengetahui polinomial p(x) dan V mengetahui d < n akar dari p(x) atau, ekuivalennya, V mengetahui polinomial target t(x). P juga mengetahui t(x).

Protokol kedua kami adalah sebagai berikut:

1. V mengambil nilai acak s dan menghitung t = t(s).
2. V menghitung dan mengirim ke P kekuatan berikut:

4. Dengan menggunakan nilai , P menghitung g^p = g^{p(s)} dan g^h = g*{h(s)} menggunakan instruksi dari contoh sebelumnya.

5. P mengirimkan g^p dan g^h ke V.

6. V memeriksa apakah identitas berikut berlaku: g^p = (g^h)^t

Perhatikan bahwa cacat yang terdeteksi pada protokol pertama telah diamandemen, tetapi protokol kedua ini belum kuat. Memang P masih dapat menggunakan nilai zp dan zh sehingga z_p = (z_h)^t dan mengirimkannya ke V seolah-olah g^p dan g^h. P dapat melakukannya dengan mengambil r acak, menghitung z_h = g^r dan menyetel z_p = (g^t)^r. Nilai z_p dapat dihitung menggunakan kekuatan yang dikaburkan yang dikirim oleh V.

Untuk menghindari situasi ini, kita perlu memastikan bahwa g^p dan g^h dihitung hanya menggunakan kekuatan obfuscated yang dikirim oleh V.

Langkah ketiga: asumsi pengetahuan eksponen

Ada satu asumsi umum saat mendefinisikan SNARK: mari kita pertimbangkan bilangan prima q sehingga 2q + 1 juga bilangan prima. Mari kita pertimbangkan generator ga dari ℤ_{2q + 1}. Diketahui q, g dan g' = g^, kita ingin mencari pasangan (x, y) sehingga x ≠ g, y ≠ g', dan y = x^. Asumsi pengetahuan eksponen (KEA) mengatakan bahwa satu-satunya cara untuk menemukan pasangan (x, y) adalah dengan mengambil nilai c ∈ ℤ_q, pertama menghitung x = g^c dan kemudian mengambil y = (g')^ C.

KEA berarti bahwa jika seseorang ingin mendapatkan pasangan (x, y), satu-satunya cara untuk melakukannya adalah dengan mengetahui eksponen c sehingga x = g^c. Dengan kata lain, kita hanya bisa mendapatkan pasangan (x,y) dengan properti KEA dengan menggunakan pangkat g.

Menggunakan KEA, protokol di bawah ini memastikan bahwa P mengembalikan kekuatan g tertentu, generator dari subgrup perkalian, yang dikirimkan oleh V:

1. V mengambil nilai acak dan menghitung g' = g^ (mod 2q + 1).
2. V mengirimkan pasangan (g, g') ke P dan meminta pasangan (b, b') sehingga (b, b') = (g, g').
3. P mengambil nilai c dan menghitung b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1) dan mengirimkan pasangan (b, b') ke V.
4. V memeriksa apakah b' = b^ (mod 2q + 1).

P menggunakan pangkat c yang sama untuk g dan g' dan dia hanya dapat menggunakan nilai yang diberikan oleh V.

Protokol ketiga

Kami siap membangun protokol yang tepat yang akan memastikan bahwa pembukti P akan mengeluarkan kekuatan dari nilai s pada domain yang disamarkan.

1. V mengambil nilai acak s dan menghitung t = t(s).
2. V mengambil nilai acak dan menghitung t( · s).
3. V menghitung rangkaian nilai yang dikaburkan berikut dan mengirimkannya ke P.
4. V menghitung rangkaian nilai yang dikaburkan berikut ini

5. P menghitung polinomial h(x).

6. Menggunakan , P menghitung p(s) dan h(s) bersama dengan g^p = g^{p(s)} dan g^h = g^{h(s)}.

7. Menggunakan , P menghitung p(s) dan h(s) bersamaan dengan g^{p'} = g^{p( · s)}.

8. P mengirimkan g^p, g^h dan g^{p'} ke V.

9. V memeriksa bahwa P menghitung nilai-nilai yang dikaburkan hanya dengan menggunakan informasi yang dia kirimkan kepadanya. Untuk melakukannya, V memeriksa apakah g^p = g^{p'}.

10. V memeriksa apakah identitas berikut berlaku: g^p = (g^h)^{t(s)}.

Protokol ini sekarang memenuhi properti yang dibutuhkan oleh SNARK: benar, kuat, dan efisien. Bagian selanjutnya akan membahas non-interaktivitas dan pengetahuan nol.

Catatan: Langkah 6 dan 7 pada protokol di atas dilakukan sesuai dengan contoh pada penyembunyian homomorfik.

Tanpa pengetahuan

Dalam protokol yang kami sajikan sejauh ini, koefisien ci dari polinomial yang diketahui P sangat spesifik, dan V dapat mencoba mempelajari beberapa informasi tentangnya menggunakan gp, gh dan gp' yang berasal dari P. Oleh karena itu, untuk memastikan P bahwa V tidak akan mempelajari apapun, P perlu menyembunyikan nilai-nilai ini.

Strategi untuk menyembunyikan nilai yang dikirim oleh P mengikuti langkah-langkah yang digunakan sebelumnya: P mengambil acak dan menggunakannya untuk menyembunyikan nilai yang dikirim dalam komunikasi dengan V. Tepatnya, alih-alih mengirim g^p, g^h dan g ^{p'}, P menghitung dan mengirim (g^p)^, (g^h)^ dan (g^{p'})^. Kemudian V menjalankan verifikasi pada nilai-nilai yang tersembunyi di bawah .

Prosedur verifikasi yang perlu dijalankan V masih valid dengan penyembunyian ini, memang:

Jadi untuk membuat protokol ketiga tanpa pengetahuan, seseorang mengganti langkah 8 sehingga P dapat mengirim nilai yang disamarkan.

Non-interaktivitas

Protokol berbeda yang kami sajikan memerlukan interaksi antara pembukti dan pemverifikasi, dan ini karena kebenaran protokol bergantung pada nilai rahasia s dan yang dipilih oleh pemverifikasi.

Jika kita ingin mengulangi protokol di atas dengan pemverifikasi lain V', V' perlu memilih nilai baru s' dan '. Menggunakan nilai yang dihasilkan oleh V memungkinkan P untuk menipu jika dia berkolusi dengan V dan V mengungkapkan nilai s dan ke P.

Untuk menghindari situasi di atas, kami membutuhkan protokol kami untuk tidak interaktif dan kami dapat mencapainya dengan menggunakan parameter yang bersifat publik, tepercaya, dan dapat digunakan kembali. Ini dapat dicapai dengan mengaburkan parameter ini menggunakan generator g. Namun demikian, bahkan jika teknik pengaburan yang digunakan adalah homomorfik, mereka hanya mengizinkan penambahan pesan yang jelas menggunakan produk dari nilai tersembunyi, tetapi mereka tidak mengizinkan melakukan produk dari nilai yang jelas di domain yang dikaburkan, dan langkah ini sangat penting saat memverifikasi kebenaran polinomial dan akarnya.

Kami akan memperkenalkan pasangan untuk memecahkan masalah ini. Ingatlah bahwa pasangan memiliki properti berikut:

Properti ini memungkinkan pemeriksaan kesetaraan produk di domain yang disamarkan.

Jadi untuk membuat protokol kami non-interaktif, langkah pertama adalah mengambil nilai acak rahasia s dan dan mengaburkannya: g^, dan .

Setelah kita menghitung kekuatan ini, kita dapat menghilangkan nilai rahasia s dan dan menyiarkan nilai yang disamarkan, yang dikenal sebagai Common Reference String (CRS). Nilai CRS biasanya disimpan sebagai:

1. Kunci evaluasi: (, ).
2. Kunci verifikasi: (g^, g^{t(s)}).

Protokol terakhir: zk-SNARK untuk pengetahuan polinomial

Kita sekarang mendefinisikan zk-SNARK untuk membuktikan pengetahuan tentang polinomial p(x) derajat n dengan target polinomial t(x).

Pengaturan parameter

1. Setiap pihak mengambil dua nilai rahasia s dan secara acak.
2. Masing-masing pihak menghitung g, dan .
3. Nilai s dan dihancurkan.
4. Seseorang menyiarkan kunci evaluasi ( dan ).
5. Seseorang menyiarkan kunci verifikasi g^, g^{t(s)}.

1. Asumsikan bahwa P mengetahui p(x), P menghitung polinomial h(x).
2. P mengevaluasi p(x) dan h(x) dan menghitung gp(s) dan gh(s) menggunakan nilai yang terkandung dalam kunci evaluasi.
3. P menghitung nilai g^{p( · s)} menggunakan kunci evaluasi.
4. P mengambil nilai acak .
5. P menyiarkan bukti π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

Dengan asumsi bahwa V memiliki akses ke π = (g^{ · p}, g^{ · h}, g^{ · p'}), ia memeriksa apakah

Kami berhasil menetapkan protokol yang memenuhi semua properti yang diperlukan dalam definisi zk-SNARK: keringkasan (karena buktinya hanya memeriksa polinomial pada suatu titik), pengetahuan nol, dan non-interaktif (karena menggunakan CRS ).

Generasi CRS

Zk-SNARKs dapat dibuat non-interaktif dengan menggunakan sekumpulan nilai tersembunyi, yang dikenal sebagai Common Reference String (CRS). Nilai tersembunyi ini, yang dalam kasus kita berbentuk dan , berasal dari nilai rahasia, s dan , yang harus dihancurkan setelah nilai tersembunyi diturunkan. Amati bahwa pembuatan CRS sangat penting karena jika seseorang mendelegasikan pembuatannya kepada peserta ketiga, setiap orang perlu percaya bahwa peserta tersebut akan menghancurkan nilai s dan . Pihak ketiga mewakili satu titik kegagalan.

Jika kita ingin menghindari satu titik kegagalan, kita memerlukan cara terdistribusi untuk menghasilkan CRS di mana satu peserta yang jujur ​​sudah cukup untuk menjamin bahwa nilai s dan tidak dapat dipulihkan.

Mari gunakan CRS untuk SNARK yang kita buat di contoh sebelumnya. Kita ingat bahwa menggunakan s dan sebagai rahasia, kita perlu menghitung nilai dan pangkat tersembunyi g^, dan .

Dalam protokol baru kami, kami akan mengganti nilai s dan , yang dihasilkan oleh satu pihak ketiga, dengan nilai s_{ABC} dan _{ABC} yang dihasilkan oleh tiga pengguna A, B, dan C. Memperluas mekanisme ke n pengguna sangatlah mudah .

Protokol berikut:

1. Pengguna A menghasilkan pasangan (sA, A), menghitung dan menyiarkan:

3.B siaran:

4. C mengambil pasangan acak (sC, C), menghitung dan menyiarkan:

Protokol ini menghasilkan nilai tersembunyi untuk s_{ABC} = s_A · s_B · s_C dan _{ABC} = _A · _B · _C tanpa ada peserta yang mengetahui pasangan nilai ini.

Namun demikian, kami memerlukan protokol yang memungkinkan peserta untuk memeriksa apakah nilai-nilai tersembunyi tersebut dihitung dengan benar. Kita perlu memastikan bahwa nilai yang dihasilkan oleh setiap pengguna memenuhi persyaratan, yaitu himpunan nilai adalah kekuatan gs, untuk nilai s setiap pengguna, dan himpunan dihitung dengan benar. Untuk melakukannya, kami memeriksa bahwa setiap (g^s)^i secara efektif adalah pangkat ke-i dari gs. Ini dapat dilakukan dengan memeriksa bahwa persamaan berikut berlaku. Pemeriksaan ini dilakukan oleh setiap peserta untuk semua nilai sU dan U yang terkait dengan setiap peserta U:

Ini bukan satu-satunya verifikasi yang diperlukan. Kami juga perlu memeriksa apakah setiap peserta menggunakan nilai yang benar dari peserta sebelumnya. Untuk melakukannya, setiap peserta akan menggunakan parameter publik tersembunyi dari satu pengguna yang digabungkan dengan keluaran peserta lain. Sebagai contoh, C dapat memeriksa nilai tengah dari CRS yang dihasilkan oleh B, menggunakan informasi CRS dari A, dengan memverifikasi hal berikut:

Kesimpulan

Sejauh ini kita telah mempelajari cara membuat SNARK, dari nol dan dengan detail lengkap, untuk membuktikan pengetahuan polinomial. Di posting kami berikutnya, yang terakhir, kami akan memperluas konstruksi di atas ke perhitungan apa pun. Untuk melakukannya kami akan memperkenalkan dua konsep utama: program aritmatika kuadrat, QAP, dan sistem kendala peringkat-1, R1CS, meskipun yang terakhir tidak akan diperkenalkan secara khusus (akan muncul sebagai pesan subliminal).

Referensi

Jordi Herrera Joancomartí, Cristina Pérez Solà, Criptografia avançada. Catatan kuliah. Universitas Terbuka Catalonia, 2022.