ZK-STARK là gì? Scalable, Transparent và Kháng Quantum

IZK-STARK là gì?

ZK-STARK là viết tắt của Zero-Knowledge Scalable Transparent Argument of Knowledge. Được Eli Ben-Sasson và nhóm nghiên cứu tại Technion (Israel) đề xuất năm 2018, STARK ra đời như một giải pháp thay thế SNARK với ba cải tiến cốt lõi được nhấn mạnh ngay trong tên gọi:

• Scalable: Proving time và verification time scale tốt với kích thước computation. Proving time là quasi-linear O(n·polylog(n)), tốt hơn đáng kể so với một số SNARK scheme khi n lớn.
• Transparent: Không cần trusted setup — không có toxic waste, không có rủi ro từ setup ceremony. Mọi tham số đều public và có thể kiểm chứng.
• Argument of Knowledge: Cùng với SNARK, STARK cũng đảm bảo prover thực sự "biết" witness — không thể chứng minh một điều sai trừ khi vi phạm hardness assumption của hash function.

Điểm khác biệt căn bản nhất: STARK dùng hash function (cụ thể là Merkle tree và FRI protocol) thay cho elliptic curve pairing của SNARK. Hash function là cấu trúc toán học "đơn giản" hơn, được hiểu rõ hơn về mặt bảo mật và không bị đe dọa bởi máy tính lượng tử trong tương lai gần.

Trong blockchain, STARK đang được dùng chủ yếu bởi StarkWare (StarkNet, StarkEx) và đang được nghiên cứu tích hợp vào nhiều zkEVM dự án khác. Để hiểu bức tranh tổng thể của zero-knowledge proof, hãy xem ZK Proof tổng quan.

IITransparent — Loại bỏ hoàn toàn Trusted Setup

Đây là ưu điểm chiến lược nhất của STARK so với hầu hết SNARK. Trong SNARK (trừ HALO2), cần tổ chức trusted setup ceremony để tạo ra Common Reference String (CRS). Nếu bất kỳ người tham gia nào giữ lại toxic waste, toàn bộ hệ thống có thể bị compromise.

Tại sao "transparent" quan trọng?

Với STARK, quá trình setup chỉ cần một chuỗi ngẫu nhiên công khai (public randomness) — có thể lấy từ block hash hay bất kỳ nguồn entropy nào. Không có secret nào được tạo ra, không có toxic waste nào cần hủy. Điều này mang lại:

• Trustless setup: Bất kỳ ai cũng có thể verify toàn bộ tham số hệ thống từ đầu đến cuối.
• Auditable: Không có "điểm tin cậy" ẩn — phù hợp với tinh thần "don't trust, verify" của blockchain.
• No ceremony risk: Không lo lắng về việc ai đó trong ceremony thiếu trung thực.
• Universal: Không cần setup riêng cho từng circuit — một bộ tham số dùng cho mọi loại computation.

Trade-off: Proof size lớn hơn

Để đạt được tính transparent, STARK phải "bù" bằng cách dùng nhiều hash hơn trong quá trình prove và verify. Kết quả là proof size của STARK thường từ 50KB đến 500KB — lớn hơn nhiều so với ~200 byte của Groth16 SNARK. Điều này có nghĩa là chi phí calldata khi post proof lên Ethereum (Layer 1) cao hơn đáng kể.

IIIFRI Protocol — Trái tim của ZK-STARK

FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) là giao thức mật mã cốt lõi cho phép STARK hoạt động mà không cần elliptic curve pairing. Hiểu FRI là hiểu bản chất của STARK.

Bài toán FRI giải quyết

FRI giải quyết bài toán: làm thế nào để prove rằng một oracle function f (được commit dưới dạng Merkle tree của các evaluation) gần với một đa thức bậc thấp, mà không cần reveal toàn bộ f? Nói đơn giản hơn: prove rằng "tôi biết một đa thức d(x) có bậc ≤ d sao cho f ≈ d" — đây chính là cách biểu diễn computation trong STARK.

Quy trình FRI — Folding Technique

FRI dùng kỹ thuật folding lặp lại để giảm dần bậc đa thức:

1. Prover commit đa thức f bậc d bằng Merkle tree của tất cả evaluation trên một domain lớn L.
2. Verifier gửi random challenge r.
3. Prover "fold" f thành f' bậc d/2 bằng cách kết hợp: f'(x²) = f_even(x²) + r·f_odd(x²).
4. Lặp lại bước 2–3 cho đến khi đa thức đủ nhỏ để reveal hoàn toàn.
5. Verifier kiểm tra tính nhất quán qua các vòng fold bằng Merkle proof.

Mỗi vòng fold cắt đôi bậc đa thức, nên toàn bộ quá trình chỉ cần O(log d) vòng. Đây là lý do STARK "scalable" — proving time chỉ tăng quasi-linear theo kích thước computation.

Từ Interactive đến Non-Interactive: Fiat-Shamir

FRI là interactive proof — cần verifier gửi challenge. Để làm non-interactive (không cần trao đổi qua lại), STARK dùng Fiat-Shamir heuristic: thay thế challenge của verifier bằng hash của transcript cho đến thời điểm đó. Kết quả là proof có thể tạo độc lập mà không cần verifier online.

IVKiến trúc kỹ thuật của ZK-STARK

Quy trình từ computation đến STARK proof gồm nhiều bước trừu tượng hóa, khác biệt so với pipeline R1CS → QAP của SNARK.

Bước 1: Execution Trace

Computation được biểu diễn dưới dạng execution trace — một bảng matrix trong đó mỗi hàng là trạng thái của computation tại một thời điểm, mỗi cột là một register. Nếu computation gồm T bước với W register, trace là matrix T×W trên trường hữu hạn.

Bước 2: Algebraic Intermediate Representation (AIR)

Thay vì R1CS, STARK dùng AIR để mô tả ràng buộc. AIR gồm hai loại ràng buộc:

• Boundary constraints: Giá trị tại các bước đầu/cuối phải bằng giá trị đã biết (input/output).
• Transition constraints: Quan hệ giữa trạng thái tại bước t và bước t+1 phải thỏa mãn một đa thức nhất định.

AIR linh hoạt hơn R1CS vì cho phép express các ràng buộc phức tạp hơn, đặc biệt với các tính toán lặp lại (loop). Đây là lý do STARK phù hợp với virtual machine (CPU simulation) hơn SNARK.

Bước 3: Polynomial IOP

Execution trace được interpolate thành các đa thức (một đa thức cho mỗi cột). Prover commit các đa thức này bằng Merkle tree. Verifier gửi random challenges để prover chứng minh các ràng buộc AIR thỏa mãn. Sau đó FRI được dùng để prove độ bậc thấp của các đa thức liên quan.

Bước 4: Proof composition

Proof cuối cùng bao gồm Merkle root của trace polynomial, các Merkle proof cho các query điểm ngẫu nhiên, và FRI proof. Verifier chỉ cần query O(log T) điểm ngẫu nhiên để đạt xác suất lỗi negligible.

VSo sánh chi tiết ZK-STARK vs ZK-SNARK

Hai hệ thống có điểm mạnh bổ sung cho nhau. Lựa chọn phụ thuộc vào ưu tiên của use case:

Kết hợp STARK + SNARK: Best of both worlds

StarkWare đã giải quyết vấn đề proof size lớn bằng cách dùng recursive proof composition: STARK prove execution, sau đó một SNARK prove tính đúng đắn của STARK verifier. Kết quả là một SNARK nhỏ (~200 byte) đại diện cho toàn bộ STARK proof. Đây là nền tảng của hệ thống SHARP (Shared Prover) của StarkWare.

VICairo VM — Ngôn ngữ được thiết kế cho STARK

Một trong những thách thức lớn khi dùng STARK để prove general computation là thiết kế AIR cho mọi loại instruction set. StarkWare giải quyết bằng cách tạo ra Cairo VM — một virtual machine được thiết kế từ đầu để STARK-friendly.

Tại sao cần Cairo VM?

EVM (Ethereum Virtual Machine) không được thiết kế với ZK trong đầu. Mỗi opcode EVM có thể cần hàng trăm đến hàng nghìn AIR constraint khi prove. Ngược lại, Cairo VM được thiết kế với một instruction set tối giản, mỗi instruction chỉ cần vài constraint rõ ràng.

Cairo language

Cairo là ngôn ngữ lập trình high-level cho Cairo VM, được design để biên dịch xuống Cairo bytecode hiệu quả cho STARK proving. Cairo 1.0 (hiện tại) dùng cú pháp tương tự Rust, có kiểu dữ liệu mạnh và hỗ trợ các pattern blockchain phổ biến. Smart contract trên StarkNet được viết bằng Cairo.

STWO Prover — Thế hệ mới

StarkWare năm 2024 ra mắt STWO prover — thế hệ prover mới dùng Circle STARK, một biến thể STARK sử dụng Circle group thay vì multiplicative group thông thường. STWO nhanh hơn ~10x so với Stone prover cũ, mở ra khả năng real-time proving.

VIIỨng dụng thực tế: StarkNet, StarkEx và hệ sinh thái

StarkEx — Application-specific scaling

StarkEx là dịch vụ scaling theo yêu cầu (SaaS) của StarkWare, cung cấp STARK-based scaling cho các ứng dụng cụ thể. Mỗi application có một instance riêng, được tùy chỉnh cho use case:

• dYdX v3: Dùng StarkEx để scale perpetual trading, đạt 10,000+ TPS so với ~14 TPS của Ethereum.
• Immutable X: Dùng StarkEx cho NFT minting và trading, zero gas fee cho user.
• Sorare, RhinoFi: Cũng dùng StarkEx cho game và DeFi.

StarkNet — Permissionless Layer 2

StarkNet là Layer 2 permissionless, cho phép bất kỳ developer nào deploy smart contract Cairo. Khác với StarkEx, StarkNet là general-purpose — không giới hạn use case. Kiến trúc của StarkNet:

• User gửi giao dịch đến Sequencer.
• Sequencer batch giao dịch và tạo execution trace.
• Prover (Stone/STWO) tạo STARK proof từ trace.
• SHARP aggregator wrap STARK thành SNARK để submit lên Ethereum.
• Smart contract StarkCore trên L1 verify SNARK proof.

SHARP — Shared Prover

SHARP (Shared Prover) là hệ thống prove tập trung của StarkWare, nhận job từ nhiều application (StarkNet, StarkEx, ...), aggregate và prove chung trong một batch lớn. Chia sẻ chi phí proof submission giữa nhiều user — mỗi giao dịch chỉ trả một phần nhỏ chi phí L1 gas.

Các dự án khác dùng STARK

Polygon Miden đang xây dựng zkVM dựa trên STARK (Miden VM). Risc0 dùng STARK để prove RISC-V execution — cho phép prove bất kỳ Rust/C program nào. SP1 (Succinct Labs) cũng dựa trên STARK để tạo zkVM. Xu hướng chung: STARK đang trở thành nền tảng cho "universal" ZK computation.

VIIIGiới hạn hiện tại và hướng phát triển

Proof size — Thách thức on-chain

Proof size lớn (~50–500KB) là barrier chính khi submit lên Ethereum. Với EIP-4844 (blob transactions), data availability rẻ hơn nhiều nhưng verification cost vẫn còn đáng kể. Giải pháp trước mắt là SNARK wrapping (như SHARP), nhưng tạo ra dependency vào SNARK circuit.

EVM compatibility — Bài toán chưa giải triệt để

StarkNet dùng Cairo VM (không compatible EVM), đòi hỏi developer học ngôn ngữ mới. Kakarot (zkEVM viết bằng Cairo) là nỗ lực mang EVM compatibility lên StarkNet, nhưng vẫn còn nhiều opcode chưa hỗ trợ đầy đủ.

Prover centralization

Hiện tại StarkNet dùng prover tập trung của StarkWare (SHARP). Decentralized proving network đang được phát triển nhưng chưa ra production. Đây là rủi ro censorship tương tự sequencer centralization trong các L2 khác.

Tương lai: Quantum era và STARK

Khi máy tính lượng tử đủ mạnh xuất hiện, các hệ thống dựa trên elliptic curve (bao gồm hầu hết SNARK) sẽ bị ảnh hưởng. STARK, với nền tảng hash function, được coi là "quantum-resistant" — một lợi thế dài hạn quan trọng. Dù timeline vẫn còn bất định, việc thiết kế hệ thống quantum-safe ngay từ bây giờ là chiến lược đúng đắn.

❓Câu Hỏi Thường Gặp