Knot Recognition sebagai Bukti Kerja

Saat ini bitcoin memiliki sistem proof of work (PoW) menggunakan SHA256. Fungsi hash lainnya menggunakan bukti sistem kerja menggunakan grafik, inversi fungsi hash parsial.

Apakah mungkin untuk menggunakan masalah Keputusan dalam Knot Theory seperti pengakuan Knot dan menjadikannya sebagai bukti fungsi kerja? Adakah yang pernah melakukan ini sebelumnya? Juga, ketika kita memiliki fungsi Proof of Work ini, apakah akan lebih berguna daripada apa yang sedang dihitung?

Jika ada protokol Arthur-Merlin untuk simpul yang mirip dengan protokol [GMW85] dan [GS86] Arthur-Merlin untuk Grafik Non Isomorfisme, maka saya percaya bukti kerja cryptocurrency dapat dirancang, di mana masing-masing bukti pembuktian pekerjaan menunjukkan bahwa dua simpul kemungkinan tidak setara / isotop.

Secara lebih terperinci, seperti yang diketahui dalam protokol Graph Non Isomorphism [GMW85], Peggy theverver ingin membuktikan kepada Vicky verifier bahwa dua (kaku) grafik dan pada simpul bukan isomorfik. Vicky diam-diam dapat melemparkan koin acak , bersama dengan koin lain untuk menghasilkan permutasi , dan dapat memberikan kepada Peggy sebuah grafik baru . Peggy harus menyimpulkan . Jelas Peggy hanya dapat melakukan ini jika dua grafik tidak isomorfik.G 1 V i ∈ { 0 , 1 } π ∈ S V π ( G i ) $G_0$$G_1$$V$$i\in\{0,1\}$$\pi\in\ S_V$$\pi(G_i)$$i$

Demikian pula, dan lebih relevan untuk keperluan pembuktian-kerja , seperti yang diajarkan oleh [GS86] versi Arthur-Merlin dari protokol yang sama termasuk Arthur setuju dengan Merlin pada , , yang diberikan sebagai contoh misalnya matriks kedekatan. Arthur secara acak memilih fungsi hash , bersama dengan gambar . Arthur menyediakan dan ke Merlin. Merlin harus menemukan sehingga .G 1 H : { 0 , 1 } ∗ → { 0 , 1 } k y H y ( i , π ) H ( π ( G i ) ) = $G_0$$G_1$$H:\{0,1\}^*\rightarrow\{0,1\}^k$$y$$H$$y$$(i,\pi)$$H(\pi(G_i))=y$

Yaitu, Merlin mencari preimage dari hash , preimage menjadi permutasi dari salah satu dari dua matriks kedekatan yang diberikan. Selama dipilih dengan benar, jika dua grafik dan bukan isomorfik maka akan ada peluang yang lebih tinggi bahwa preimage akan ditemukan, karena jumlah matriks kedekatan dalam mungkin dua kali lebih besar daripada jika .k G 0 G 1 G 0 ∪ G 1 G 0 ≅ G $H$$k$$G_0$$G_1$$G_0 \cup G_1$$G_0\cong G_1$

Untuk mengonversi protokol [GS86] di atas menjadi proof-of-work, identifikasikan penambang sebagai Merlin, dan identifikasikan node lain sebagai Arthur. hash , yang, untuk semua tujuan, mungkin hash digunakan dalam Bitcoin. Demikian pula, setuju bahwa akan selalu , mirip dengan persyaratan Bitcoin yang hash dimulai dengan sejumlah terkemuka ‘s.S H A 256 y 0 $H$$\mathsf{SHA256}$$y$$0$$0$

• Jaringan setuju untuk membuktikan bahwa dua grafik kaku dan bukan isomorfik. Grafik dapat diberikan oleh matriks kedekatan merekaG $G_0$$G_1$

• Seorang penambang menggunakan tautan kembali ke blok sebelumnya, bersama dengan akar Merkle sendiri dari transaksi keuangan, sebut saja , bersama dengan miliknya sendiri , untuk menghasilkan angka acakc Z = H ( c ‖ B $B$$c$$Z=H(c\Vert B)$

• Penambang menghitunguntuk memilih( i , π $W= Z\:mod\: 2V!$$(i,\pi)$

• Penambang mengkonfirmasi bahwa - yaitu, untuk mengonfirmasi bahwa dipilih secara acak bukan bukti bahwa grafiknya isomorfis$\pi(G_i)\neq G_{1-i}$$\pi$

• Jika tidak, penambang menghitung hash$W=H(\pi(G_i))$

• Jika dimulai dengan angka sesuai , maka penambang “menang” dengan menerbitkan0 ( c , B $W$$0$$(c,B)$

• Node lain dapat memverifikasi bahwa untuk menyimpulkan , dan dapat memverifikasi bahwa dimulai dengan tingkat kesulitan yang tepat 's( i , π ) W = H ( π ( G i ) ) $Z=H(c\Vert B)$$(i,\pi)$$W=H(\pi(G_i))$$0$

Protokol di atas tidak sempurna, beberapa kinks saya pikir perlu dikerjakan. Misalnya, tidak jelas cara membuat dua grafik acak dan yang memenuhi sifat kekakuan yang baik, misalnya, juga tidak jelas bagaimana menyesuaikan kesulitan selain dengan menguji grafik dengan simpul yang lebih banyak atau lebih sedikit. Namun, saya pikir ini mungkin bisa diatasi.G $G_0$$G_1$

Tetapi untuk protokol yang serupa pada masalah simpul , ganti permutasi acak pada matriks adjacency dari salah satu dari dua grafik dan dengan beberapa operasi acak lainnya pada diagram simpul atau diagram grid ... atau sesuatu. Saya tidak berpikir Reidemeister bergerak secara acak berfungsi, karena ruang menjadi terlalu sulit terlalu cepat.G $G_1$$G_2$

[HTY05] mengusulkan protokol Arthur-Merlin untuk kebodohan, tetapi sayangnya ada kesalahan dan mereka menarik klaim mereka.

[Kup11] menunjukkan bahwa, dengan asumsi Hipotesis Riemann Umum, ketekunan adalah dalam , dan menyebutkan bahwa ini juga menempatkan keterikatan dalam , tetapi saya akan jujur ​​saya tidak tahu bagaimana menerjemahkan ini ke dalam kerangka kerja di atas; yang protokol [Kup11] saya pikir melibatkan menemukan seorang perdana langka modulo yang sistem persamaan polinomial adalah . utama jarang dalam , dan sistem persamaan polinom sesuai dengan representasi dari kelompok komplemen simpul.A M A M p 0 p H ( p ) = $\mathsf{NP}$$\mathsf{AM}$$\mathsf{AM}$$p$$0$$p$$H(p)=0$

Sebagai catatan, lihat jawaban ini untuk pertanyaan serupa di situs saudara perempuan, yang juga membahas kegunaan bukti kerja yang "berguna".

Referensi:

[GMW85] Oded Goldreich, Silvio Micali, dan Avi Wigderson. Bukti yang Menghasilkan Hanya Validitas mereka, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Koin Pribadi versus Koin Publik dalam Sistem Bukti Interaktif, 1986.

[HTY05] Masao Hara, Seiichi Tani, dan Makoto Yamamoto. UNKNOTTING ada di , 2005.$\mathsf{AM} \cap \mathsf{coAM}$

[Kup11] Greg Kuperberg. Ketertarikan ada dalam , modulo GRH, 2011.$\mathsf{NP}$

Saya pikir cara untuk melakukan ini adalah membuat tabel simpul mosaik dengan seperangkat batasan untuk melarang pintasan. Jadi meja simpul adalah seperangkat simpul yang memiliki properti tertentu. Properti di bawah ini menjadi simpul utama.

Sekarang mari kita lihat tabel simpul yang terbuat dari simpul mosaik: mosaik simpul adalah jenis representasi simpul yang menggunakan ubin bukannya string dalam ruang tiga dimensi.

Sekarang mari kita secara formal mendefinisikan apa itu mosaik simpul:

Dari https://arxiv.org/pdf/1602.03733.pdf Mosaik simpul adalah representasi dari simpul pada kisi yang terdiri dari 11 ubin di sini ada di bawah ini.

Ini adalah titik awal saya meminta Anda untuk meja simpul mosaik dengan serangkaian batasan. Yang ingin saya tanyakan kepada Anda adalah memberi saya meja dengan properti berikut

1. $C$
2. $N$$M$
3. $K$
4. $O$$O_n$$K$
5. Semua operasi harus unik
6. $CR$
7. Itu harus dikodekan sebagai mosaik simpul.

Jadi mari kita encode trefoil dalam format yang dapat dibaca mesin. Kami mengambil setiap ubin dan memberi mereka nomor (01-11). Menggunakan raket bahasa pemrograman akan terlihat seperti ini

(define trefoil (array #[#[00 02 01 00]
                         #[02 10 09 01]
                         #[03 09 04 06]
                         #[00 03 05 04]] : Integer))

$3_1$

(struct braidcoin ([source_knot : (Matrix Integer)]
                   [target_knot : (Matrix Integer)]
                   [crossing_number : (Refine [n : Integer] (> n 0))]
                   [dimention : (Refine [n : Integer] (> n 0))]
                   [timestamp : date])

$3_1$

Jadi, sekarang kita telah menetapkan apa yang seharusnya menjadi output. Sekarang bagaimana kita mengatasi masalah generasi?

Jadi kita tahu bahwa di bawah ambient isotopy bahwa Anda bisa mendapatkan simpul diagram lain diberi simpul diagram lain dalam satu set terbatas dari reidmeister bergerak. Jadi mari kita hasilkan dua tautan acak. Tugas yang kemudian kita definisikan diberi dua tautan acak. Saya ingin Anda menunjukkan bahwa keduanya setara dengan menghitung setiap simpul yang mungkin bisa diekspresikan atau menunjukkan bahwa mereka tidak sama dengan memberi saya satu set status atau jalur ke simpul yang dikenal di sebuah meja.

Cara di mana kita dapat meningkatkan kecepatan mengetahui bahwa sebuah simpul ada di tabel atau tidak adalah dengan membangun tabel hash dengan indeks sebagai polinom Alexander. Setiap instance akan memiliki Alexander Polynominal dihitung untuk itu dan jika mereka berbagi polynominal Alexander yang sama itu akan ditambahkan sebagai elemen ke tabel itu.

Saya memiliki bagian dari program kerja di intisari berikut: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b