Ipinakilala ni a16z ang Lattice Jolt: 3x mas mabilis na mga patunay na may post-quantum security

May-akda: a16z crypto

Isinalin: Deep潮 TechFlow

DeepChaoyu Guide: Ang zkVM ay palaging pinaparusahan dahil sa “mabagal na pagpapatotoo at sobrang laki ng lalabas,” ngunit gamit ang lattice cryptography upang palitan ang elliptic curve, nagawa ng a16z na i-triple ang bilis ng pagpapatotoo at bawasan ang laki ng patotoo sa ilalim ng 100KB. Ito ang tanging post-quantum na solusyon na nakakalaban sa tradisyonal na elliptic curve sa bilis, at may direktang epekto sa gastos ng pag-verify sa chain at mga aplikasyon sa privacy.

Ngayon ay opisyal naming ipinakilala ang Lattice Jolt, ang pinakabagong bersyon ng aming open-source zkVM (zero-knowledge virtual machine). Ang Jolt ay dating ang pinakamabilis at pinakasimpleng zkVM, at ang arkitektura nito ay hindi nagbago. Ngunit ang ilalim na kriptograpiya ay napalitan: mula sa elliptic curve patungo sa lattice-based cryptography. Ang isang pagbabagong ito ay nagdudulot ng tatlo nang sabay:

• Jolt ay naging post-quantum secure.
• Dinagdagan ng 2-3 beses ang bilis ng prover at verifier.
• Ang Lattice Jolt ay naging may pinakamaikling proof sa lahat ng post-quantum zkVM: kasalukuyang mas mababa sa 100 KB, at maaari pa ring i-compress pa. Dahil kailangan i-upload ang proof sa blockchain at i-transmit sa iba’t ibang network, mas maliit ang proof, mas mababa ang gastos sa pag-verify.

Ang mga tampok na ito ay sumasakop sa lahat ng mga paggamit ng zkVM. Sa parehong prover, maaaring tratuhin ang milyon-milyon na CPU cycle sa GPU, at maaari ring patunayan ang milyon-milyon na cycle sa cellphone. Sa parehong sitwasyon, isinusulat ng mga developer ang karaniwang programa, nang hindi kailangang sumulat ng circuit na nangangailangan ng espesyalisadong kaalaman. Ito ang dahilan kung bakit sinasabi namin na ang Jolt ay “all-purpose SNARK”.

Ngunit ang mas malaking kuwento ay ang kahalagahan ng Lattice Jolt sa disenyo at pagtanggap ng SNARK. Sa kasalukuyan, ang lahat ng post-quantum SNARK na nasa produksyon ay batay sa hash. Ipinatotohanan ng Lattice Jolt na ang mga SNARK na batay sa lattice ay maaaring maging mas mabilis at mas kompakto. Parehong pagbabago ang nangyayari sa digital signatures: ang mga hash scheme ay ang konservatibong pagpipilian, ngunit ang mga lattice scheme ang tinatanggap ng mundo sa malaking saklaw. Inaasahan naming magiging daan din ng SNARK ang ganitong landas, at ipapaliwanag ng ikalawang bahagi ng blog post ang dahilan.

Ang dating polynomial commitment scheme ng Jolt ay ang Dory, na ang tanging komponenteng nakasalalay sa elliptic curve cryptography sa buong sistema. Ang Lattice Jolt ay nagpalit ng Dory gamit ang Akita, isang bagong polynomial commitment scheme na batay sa Module-SIS lattice assumption. Batay sa standard at malawakang pag-aaral na assumption na ito, ang Lattice Jolt ay nagtatarget sa buong 128-bit security.

Ang Module-SIS at ang kanyang kapatid na Module-LWE ay bahagi ng parehong pamilya ng mga hipotesis, at ang mundo'y digital na infrastruktura ay naglalakbay patungo sa pamilyang ito. Ang mga hipotesis na ito ay hindi lamang sumusuporta sa pamantayan ng digital na lagda na ML-DSA, kundi pati na rin sa pamantayan ng pagtatayo ng susi na ML-KEM, na naging pinakamalawak na ipinapalaganap na post-quantum primitive sa buong mundo.

Ang pag-unlad at pagsasagawa ng Akita ay pinangunahan ng mga researcher at engineer ng LayerZero, kasama ang mga researcher mula sa Carnegie Mellon University at University of Southern California, at ang aming engineering at research team sa a16z crypto.

Hindi lang si Lattice Jolt post-quantum secure, mas mabilis ito kaysa sa nalilipasan nitong elliptic curve version.

Ang pagpapabilis ay nagmumula sa isang simpleng dahilan. Ang elliptic curve ay nagpapahintulot sa Jolt na gumana sa 256-bit field, habang ang lattice-based cryptography ay nakakamit ng parehong antas ng seguridad sa 128-bit field. Ang pangunahing gawain ng Jolt prover ay ang multiplication ng field elements (sa praktika, multiplication ng napakalaking numero), kaya kapag nabawasan ang laki ng numero sa kalahati, mas mabilis ang bawat multiplication.

Ang Jolt kasama ang Dory ay naging mabilis na: ang aming nakaraang pag-update sa performance ay nagpakita na ang Jolt ay nakakapag-prove ng halos 700,000 RISC-V (RV64IMAC) cycles bawat segundo sa laptop, at ang mga karagdagang pag-optimize ay nagdala sa curve-based na Jolt sa higit sa 1 milyon na cycles bawat segundo.

Ang Lattice Jolt ay makakapagpatunay ng higit sa 2 milyong cycle bawat segundo sa iisang machine.

Sa karamihan ng nakaraang anim na buwan, hindi lang namin ginugol ang oras sa pag-unlad ng Akita at pag-integrate nito sa Jolt, kundi din sa pagsusulit muli ng buong codebase ng Jolt. Kahit na kayang mag-run ang Jolt nang mabuti sa GPU dati, ang pag-rewrite na ito ay nagagawang mas madaling buuin at i-optimize ang GPU implementation.

Ang unang resulta ay ang Apple Metal implementation, na nagdala ng malaking pagpapabilis sa apple hardware. (Ang Metal ay ang framework ng Apple na ginagamit upang patakin ang code sa GPU na nakabuilt sa mga device tulad ng MacBook at iPhone.)

• Ang GPU-accelerated Lattice Jolt ay nakakapagproves ng higit sa 10 milyong RV64IMAC cycles bawat segundo sa MacBook.
• Ang Lattice Jolt na may CPU lamang ay kayang patunayan ang higit sa 2 milyong cycle bawat segundo sa parehong machine.
• Kahit ang curve version ng Jolt ay makakapag-run ng humigit-kumulang 4 milyong cycles bawat segundo sa MacBook na may Metal.

Ibig sabihin, sa isang paglalabas, tumaas ang Jolt sa MacBook mula sa halos 1 milyon cycle bawat segundo (curve version, pure CPU) patungo sa higit sa 10 milyon cycle (grid version, may Metal).

Tingnan ang mga numero sa mas malawak na konteksto: apat na taon na ang nakalipas, nang unang beses naming isulat ang gastos ng SNARK prover, ang pagpapatotoo sa isang kalkulasyon ay mas mahal ng ilang milyon beses kaysa sa direkta nitong pagpapatakbo. Ibinaba ng Lattice Jolt ang gastos na ito sa halos isang libo beses. Hindi pa ito dulo, dahil mayroon pa ring espasyo para sa pagpapabuti sa antas ng inhinyeriya at protokolo.

Mahalaga ang laki ng patotoo at ang bilis ng prover. Mas maliit na higit sa 100 KB, mas maliliit na patotoo ng Lattice Jolt kaysa sa iba pang post-quantum zkVM, kung saan ang mga patotoo ng iba pang solusyon ay mula sa higit sa 200 KB hanggang sa halos 600 KB o higit pa.

Pagkatapos ng pagpapalit sa grid, paunlarin pa ng Jolt ang kanyang nangangalang memory usage: bumaba ang paggamit ng espasyo ng prover mula sa halos 300 bytes bawat cycle patungo sa 200 bytes. Ibig sabihin nito, kayang i-prove mo ang milyon-milyon na RISC-V cycle sa iyong cellphone.

Isasagawa ang isang kasamang papel upang magdagdag ng zero-knowledge property sa Lattice Jolt, isang katangian na kailangan ng mga aplikasyon sa privacy.

Sa loob ng maraming taon, ang atensyon ng SNARK community (at sa praktikal lahat ng production deployment) ay nakatuon sa hash-based SNARK, itinuturing ito bilang daan patungo sa post-quantum security.

Ang isang patuloy na linya ng pananaliksik sa lattice SNARK at lattice commitment ay nananatili, na sumasakop sa LaBRADOR, Greyhound, LatticeFold, SuperNeo, at ang direkta na ninuno ng Akita na si Hachi. Ang Lattice Jolt ay bumubuo sa mga pananaliksik na ito, na nagdadala ng lattice commitment layer sa isang high-performance zkVM architecture, habang pinapatunayan na ang lattice-based SNARK ay walang katumbas sa bilis at kahusayan.

Hindi ito dapat magdulot ng pagkabigla. Tulad na nabanggit, nangyari na ang parehong pattern sa digital signatures.

Ang mga kriptograpo ay nagbuo ng maraming uri ng pagsusulat batay sa maraming aksiyoma. Ang mga hash signature ay karaniwang itinuturing na pinakamapagkakatiwalaang pagpipilian: ang kanilang mga aksiyoma sa kaligtasan ay simpleng at matandang mga aksiyoma. Ngunit ang mundo ay patuloy na lumilipat patungo sa lattice signatures dahil mas maikli at mas mabilis ito:

• Ang ML-DSA signature ay humigit-kumulang ilang KB.
• Mas malaki ang SLH-DSA, ang standardized hash alternative ng NIST, ng ilang beses.
• Para sa encryption at key exchange, mas malinaw ang sitwasyon: walang alternatibong hash scheme (may patunay na imposible ito), at ang post-quantum deployment ay malaking bahagi ay batay sa lattice. Ang ML-KEM (ang pangunahing pamantayan para sa key establishment na itinakda ng NIST noong 2024) ay nangangalap na default sa mga pangunahing browser at communication apps, at ginagamit sa malaking bilang ng TLS connections sa web.

Ang paghahambing sa pagitan ng SNARK at ng digital signature ay hindi lamang pang-mukha. Ang digital signature ay sa katotohanan ay isang patunay ng kaalaman sa private key para sa isang pinapahintulot na mensahe. Ang SNARK ay nagpapalawak sa paradigm na ito mula sa isang maliit na pahayag patungo sa anumang computation. Kaya, kung ang matagalang cryptography landscape ng SNARK ay magkakaiba nang lubos sa landscape ng signature at encryption, magiging kakaiba ito.

Mayroon ding maling pagkaunawa na dapat linawin: ang Hash SNARK ay madalas na itinuturing na isang konservatibong post-quantum na pagpili, dahil “nag-iisa lamang silang nakadepende sa mga hash function.” Ito ay tama lamang kung ang ilalim na hash function ay hindi algebraic.

Sa kasalukuyan, ang karamihan sa mga deployment ng hash-based SNARK ay nagtatagpuan sa SNARK-friendly na algebraic hash constructions (tulad ng Poseidon) upang mabawasan ang gastos sa pagpapatunay na tama ang pag-e-evaluate ng hash. Mahalaga ito lalo na sa rekursyon (kung saan ang rekursyon ay ang pagpapatunay na mayroon ka ng isang epektibong SNARK proof). Ang mga konstruksyong ito ay may higit pang istruktura kaysa sa mga standard hash function, at ang kanilang crypanalysis ay hindi pa lubos na matatag.

Sa madaling salita, wala tayong tiwala sa kaligtasan ng algebraic hash functions. Gayunpaman, ginagamit pa rin sila nang palaganap sa mga production-grade na SNARK systems. (Ngunit may isang positibong signal: ipinahayag ng Ethereum Foundation na gagawin nilang pabaya ang paggamit dito.)

Ang algebraic hash ay hindi ang tanging hidden assumption sa mga deployed na hash-based SNARK: maraming sistema ay dating gumagamit ng speculative proximity-gap bounds upang tukuyin ang partikular na antas ng seguridad, kesa sa paggamit ng buong napapatunayang bounds. Ang ilan sa mga ito, na itinuturing na pinakamalakas, ay ipinatotohanang mali sa huli.

Kahit na iwasan ang mga nagmumula sa hash na SNARK na nabanggit, ang kanilang layunin sa seguridad ay karaniwang mas mababa sa 128-bit, dahil ang ganap na 128-bit na seguridad ay nagdudulot ng malaking pagkawala sa performance. Bakit? Ang mga SNARK na batay sa hash ay hindi makakamit ng 128-bit na seguridad sa isang 128-bit na field, dahil ang kanilang error sa reliability ay sumusukat sa n/|F|, kung saan ang n ay halos ang sukat ng pahayag na patotohanan, at |F| ay ang laki ng field. Kaya ang pagpapatotohan sa isang pahayag na may isang bilyon na hakbang sa isang 128-bit na field ay mawawala ng halos 30 bit ng seguridad, na nag-iiwan sa ilalim ng 100 bit. Sa kabilang banda, ang error sa reliability ng Lattice Jolt ay sumusukat sa log(n)/|F|, at kaya naman ay nakakapagpanatili ng halos buong 128-bit na seguridad sa parehong field (ang kaunting pagkawala sa log(n) ay maaaring mabawi gamit ang mga karaniwang teknik).

Kakaibang, ilang sistemang ipinakikilala bilang "conservative" na post-quantum options ay talagang nakabatay sa algebraic hash functions, speculative proximity-gap bounds, at target security level na mas mababa sa 128-bit. Kaya, habang ang hash-based SNARKs ay isang mahalagang direksyon, hindi ito awtomatikong naging mababang panganib na opsyon gaya ng inaakala ng marami.

Tinatayangan namin na hindi dapat ma-bind ang Jolt sa isang solong cryptographic foundation. Dapat nating magkaroon ng matatag at mataas na performance na SNARK na batay sa curve, hash, at lattice. Magkakaiba ang mga ipinapalagay at performance characteristics na angkop sa iba’t ibang mga sitwasyon.

Ngunit kung batay sa digital signature, ang lattice-based SNARK ay magiging pinakamalawak na ipinapalabas na post-quantum na pagpilian.

Nasa hindi karaniwang posisyon ang Jolt sa pagbabagong ito. Ang orihinal na disenyo ng Jolt ay gumagamit ng mga katangian ng elliptic curve na kapaki-pakinabang para sa commitment, kabilang ang mabilis na commitment sa mga sparse vector. Ang lattice commitment ay may parehong katangian: mababa ang gastos sa commitment sa isang vector kapag ang karamihan sa mga entry nito ay zero o maliit, at ang Jolt ay halos eksklusibong nag-commit sa mga vector na ganito. Ang katangiang ito ang nagpapahintulot sa amin na palitan ang Dory ng Akita, habang pinapanatili ang natitirang bahagi ng Jolt nang hindi nababago.

Bubuo namin ang Jolt na batay sa hash. Gayunpaman, kumpara sa Jolt na batay sa curve at lattice, mas masamang space efficiency ang bersyon na batay sa hash, mas malaki ang proof, at mayroon itong iba’t ibang komplikadong problema. Ito ay dahil ang pinakamalayong trabaho sa hash-based SNARK ay nasa binary field. Ang numerikong sistema na ito ay nakakatulong sa pagpapatotoo ng hash evaluation, ngunit hindi tumutugma sa paraan ng arithmetic ng CPU. Ang hindi pagtutugma na ito ay nagiging mahal sa pagpapatotoo ng karaniwang CPU multiplication. Gayunpaman, dapat mayroon ang ecosystem na zkVM sa bawat pangunahing grupo ng assumptions, tulad ng sa larangan ng digital signatures.

Lattice Jolt ay sumasagot sa lahat ng pangangailangan ng mga tagagawa para sa zkVM: post-quantum, transparent, mabilis, kompakto, at espasyo-efisiente. Ito ay dala ang research roadmap ng lattice SNARK mula sa LaBRADOR hanggang Hachi sa production-grade zkVM, habang hindi iniiwanan ang anumang kahusayan na nagbigay-daan sa Jolt na maging mabilis.

Ang aming layunin ay hindi lamang magbukas ng pinakamalakas na zkVM para sa anumang gamit, kundi pati na rin ang malaking pagbawas sa pangangailangan ng pagtutuwid ng SNARK para sa mga partikular na aplikasyon. Hindi ito nangangailangan na pareho ang bilis ng Jolt sa mga proofer na handaing tinitiyak. Ito ay isang imposibleng layunin, tulad ng paghahambing ng CPU sa bawat gawain sa isang espesyalisadong ASIC. Kailangan lamang na sapat na mabilis ang Jolt upang magbigay ng tanggap na用户体验.

Para sa mga “maliit” na pahayag na may kaugnayan sa client proof (kung saan ang manual na optimisasyon ng circuit ay dominante sa mga skenaryong ito), ang pangunahing pamantayan ay ang pagbuo ng proof sa loob ng higit sa isang segundo sa isang mobile phone. Nakakamit na ng Jolt ang punto na ito, at maraming mga paraan para pa sa pagpapabilis ang nasa pagpapalaganap.

Ang panahon ng SNARK ay naparito na.

Ang nilalaman na ito ay para sa pag-iisip lamang at hindi dapat gamitin bilang legal, komersyal, pagsusuri, o tax na payo. Sa mga isyung ito, kailangan mong konsultahin ang iyong sariling tagapayo. Ang anumang pagbanggit sa anumang security o digital asset ay para sa paglalarawan lamang at hindi nagtataglay ng payo sa pagsusuri o alok na magbigay ng serbisyo bilang isang tagapayo sa pagsusuri. Bukod dito, ang nilalaman na ito ay hindi direktang inilalayon sa anumang investor o potensyal na investor, at hindi dapat gamitin sa anumang sitwasyon bilang batayan para sa desisyon na mag-invest sa anumang pondo na pinamamahalaan ni a16z. (Ang alok na mag-invest sa mga pondo ni a16z ay ginagawa lamang sa pamamagitan ng private placement memorandum, subscription agreement, at iba pang kaugnay na dokumento ng pondo, at dapat basahin nang buo ang mga dokumentong ito.) Ang anumang inihayag, isinalaysay, o binanggit na investment o portfolio company ay hindi kumakatawan sa lahat ng investment sa mga instrumentong pinamamahalaan ni a16z, at hindi maaaring jaminan na ang mga investment na ito ay magiging profitable, o na ang mga susunod na investment ay magkakaroon ng katulad na mga katangian o resulta. Ang listahan ng mga investment na ginawa ng mga pondo na pinamamahalaan ni Andreessen Horowitz (na naglalabas ng mga investment na hindi pinahihintulutan ng issuer na maipahayag ni a16z, at mga hindi pa nagpapahayag na investment sa listahan ng digital asset) ay maaaring makita sa https://a16z.com/investments/.

Ang mga grap na ibinigay sa artikulo ay para sa refrensya lamang at hindi dapat gamitin bilang batayan sa anumang desisyon sa pag-invest. Ang nakaraang performance ay hindi nagpapakita ng mga resulta sa hinaharap. Ang nilalaman na ito ay nagpapakita lamang ng sitwasyon noong ibinigay na petsa. Ang anumang paghuhula, pagtataya, pahayag na may kinabukasan, layunin, pananaw, at/o opinyon na ipinahahayag sa mga materyales na ito ay maaaring palitan kahit kailan nang walang karagdagang abiso, at maaaring magkaiba o magkasalungat sa opinyon ng iba. Para sa karagdagang mahalagang impormasyon, tingnan ang https://a16z.com/disclosures.