การวิเคราะห์อัลกอริทึม STARK (บทนำ)
การวิเคราะห์อัลกอริทึมของ STARK
ตอนที่ 0: บทนำ
ตอนที่ 1: มองดูสตาร์ค
ตอนที่ 2: "เครื่องมือ" ที่มีประโยชน์
ส่วนที่ 3: สอศ
ตอนที่ 4: STARK Polynomial IOP
ตอนที่ 5: สตาร์คผู้ช่วยเหลือไพรม์
ตอนที่ 6: เร่งความเร็วกระบวนการทั้งหมด
โดยทั่วไป zk-SNARK เป็นแบบทั่วไป หมายความว่าสามารถพิสูจน์ความสมบูรณ์ของการคำนวณใดๆ
zk-SNARK ไม่ใช่แบบโต้ตอบ หมายความว่าการพิสูจน์ความสมบูรณ์ทั้งหมดประกอบด้วยข้อความเดียว
การตรวจสอบความถูกต้องของ zk-SNARK นั้นมีประสิทธิภาพ กล่าวคือ ภาระงานของผู้ตรวจสอบมีลำดับความสำคัญน้อยกว่าการเรียกใช้การคำนวณซ้ำ (หมายเหตุของผู้แปล: สามารถทำได้หลายลำดับความสำคัญ)
zk-SNARK นั้นไม่มีความรู้ ซึ่งหมายความว่าจะไม่เปิดเผยข้อมูลใด ๆ เกี่ยวกับการคำนวณข้อมูลที่เป็นความลับ
1. STARK คืออะไร?
เมื่อเร็ว ๆ นี้ หนึ่งในการพัฒนาที่น่าตื่นเต้นที่สุดในด้านระบบพิสูจน์การเข้ารหัสคือการพัฒนาของ STARK มันมาหลังจากอุตสาหกรรมบล็อกเชนที่เฟื่องฟู โดยรวมแล้ว ระบบพิสูจน์ดูเหมือนจะถูกสร้างมาโดยเฉพาะ: เครือข่ายบล็อกเชนมักประกอบด้วยฝ่ายที่ไม่ไว้วางใจซึ่งกันและกันซึ่งต้องการใช้ข้อมูลลับในการทำธุรกรรมหรือเพื่ออัปเดตสถานะโดยรวมตามกฎวิวัฒนาการของรัฐ เนื่องจากผู้เข้าร่วมมีความไม่ไว้วางใจซึ่งกันและกัน พวกเขาจึงต้องการวิธีตรวจสอบความถูกต้องของธุรกรรม (หรือการอัปเดตสถานะ) ที่เสนอโดยเพื่อนร่วมงาน
เนื่องจากคุณสมบัติต่อไปนี้ของ zk-SNARK จึงสามารถรับประกันความสมบูรณ์ของการคำนวณในสภาพแวดล้อมนี้ได้โดยธรรมชาติ:
ในขณะที่ zk-SNARK แบบดั้งเดิมอาศัยปริศนาและสมมติฐานการเข้ารหัสที่ซับซ้อน ส่วนประกอบการเข้ารหัสเดียวในระบบพิสูจน์ STARK คือฟังก์ชันแฮชที่ป้องกันการชนกัน ดังนั้นภายใต้โมเดลฟังก์ชันแฮชในอุดมคติ จึงสามารถพิสูจน์ความปลอดภัยต่อต้านควอนตัมของระบบพิสูจน์ได้ (ในวรรณกรรม อุดมคตินี้เรียกว่า "แบบจำลองควอนตัมสุ่มออราเคิล" แบบจำลองควอนตัมสุ่มออราเคิล) สิ่งนี้ตรงกันข้ามอย่างสิ้นเชิงกับ SNARK รุ่นแรกซึ่งใช้แผนที่แบบทวิเนียร์และมีความปลอดภัยที่พิสูจน์ได้ภายใต้สมมติฐานที่พิสูจน์ไม่ได้เท่านั้น
การคำนวณเลขคณิตของ STARK นั้นไม่ขึ้นกับปัญหาที่ยากในการเข้ารหัส ดังนั้นจึงสามารถเลือกโดเมนนี้โดยเฉพาะเพื่อเพิ่มประสิทธิภาพการทำงาน ดังนั้น STARK จึงพิสูจน์ได้อย่างรวดเร็ว (Prover) อย่างแท้จริง
zk-SNARK แบบดั้งเดิมอาศัยพิธีการตั้งค่าที่เชื่อถือได้เพื่อสร้างพารามิเตอร์สาธารณะ หลังจากพิธีแล้ว พารามิเตอร์สุ่มที่ใช้จะต้องถูกลืมอย่างปลอดภัย พิธีนี้ไม่น่าเชื่อถือเพราะหากผู้เข้าร่วมปฏิเสธหรือลืมที่จะลบ "ขยะอันตราย" ที่เข้ารหัสนี้พวกเขาจะยังคงความสามารถในการปลอมแปลงหลักฐาน ในทางตรงกันข้าม STARK ไม่มีการตั้งค่าที่เชื่อถือได้ ดังนั้นจึงไม่มีการเข้ารหัส"ของเสียอันตราย".
เอกสารเกี่ยวกับ FRI, STARK, DEEP-FRI และการวิเคราะห์ความน่าเชื่อถือล่าสุดของ FRI
บทช่วยสอนแบบหลายส่วน (ตอนที่ 1/2/3) โดย Vitalik Buterin
ชุดบล็อกโพสต์จาก StarkWare (ตอนที่ 1, 2, 3, 4, 5)
เว็บคาสต์ STARK@Home ของ StarkWare
หลักสูตรออนไลน์ STARK 101 ของ StarkWare
เอกสาร EthStark โดย StarkWare
โดยทั่วไป อะไรก็ตามที่ StarkWare นำเสนอ
"ฉันคาดว่า zk-SNARKs จะเจาะโลกกระแสหลักในอีก 10-20 ปีข้างหน้าและนำไปสู่การปฏิวัติครั้งใหญ่"—— "วีก็อด" 2021.9.2
zk-SNARK มีมาระยะหนึ่งแล้ว แต่ระบบพิสูจน์ STARK นั้นค่อนข้างใหม่ มันโดดเด่นด้วยเหตุผลหลายประการ:
"ฉันเห็นด้วยโดยทั่วไป โดยมีข้อสงวนในสองประเด็น:
1) STARKs จะครอบงำ ไม่ใช่ SNARK
2) 3-5 ปีจะเข้าสู่โลกกระแสหลัก
เตือนความจำในปฏิทินของฉันเพื่อทดสอบคำศัพท์เหล่านั้นในอีก 4 ปีนับจากนี้ —— อีไล เบน-ซาซง 2021.9.2
ในบทช่วยสอนนี้ ฉันจะอธิบายว่าส่วนเหล่านี้ทำงานร่วมกันกี่ส่วน คำอธิบายตามตัวอักษรนี้ได้รับการสนับสนุนโดยการใช้งาน Python ที่พิสูจน์และยืนยันการคำนวณอย่างง่ายตามฟังก์ชันแฮชของ Rescue-Prime หลังจากอ่านหรือทำตามบทช่วยสอนนี้ คุณควรจะสามารถเขียนตัวพิสูจน์และตัวตรวจสอบ STARK ที่ไม่มีความรู้ของคุณเองสำหรับการคำนวณที่คุณเลือกได้
2. ทำไมต้องเขียนบทความนี้?
ควรแจ้งให้ทราบตั้งแต่เนิ่นๆ ว่ามีแหล่งการเรียนรู้ STARK หลายแห่ง นี่คือรายการที่ไม่สมบูรณ์
ด้วยทรัพยากรการเรียนรู้มากมาย เหตุใดฉันจึงเขียนบทช่วยสอนอีก
เขตข้อมูลจำกัดและเขตข้อมูลขยาย
พหุนามบนเขตข้อมูลจำกัด รวมถึงพหุนามหลายตัวแปรและหลายตัวแปร
ฟังก์ชันแฮช
ฟังก์ชันแฮช
ตอนที่ 1: การดู STARK อธิบายแนวคิดและขั้นตอนการทำงานในระดับสูง
ส่วนที่ 2: "เครื่องมือ" ที่มีประโยชน์แนะนำเครื่องมือทางคณิตศาสตร์และการเข้ารหัสขั้นพื้นฐานที่จะใช้สร้างระบบพิสูจน์
ส่วนที่ 3: FRI ครอบคลุมการทดสอบระดับต่ำ ซึ่งเป็นแกนหลักการเข้ารหัสของระบบพิสูจน์
Part 4: STARK Polynomial IOP（IOP,การพิสูจน์ด้วยออราเคิลเชิงโต้ตอบ) อธิบายทฤษฎีข้อมูลสำหรับการสร้างระบบพิสูจน์นามธรรมจากข้อกำหนดการคำนวณโดยพลการ
ตอนที่ 5: Rescue-Prime STARK รวมเครื่องมือเหล่านี้เข้าด้วยกันเพื่อสร้างระบบพิสูจน์ความรู้ที่ไม่มีความรู้ที่โปร่งใสสำหรับการคำนวณอย่างง่าย
ตอนที่ 6: เร่งกระบวนการทั้งหมด แนะนำอัลกอริธึมและเทคโนโลยีเพื่อทำให้กระบวนการทั้งหมดเร็วขึ้นและมีประสิทธิภาพ"S "(รวบรัดรวบรัด) ใส่ใน STARK
5. กิตติกรรมประกาศ
แบบฝึกหัดที่มีอยู่นั้นค่อนข้างตื้นเขิน บทช่วยสอนเหล่านี้ทำงานได้ดีในการอธิบายในระดับสูงว่าเทคนิคเหล่านี้ทำงานอย่างไร และถ่ายทอดสัญชาตญาณว่าเหตุใด STARK จึงใช้งานได้ อย่างไรก็ตาม สิ่งเหล่านี้ไม่ได้อธิบายถึงระบบที่สมบูรณ์และปรับใช้ได้ ตัวอย่างเช่น ไม่มีบทช่วยสอนใดอธิบายถึงวิธีการนำความรู้ที่เป็นศูนย์ไปใช้ วิธีแบทช์การพิสูจน์ระดับต่ำต่างๆ หรือวิธีกำหนดระดับความปลอดภัยที่เป็นผลลัพธ์ เอกสารประกอบของ EthSTARK ให้การอ้างอิงที่สมบูรณ์เพื่อตอบคำถามเหล่านี้ส่วนใหญ่ แต่เป็นการเฉพาะสำหรับการคำนวณเฉพาะ ไม่ครอบคลุมความรู้ที่เป็นศูนย์ และไม่ได้ให้คำอธิบายที่เข้าถึงได้และเข้าใจได้ง่าย
กระดาษเหล่านี้ยากที่จะเข้าใจ น่าเศร้าที่สิ่งจูงใจในการเผยแพร่ทางวิทยาศาสตร์ถูกกำหนดขึ้นเพื่อทำให้เอกสารทางวิทยาศาสตร์เป็นเรื่องยากสำหรับผู้อ่านทั่วไป ดังนั้น บทช่วยสอนเช่นบทความนี้จึงมีความจำเป็นเพื่อให้ผู้คนจำนวนมากขึ้นสามารถเข้าใจบทความเหล่านี้ได้
ข้อมูลล้าสมัย เทคนิคมากมายที่อธิบายไว้ในบทช่วยสอนต่างๆ ได้รับการปรับปรุงตั้งแต่นั้นมา ตัวอย่างเช่น เอกสารประกอบของ EthSTARK (อ้างอิงล่าสุดด้านบน) อธิบายถึงเทคนิคการแก้ไข DEEP เพื่อลดข้อกำหนดสำหรับการประเมินที่ถูกต้องสำหรับพหุนามของระดับขอบเขต เทคนิคนี้ไม่ได้กล่าวถึงในแหล่งข้อมูลเหล่านี้เนื่องจากแหล่งข้อมูลเหล่านี้มีมาก่อนเทคนิคนี้
ฉันชอบสไตล์ของตัวเองมากกว่า ฉันไม่เห็นด้วยกับสัญลักษณ์และชื่อมากมาย และฉันหวังว่าผู้คนจะใช้สัญลักษณ์และชื่อที่ถูกต้อง โดยเฉพาะอย่างยิ่ง ฉันชอบเน้นไปที่พหุนาม ซึ่งเป็นวัตถุพื้นฐานที่สุดของระบบการพิสูจน์อักษร ในทางตรงกันข้าม แหล่งข้อมูลอื่นๆ อธิบายถึงกลไกของระบบพิสูจน์ในแง่ของการดำเนินการกับโค้ดเวิร์ดของรีด-โซโลมอน
บทช่วยสอนนี้ช่วยให้ฉันเข้าใจ STARK ได้ดีขึ้น การเขียนบทช่วยสอนนี้ช่วยให้ฉันจัดระบบความรู้ของฉันและค้นหาว่าความรู้ยังน้อยหรือขาดหายไปตรงไหน
3. ความรู้พื้นฐานที่จำเป็น
บทช่วยสอนนี้จะอธิบายความรู้พื้นฐานบางอย่างตามความจำเป็น อย่างไรก็ตาม ขอแนะนำให้ผู้อ่านทุกท่านทำความเข้าใจและศึกษาหัวข้อต่อไปนี้ เนื่องจากบทนำในที่นี้อาจดูหนาแน่นเกินไปหากผู้อ่านไม่คุ้นเคย
4. ตัวช่วยสร้างซีรีส์
ผู้เขียนขอขอบคุณ Bobbin Threadbare, Thorkil Værge และ Eli Ben-Sasson สำหรับข้อเสนอแนะและความคิดเห็นที่เป็นประโยชน์ และ Nervos Foundation สำหรับการสนับสนุนทางการเงิน ส่งอีเมลถึงเขา: alan@nervos.org หรือติดตาม aszepieniec บน twitter หรือ Github
หมายเหตุผู้แปล: มีลิงก์เอกสารจำนวนมากในข้อความต้นฉบับซึ่งไม่สามารถแนบได้เนื่องจากข้อจำกัดของบัญชีทางการ ผู้อ่านโปรดอ้างอิงลิงก์เอกสารในข้อความต้นฉบับ
About zCloak Network
zCloak Network เป็นแพลตฟอร์มบริการคอมพิวเตอร์ส่วนบุคคลที่อิงตามระบบนิเวศของ Polkadot ซึ่งใช้เครื่องเสมือน zk-STARK เพื่อสร้างและตรวจสอบหลักฐานที่ไม่มีความรู้สำหรับการประมวลผลทั่วไป ผู้ใช้สามารถวิเคราะห์และคำนวณข้อมูลโดยไม่ต้องส่งข้อมูลภายนอกโดยอาศัยข้อมูลอัตโนมัติดั้งเดิมและเทคโนโลยีการประมวลผลที่รับรองด้วยตนเอง ด้วยกลไกการส่งข้อความข้ามสายของ Polkadot คุณสามารถให้การสนับสนุนการปกป้องความเป็นส่วนตัวของข้อมูลสำหรับเครือข่ายคู่ขนานและเครือข่ายสาธารณะอื่นๆ ในระบบนิเวศของ Polkadot โครงการจะใช้รูปแบบธุรกิจ "zero-knowledge proof-as-a-service" เพื่อสร้างโครงสร้างพื้นฐานการประมวลผลความเป็นส่วนตัวแบบ multi-chain ที่ครบวงจรในจุดเดียว
