nonnative

Gadget Bidang Non-Asli

Pustaka nonnative memberikan batasan R1CS untuk memeriksa komputasi pada bidang non-asli dalam sistem pembuktian.

Pustaka ini didasarkan pada kerangka penulisan batasan arkworks-rs dan dirilis di bawah Lisensi MIT dan Lisensi Apache v2 (lihat Lisensi).

PERINGATAN: Ini adalah prototipe pembuktian konsep akademis; khususnya, ia belum menerima tinjauan kode yang cermat. Implementasi ini TIDAK siap untuk penggunaan produksi.

Ringkasan

Pustaka ini mengimplementasikan gadget bidang untuk bidang utama Fp di atas bidang utama lainnya Fq dengan p != q .

Saat menulis sistem batasan untuk banyak bukti kriptografi, kita dibatasi pada bidang asli (misalnya, bidang skalar dari kurva ramah pasangan). Hal ini dapat menimbulkan ketidaknyamanan; misalnya, komposisi pembuktian rekursif melalui siklus kurva mengharuskan pemverifikasi untuk menghitung bidang non-asli.

Perpustakaan memungkinkan untuk menulis perhitungan pada bidang non-asli dengan cara yang sama seperti seseorang menulis perhitungan pada bidang asli. Hal ini tentu saja menimbulkan overhead tambahan, yang kami minimalkan menggunakan berbagai pengoptimalan.

Penggunaan

Karena bidang non-asli mengimplementasikan sifat FieldVar di arkworks, kita dapat memperlakukannya seperti variabel bidang asli ( FpVar ).

Kita dapat melakukan operasi lapangan standar, seperti + , - , dan * . Lihat contoh berikut:

 let a = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "a" ) , || Ok ( a_value ) ) ? ;
let b = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "b" ) , || Ok ( b_value ) ) ? ;

// add
let a_plus_b = & a + & b ;

// sub
let a_minus_b = & a - & b ;

// multiply
let a_times_b = & a * $b ;

// enforce equality
a . enforce_equal ( & b ) ? ; 

Pengoptimalan tingkat lanjut

Setelah setiap perkalian, perpustakaan kami secara internal melakukan operasi pengurangan , yang mengurangi tipe perantara NonNativeFieldMulResultVar menjadi tipe yang dinormalisasi NonNativeFieldVar . Hal ini memungkinkan pengguna untuk melakukan serangkaian operasi dengan lancar tanpa mengkhawatirkan detail mendasarnya.

Namun, operasi ini mahal dan terkadang dapat dihindari. Kita dapat mengurangi jumlah batasan dengan menggunakan tipe perantara ini, yang hanya mendukung penambahan. Untuk mengalikannya, ia harus dikurangi kembali menjadi NonNativeFieldVar . Lihat di bawah untuk contoh kerangka.

---

Untuk menghitung a * b + c * d , implementasi langsung (tetapi lebih mahal) adalah sebagai berikut:

 let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;

Ini melakukan total dua operasi pengurangan , satu untuk setiap perkalian.

---

Kita dapat menyimpan satu pengurangan dengan menggunakan NonNativeFieldMulResultGadget , sebagai berikut:

 let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;

Ia hanya melakukan satu operasi pengurangan dan kira-kira 2x lebih cepat dibandingkan implementasi pertama.

Inspirasi dan desain dasar

Perpustakaan menggunakan ide standar menggunakan banyak anggota badan untuk mewakili elemen bidang target. Misalnya, sebuah elemen dalam TargetField dapat diwakili oleh tiga elemen BaseField (yaitu, anggota badan).

 TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)

Setelah beberapa perhitungan, anggota tubuh menjadi kewalahan dan perlu direduksi , agar dapat melakukan lebih banyak perhitungan.

Kami banyak menggunakan teknik optimasi di [KPS18] dan [OWWB20]. Kedua karya tersebut memiliki perpustakaan sumber terbukanya sendiri: xJsnark dan bellman-bignat. Dibandingkan dengan mereka, perpustakaan ini bekerja dengan lingkungan arkworks dan juga dioptimalkan untuk kepadatan, bukan jumlah batasan, yang berguna untuk bukti tanpa pengetahuan holografik seperti Marlin.

Lisensi

Perpustakaan dilisensikan berdasarkan salah satu lisensi berikut, sesuai kebijaksanaan Anda.

• Lisensi Apache Versi 2.0 (LICENSE-APACHE atau http://www.apache.org/licenses/LICENSE-2.0)
• Lisensi MIT (LICENSE-MIT atau http://opensource.org/licenses/MIT)

Kecuali jika Anda secara eksplisit menyatakan sebaliknya, setiap kontribusi yang Anda kirimkan untuk dimasukkan ke dalam perpustakaan ini akan memiliki lisensi ganda seperti di atas (sebagaimana didefinisikan dalam Lisensi Apache v2), tanpa syarat atau ketentuan tambahan apa pun.

Referensi

[KPS18]: AE Kosba, C. Papamanthou, dan E. Shi. "xJsnark: kerangka kerja untuk komputasi yang efisien dan dapat diverifikasi," dalam Prosiding Simposium ke-39 tentang Keamanan dan Privasi , ser. S&P '18, 2018, hlm.944–961.

[OWWB20]: A. Ozdemir, RS Wahby, B. Whitehat, dan D. Boneh. "Menskalakan komputasi yang dapat diverifikasi menggunakan akumulator set yang efisien," dalam Prosiding Simposium Keamanan USENIX ke-29 , ser. Keamanan '20, 2020.