Bukti Zero-Knowledge: Pengantar Dasar-Dasarnya

Pendahuluan

Bukti zero-knowledge merupakan salah satu alat paling canggih yang diciptakan kriptografer. Sayangnya, kebanyakan orang belum memahaminya. Artikel ini berupaya mengatasinya dengan memberikan gambaran menyeluruh tentang bukti zero-knowledge dari prinsip dasarnya. Kami membahas teori, matematika, dan kriptografi di balik bukti zero-knowledge agar siapa pun dapat memahami perkembangan terbaru di Solana, yaitu ZK Compression dan masa depan interoperabilitas.

Artikel ini mengasumsikan pemahaman tentang model pemrograman Solana dan primitif kriptografi yang melekat pada sistem blockchain (yaitu fungsi hash, pointer hash, pohon Merkle, dan pohon Merkle konkuren). Jika konsep-konsep ini masih baru bagi Anda, sebaiknya baca postingan blog berikut terlebih dahulu:

• Dasar-Dasar Alat Kriptografi — Penjelasan Fungsi Hash dan Pohon Merkle
• Model Pemrograman Solana: Pengantar Pengembangan di Solana

Perlu diketahui bahwa artikel ini dirancang secara modular. Pembaca yang baru mengenal topik ini disarankan membaca setiap bagian dan subbagian secara berurutan. Namun, jika Anda sudah memahami topik tertentu atau ingin mempelajari topik khusus, Anda dapat langsung membuka bagian terkait tanpa masalah.

Ini juga merupakan artikel pertama dalam seri dua bagian tentang bukti zero-knowledge. Anda sangat disarankan membaca artikel ini terlebih dahulu sebelum melanjutkan ke Bukti Zero-Knowledge: Penerapannya di Solana.

Teori di Balik Bukti Zero-Knowledge

Pada 1989, peneliti MIT Shafi Goldwasser, Silvio Micali (pendiri Algorand), dan Charles Rackoff menerbitkan Kompleksitas Pengetahuan dalam Sistem Pembuktian Interaktif. Mereka mengembangkan sistem tempat satu pihak (yaitu pembukti) bertukar pesan dengan pihak kedua (yaitu pemverifikasi) untuk meyakinkannya bahwa suatu pernyataan matematis benar. Mereka adalah pihak pertama yang bertanya: “Bagaimana jika pembukti dan pemverifikasi sama-sama tidak saling percaya?” Kekhawatirannya adalah seberapa banyak informasi yang akan diketahui pemverifikasi selama pertukaran pesan tersebut, selain fakta bahwa pernyataannya benar. Misalnya, pembukti mungkin ingin meyakinkan pemverifikasi bahwa ia mengetahui solusi suatu teka-teki rumit tanpa mengungkapkan solusi itu sendiri.

Sebenarnya, masalah seperti apa yang ingin kita selesaikan?

Pewarnaan Graf dengan Tiga Warna

Pewarnaan graf dengan tiga warna adalah masalah klasik dalam ilmu komputer dan teori graf. Masalah ini melibatkan pewarnaan simpul-simpul graf menggunakan tiga warna agar tidak ada simpul yang bersebelahan memiliki warna sama. Untuk graf dengan tiga simpul, hal ini mudah dilakukan. Namun, semakin banyak jumlah simpulnya, semakin sulit pula pengerjaannya.

Salah satu penerapannya di dunia nyata adalah penyusunan jadwal universitas. Di universitas besar, jadwal harus dibuat agar tidak ada mahasiswa yang memiliki kelas bertumpang tindih. Setiap kelas dapat direpresentasikan sebagai simpul dalam graf, sedangkan sisi merepresentasikan mahasiswa yang mengikuti kedua kelas. Ini memastikan bahwa dua kelas dengan mahasiswa yang sama tidak dijadwalkan pada waktu bersamaan. Selain itu, batasannya mencakup kapasitas ruangan, waktu pilihan dosen, dan distribusi kelas secara merata sepanjang minggu. Karena itu, slot waktu dan ruangan harus dialokasikan ke kelas agar dua kelas yang bersebelahan tidak menggunakan slot waktu yang sama. Hal ini dapat dilakukan melalui pewarnaan graf dengan tiga warna.

Sekarang, bayangkan jadwal akhir harus diverifikasi oleh firma audit eksternal. Karena peraturan privasi tertentu, universitas tidak dapat membagikan informasi pendaftaran mahasiswa secara terperinci kepada auditor. Sebagai gantinya, universitas harus membuktikan bahwa jadwal akhir memenuhi batasan yang diwajibkan tanpa mengungkapkan mahasiswa mana yang terdaftar di setiap kelas. 

Untuk melakukannya, universitas harus membuat graf dengan setiap simpul merepresentasikan sebuah kelas. Sisi ditarik di antara dua simpul jika kelas terkait memiliki setidaknya satu mahasiswa yang sama. Universitas akan menetapkan slot waktu untuk setiap kelas agar dua kelas yang bersebelahan tidak dijadwalkan bersamaan. Universitas akan membuat komitmen atas jadwal akhirnya menggunakan skema komitmen kriptografi. Proses ini mencakup pembuatan hash kriptografi dari slot waktu yang ditetapkan untuk setiap kelas dan pembagian hash tersebut kepada pemverifikasi tanpa mengungkapkan slot waktunya. Firma audit eksternal kemudian akan memilih secara acak pasangan kelas yang bersebelahan untuk menguji slot waktu yang ditetapkan. Universitas akan mengungkapkan slot waktu yang telah dikomitmenkan untuk pasangan kelas terpilih dan memberikan komitmen asli (yaitu hash) agar firma audit eksternal dapat memverifikasi nilai yang diungkapkan. Beberapa langkah terakhir berupa pengujian, pengungkapan, dan verifikasi diulang hingga firma audit eksternal yakin bahwa tidak ada kelas yang bertumpang tindih. Saya sangat menyarankan demonstrasi interaktif pewarnaan tiga warna zero-knowledge dari MIT untuk melihat langkah-langkah ini berlangsung secara langsung.

Universitas ingin membuktikan kepada firma audit eksternal bahwa mereka mengetahui jadwal yang benar. Artinya, mereka ingin membuktikan kepada pihak lain bahwa mereka mengetahui sesuatu. Hal menarik dari masalah ini adalah sifatnya yang NP-complete.

NP-Complete

Dalam teori kompleksitas komputasi, sebuah masalah disebut NP-complete ketika:

• Untuk setiap input masalah, output-nya adalah “ya” atau “tidak”
• Jika jawabannya “ya”, hal itu dapat ditunjukkan dengan solusi singkat
• Kebenaran setiap solusi harus dapat diverifikasi dengan cepat dan algoritma brute force dapat menemukan solusi dengan mencoba semua kemungkinan solusi

Masalah NP-complete penting karena merepresentasikan masalah tersulit dalam kelas NP (yaitu kelompok teka-teki yang sangat sulit, yang solusi dugaannya mudah diverifikasi dalam waktu polinomial, tetapi solusinya sulit ditemukan). Masalah ini dikenal karena dapat disimulasikan secara universal. Artinya, jika kita dapat menyelesaikan satu masalah NP-complete dengan cepat, kita dapat mereduksi atau mengubah masalah NP apa pun menjadi masalah NP-complete dan menemukan solusinya dalam waktu polinomial. Solusi masalah NP-complete juga mudah diverifikasi. 

Dengan demikian, kita memiliki seluruh kelas masalah yang dapat dibuktikan secara efisien menggunakan bukti zero-knowledge. Contohnya:

• Masalah Pedagang Keliling — Dengan daftar kota dan jarak di antara setiap pasangan kota, temukan rute terpendek yang mengunjungi setiap kota satu kali dan kembali ke kota asal. Masalah ini memiliki banyak penerapan dalam logistik, perencanaan rute, manufaktur, dan manajemen rantai pasok
• Masalah Knapsack — Dengan sekumpulan barang, tentukan jumlah setiap barang yang akan dimasukkan ke dalam koleksi agar bobot totalnya kurang dari atau sama dengan batas tertentu dan nilai totalnya sebesar mungkin. Masalah ini umum dijumpai dalam bidang keuangan dan alokasi sumber daya
• Penjadwalan Pekerjaan — Dengan sekumpulan pekerjaan yang memiliki durasi dan tenggat tertentu, jadwalkan semuanya pada satu mesin untuk meminimalkan total penalti akibat pekerjaan yang terlambat. Masalah ini memiliki penerapan luas dalam komputasi, manufaktur, dan manajemen proyek

Selain itu, teorema Cook-Levin menyatakan bahwa masalah satisfiabilitas Boolean bersifat NP-complete. Artinya, setiap masalah yang variabelnya dapat diganti dengan nilai benar atau salah hingga pada akhirnya menghasilkan nilai benar dapat diubah menjadi masalah NP-complete. Ini berarti bahwa setiap masalah yang dapat kita reduksi menjadi serangkaian pertanyaan benar dan salah dapat dibuktikan secara efisien menggunakan bukti zero-knowledge.

Sifat Bukti Zero-Knowledge

Mengingat kompleksitas dan pentingnya masalah NP-complete, kemampuan untuk membuktikan solusi bagi kelas masalah ini secara efisien dan aman menjadi sangat penting. Bukti zero-knowledge menyediakan cara untuk melakukannya tanpa mengorbankan privasi informasi yang terlibat. Goldwasser, Micali, dan Rackoff mengusulkan bahwa semua bukti zero-knowledge harus memenuhi sifat berikut:

• Kelengkapan — Pembukti pada akhirnya akan meyakinkan Pemverifikasi jika ia jujur
• Kesahihan — Pembukti yang curang tidak akan pernah meyakinkan Pemverifikasi mengenai pernyataan yang salah
• Zero-knowledge — interaksi antara Pembukti dan Pemverifikasi hanya mengungkapkan apakah suatu pernyataan benar, tanpa mengungkapkan hal lain

Dengan memanfaatkan sifat bukti zero-knowledge yang kuat, kita dapat membuktikan fakta atau pengetahuan atas informasi tertentu dalam berbagai konteks dengan tetap menjaga privasi dan memastikan kebenarannya secara presisi. Di bagian berikutnya, kita akan membahas mengapa hal ini sangat bermanfaat bagi aplikasi yang membutuhkan tingkat keamanan dan efisiensi tinggi, seperti blockchain.

Interaktif versus Noninteraktif

Bukti zero-knowledge cenderung memiliki struktur tiga langkah yang sama:

• Pembukti menghasilkan solusi komputasi (yaitu saksi), lalu mengirimkan komitmen atas jawaban saksi tersebut
• Pemverifikasi merespons dengan nilai tantangan yang dihasilkan secara acak
• Pembukti menghitung bukti akhir berdasarkan komitmen dan tantangan tersebut

Struktur ini pada dasarnya bersifat interaktif — pembukti menyatakan bahwa ia mengetahui sesuatu, lalu pemverifikasi terus mengujinya hingga kemungkinan pembukti menipunya menjadi tidak signifikan. Hal ini tidak ideal untuk sebagian besar aplikasi karena pembukti memerlukan satu atau beberapa respons sebelum menghasilkan bukti lengkap. Penyiapan ini pada dasarnya menimbulkan tantangan berikut:

• Pemverifikasi dapat berkolusi dengan pembukti sehingga mereka dapat memalsukan bukti
• Pemverifikasi dapat membuat bukti palsu
• Pemverifikasi harus menyimpan nilai rahasianya di suatu tempat yang mungkin rentan terhadap kebocoran atau serangan

Heuristik Fiat-Shamir adalah teknik untuk mengubah bukti pengetahuan interaktif menjadi tanda tangan digital. Dengan demikian, suatu fakta dapat dibuktikan secara publik tanpa mengungkapkan informasi yang mendasarinya. Gagasannya adalah, alih-alih pemverifikasi mengirimkan nilai tantangan acak kepada pembukti, pembukti dapat menghitung sendiri tanda tangan digital ini menggunakan fungsi acak, seperti fungsi hash kriptografi yang baik. Jadi, alih-alih meminta pemverifikasi memeriksa komputasi di 500 tempat berbeda untuk memastikan semuanya benar, pembukti menghitung root Merkle dari komputasi tersebut, menggunakan root Merkle untuk memilih 500 indeks secara pseudoacak, dan menyediakan 500 cabang data Merkle yang sesuai. Gagasan utamanya adalah pembukti tidak mengetahui cabang mana yang harus diungkapkan hingga data selesai dikomitmenkan.

Pembaca yang jeli mungkin melihat kelemahan fatal dalam penerapan pengambilan sampel acak untuk memeriksa komputasi — komputasi pada dasarnya rapuh. Pembukti jahat dapat membalik satu bit saja di tengah komputasi dan pemverifikasi mungkin tidak akan pernah mengetahuinya. Bagaimana pemverifikasi dapat memeriksa setiap bagian komputasi tanpa melihatnya satu per satu? Polinomial.

Namun, ada cukup banyak matematika yang perlu kita pahami sebelum membahas polinomial.

Matematika di Balik Bukti Zero-Knowledge

Bagian ini tidak dimaksudkan sebagai pengantar mendalam untuk bidang-bidang matematika berikut — setiap bagiannya bahkan dapat menjadi artikel tersendiri. Ini merupakan pengantar singkat agar Anda mulai memahami dasar matematika di balik bukti zero-knowledge dan cara kerjanya secara umum.

Artikel ini juga akan memperkenalkan notasi matematika yang tepat. Misalnya, dalam subbagian berikut tentang Teori Himpunan, kami memperkenalkan simbol ∈, ∉, dan ⊆. Pada dasarnya, semua simbol ini merupakan placeholder untuk hal lain. Bukti zero-knowledge bukanlah topik untuk pemula; karena itu, sebagian besar artikel mengenai topik ini tidak ramah bagi pemula. Artikel-artikel tersebut tidak akan menjelaskan arti simbol ini, dan mengasumsikan bahwa pembaca memahami notasi tersebut. Memperkenalkan notasi ini sekarang penting agar tidak terlalu menakutkan bagi mereka yang ingin mempelajari bukti zero-knowledge lebih jauh. Jangan sampai tersesat dalam notasi. Teruslah belajar karena akan tiba saatnya Anda melihat simbol-simbol ini dan memahami konsep yang mendasarinya, bukan sekadar melihat huruf Yunani.

Teori Himpunan

Teori himpunan adalah cabang matematika yang mempelajari kumpulan objek. Sebuah himpunan adalah kumpulan objek yang berbeda. Objek-objek berbeda tersebut disebut elemen, atau anggota, dari himpunan. Sebagai contoh, perhatikan kumpulan buah berikut:

Kurung kurawal digunakan dalam notasi himpunan untuk mengapit kumpulan elemen yang merepresentasikan suatu himpunan. Dengan demikian, kita mengetahui bahwa apel, jeruk, pir, dan pisang merupakan bagian dari himpunan, sedangkan sesuatu seperti “kentang” bukan. Simbol ∈ digunakan untuk menunjukkan keanggotaan himpunan dan dibaca “adalah elemen dari”. Demikian pula, ∉ menunjukkan bahwa suatu elemen bukan anggota dari himpunan tertentu. Jadi, kita dapat menyatakan:

Kita membacanya sebagai “apel adalah elemen dari himpunan Fruit dan kentang bukan elemen dari himpunan Fruit.”

Subhimpunan

Kita juga dapat memiliki himpunan yang terdiri dari himpunan lain. Subhimpunan adalah himpunan yang hanya berisi elemen yang terdapat dalam himpunan lain. Misalnya, jika kita memiliki:

Kita dapat mengatakan bahwa himpunan Citrus merupakan subhimpunan dari himpunan AllFruits yang lebih besar. Kita juga dapat menggunakan himpunan Fruit sebelumnya untuk menyatakan bahwa Fruit merupakan subhimpunan dari himpunan AllFruit yang lebih besar. Dalam notasi himpunan, kita menuliskannya sebagai:

Mengapa ini penting bagi saya?

Teori himpunan sangat penting untuk memahami konsep rentang dan batasan. Dalam bagian berikutnya tentang teori bilangan dan aritmetika modular, kita akan membahas gagasan tentang bilangan yang berada dalam rentang tertentu. Misalnya, kita mungkin memiliki himpunan nilai yang mungkin untuk kunci kriptografi:

Di sini, K menentukan rentang semua kunci yang mungkin. Kita dapat merancang bukti zero-knowledge agar batasan tertentu diterapkan pada himpunan ini sehingga hanya nilai tertentu yang valid. Misalnya, kita dapat menentukan bahwa kunci harus berupa bilangan antara 1 dan 5. 

Dengan demikian, teori himpunan menyediakan bahasa, alat, dan notasi dasar untuk menentukan serta menganalisis himpunan input, output, dan status yang mungkin dalam protokol kriptografi. Dalam bukti zero-knowledge, kita sering perlu membuktikan bahwa suatu elemen termasuk dalam himpunan atau rentang tertentu tanpa mengungkapkan elemen itu sendiri.

Saya menyarankan Anda mengunjungi Khan Academy untuk mencoba soal latihan yang sangat baik tentang notasi himpunan dasar.

Teori Bilangan

Teori bilangan adalah cabang matematika yang mempelajari bilangan bulat dan fungsi aritmetika. Kita dapat mendefinisikan bilangan bulat sebagai himpunan angka utuh (yaitu angka yang bukan pecahan), termasuk bilangan positif, bilangan negatif, dan nol. Secara lebih formal, kita dapat mendefinisikan himpunan bilangan bulat sebagai:

Di sini, ℤ digunakan untuk menunjukkan himpunan bilangan bulat, sedangkan elipsis menunjukkan bahwa bilangan bulat membentang dari negatif tak terhingga hingga positif tak terhingga. Misalnya, angka 12 adalah bilangan bulat, dan -1978649832794275 juga merupakan bilangan bulat.

Bilangan Rasional

Bilangan rasional adalah bilangan bulat yang dapat kita nyatakan sebagai pecahan dengan penyebut (yaitu angka di bawah garis dalam pecahan biasa, atau pembagi) yang bukan nol. Misalnya, $(\frac{1}{2}), 74, (\frac{2}{3})$ semuanya merupakan bilangan rasional. Secara lebih formal, kita dapat mendefinisikan bilangan rasional sebagai himpunan bilangan bulat yang dapat dinyatakan sebagai pecahan pq, dengan p sebagai pembilang, q sebagai penyebut, dan q bukan 0. Simbol ℚ digunakan untuk menunjukkan bilangan rasional. Dalam notasi himpunan, kita menuliskannya sebagai:‍

‍Walaupun awalnya mungkin terlihat menakutkan, notasi ini menjelaskan persis apa yang disebutkan dalam kalimat sebelumnya. Jargon matematika yang tampak aneh ini dibaca sebagai “Q adalah himpunan semua pecahan p per q, dengan p dan q merupakan bilangan bulat, serta q tidak sama dengan nol.” 

Bilangan Riil

Bilangan riil mencakup bilangan rasional dan irasional. Bilangan irasional adalah bilangan yang tidak dapat dinyatakan sebagai pecahan sederhana serta memiliki angka desimal yang tidak berulang dan tidak berakhir. Misalnya, pi (yaitu π) dan $\sqrt{2}$ (yaitu 1.4.1421…) adalah bilangan irasional. Untuk sementara, kita akan melewatkan notasi himpunannya. Namun, perlu diketahui bahwa bilangan riil ditunjukkan dengan simbol ℝ.

Mengapa ini penting bagi saya?

Teori bilangan berkaitan erat dengan teori himpunan karena melibatkan studi mengenai himpunan bilangan tertentu (misalnya bilangan rasional). Himpunan ini sering menjadi dasar untuk menentukan rentang dan batasan dalam masalah matematika dan kriptografi. 

Kita juga dapat melihat keterkaitan antara teori bilangan dan teori himpunan. Misalnya, kita dapat menyatakan bahwa himpunan semua bilangan bulat ℤ merupakan subhimpunan dari bilangan rasional ℚ. Hal ini terlihat dalam definisi bilangan riil pada notasi himpunan di atas ketika kita menyatakan bahwa pembilang dan penyebutnya merupakan bilangan bulat.

Aritmetika Modular

Aritmetika modular, yang juga dikenal sebagai aritmetika jam, adalah sistem operasi numerik untuk bilangan bulat ketika angka “kembali ke awal” setelah mencapai nilai tertentu yang disebut modulus. Gagasannya adalah, alih-alih bekerja dengan himpunan angka yang tak terbatas, kita menggunakan n bilangan positif pertama.

Jam

Bayangkan sebuah jam analog (saya kesal karena pada zaman ini harus menjelaskan bahwa jam tersebut memiliki jarum dan bukan jam digital) dengan angka 1 hingga 12. Jika sekarang pukul 11 dan kita ingin mengetahui waktu dua jam kemudian, hasilnya bukan pukul 13. Sebaliknya, kita kembali ke pukul 1. Hal ini dapat dinyatakan sebagai $11 + 2 \equiv 1 \pmod{12}$ . Ekspresi matematika yang tepat adalah $13 \bmod 12 = 1$. Programmer tentu familier dengan penggunaan operasi modulo dalam format $13 \% 12 = 1$.

Operasi Modulo

Saat menulis n mod k, kita ingin mengetahui sisa pembagian n oleh k. Ini disebut operasi modulo. Contohnya:

• 25 mod 3 berarti membagi 25 dengan 3, yang menghasilkan sisa 1 karena $25 = 8 \times 3 + 1$
• 15 mod 4 berarti membagi 15 dengan 4, yang menghasilkan sisa 3 karena $15 = 3 \times 4 + 3$

Dalam aritmetika modular, sisanya selalu nonnegatif.

Mengapa ini penting bagi saya?

Memahami aritmetika modular sangat penting karena memberikan wawasan tentang perilaku bilangan di bawah batasan, yang bermanfaat dalam kriptografi. Aritmetika modular merupakan dasar bagi banyak algoritma kriptografi dan digunakan di seluruh bidang ilmu komputer, rekayasa, serta setiap bidang yang memerlukan penanganan dan enkripsi data secara aman.

Perhatikan komputasi x + y = z. Jika kita bekerja dengan medan hingga yang ditentukan oleh bilangan prima p = 17 (kita akan segera membahasnya. Untuk saat ini, anggap saja sebagai himpunan semua bilangan bulat dari 0 hingga 16 yang kembali ke awal pada 17). Komputasinya menjadi (x + y) mod p = z dalam medan ini. Jika x = 12 dan y = 15, komputasinya adalah:‍

Penggunaan aritmetika modular di sini memungkinkan kita melakukan komputasi dalam rentang nilai yang mudah dikelola, yang ditentukan oleh bilangan prima p. Hal ini sangat penting karena komputer dan prosesor memiliki ruang terbatas. Karena itu, kita biasanya menggunakan bilangan bulat berukuran tetap seperti u32 atau u64. Aritmetika modular memastikan nilai kita tetap berada dalam batas tersebut. Selain itu, penggunaan bilangan prima menambahkan lapisan kompleksitas. Hal ini penting dari sudut pandang kriptografi karena meningkatkan keamanan serta membuat sifat matematika tertentu lebih mudah diprediksi dan lebih andal.

Sebagai contoh, aritmetika modular digunakan dalam zk-SNARKs untuk memastikan nilai yang dihitung tetap berada dalam batas tertentu yang mudah dikelola. Aritmetika modular juga digunakan untuk membuat sirkuit aritmetika pada himpunan bilangan tertentu. Hal ini dilakukan agar kita dapat menyatakan komputasi sekaligus memastikan bahwa komputasi tersebut dapat diverifikasi secara efisien. Di sini, pembukti harus membuktikan bahwa ia melakukan komputasi tersebut tanpa mengungkapkan nilai x, y, dan z.

Saya sangat menyarankan Anda mencoba kumpulan soal Art of Problem Solving dan Latihan Aritmetika Modular Joseph Zoller untuk mendapatkan lebih banyak pengalaman langsung dalam menyelesaikan masalah aritmetika modular. 

Teori Grup

Teori grup adalah cabang matematika yang mempelajari struktur aljabar yang disebut grup. Grup adalah himpunan elemen dengan sebuah operasi yang memenuhi kondisi berikut, yang dikenal sebagai aksioma grup:

• Ketertutupan — Hasil perhitungan aritmetika apa pun akan menjadi elemen lain dalam himpunan
• Asosiativitas — Saat melakukan operasi yang sama pada tiga elemen atau lebih, urutan pengelompokan elemen tidak memengaruhi hasil; hasilnya akan tetap sama
• Elemen Identitas — Terdapat elemen yang dapat digunakan dalam operasi apa pun dengan elemen lain tanpa mengubah nilainya
• Elemen Invers — Terdapat elemen yang dapat digunakan dalam operasi dengan elemen lain dan menghasilkan elemen identitas

Secara formal, semuanya didefinisikan sebagai berikut:

• Ketertutupan — Jika a dan b merupakan anggota grup, hasil operasi (sering dinyatakan sebagai $a \times b$, $ab$, $a \circ b$, atau $ab$) juga merupakan anggota grup. Secara formal, kita dapat menulis $\forall a, b \in G \mid a \circ b \in G$. Kita dapat membacanya sebagai: “untuk semua nilai elemen a dan b dalam himpunan G, hasil operasi antara a dan b berada dalam G”
• Asosiativitas — Jika a, b, dan c merupakan anggota grup, maka (ab)c = a(cb). Secara formal, kita dapat menulis $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Kita dapat membacanya sebagai: “untuk semua nilai elemen a, b, dan c dalam himpunan G, operasi a dan b yang dilanjutkan dengan c sama dengan operasi a yang dilanjutkan dengan operasi b dan c
• Elemen Identitas — Terdapat elemen e dalam grup sehingga, untuk setiap elemen a dalam grup, berlaku operasi $e \circ a = a \circ e = a$. Secara formal, kita menuliskannya sebagai $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Kita dapat membacanya sebagai “terdapat elemen e dalam himpunan G, sehingga untuk setiap elemen a dalam himpunan G, operasi e yang dilanjutkan dengan a sama dengan operasi a yang dilanjutkan dengan e, yang sama dengan a
• Elemen Invers — Untuk setiap elemen a dalam grup, terdapat elemen b dalam grup sehingga $a \circ b = b \circ a = e$, dengan e sebagai elemen identitas. Secara formal, kita menuliskannya sebagai $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Kita dapat membacanya sebagai “untuk semua nilai elemen a dalam himpunan G, terdapat elemen b dalam himpunan G, sehingga operasi a yang dilanjutkan dengan b sama dengan operasi b yang dilanjutkan dengan a, yang sama dengan elemen identitas

Kita dapat menguraikan semua jargon matematika ini menjadi sesuatu yang lebih mudah dipahami melalui sebuah contoh. Perhatikan himpunan bilangan bulat dalam operasi penjumlahan. Kita dapat mengatakan bahwa himpunan ini membentuk grup karena memenuhi keempat aksioma grup:

• Ketertutupan — Jika Anda menjumlahkan dua bilangan bulat, hasilnya adalah bilangan bulat lain
• Asosiativitas — $(5 + 4) + 3 = 5 + (4 + 3)$
• Elemen Identitas — Angka nol dianggap sebagai elemen identitas karena bilangan bulat apa pun yang ditambah nol tidak berubah nilainya. Misalnya, $7 + 0 = 0 + 7 = 7$
• Elemen Invers — Invers dari bilangan bulat apa pun adalah negasinya karena menjumlahkan keduanya akan menghasilkan elemen identitas. Misalnya, $5 + (-5) = 0$. Kita dapat menggeneralisasikannya menjadi $n + (-n) = 0$

Kita juga dapat memperluasnya ke contoh yang lebih sulit, seperti himpunan bilangan rasional bukan nol $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ dengan operasi perkalian. Ini juga membentuk sebuah himpunan:

• Ketertutupan — Perkalian dua bilangan rasional bukan nol akan menghasilkan bilangan rasional bukan nol
• Asosiativitas — $ab \times cd \times ef = ab \times (cd \times ef)$
• Elemen Identitas — Angka 1 dianggap sebagai elemen identitas karena bilangan rasional bukan nol apa pun yang dikalikan satu tidak berubah nilainya. Misalnya, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemen Invers — Invers dari setiap bilangan rasional bukan nol adalah resiprokalnya (yaitu menukar pembilang dan penyebut) karena hasilnya sama dengan 1, yaitu elemen identitas. Misalnya, $\frac{3}{5} \times \frac{5}{3} = 1$

Subgrup

Subgrup adalah grup di dalam grup. Jika kita menyatakan bahwa subgrup H dari grup G merupakan subhimpunan dari G, kita harus memenuhi aksioma grup berikut:

• Ketertutupan — Jika a dan b berada dalam H, hasil operasi di antara keduanya juga harus berada dalam H
• Asosiativitas — Aksioma ini diwarisi dari grup G yang lebih besar 
• Elemen Identitas — Elemen identitas dari G juga harus berada dalam H 
• Elemen Invers — Untuk setiap elemen a dalam H, harus ada elemen b yang juga berada dalam H sehingga ab dan ba sama-sama menghasilkan elemen identitas

Contoh klasiknya adalah himpunan bilangan bulat genap dalam operasi penjumlahan yang menjadi subgrup dari himpunan bilangan bulat dalam operasi penjumlahan:

• Ketertutupan — Penjumlahan dua bilangan bulat genap menghasilkan bilangan bulat genap lain
• Asosiativitas — Aksioma ini diwarisi dari bilangan bulat. Misalnya, $2 + (4 + 6) = (2 + 4) + 6$
• Elemen Identitas — Angka nol dianggap sebagai elemen identitas karena bilangan bulat genap apa pun yang ditambah nol tidak berubah nilainya. Nol juga terdapat dalam himpunan bilangan bulat
• Elemen Invers — Invers dari setiap bilangan genap juga merupakan bilangan genap. Misalnya, invers dari 4 adalah -4 karena $4 + (-4) = 0$, yang merupakan elemen identitas

Kita dapat menerapkannya pada contoh yang lebih sulit. Perhatikan himpunan semua bilangan rasional bukan nol (yaitu ℚ*) dalam operasi perkalian. Kita dapat membuktikan bahwa ℚ* merupakan subgrup dari himpunan bilangan riil bukan nol (yaitu ℝ*) dalam operasi perkalian:

• Ketertutupan — Jika a dan b merupakan bilangan rasional bukan nol, hasil kalinya ab juga merupakan bilangan bukan nol. Misalnya, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$ yang merupakan bilangan rasional bukan nol
• Asosiativitas — Perkalian bilangan rasional bersifat asosiatif. Misalnya, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Elemen Identitas — Angka 1 dianggap sebagai elemen identitas karena mengalikan bilangan rasional bukan nol apa pun dengan 1 tidak mengubah nilainya. Misalnya, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemen Invers — Setiap bilangan rasional bukan nol $a = \frac{p}{q}$ memiliki invers perkalian $a^{-1} = \frac{q}{p}$, yang juga merupakan bilangan rasional bukan nol dan menghasilkan elemen identitas. Misalnya, anggap a = $\frac{2}{3}$. Inversnya adalah $\frac{3}{2}$ karena $\frac{2}{3} \times \frac{3}{2} = 1$

Karena ℚ* memenuhi semua aksioma grup, ia membentuk sebuah grup. Selain itu, karena ℚ* merupakan subhimpunan dari ℝ* dan mewarisi sifat-sifatnya, kita dapat menyatakan bahwa ℚ* merupakan subgrup dari ℝ*.

Mengapa ini penting bagi saya?

Grup menjadi dasar berbagai konsep dan struktur matematika serta kriptografi. Misalnya, sistem kriptografi seperti RSA dan kriptografi kurva eliptik sangat bergantung pada sifat grup dan operasinya. Memahami subgrup membantu kita memahami struktur grup yang lebih besar dengan memeriksa subhimpunannya yang lebih kecil dan lebih mudah dikelola. Grup menyediakan kerangka dasar untuk memahami simetri, operasi, dan transformasi, yang akan sangat penting saat kita beralih ke bagian berikutnya tentang medan.

Medan

Sebuah medan adalah himpunan elemen yang memenuhi aksioma medan untuk penjumlahan dan perkalian serta merupakan aljabar pembagian komutatif (yaitu pembagian, kecuali oleh nol, selalu dapat dilakukan). Aksioma medan umumnya ditulis dalam pasangan aditif dan multiplikatif:

• Penjumlahan
  • Asosiativitas: $(a + b) + c = a + (b + c)$
  • Komutativitas: $a + b = b + a$
  • Distributivitas: $a(b + c) = ab + ac$
  • Elemen Identitas: $a + 0 = 0 + a = a$
  • Elemen Invers: $a + (-a) = 0$
• Perkalian
  • Asosiativitas: $(ab)c = a(bc)$
  • Komutativitas: $ab = ba$
  • Distributivitas: $(a + b)c = ac + bc$
  • Elemen Identitas: $(a + b)c = ac + bc$
  • Elemen Invers: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Medan Hingga dan Generator

Medan hingga adalah medan dengan himpunan elemen yang terbatas. Medan hingga juga disebut Medan Galois. Jumlah elemen disebut orde, atau kardinalitas, medan tersebut. Jumlah elemennya akan selalu berupa pangkat bilangan prima. Hal menarik dari medan hingga adalah setiap operasi aritmetika yang dilakukan pada elemen di dalam medan akan tetap berada dalam medan tersebut. Hal ini terjadi karena semua operasi dilakukan dengan modulo orde medan sehingga nilainya kembali ke awal.

Setiap medan hingga memiliki generator. Generator dapat menghasilkan semua elemen dalam medan melalui eksponensiasi. Artinya, kita dapat mengambil generator dan menaikkan eksponennya satu per satu hingga memperoleh semua elemen dalam medan. Dengan demikian, generator adalah elemen dalam medan yang melalui pangkat-pangkatnya dapat menghasilkan setiap elemen bukan nol dalam medan tersebut.

Sebagai contoh, bayangkan kita mengambil himpunan bilangan bulat modulo p = 7 dan memiliki medan $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Jika ingin mencari generator g dari $\mathbb{Z}_7^*$ (yaitu grup multiplikatif elemen bukan nol dari $\mathbb{Z}_7$, kita perlu memastikan bahwa g1, g2,g3, dan seterusnya dapat menghasilkan semua elemen bukan nol dalam medan tersebut.

Mari kita periksa apakah 3 merupakan generator:

Pangkat-pangkat dari 3 menghasilkan semua elemen bukan nol dari $\mathbb{Z}_7$. Oleh karena itu, 3 merupakan generator dari grup multiplikatif $\mathbb{Z}_7^*$.

Mengapa ini penting bagi saya?

Kriptografi adalah ilmu yang berkaitan dengan himpunan hingga. Bidang ini membentuk pemahaman mendasar yang sangat penting untuk mempelajari topik seperti Masalah Logaritma Diskret, enkripsi, Pertukaran Diffie-Hellman, dan kurva eliptik. Generator memungkinkan operasi aritmetika pada polinomial terenkripsi tanpa mendekripsinya (yaitu enkripsi homomorfik). Artinya, kita dapat mengolah data terenkripsi sambil menjaga privasi nilai yang mendasarinya. Memahami bagian ini sangat penting untuk aspek zero-knowledge dalam bukti zero-knowledge.

Saya menyarankan Anda mengunjungi Bill’s Security Site, yang menyediakan contoh interaktif untuk menghasilkan medan hingga dengan parameter tertentu beserta teori yang mendasarinya dalam Python. 

Fungsi

Fungsi adalah ekspresi, aturan, atau hukum yang menentukan hubungan antara dua variabel — variabel independen dan variabel dependen. Kedua variabel ini sering masing-masing dijelaskan sebagai sebab dan akibat. Hubungan ini biasanya dinyatakan sebagai y = f(x), yang dibaca “f dari x.” Untuk setiap nilai x, terdapat satu nilai y yang unik. Artinya, f(x) tidak dapat memiliki lebih dari satu nilai untuk x yang sama.

Fungsi dapat bersifat 1-ke-1 atau banyak-ke-1, yang sering disebut kardinalitas. Artinya, suatu nilai x dapat dipetakan ke satu nilai y yang unik, atau beberapa nilai x dapat dipetakan ke nilai y yang sama

Bayangkan sebuah garis yang ditentukan oleh $y = 3x + 4$. Ini adalah fungsi linear. Memasukkan nilai x akan menghasilkan nilai y yang sesuai. Kedua nilai tersebut membentuk sebuah titik pada garis. Misalnya, kita dapat menulis ulang persamaannya menjadi $f(x) = 3x + 4$ dan menghitungnya saat x = 1, yaitu $f(1) = 7$. Fungsi juga dapat memiliki beberapa variabel. Sebagai contoh, gunakan rumus luas segitiga: $A = \frac{bh}{2}$. Di sini, A (yaitu luas) didefinisikan sebagai fungsi dari b (yaitu alas) dan h (yaitu tinggi).

Domain dan Rentang

Domain suatu fungsi adalah himpunan semua kemungkinan nilai input (yaitu variabel independen) yang dapat diterima fungsi tersebut. Rentang fungsi adalah himpunan semua kemungkinan nilai output (yaitu variabel dependen) yang dapat dihasilkan fungsi tersebut.

Untuk fungsi $y = 2x + 2$:

• Domainnya adalah semua bilangan riil karena angka apa pun dari negatif tak terhingga hingga positif tak terhingga dapat digunakan. Contohnya:
  • Jika x = 2.5, maka $y = 2(2.5) + 2 = 7$ 
  • Jika x = -9234525, maka $y = 2(-9234525) + 2 = -18469048$
• Rentangnya juga mencakup semua bilangan riil karena angka apa pun dari negatif tak terhingga hingga positif tak terhingga dapat dihasilkan. Contohnya:
  • Untuk mencari y = -50, kita menyelesaikan -50 = 2x + 2, yang menghasilkan x = -26. 
  • Untuk mencari y = 0, kita menyelesaikan 0 = 2x + 2, yang menghasilkan x = 0

Mengapa ini penting bagi saya?

Fungsi sangat penting untuk memahami polinomial. Polinomial merupakan fungsi khusus yang melibatkan variabel dengan berbagai pangkat dan koefisiennya. Polinomial adalah struktur aljabar fundamental yang menjadi dasar untuk membangun protokol kriptografi. Di bagian berikutnya, kita akan membahas polinomial secara mendetail dengan melihat sifat dan perannya dalam bukti zero-knowledge.

Saya menyarankan Anda membaca Paul’s Online Notes dan mengerjakan soal latihannya untuk memperoleh pemahaman yang lebih baik tentang fungsi.

Polinomial

Polinomial adalah fungsi yang terdiri dari beberapa variabel dan koefisien serta hanya melibatkan operasi penjumlahan, pengurangan, perkalian, dan eksponensiasi variabel dengan bilangan bulat nonnegatif. Polinomial biasanya ditulis dalam bentuk:‍

Dengan $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ sebagai koefisien, dan x sebagai variabel. Pangkat tertinggi dari variabel x yang memiliki koefisien bukan nol disebut derajat polinomial.

Polinomial dapat diklasifikasikan sebagai univariat, yang melibatkan satu variabel (seperti bentuk yang ditulis di atas), atau multivariat, yang melibatkan beberapa variabel (misalnya, $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check adalah contoh protokol yang menggunakan polinomial multivariat. Namun, pada umumnya bukti zero-knowledge hanya memerlukan satu variabel.

Nama umum yang diberikan kepada polinomial berdasarkan derajatnya adalah:

• Derajat 0 — Konstanta bukan nol (misalnya, $P(x) = 6$)
• Derajat 1 — Linear (misalnya, $P(x) = 2x - 7$)
• Derajat 2 — Kuadratik (misalnya, $P(x) = 8x^2 - 3x + 1$)
• Derajat 3 — Kubik (misalnya, $P(x) = 3x^3 - 4x$)

Jika kita memiliki dua polinomial tidak sama dengan derajat paling tinggi $d$, keduanya dapat berpotongan di paling banyak $d$ titik (misalnya, jika kita menyamakan fungsi linear dengan fungsi kubik, keduanya dapat berpotongan hingga tiga kali). Sifat ini berasal dari cara kita menemukan titik bersama. Untuk menemukan perpotongan dua polinomial, kita menyamakan keduanya. Pada subbagian berikut, kita akan berlatih mencari akar polinomial, yaitu mencari titik tempat polinomial tertentu berpotongan dengan sumbu x. Teorema Dasar Aljabar menyatakan bahwa polinomial berderajat $d$ dapat memiliki paling banyak $d$ solusi dan, oleh karena itu, paling banyak $d$ titik bersama.

Akar Polinomial 

Akar, atau nol, dari suatu polinomial adalah nilai x yang membuat polinomial tersebut sama dengan nol. Dengan kata lain, jika $P(x)$ adalah polinomial, akar $r$ merupakan solusi untuk persamaan $P(r) = 0$. Untuk mencari akar, kita harus memahami faktorisasi polinomial. Faktorisasi berarti mencari nilai-nilai yang dikalikan untuk menghasilkan kuantitas tertentu. Misalnya, ada beberapa cara untuk memfaktorkan 12:

Metode faktorisasi yang umum adalah memfaktorkan bilangan sepenuhnya menjadi faktor-faktor prima positif. Saat melakukan faktorisasi, sebaiknya selalu mulai dengan faktor persekutuan terbesar (FPB) yang dimiliki semua suku. Contohnya,

Dalam contoh di atas, kedua suku (yaitu, 6x dan 3) dapat dibagi 3 sehingga memiliki FPB 3. Dengan demikian, faktornya adalah 3 dan $2x + 1$. Kita membalik sifat distributif: $3 \times 2x$ dan $3 \times 1$. Mencari akar berarti menyelesaikan x ketika $P(x) = 0$.

Faktorisasi cukup mudah untuk polinomial dengan dua suku. Prosesnya bahkan lebih mudah jika tersedia grafik, karena akar berada di titik tempat polinomial berpotongan dengan sumbu x. Namun, penambahan tiga derajat atau lebih dapat membuatnya semakin rumit. Saya menyarankan Anda membaca artikel Penjelasan Cara Memfaktorkan Polinomial untuk penjelasan yang lebih mendalam. 

Memahami setiap nuansa faktorisasi berbagai polinomial secara persis tidaklah penting untuk membaca bagian selanjutnya dari artikel ini. Untuk tujuan kita, kita tertarik pada saat sebuah polinomial disamakan dengan nilai lain. Dalam hal ini, kita tertarik pada saat polinomial sama dengan nol. Selanjutnya, kita akan membahas saat satu polinomial sama dengan polinomial lain atau saat selisih antara dua polinomial identik dengan nol (yaitu, semua koefisiennya nol), yang mengharuskan kita memeriksa apakah polinomial tertentu memiliki akar tertentu.

Lema Schwartz-Zippel 

Lema Schwartz-Zippel adalah alat probabilistik untuk memeriksa apakah persamaan polinomial selalu benar. Alat ini mengevaluasi polinomial pada titik-titik acak dan memeriksa apakah hasilnya nol.

Bayangkan persamaan kompleks yang melibatkan variabel $x_1, x_2, \ldots, x_n$. Jika persamaan ini merupakan polinomial dan bukan sekadar kumpulan suku acak, Lema Schwartz_Zippel membantu kita memverifikasi apakah persamaan tersebut berlaku untuk semua kemungkinan nilai variabel ini.

Berikut cara kerjanya:

• Misalkan $P(x_1, x_2, \ldots, x_n)$ adalah polinomial dengan derajat total d (yaitu, jumlah pangkat tertinggi dalam suku mana pun)
• Pilih himpunan terbatas S dari medan tersebut (seperti memilih sekumpulan bilangan)
• Pilih nilai secara acak untuk setiap variabel $x_1, x_2, \ldots, x_n$ dari himpunan S

Lema ini menyatakan bahwa probabilitas P bernilai nol pada titik-titik yang dipilih secara acak tersebut paling tinggi $\frac{d}{S}$. Artinya, jika polinomial tersebut tidak nol, sangat kecil kemungkinannya polinomial itu tampak bernilai nol hanya karena kebetulan acak. Hal ini sangat berguna untuk bukti zero-knowledge, karena kita perlu memverifikasi identitas polinomial secara efisien.

Interpolasi Lagrange

Interpolasi Lagrange adalah metode untuk membentuk polinomial yang melewati sekumpulan titik tertentu. Polinomial Lagrange adalah polinomial dengan derajat terendah yang melewati setiap titik yang diberikan. Untuk n titik, kita dapat membuat polinomial berderajat n-1 yang melewati semua titik tersebut. Misalnya, jika Anda memiliki dua titik pada sebuah bidang, kita dapat menentukan garis lurus yang melewati kedua titik itu. Jika kita memiliki tiga titik pada sebuah bidang, kita dapat menentukan polinomial kuadrat (yaitu, $y = ax^2 + bx + c$) yang melewati semua titik tersebut. Demikian seterusnya.

Mengapa ini penting?

Polinomial adalah satu objek matematika yang dapat memuat informasi dalam jumlah tak terbatas — bayangkan polinomial sebagai daftar bilangan bulat, dan hal ini akan langsung terlihat jelas. Dengan demikian, satu persamaan antarpoinomial dapat merepresentasikan persamaan antarbilangan dalam jumlah tak terbatas. Jika seseorang dapat memverifikasi persamaan tertentu antarpoinomial, secara implisit mereka memverifikasi semua kemungkinan persamaan secara bersamaan. Beginilah cara kita mengamankan bukti noninteraktif dari bahaya pembukti jahat dan dari keharusan mengandalkan pemeriksaan acak terhadap komputasi tertentu. 

Polinomial juga memiliki beberapa sifat yang membuatnya berguna untuk membuat bukti:

• Jika tersedia cukup banyak titik untuk polinomial tertentu, seluruh polinomial dapat direkonstruksi
• Perubahan kecil pada input polinomial dapat menyebabkan perubahan besar pada output-nya sehingga kesalahan lebih mudah dideteksi
• Polinomial dapat mendeteksi dan memperbaiki kesalahan dalam komputasi, serupa dengan cara erasure coding membuat data toleran terhadap kegagalan (yang sangat penting bagi cara kerja Turbine)

Bukti zero-knowledge digunakan untuk membuktikan komputasi tertentu. Polinomial sangat berharga untuk tujuan ini karena kita dapat menyusunnya dengan karakteristik tertentu. Misalnya, Anda memiliki komputasi atau sekumpulan titik data yang ingin dibuktikan. Cara termudah untuk melakukannya adalah dengan mengodekannya ke dalam polinomial dan menggunakan sifat-sifatnya untuk membuat bukti:

• Enkodekan data ke dalam polinomial $P(x)$ sehingga evaluasi $P(x)$ pada titik-titik tertentu menghasilkan data asli atau hasil komputasi tertentu
• Untuk memastikan polinomial memenuhi kriteria yang diberikan (misalnya, semua nilai berada dalam suatu rentang), buat polinomial batasan $C(x)$. Sebagai contoh, $C(x) = (P(x) - 0)(P(x) - 1)$ memastikan $P(x)$ bernilai 0 atau 1
• Ubah masalah menjadi pembuktian bahwa $P(x)$ memenuhi kondisi tertentu untuk kumpulan data atau komputasi Anda
• Buat polinomial yang diketahui $H(x)$ yang merupakan kelipatan dari $P(x)$ dan mengodekan kondisi-kondisi ini
• Pembukti mengikat nilai $P(x)$ dan polinomial terkait apa pun dengan membuat pohon Merkle dari hasil evaluasi, lalu mengirimkan hash akar kepada pemverifikasi
• Pemverifikasi memilih beberapa titik secara acak dan meminta pembukti memberikan nilai $P(x)$ dan $C(x)$ pada titik-titik tersebut
• Pemverifikasi memeriksa nilai yang diberikan terhadap hash akar yang telah diikat dan hubungan polinomial yang diharapkan

Berapa pun ukuran polinomialnya tidak menjadi masalah; karena kita menggunakan komitmen polinomial, kita dapat memverifikasi persamaan antarpoinomial dalam waktu singkat. Ini adalah cara yang sangat ringkas dan efisien untuk membuat bukti. Setiap kesalahan diperkuat dan, menggunakan teknik seperti heuristik Fiat-Shamir, bukti ini dapat menjadi noninteraktif sehingga siapa pun dapat memverifikasinya tanpa interaksi lebih lanjut. 

Untuk memperdalam pemahaman, saya menyarankan Anda mencoba soal-soal latihan berikut:

• Soal Latihan Polinomial
• Soal Latihan Mencari Nol Polinomial
• Faktorisasi Polinomial: Soal Sangat Sulit Beserta Solusinya

Khan Academy juga memiliki unit lengkap tentang ekspresi, persamaan, dan fungsi polinomial.

Sekarang, untuk lebih memahami komitmen polinomial, kita perlu mempelajari kriptografi yang mendasari bukti zero-knowledge.

Kriptografi di Balik Bukti Zero-Knowledge

Mari kita pelajari enkripsi simetris dan asimetris.

Enkripsi Simetris

Enkripsi simetris adalah teknik enkripsi yang menggunakan kunci yang sama untuk mengenkripsi teks polos dan mendekripsi teks sandi. Kunci ini sering disebut kunci rahasia atau kunci privat karena penggunaan satu kunci mengharuskannya tetap dirahasiakan. Namun, hal ini juga berarti kunci rahasia harus dibagikan kepada kedua pihak sebelum mereka dapat berkomunikasi dengan aman. Karena itu, pengelolaan dan distribusi kunci rahasia secara aman dapat menjadi tantangan dan rentan terhadap kebocoran jika tidak ditangani dengan benar. Terlepas dari kekurangan ini, enkripsi simetris cepat, efisien, serta membutuhkan daya komputasi dan memori yang lebih sedikit dibandingkan skema enkripsi lainnya.

Algoritma enkripsi simetris yang umum meliputi:

Advanced Encryption Standard (AES)

Advanced Encryption Standard (AES) adalah varian block cipher Rijndael yang banyak digunakan di seluruh dunia untuk mengamankan data. Algoritma ini mendukung ukuran kunci 128, 192, dan 256 bit.

ChaCha20

ChaCha20 adalah stream cipher modern dan efisien yang dikembangkan oleh Daniel J. Bernstein. Algoritma ini merupakan varian stream cipher Salsa20 yang memanfaatkan operasi add-rotate-XOR (ARX). Algoritma ini memetakan kunci 256 bit, nonce 64 bit, dan penghitung 64 bit ke blok keystream 512 bit. Artinya, pengguna dapat mencari posisi mana pun pada keystream secara efisien dalam waktu konstan.

Meskipun enkripsi simetris kuat dan efisien, enkripsi ini memerlukan metode aman untuk bertukar kunci. Salah satu metode tersebut adalah pertukaran kunci Diffie-Hellman, yang memungkinkan dua pihak berbagi kunci rahasia dengan aman melalui saluran yang tidak aman. Namun, metode ini didasarkan pada prinsip enkripsi asimetris, yang akan kita bahas di bagian berikutnya.

Enkripsi Asimetris

Enkripsi asimetris, yang juga dikenal sebagai enkripsi kunci publik, adalah metode yang menggunakan sepasang kunci terkait (yaitu, kunci publik dan kunci privat) untuk mengenkripsi dan mendekripsi informasi. Kunci publik dibagikan secara terbuka, sedangkan kunci privat dirahasiakan. Saat pengirim ingin mengenkripsi pesan, mereka menggunakan kunci publik penerima. Setelah menerimanya, penerima mendekripsi pesan menggunakan kunci privat terkait. Data yang dienkripsi dengan kunci publik hanya dapat didekripsi dengan kunci privat. Dengan demikian, enkripsi asimetris memungkinkan komunikasi aman melalui saluran yang tidak aman karena kunci dekripsi tidak pernah dibagikan.

Enkripsi asimetris menguntungkan karena memberikan tingkat keamanan tinggi sebab kunci privat tidak pernah dibagikan. Enkripsi ini juga menyederhanakan distribusi kunci karena kunci publik dapat dibagikan secara terbuka dan memungkinkan penggunaan tanda tangan digital. Namun, enkripsi asimetris membutuhkan komputasi lebih intensif dan lebih lambat dibandingkan enkripsi simetris. Pengelolaan pasangan kunci juga dapat menjadi rumit, terutama dalam sistem dengan banyak pengguna dan saat pasangan kunci tidak intuitif. 

Algoritma enkripsi asimetris yang umum meliputi:

• Rivest-Shamir-Adleman (RSA) — salah satu sistem kriptografi kunci publik tertua dan paling banyak digunakan untuk transmisi data yang aman. Sistem ini dikembangkan pada 1970-an dan mengandalkan kesulitan praktis dalam memfaktorkan hasil kali dua bilangan prima besar
• Kriptografi Kurva Eliptik (ECC) — pendekatan terhadap kriptografi kunci publik yang didasarkan pada struktur aljabar kurva eliptik pada medan berhingga. Pendekatan ini menawarkan keamanan serupa dengan RSA, tetapi menggunakan ukuran kunci yang lebih kecil sehingga komputasi lebih cepat dan kebutuhan penyimpanan berkurang. Solana menggunakan kurva eliptik Ed25519 untuk menghasilkan pasangan kuncinya

Tanda Tangan Digital

Tanda tangan digital merupakan aspek penting dalam kriptografi kunci publik dan menyediakan cara untuk memverifikasi keaslian serta integritas pesan, perangkat lunak, atau dokumen digital. Tanda tangan digital dibuat menggunakan kunci privat pengirim dan dapat diverifikasi oleh siapa pun yang memiliki akses ke kunci publik terkait. Hal ini memastikan bahwa pesan dikirim oleh pengirim yang sah dan tidak diubah.

Algoritma yang umum digunakan untuk tanda tangan digital meliputi:

• Digital Signature Algorithm (DSA) — pendekatan yang didasarkan pada eksponensiasi modular (yaitu, eksponensiasi yang dilakukan terhadap suatu modulus) dan masalah logaritma diskret
• Elliptic Curve Digital Signature Algorithm (ECDSA) — varian DSA yang menggunakan kriptografi kurva eliptik untuk memberikan tingkat keamanan lebih tinggi dengan ukuran kunci yang lebih kecil

Masalah Logaritma Diskret

Masalah logaritma diskret adalah tugas mencari eksponen k dalam persamaan $g^k \equiv h \pmod{p}$, dengan:

• g adalah basis yang diketahui (yaitu, generator)
• h adalah hasil yang diketahui (yaitu, elemen grup)
• p adalah bilangan prima (yaitu, orde grup)
• k adalah eksponen yang tidak diketahui (yaitu, logaritma diskret h dengan basis g)

Sederhananya, jika Anda mengetahui nilai g, h, dan p, masalah logaritma diskret adalah mencari k. Sebagai contoh, jika diberikan persamaan $2^k \equiv 9 \pmod{23}$, tujuannya adalah mencari k.

Masalah logaritma diskret dianggap sulit diselesaikan secara efisien, terutama untuk bilangan besar. Karena kesulitan ini, masalah tersebut menjadi dasar keamanan berbagai sistem kriptografi, termasuk Solana, Enkripsi ElGamal, Digital Signature Algorithms (yaitu, DSA dan ECDSA), serta Pertukaran Kunci Diffie-Hellman

Pertukaran Kunci Diffie-Hellman

Pertukaran kunci Diffie-Hellman adalah metode untuk bertukar kunci kriptografi secara aman melalui saluran publik.  Implementasi paling sederhana dan awalnya (yaitu, Finite Field Diffie-Hellman) adalah sebagai berikut:

• Alice dan Bob menyepakati dua bilangan secara terbuka — bilangan prima besar p (yaitu, modulus) dan basis g (yaitu, generator), yang merupakan akar primitif modulo p 
• Alice memilih bilangan bulat rahasia a, lalu mengirimkan $A \equiv g^a \pmod{p}$ kepada Bob
• Bob memilih bilangan bulat rahasia b, lalu mengirimkan $B \equiv g^b \pmod{p}$ kepada Alice
• Alice menghitung $s \equiv B^a \pmod{p}$ 
• Bob menghitung $s = A^b \pmod{p}$ 

Alice dan Bob kini memiliki nilai rahasia yang sama. Ini karena kedua komputasi menghasilkan rahasia s yang sama sebab:

Rahasia bersama s ini kemudian dapat digunakan sebagai kunci untuk enkripsi simetris, sehingga Alice dan Bob dapat berkomunikasi dengan aman. Keamanan pertukaran kunci Diffie-Hellman bergantung pada sulitnya masalah logaritma diskret. Tanpa mengetahui nilai rahasia a dan b, secara komputasi penyadap tidak mungkin memperoleh rahasia bersama tersebut. Ini dikenal sebagai fungsi satu arah—relatif mudah dihitung, tetapi sangat sulit dibalik.

Meskipun pertukaran kunci Finite Field Diffie-Helman aman dan digunakan secara luas, metode ini memerlukan ukuran kunci besar untuk menjamin keamanan. Misalnya, jika Alice dan Bob memilih modulus 23 secara terbuka, kunci akan jauh lebih mudah dipecahkan karena hanya ada 23 kemungkinan hasil dari n mod 23. Dengan demikian, metode ini dapat membutuhkan komputasi intensif dan kurang efisien. Untuk mengatasi tantangan tersebut, kriptografi kurva eliptik (ECC) menyediakan alternatif yang lebih efisien karena menawarkan tingkat keamanan yang sama dengan ukuran kunci jauh lebih kecil dan komputasi lebih cepat.

Kurva Eliptik

Kurva eliptik didefinisikan oleh persamaan $y^2 = x^3 + ax + b$, dengan a dan b sebagai konstanta. Kriptografi kurva eliptik pada dasarnya bekerja dengan titik-titik pada kurva eliptik tertentu. Kurva ini memiliki sejumlah sifat unik yang membuatnya berguna untuk kriptografi. Contohnya:

• Penjumlahan Titik — Jika terdapat dua titik, P dan Q, pada kurva eliptik tertentu, jumlahnya R = P + Q juga akan menjadi titik pada kurva tersebut. Artikel Preethi Kasireddy, Panduan Kriptografi Tanpa Kerumitan untuk Bukti Zero-Knowledge memberikan penjelasan yang baik tentang cara menjumlahkan titik pada kurva eliptik
• Perkalian Skalar — Jika terdapat titik P pada kurva eliptik tertentu dan bilangan bulat k, perkalian skalar adalah proses menjumlahkan titik P dengan dirinya sendiri sebanyak k kali. Proses ini akan menghasilkan titik lain (yaitu, kP) pada kurva. Proses ini digunakan untuk menghasilkan kunci publik dari kunci privat
• Masalah Logaritma Diskret — Masalah logaritma diskret pada kurva eliptik jauh lebih sulit diselesaikan dibandingkan padanannya dalam bilangan bulat. Jika diketahui titik P dan q = kP, secara komputasi mustahil menentukan k apabila parameter kurva dipilih dengan benar. Artinya, kurva eliptik memberikan keamanan yang sama seperti sistem tradisional dengan ukuran kunci jauh lebih kecil sehingga lebih efisien

Dengan pemahaman baru kita tentang teori grup, kita dapat mengatakan bahwa persamaan kurva eliptik tertentu akan memenuhi kumpulan aksioma berikut:

• Setiap dua titik dapat dijumlahkan untuk menghasilkan titik ketiga
• Urutan penjumlahan kedua titik tidak berpengaruh
• Jika Anda memiliki lebih dari dua titik untuk dijumlahkan, urutan penjumlahannya tidak berpengaruh
• Terdapat elemen identitas (yaitu, penambahan nol ke titik mana pun pada kurva menghasilkan titik yang sama)

Saya sangat menyarankan Anda membaca Kriptografi Kurva Eliptik oleh Georgie Bumpus untuk mempelajari struktur grup ini secara lebih menyeluruh. 

Kurva eliptik menawarkan tingkat keamanan yang sama dengan sistem kriptografi tradisional lainnya, seperti RSA, tetapi dengan ukuran kunci jauh lebih kecil. Sebagai contoh, kunci 256 bit dalam ECC memberikan keamanan yang sebanding dengan kunci 3.072 bit dalam RSA. Hal ini bermanfaat karena:

• Ukuran kunci yang lebih kecil mempercepat enkripsi dan dekripsi
• Kunci dan sertifikat memerlukan lebih sedikit ruang
• Kunci yang lebih kecil mengurangi jumlah data yang dikirimkan, yang bermanfaat dalam lingkungan dengan bandwidth terbatas, seperti blockchain

Kurva Montgomery

Kurva Montgomery adalah kurva eliptik yang didefinisikan oleh persamaan $By^2 = x^3 + Ax^2 + x$ pada medan berhingga, dengan A dan B sebagai konstanta, B tidak sama dengan nol, serta A bukan -2 atau 2. Kurva ini istimewa karena perkalian kurva eliptik dapat diimplementasikan secara lebih efisien menggunakan Montgomery ladder. 

Pada dasarnya, Montgomery ladder mengambil titik P pada kurva Montgomery dan skalar k, menginisialisasi dua titik dari titik tak terhingga ke P, lalu memperbarui setiap bit skalar k dari bit paling signifikan ke titik paling tidak signifikan. Gagasan utamanya adalah mempertahankan dua titik dan memperbaruinya dalam urutan operasi yang konstan, terlepas dari bit skalar k.

Hal ini penting karena beberapa alasan:

• Metode ini tahan terhadap serangan side-channel, yaitu setiap serangan yang didasarkan pada informasi tambahan yang dapat dikumpulkan akibat implementasi atau desain protokol atau algoritma tertentu. Ini adalah topik yang sangat, sangat teknis dan saya menyarankan Anda mendalaminya. Jenis serangan ini berkisar dari perubahan konsumsi daya perangkat keras selama komputasi hingga kebocoran radiasi elektromagnetik
• Koordinat y tidak diperlukan karena perkalian skalar dapat dilakukan hanya menggunakan koordinat x
• Metode ini beroperasi dalam waktu konstan, artinya waktu yang diperlukan untuk komputasi tertentu tidak bergantung pada nilai input

Kurva Montgomery banyak digunakan dalam protokol kriptografi, seperti algoritma X25519 untuk pertukaran kunci, yang menggunakan bentuk Montgomery dari kurva Curve25519. Algoritma ini menjadi fondasi komunikasi aman modern, termasuk implementasi dalam protokol populer seperti TLS. 

Kurva Edwards

Kurva Edwards adalah jenis kurva eliptik yang didefinisikan oleh persamaan $x^2 + y^2 = 1 + d x^2 y^2$, dengan d sebagai konstanta bukan nol dan tidak sama dengan 1.  

Kurva ini penting karena:

• Efisiensi Operasi Titik — Penjumlahan dua titik pada kurva Edwards lebih efisien dibandingkan bentuk kurva eliptik lainnya. Rumus penjumlahan dan penggandaan titik lebih sederhana dan melibatkan lebih sedikit operasi medan sehingga lebih cepat dihitung
• Rumus Penjumlahan Terpadu — Kurva Edwards menggunakan rumus penjumlahan terpadu, yang berarti rumus yang sama dapat digunakan untuk penjumlahan dan penggandaan titik. Hal ini mengurangi potensi kesalahan implementasi dan meningkatkan keamanan
• Kelengkapan — Untuk nilai d tertentu, kurva Edwards bersifat lengkap. Artinya, hukum penjumlahannya mencakup semua kemungkinan input tanpa pengecualian.
• Ketahanan terhadap Serangan Side-Channel — Seperti kurva Montgomery, kurva Edwards tahan terhadap serangan side-channel karena pola operasinya seragam dan dapat diprediksi.

Kurva Edwards yang banyak digunakan adalah Edwards25519, yang didefinisikan oleh persamaan $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Kurva ini dikenal karena aritmetikanya yang efisien dan ukuran kuncinya yang sebesar 256 bit. Skema tanda tangannya diimplementasikan dalam berbagai protokol dan sistem keamanan, termasuk Solana, OpenSSH, dan Tor. Monero menggunakan Edwards25519 sebagai dasar untuk menghasilkan pasangan kuncinya.

Mengapa ini penting?

Kurva eliptik sangat penting dalam bukti zero-knowledge karena efisiensi dan sifatnya yang meningkatkan keamanan. Perlu diperhatikan: penggunaan kurva eliptik memungkinkan pembuatan bukti yang lebih kecil dan cepat, yang sangat penting untuk implementasi praktis apa pun. Kita akan menganalisisnya lebih lanjut saat membahas perkembangan terkait zero-knowledge, tetapi kebutuhan akan bukti yang kecil dan cepat sangatlah penting dalam lingkungan komputasi tinggi dengan berbagai batasan akun dan transaksi. Inilah yang membuat bukti zero-knowledge menarik untuk membangun rollup, karena seseorang dapat menghasilkan bukti ringkas bahwa semua operasi pada L2 valid dan memvalidasinya pada L1.

Pada akhirnya, anggap kurva eliptik sebagai pengganti aritmetika modular. Dengan kurva eliptik, mendapatkan titik tertentu jauh lebih sulit. Jika kita menggunakan aritmetika modular tradisional dengan $g^a \bmod n$, dengan g sebagai generator, n sebagai bilangan prima besar, dan a sebagai kunci rahasia. Seperti yang sebelumnya dibahas dalam masalah logaritma diskret, Anda memerlukan bilangan prima yang sangat besar untuk mengamankan kunci rahasia. Kurva eliptik menawarkan alternatif yang lebih efisien dengan ukuran kunci lebih kecil, memberikan tingkat keamanan yang sama dengan performa yang jauh lebih baik.

Keacakan

Bagian lain dalam artikel ini tidak akan berarti tanpa keacakan, aspek fundamental dalam kriptografi. Bagaimana Anda dapat mengharapkan sistem tetap aman jika nilainya dapat diprediksi dan bias? Keacakan sejati sulit dicapai, tetapi sangat penting karena beberapa alasan:

• Pembuatan Kunci — Kunci kriptografi harus dihasilkan secara acak untuk memastikan kunci tersebut tidak dapat diprediksi dan aman
• Nonce dan Salt — Nonce (yaitu, bilangan yang digunakan satu kali) dan salt (yaitu, nilai acak yang ditambahkan ke data sebelum hashing) masing-masing mencegah serangan replay dan melindungi dari serangan prakomputasi
• Protokol Aman — Keacakan digunakan untuk memastikan keadilan dan keamanan serta mencegah prediktabilitas dan pola yang dapat dieksploitasi penyerang

Sebagian besar generator bilangan acak gagal menghasilkan bilangan acak yang dapat diverifikasi secara kriptografis. Hal ini membuatnya rentan terhadap manipulasi dan membatasi kasus penggunaannya. Namun, fungsi acak terverifikasi mengatasi masalah ini.

Fungsi Acak Terverifikasi

Verifiable Random Function (VRF) adalah primitif kriptografi yang menghasilkan output acak dan bukti bahwa output tersebut dihasilkan dengan benar dari input tertentu. VRF harus tidak dapat diprediksi, yang berarti output-nya tidak dapat dibedakan dari nilai acak oleh siapa pun yang tidak mengetahui input rahasianya. Keamanannya bergantung pada asumsi RSA bahwa sulit menghitung $y = h^d \bmod n$ tanpa mengetahui eksponen rahasia d dan pada keamanan fungsi hash H. 

Langkah-langkah utama VRF adalah sebagai berikut:

• Pembuatan Kunci — Pengguna menghasilkan sepasang kunci RSA, yaitu (e, n) sebagai kunci publik dan (d, n) sebagai kunci privat. Kunci publik e adalah eksponen, sedangkan n adalah modulus. Kunci privat d adalah eksponen rahasia
• Komputasi — Dengan input x, pengguna menghitung output VRF y dan bukti π. Pertama, hash h = H(x) dihitung, dengan H sebagai fungsi hash kriptografi. Kemudian $y = h^d \bmod n$ dihitung, yang merupakan tanda tangan RSA dari hash tersebut. Terakhir, bukti π = (h, y) dihitung
• Verifikasi — Dengan kunci publik (e, n), input x, output y, dan bukti π = (h, y), siapa pun dapat memverifikasi kebenaran output VRF dengan memeriksa apakah hash h sama dengan $H(x)$ dan apakah $y^e \equiv h \pmod{n}$ untuk memverifikasi persamaan RSA‍

VRF sering digunakan dalam protokol konsensus yang membutuhkan keacakan yang tidak dapat diprediksi, tetapi tetap dapat diverifikasi. L1, termasuk Algorand, Cardano, Internet Computer, dan Polkadot, menggunakan VRF dalam mekanisme konsensusnya untuk memilih produsen blok secara acak. Chainlink menawarkan Chainlink VRF sebagai lapisan abstraksi antara pengguna dan blockchain untuk menghasilkan nilai yang terbukti adil dan dapat diverifikasi. Pyth Entropy juga menawarkan sumber keacakan yang andal dan aman.

Seremoni dan Trusted Setup

Seremoni kriptografi adalah protokol atau acara tempat komputasi kriptografi penting dilakukan dalam lingkungan yang aman dan terkendali. Terdapat beberapa jenis seremoni kriptografi, yaitu:

• Seremoni Pembuatan Kunci — Seremoni ini melibatkan pembuatan kunci kriptografi untuk memastikan tidak ada satu entitas pun yang mengendalikan proses pembuatan kunci
• Seremoni Pembuatan Parameter — Seremoni ini melibatkan pembuatan parameter kriptografi yang akan digunakan oleh banyak pihak
• Seremoni Multi-Party Computation (MPC) — Seremoni ini melibatkan banyak pihak yang bersama-sama melakukan komputasi kriptografi untuk memastikan tidak ada satu pihak pun yang dapat membahayakan proses

Seremoni trusted setup adalah acara atau proses khusus yang dirancang untuk menghasilkan sekumpulan parameter kriptografi yang diperlukan untuk menjalankan protokol kriptografi. Dalam bagian mengenai bukti zero-knowledge interaktif dan noninteraktif, kita mengidentifikasi bahwa langkah pertama pembuktian adalah membuat pembukti dan pemverifikasi menyepakati suatu nilai yang akan digunakan. Dalam seremoni trusted setup, banyak peserta menyumbangkan keacakan ke dalam penyiapan untuk memastikan tidak ada satu peserta pun yang mengendalikan proses. Setiap peserta menghasilkan nilai acak yang digabungkan dengan nilai dari peserta lain. Output gabungan tersebut menjadi sekumpulan parameter yang dapat dipercaya semua orang. 

Proses ini sangat penting karena jika semua peserta berkolusi, mereka dapat membobol sistem dengan menghasilkan bukti untuk klaim yang tidak valid. Namun, keberadaan satu peserta yang jujur saja sudah cukup untuk menjamin keamanan parameter. 

Zcash dikenal menggunakan seremoni tepercaya untuk memulai fitur privasi chain tersebut. Ethereum juga mengadakan KZG Ceremony, ritual publik terkoordinasi untuk menyediakan fondasi kriptografi bagi upaya penskalaan mereka (misalnya, EIP-4844 / proto-danksharding). 

Perlu diperhatikan bahwa beberapa sistem bukti zero-knowledge, seperti zk-STARK, tidak memerlukan trusted setup. Kita akan membahasnya lebih lanjut dalam artikel kedua.

Kesimpulan

Melalui artikel ini, kita telah membahas teori, matematika, dan kriptografi yang mendasari bukti zero-knowledge. Inilah semua yang perlu Anda ketahui untuk mulai memahami apa itu bukti zero-knowledge. Sekarang, kita dapat mulai menerapkan pembelajaran ini pada jaringan seperti Solana untuk berkontribusi terhadap diskusi dan pengembangan bukti zero-knowledge secara keseluruhan.

Kami melanjutkan analisis ini dalam artikel kedua sekaligus terakhir dari seri dua bagian kami tentang bukti zero-knowledge, yang diberi judul Bukti Zero-Knowledge: Penerapannya di Solana. 

Jika Anda sudah membaca sejauh ini, terima kasih, anon! Pastikan untuk memasukkan alamat email Anda di bawah agar tidak melewatkan informasi terbaru tentang perkembangan Solana. Siap mempelajari lebih dalam? Jelajahi artikel terbaru di blog Helius dan lanjutkan perjalanan Solana Anda hari ini.

Sumber Daya Tambahan

• Apakah Keacakan Sejati Itu Ada?
• Kurva Eliptik — Computerphile
• Pengantar Kelas Kompleksitas NP-Complete
• Masalah Pertukaran Kunci — Computerphile
• Unit Khan Academy tentang Kriptografi
• Kriptografi Kunci Publik — Computerphile
• Kompleksitas Pengetahuan Sistem Bukti Interaktif