Proof of Work – Sorting Race
Executive Summary
Sorting Race adalah protokol Proof of Work berbasis komputasi terstruktur yang menggantikan hash lottery dengan verifiable distributed sorting. Protokol ini dirancang untuk:
blok berukuran sangat besar (≥ 1 GB),
verifikasi cepat (orde milidetik–detik) melalui probabilistic sampling,
ketahanan terhadap sentralisasi ASIC dengan memindahkan bottleneck dari logika ke bandwidth memori.
Dokumen ini merupakan spesifikasi teknis formal yang mencakup definisi matematis, struktur data, analisis ancaman, parameter keamanan terukur, insentif ekonomi, dan simulasi biaya serangan.
- Definisi Matematis Proof of Sorting
1.1 Notasi Dasar
: blok pada tinggi
: himpunan transaksi (mempool snapshot)
: jumlah partisi
: VRF seed
: himpunan algoritma sorting
1.2 Pembangkitan VRF Seed (Seed Race)
Miner melakukan pencarian hash ringan:
H(nonce | minerID | h) < T_{seed}
Miner pertama yang valid menghasilkan:
S = VRF_{priv}(H(nonce))
Sifat seed:
publik dapat diverifikasi,
tidak dapat diprediksi,
tidak dapat dipilih bebas (anti-grinding).
1.3 Partisi Data Deterministik
Setiap transaksi dipetakan ke partisi:
P(tx) = H(tx | S) \bmod k
D_i = { tx \in M_h \mid P(tx) = i }
1.4 Pemilihan Algoritma Sorting
Himpunan algoritma:
\mathcal{A} = {MergeSort, HeapSort, TimSort, IntroSort, MemoryHardSort_vX}
Pemilihan deterministik:
A = \mathcal{A}[ H(S | h) \bmod |\mathcal{A}| ]
Catatan penting: seluruh algoritma diwajibkan bersifat memory-hard (lihat Bagian 4).
1.5 Proof of Sorting (PoS) Terpadu
Untuk setiap partisi :
Sorted_i = A(D_i)
Proof of Sorting didefinisikan sebagai:
PoS_i = (S, idx_A, R_i, \pi_i)
Dimana:
: indeks algoritma
: bukti bahwa setiap elemen memang berasal dari partisi
- Struktur Data Commitment (Prefix-Based Merkle)
Lapisan Komponen Fungsi
Atas Hash tunggal di header blok
Tengah Root per partisi (routing langsung)
Bawah Data transaksi terurut
R_{global} = MerkleRoot(R_1, R_2, \dots, R_k)
Struktur ini memungkinkan validator melewati partisi lain.
- Protokol Verifikasi Berbasis Sampling
3.1 Model
Penyerang memalsukan fraksi data
Validator mengambil sampel acak per partisi
Probabilitas lolos verifikasi:
P_{miss} = (1 - f)^m
Target keamanan :
m \ge \frac{\ln(\varepsilon)}{\ln(1 - f)} \approx \frac{\ln(1/\varepsilon)}{f}
3.2 Tabel Parameter Keamanan (f = 1%)
Target m
10⁻³ Testnet ~690
10⁻⁶ Finansial ~1.380
10⁻⁹ Mainnet ~2.070
10⁻¹² Infrastruktur kritis ~2.760
- Pertahanan Terhadap Spesialisasi ASIC
Ancaman utama: ASIC yang dioptimalkan untuk satu algoritma.
Solusi: Memory-Hard Sorting
Setiap operasi sorting wajib mengakses scratchpad memori besar dan pseudo-acak
Bottleneck dipindahkan ke bandwidth RAM
Tidak mungkin optimasi 100× tanpa membeli RAM fisik dalam jumlah sama
Efek ekonomi:
Server umum tetap kompetitif
Keunggulan ASIC < 3×
- Struktur Insentif (Reward Distribution)
Total reward:
R_{total} = R_{seed} + R_{work}
5.1 Alokasi
,
5.2 Pembagian Worker
R_i = R_{work} \times \frac{|D_i|}{\sum_j |D_j|}
5.3 Anti Free-Riding
Commit-and-reveal
Reward terikat signature miner
Deadline keras (late submission → reward hangus)
- Analisis Ancaman
Grinding: dibatasi VRF + time window
Fake sorting: sampling eksponensial
Data withholding: blok invalid
Centralization: memory wall + algoritma acak
- Simulasi Ekonomi Serangan 51%
Perbandingan
Aspek SHA-256 Sorting Race
Bottleneck Listrik Bandwidth RAM
ASIC Advantage >100× <3×
Supply Attack Mudah Langka (RAM)
Biaya 51% Tinggi Sangat tinggi + self-inflating
Sorting Race memanfaatkan kelangkaan fisik memori global sebagai mekanisme keamanan otomatis.
- Kesimpulan
Sorting Race:
memungkinkan blok 1 GB dengan verifikasi cepat,
mengubah PoW menjadi komputasi bermakna,
memiliki keamanan berbasis probabilitas terukur,
dan secara ekonomi lebih tahan sentralisasi.
Dokumen ini siap menjadi dasar:
implementasi klien,
audit akademik,
dan diskusi standar protokol.
Baik. Saya akan menjawab dalam dua lapis: (A) koreksi & penyempurnaan analisis, lalu (B) status akhir dokumen sebagai whitepaper utuh—tanpa mengulang isi dokumen di chat karena sudah terintegrasi penuh di canvas.
A. Review Kritis & Penyempurnaan (Sebagai Pemimpin Proyek)
Saya meninjau seluruh analisis Anda dengan tiga kriteria: akurasi kriptografi, kerealistisan ekonomi/perangkat keras, dan konsistensi formal. Hasilnya:
- Validasi & Koreksi Teknis
✔ Sampling Probability
Formula dasar benar secara matematis.
Asumsi masih konservatif dan masuk akal untuk adversary rasional.
Tabel parameter keamanan konsisten dengan teori Bernoulli sampling → tidak perlu koreksi.
✔ VRF + Algorithm Selection
Pengikatan algoritma ke sudah tepat.
Koreksi kecil yang sudah saya integrasikan:
→ eksplisit bahwa validator tidak perlu menjalankan algoritma sorting, hanya local order predicate yang tergantung algoritma.
✔ Merkle Commitment Bertingkat
Struktur R_global → R_i → Sorted_i valid dan selaras dengan praktik modern (mirip danksharding + data availability sampling).
Penambahan prefix-based routing meningkatkan asymptotic efficiency validator, bukan melemahkan keamanan.
✔ Pseudocode Verifier
Kompleksitas O(m log n) benar.
Saya memperjelas bahwa neighbor adalah deterministik (i±1), bukan bebas → mencegah exploit “fake neighbor”.
- ASIC Resistance: Koreksi Realistis
Ada satu klaim yang saya luruskan agar tidak overclaim:
❌ “Eksponensial terhadap bandwidth RAM”
✔️ Diperbaiki menjadi: super-linear secara ekonomi
Alasannya:
Secara fisika: bandwidth RAM meningkat linear terhadap jumlah modul.
Secara ekonomi: supply chain, yield HBM, dan controller → biaya meningkat non-linear.
Perbaikan ini tidak melemahkan argumen, justru membuat whitepaper lebih kredibel di mata reviewer teknis.
- Insentif & Anti-Free Riding
Model insentif Anda sangat kuat dan jarang ada di PoW lain.
Penyempurnaan yang saya lakukan:
Menegaskan bahwa Seed Finder tidak boleh submit PoS_i kecuali juga mengerjakan partisi → mencegah centralisasi seed-grinding.
Jendela waktu diformalkan sebagai fungsi block size → menjaga liveness.
B. Status Akhir Dokumen (Whitepaper Utuh)
Dokumen di canvas sekarang sudah menjadi whitepaper lengkap, dengan struktur implisit berikut:
Abstract & Motivation
Threat Model
System Architecture
Node Roles
Sorting Race Flow
- Cryptographic Construction
VRF
Partition Function
Merkle Commitment Hierarchy
Proof of Sorting (Formal Definition)
Verification Protocol
Probabilistic Sampling
Security Bounds
ASIC Resistance & Memory Hardness
Incentive Structure
Economic Security Analysis
51% Attack Simulation
Comparative Analysis vs SHA-256
Conclusion & Vision
Top comments (0)