Beberapa waktu lalu saya sedang menerjemahkan buku tentang teknologi tanpa bukti pengetahuan. Konten dasar diterjemahkan pada akhir bulan lalu. Terjemahannya memakan waktu lebih lama dari yang saya perkirakan. Kami sedang mendiskusikan beberapa kesalahan administrasi dalam buku ini dengan penulis dan mempersiapkan draf akhir.
Bagaimanapun, saya akhirnya punya waktu untuk melihat sesuatu yang baru. Mari kita mulai dengan algoritma Nova~
Informasi terkait algoritma Nova
Tiga informasi dapat membantu memahami algoritma Nova:
Kertas baru:
Potensi serangan baru dan koreksi terkait:
Ringkasan pemahaman potensi serangan Nova:
Artikel ini merupakan pengertian dan rangkuman dari informasi di atas. **Beberapa gambar dalam artikel ini berasal dari informasi di atas dan tidak akan diberi label satu per satu di artikel ini. **
Mulai dengan IVC
Algoritma Nova adalah algoritma bukti tanpa pengetahuan baru untuk IVC (Komputasi yang Dapat Diverifikasi Secara Inkremental). IVC, yaitu fungsi yang sama menghitung keluaran sebelumnya secara berulang sebagai masukan berikutnya. Proses perhitungan iteratif fungsi F adalah sebagai berikut:
z0 merupakan masukan awal, dan hasil perhitungan fungsi F digunakan sebagai masukan fungsi F berikutnya.
Santai R1CS dan Slack Commitment R1CS
Seperti yang kita ketahui bersama, R1CS adalah representasi dari batasan sirkuit dalam teknologi tanpa pengetahuan. R1CS yang santai dapat dilihat sebagai bentuk lanjutan dari R1CS. Berdasarkan R1CS, skalar u dan vektor kesalahan E ditambahkan. Sebuah contoh dari R1CS santai diwakili oleh (E, u, x).
Komitmen santai R1CS melakukan vektor E dan W berdasarkan R1CS santai. Contoh komitmen kendur R1CS diwakili oleh (\bar{E}, u, \bar{W}, x), di mana x dan u adalah variabel publik.
Perpanjangan dari R1CS ke R1CS yang santai untuk skema pelipatan. Perhatikan bahwa dari perspektif R1CS yang santai, R1CS adalah kasus khusus. Dengan kata lain, R1CS juga merupakan slack R1CS yang "khusus".
Skema Lipat
Secara intuitif, skema pelipatan untuk suatu relasi R adalah dengan "menciutkan" dua instance yang sesuai dengan relasi R menjadi instance baru dari relasi komposit R. Slack R1CS/Relax Commitment R1CS dapat melakukan lipatan serupa. Proses pelipatannya serupa untuk keduanya. Skema pelipatan Slack Commitment R1CS adalah sebagai berikut:
Seluruh skema pelipatan terdiri dari 4 langkah. Pada langkah pertama, peribahasa P mengirimkan komitmen \bar{T} dari item silang T ke verifikator. Pada langkah kedua, verifikator mengirimkan tantangan acak r ke pembukti. Langkah ketiga adalah pelipatgandaan komitmen yang harus dilakukan oleh pembukti dan verifikator. Pada langkah keempat, pembuktian melakukan sendiri dan menjumlahkan vektor E dan W dari dua contoh.
Fungsi tambahan F' (Fungsi Argumentasi)
Skema ciutkan, instance R1CS yang diciutkan dilonggarkan. Jadi, apa saja perhitungan yang dibuktikan oleh contoh R1CS yang santai ini? Tentunya perhitungan tersebut termasuk perhitungan lipat. Perhitungan ini bukan hanya fungsi F dalam perhitungan IVC, tetapi juga disebut fungsi augmented F'. Perhitungan fungsi augmented F' pada dasarnya terdiri dari dua bagian:
Fungsi 1/F di IVC
2/ Perhitungan lipat dari instance R1CS
Tampilan ideal
Dengan pengertian di atas, bisa dibayangkan proses pelipatannya:
Diantaranya, rangkaian adalah rangkaian yang bersesuaian dengan fungsi augmented F'. acc{1,2,3,4,5,6} adalah instance R1CS dengan komitmen kendur. Sirkuit ini memiliki dua perhitungan: 1/Relakskan pelipatan instance komitmen R1CS, seperti acc1+acc2->acc3. 2/Hitung fungsi F, ubah status dari status1 ke status2, lalu dari status2 ke status3, dan seterusnya.
Perhatikan bahwa rangkaian yang sesuai dengan fungsi augmented F' itu sendiri merupakan turunan R1CS, yang dapat dinyatakan sebagai turunan R1CS santai. Itu adalah acc4 dan acc6 pada gambar. "meringkas" adalah mengubah instance slack R1CS menjadi instance R1CS yang dilakukan secara slack.
Melihat dengan cermat masukan dari rangkaian kedua, acc3 adalah contoh komitmen santai R1CS setelah pelipatan, dan acc4 adalah contoh komitmen santai R1CS yang membuktikan acc3 adalah hasil pelipatan yang benar. Kedua instance ini akan memasuki pelipatan berikutnya dan menghasilkan acc5. Anda dapat membayangkan bahwa jika acc3 dan acc4 adalah contoh R1CS komitmen slack yang dapat dipenuhi, itu berarti bahwa acc3 dilipat dari dua contoh R1CS komitmen slack yang dapat dipenuhi. Dengan kata lain, acc1 dan acc2 adalah contoh komitmen slack yang dapat memuaskan. Keandalan semacam ini dapat disimpulkan "maju" selangkah demi selangkah, sehingga membuktikan bahwa perhitungan fungsi F pada setiap rangkaian sudah benar. Secara umum, melalui kepuasan dua contoh R1CS komitmen slack yang sesuai dengan sirkuit tertentu, semua perhitungan IVC sebelumnya dapat dibuktikan kebenarannya.
Tampilan nyata
Teman-teman yang akrab dengan bukti tanpa pengetahuan tahu bahwa kurva elips sering digunakan dalam skema komitmen polinomial. Komitmen polinomial yang sesuai pada domain skalar diwakili oleh domain dasar kurva elips. Sirkuit R1CS biasanya diwakili oleh domain skalar. Perhatikan baik-baik, "ringkasan" pada gambar di atas melibatkan konversi domain. Artinya, jika Anda ingin melipat instance R1CS komitmen kendur yang terkait dengan suatu sirkuit, Anda harus "melipatnya" di sirkuit lain. Pada saat ini perlu diperkenalkan siklus kurva elips. Di antara dua atau lebih kurva elips, domain skalar suatu kurva sama dengan domain dasar kurva lainnya. Kebetulan domain skalar kurva ini sama dengan domain dasar kurva sebelumnya. Dengan menggunakan lingkaran kurva elips, "tampilan ideal" dapat diwujudkan:
Seluruh proses pelipatan dibagi menjadi dua sirkuit pelipatan. Bagian atas disebut lipatan Sirkuit 1, dan bagian bawah disebut lipatan Sirkuit 2. Representasi formal dari hubungan antara dua sirkuit ada di halaman 8 makalah "Potensi Serangan terhadap Nova dan Koreksi yang Sesuai". U mewakili instance terlipat, dan u mewakili instance santai yang sesuai dengan instance R1CS. Perhatikan bahwa Sirkuit 1 menciutkan instans R1CS komitmen kendur yang sesuai dengan Sirkuit 2, sedangkan Sirkuit 2 menciutkan instans R1CS komitmen kendur yang terkait dengan Sirkuit 1. Tujuan utama Sirkuit 2 adalah untuk menciutkan instance R1CS komitmen kendur yang sesuai dengan Sirkuit1, dan penghitungan fungsi di sirkuitnya tidak ada artinya. Sebaliknya, fungsi F diimplementasikan di Sirkuit 1. Dikombinasikan dengan "penampilan ideal", kita dapat menebak secara kasar kepuasan U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 merupakan bagian penting dari pembuktian.
Karena "rangkaian" tersebut dipotong menjadi dua bagian, dan masing-masing rangkaian tersebut dilipat menjadi rangkaian yang lain. Ada beberapa masalah yang mengikat antar instance: pengikatan antara instance u dan U dan pengikatan instance u yang lewat di antara dua sirkuit. Untuk mengatasi masalah pengikatan ini, variabel publik x_0/x_1 diperkenalkan di sirkuit, di mana x_1 menentukan output rangkaian instance U yang terikat ke instance u dan output dari fungsi F saat ini (untuk menyederhanakan struktur rangkaian, tidak tercermin pada gambar). Anda berpikir, jika hasil H_1 dari instance U dimasukkan ke dalam rangkaian, jika instance u dapat dipenuhi, x_0/x_1 adalah nyata dan dapat diandalkan, artinya, ia "terikat" ke U. x_0 menetapkan hubungan pengikatan antara masukan u dan U, dan x_1 menetapkan hubungan pengikatan antara keluaran u dan U.
Misalnya, ketika u{i+1}^1 digunakan sebagai input paruh kedua rangkaian, ia melewati Sirkuit 2, dan outputnya u{i+1}^2.x0 = u{i+1 }^1.x1, jadi, ketika input ke bagian atas rangkaian, jika u{i+1}^2 dapat dipenuhi, maka x_0-nya harus sama dengan hasil H1 dari U_{i +1}^2. Ini diperiksa di Sirkuit 1. Dengan cara ini, dijamin bahwa instance yang benar dilewatkan di antara kedua sirkuit.
Bukti IVC
Untuk membuktikan bahwa IVC dihitung dengan benar pada iterasi tertentu, informasi berikut perlu dibuktikan secara logis:
Selain membuktikan empat kejadian dapat dipenuhi, perlu juga dibuktikan hubungan pengikatan antara dua x1, seperti terlihat pada gambar berikut:
Benar atau tidaknya informasi ini memerlukan bukti implementasi rangkaian tambahan. Artinya, pembuktian perhitungan IVC merupakan pembuktian rangkaian. Bisa dibayangkan jika ini adalah perhitungan dengan banyak iterasi, awalnya iterasi ini perlu dilakukan di sirkuit satu per satu, tetapi sekarang hanya empat instance sirkuit yang perlu diverifikasi untuk kepuasan dan hubungan yang mengikat. Peningkatan kinerjanya sangat besar.
Koreksi Serangan dan Algoritma
Melihat gambar di atas, saya mempunyai intuisi, saya merasa contoh rangkaian atas dan bawah “terpisah” dan tidak ada ikatannya. Faktanya, beginilah struktur serangannya.
U_i^1 dan U{i+1}^2 yang dipalsukan, meskipun dipalsukan, merupakan contoh yang memuaskan. Tempa u{i+1}^1, modifikasi x_0 dan x_1 agar sesuai dengan instance U palsu. Jelasnya, instance u{i+1}^1 tidak terpenuhi. Meskipun tidak puas, rangkaian Sirkuit 2 masih dapat dipenuhi, tetapi instance keluaran U{i+1}^1 tidak terpenuhi. Jika u{i+1}^2 berhasil dibangun, Sirkuit 1 dapat membangun u{i+2}^1 dan U_{i+2}^2 yang memuaskan, dan memenuhi hubungan pengikatan x1. Dengan cara ini, setengah dari bukti pemalsuan akhir dibuat terlebih dahulu. Melalui simetri, contoh keluaran dari bagian bawah dapat dibangun. Dengan “menyambung” hasil kedua konstruksi tersebut maka pembuktian perhitungan IVC dapat dipalsukan.
Logika pemeriksaan yang direvisi adalah sebagai berikut:
Bab 6 dari makalah "Potensi Serangan pada Nova dan Perbaikan Terkait" memberikan analisis keamanan terperinci. Teman-teman yang berminat bisa mengecek sendiri kertas aslinya.
Ide dasar Nova adalah melipat contoh rangkaian melalui skema pelipatan. Logikanya agak berbelit-belit dan memerlukan pemikiran yang cermat tentang proses pelipatan rangkaian dan hubungan pengikatan dalam rangkaian.
Satu kata untuk menggambarkannya: Mutlak~
Lihat Asli
Halaman ini mungkin berisi konten pihak ketiga, yang disediakan untuk tujuan informasi saja (bukan pernyataan/jaminan) dan tidak boleh dianggap sebagai dukungan terhadap pandangannya oleh Gate, atau sebagai nasihat keuangan atau profesional. Lihat Penafian untuk detailnya.
Kemajuan revolusioner dalam teknologi tanpa bukti pengetahuan: eksplorasi mendalam terhadap algoritma Nova
Beberapa waktu lalu saya sedang menerjemahkan buku tentang teknologi tanpa bukti pengetahuan. Konten dasar diterjemahkan pada akhir bulan lalu. Terjemahannya memakan waktu lebih lama dari yang saya perkirakan. Kami sedang mendiskusikan beberapa kesalahan administrasi dalam buku ini dengan penulis dan mempersiapkan draf akhir.
Bagaimanapun, saya akhirnya punya waktu untuk melihat sesuatu yang baru. Mari kita mulai dengan algoritma Nova~
Informasi terkait algoritma Nova
Tiga informasi dapat membantu memahami algoritma Nova:
Artikel ini merupakan pengertian dan rangkuman dari informasi di atas. **Beberapa gambar dalam artikel ini berasal dari informasi di atas dan tidak akan diberi label satu per satu di artikel ini. **
Mulai dengan IVC
Algoritma Nova adalah algoritma bukti tanpa pengetahuan baru untuk IVC (Komputasi yang Dapat Diverifikasi Secara Inkremental). IVC, yaitu fungsi yang sama menghitung keluaran sebelumnya secara berulang sebagai masukan berikutnya. Proses perhitungan iteratif fungsi F adalah sebagai berikut:
z0 merupakan masukan awal, dan hasil perhitungan fungsi F digunakan sebagai masukan fungsi F berikutnya.
Santai R1CS dan Slack Commitment R1CS
Seperti yang kita ketahui bersama, R1CS adalah representasi dari batasan sirkuit dalam teknologi tanpa pengetahuan. R1CS yang santai dapat dilihat sebagai bentuk lanjutan dari R1CS. Berdasarkan R1CS, skalar u dan vektor kesalahan E ditambahkan. Sebuah contoh dari R1CS santai diwakili oleh (E, u, x).
Komitmen santai R1CS melakukan vektor E dan W berdasarkan R1CS santai. Contoh komitmen kendur R1CS diwakili oleh (\bar{E}, u, \bar{W}, x), di mana x dan u adalah variabel publik.
Perpanjangan dari R1CS ke R1CS yang santai untuk skema pelipatan. Perhatikan bahwa dari perspektif R1CS yang santai, R1CS adalah kasus khusus. Dengan kata lain, R1CS juga merupakan slack R1CS yang "khusus".
Skema Lipat
Secara intuitif, skema pelipatan untuk suatu relasi R adalah dengan "menciutkan" dua instance yang sesuai dengan relasi R menjadi instance baru dari relasi komposit R. Slack R1CS/Relax Commitment R1CS dapat melakukan lipatan serupa. Proses pelipatannya serupa untuk keduanya. Skema pelipatan Slack Commitment R1CS adalah sebagai berikut:
Seluruh skema pelipatan terdiri dari 4 langkah. Pada langkah pertama, peribahasa P mengirimkan komitmen \bar{T} dari item silang T ke verifikator. Pada langkah kedua, verifikator mengirimkan tantangan acak r ke pembukti. Langkah ketiga adalah pelipatgandaan komitmen yang harus dilakukan oleh pembukti dan verifikator. Pada langkah keempat, pembuktian melakukan sendiri dan menjumlahkan vektor E dan W dari dua contoh.
Fungsi tambahan F' (Fungsi Argumentasi)
Skema ciutkan, instance R1CS yang diciutkan dilonggarkan. Jadi, apa saja perhitungan yang dibuktikan oleh contoh R1CS yang santai ini? Tentunya perhitungan tersebut termasuk perhitungan lipat. Perhitungan ini bukan hanya fungsi F dalam perhitungan IVC, tetapi juga disebut fungsi augmented F'. Perhitungan fungsi augmented F' pada dasarnya terdiri dari dua bagian:
Fungsi 1/F di IVC
2/ Perhitungan lipat dari instance R1CS
Tampilan ideal
Dengan pengertian di atas, bisa dibayangkan proses pelipatannya:
Diantaranya, rangkaian adalah rangkaian yang bersesuaian dengan fungsi augmented F'. acc{1,2,3,4,5,6} adalah instance R1CS dengan komitmen kendur. Sirkuit ini memiliki dua perhitungan: 1/Relakskan pelipatan instance komitmen R1CS, seperti acc1+acc2->acc3. 2/Hitung fungsi F, ubah status dari status1 ke status2, lalu dari status2 ke status3, dan seterusnya.
Perhatikan bahwa rangkaian yang sesuai dengan fungsi augmented F' itu sendiri merupakan turunan R1CS, yang dapat dinyatakan sebagai turunan R1CS santai. Itu adalah acc4 dan acc6 pada gambar. "meringkas" adalah mengubah instance slack R1CS menjadi instance R1CS yang dilakukan secara slack.
Melihat dengan cermat masukan dari rangkaian kedua, acc3 adalah contoh komitmen santai R1CS setelah pelipatan, dan acc4 adalah contoh komitmen santai R1CS yang membuktikan acc3 adalah hasil pelipatan yang benar. Kedua instance ini akan memasuki pelipatan berikutnya dan menghasilkan acc5. Anda dapat membayangkan bahwa jika acc3 dan acc4 adalah contoh R1CS komitmen slack yang dapat dipenuhi, itu berarti bahwa acc3 dilipat dari dua contoh R1CS komitmen slack yang dapat dipenuhi. Dengan kata lain, acc1 dan acc2 adalah contoh komitmen slack yang dapat memuaskan. Keandalan semacam ini dapat disimpulkan "maju" selangkah demi selangkah, sehingga membuktikan bahwa perhitungan fungsi F pada setiap rangkaian sudah benar. Secara umum, melalui kepuasan dua contoh R1CS komitmen slack yang sesuai dengan sirkuit tertentu, semua perhitungan IVC sebelumnya dapat dibuktikan kebenarannya.
Tampilan nyata
Teman-teman yang akrab dengan bukti tanpa pengetahuan tahu bahwa kurva elips sering digunakan dalam skema komitmen polinomial. Komitmen polinomial yang sesuai pada domain skalar diwakili oleh domain dasar kurva elips. Sirkuit R1CS biasanya diwakili oleh domain skalar. Perhatikan baik-baik, "ringkasan" pada gambar di atas melibatkan konversi domain. Artinya, jika Anda ingin melipat instance R1CS komitmen kendur yang terkait dengan suatu sirkuit, Anda harus "melipatnya" di sirkuit lain. Pada saat ini perlu diperkenalkan siklus kurva elips. Di antara dua atau lebih kurva elips, domain skalar suatu kurva sama dengan domain dasar kurva lainnya. Kebetulan domain skalar kurva ini sama dengan domain dasar kurva sebelumnya. Dengan menggunakan lingkaran kurva elips, "tampilan ideal" dapat diwujudkan:
Seluruh proses pelipatan dibagi menjadi dua sirkuit pelipatan. Bagian atas disebut lipatan Sirkuit 1, dan bagian bawah disebut lipatan Sirkuit 2. Representasi formal dari hubungan antara dua sirkuit ada di halaman 8 makalah "Potensi Serangan terhadap Nova dan Koreksi yang Sesuai". U mewakili instance terlipat, dan u mewakili instance santai yang sesuai dengan instance R1CS. Perhatikan bahwa Sirkuit 1 menciutkan instans R1CS komitmen kendur yang sesuai dengan Sirkuit 2, sedangkan Sirkuit 2 menciutkan instans R1CS komitmen kendur yang terkait dengan Sirkuit 1. Tujuan utama Sirkuit 2 adalah untuk menciutkan instance R1CS komitmen kendur yang sesuai dengan Sirkuit1, dan penghitungan fungsi di sirkuitnya tidak ada artinya. Sebaliknya, fungsi F diimplementasikan di Sirkuit 1. Dikombinasikan dengan "penampilan ideal", kita dapat menebak secara kasar kepuasan U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1 merupakan bagian penting dari pembuktian.
Karena "rangkaian" tersebut dipotong menjadi dua bagian, dan masing-masing rangkaian tersebut dilipat menjadi rangkaian yang lain. Ada beberapa masalah yang mengikat antar instance: pengikatan antara instance u dan U dan pengikatan instance u yang lewat di antara dua sirkuit. Untuk mengatasi masalah pengikatan ini, variabel publik x_0/x_1 diperkenalkan di sirkuit, di mana x_1 menentukan output rangkaian instance U yang terikat ke instance u dan output dari fungsi F saat ini (untuk menyederhanakan struktur rangkaian, tidak tercermin pada gambar). Anda berpikir, jika hasil H_1 dari instance U dimasukkan ke dalam rangkaian, jika instance u dapat dipenuhi, x_0/x_1 adalah nyata dan dapat diandalkan, artinya, ia "terikat" ke U. x_0 menetapkan hubungan pengikatan antara masukan u dan U, dan x_1 menetapkan hubungan pengikatan antara keluaran u dan U.
Misalnya, ketika u{i+1}^1 digunakan sebagai input paruh kedua rangkaian, ia melewati Sirkuit 2, dan outputnya u{i+1}^2.x0 = u{i+1 }^1.x1, jadi, ketika input ke bagian atas rangkaian, jika u{i+1}^2 dapat dipenuhi, maka x_0-nya harus sama dengan hasil H1 dari U_{i +1}^2. Ini diperiksa di Sirkuit 1. Dengan cara ini, dijamin bahwa instance yang benar dilewatkan di antara kedua sirkuit.
Bukti IVC
Untuk membuktikan bahwa IVC dihitung dengan benar pada iterasi tertentu, informasi berikut perlu dibuktikan secara logis:
Selain membuktikan empat kejadian dapat dipenuhi, perlu juga dibuktikan hubungan pengikatan antara dua x1, seperti terlihat pada gambar berikut:
Benar atau tidaknya informasi ini memerlukan bukti implementasi rangkaian tambahan. Artinya, pembuktian perhitungan IVC merupakan pembuktian rangkaian. Bisa dibayangkan jika ini adalah perhitungan dengan banyak iterasi, awalnya iterasi ini perlu dilakukan di sirkuit satu per satu, tetapi sekarang hanya empat instance sirkuit yang perlu diverifikasi untuk kepuasan dan hubungan yang mengikat. Peningkatan kinerjanya sangat besar.
Koreksi Serangan dan Algoritma
Melihat gambar di atas, saya mempunyai intuisi, saya merasa contoh rangkaian atas dan bawah “terpisah” dan tidak ada ikatannya. Faktanya, beginilah struktur serangannya.
U_i^1 dan U{i+1}^2 yang dipalsukan, meskipun dipalsukan, merupakan contoh yang memuaskan. Tempa u{i+1}^1, modifikasi x_0 dan x_1 agar sesuai dengan instance U palsu. Jelasnya, instance u{i+1}^1 tidak terpenuhi. Meskipun tidak puas, rangkaian Sirkuit 2 masih dapat dipenuhi, tetapi instance keluaran U{i+1}^1 tidak terpenuhi. Jika u{i+1}^2 berhasil dibangun, Sirkuit 1 dapat membangun u{i+2}^1 dan U_{i+2}^2 yang memuaskan, dan memenuhi hubungan pengikatan x1. Dengan cara ini, setengah dari bukti pemalsuan akhir dibuat terlebih dahulu. Melalui simetri, contoh keluaran dari bagian bawah dapat dibangun. Dengan “menyambung” hasil kedua konstruksi tersebut maka pembuktian perhitungan IVC dapat dipalsukan.
Logika pemeriksaan yang direvisi adalah sebagai berikut:
Bab 6 dari makalah "Potensi Serangan pada Nova dan Perbaikan Terkait" memberikan analisis keamanan terperinci. Teman-teman yang berminat bisa mengecek sendiri kertas aslinya.
Ide dasar Nova adalah melipat contoh rangkaian melalui skema pelipatan. Logikanya agak berbelit-belit dan memerlukan pemikiran yang cermat tentang proses pelipatan rangkaian dan hubungan pengikatan dalam rangkaian.
Satu kata untuk menggambarkannya: Mutlak~