ส่งต่อชื่อเดิม 'Vitalik อธิบาย Binius โดยละเอียด: ระบบพิสูจน์ที่มีประสิทธิภาพตามฟิลด์ไบนารี'

โพสต์นี้มีจุดประสงค์หลักคือสำหรับผู้อ่านที่ค่อนข้างคุ้นเค้ากับการเข้าใจเกี่ยวกับการเข้ารหัสในปี 2019 โดยเฉพาะ SNARKs และ STARKs หากคุณไม่คุ้นเค้าฉบับนั้น ฉันขอแนะนำให้คุณอ่านบทความเหล่านั้นก่อน เพิ่มเติมขอขอบคุณพิเศษแก่ Justin Drake, Jim Posen, Benjamin Diamond และ Radi Cojbasic สำหรับคำแนะนำและการทบทวน

ในช่วงสองปีที่ผ่านมา STARKs ได้กลายเป็นเทคโนโลยีที่สําคัญและไม่สามารถถูกแทนที่ได้สําหรับการพิสูจน์การเข้ารหัสที่ง่ายต่อการตรวจสอบข้อความที่ซับซ้อนมาก (เช่น การพิสูจน์ว่าบล็อก Ethereum นั้นถูกต้อง) เหตุผลสําคัญที่ทําให้ขนาดฟิลด์เล็ก: ในขณะที่ SNARKs ที่ใช้เส้นโค้งวงรีต้องการให้คุณทํางานมากกว่าจํานวนเต็ม 256 บิตเพื่อให้ปลอดภัยเพียงพอ STARKs ช่วยให้คุณใช้ขนาดฟิลด์ที่เล็กกว่ามากซึ่งมีประสิทธิภาพมากกว่า: อันดับแรกฟิลด์ Goldilocks (จํานวนเต็ม 64 บิต) จากนั้น Mersenne31 และ BabyBear (ทั้ง 31 บิต) ด้วยประสิทธิภาพที่เพิ่มขึ้นเหล่านี้ Plonky2 ซึ่งใช้ Goldilocks จึงเร็วกว่าหลายร้อยเท่าในการพิสูจน์การคํานวณหลายประเภทมากกว่ารุ่นก่อน

คำถามที่น่าสนใจคือ: เราสามารถพาแนวโน้มนี้ไปสู่ผลสรุปตรรกะของมันได้หรือไม่ โดยการสร้างระบบพิสูจน์ที่ทำงานได้เร็วขึ้นโดยการดำเนินการโดยตรงบนเลขศูนย์และหนึ่ง นี่คือสิ่งที่ Binius กำลังพยายามทำ โดยใช้เล่ห์เล่าทางคณิตศาสตร์จำนวนมากที่ทำให้มันแตกต่างมากจาก SNARKs และ STARKs ของสามปีที่ผ่านมา โพสต์นี้จะอธิบายเหตุผลว่าทำไมฟิลด์ขนาดเล็กทำให้การสร้างพิสูจน์มีประสิทธิภาพมากขึ้น ทำไมฟิลด์ทวิภาคเป็นพลังพิเศษอย่างไม่เหมือนใคร และเล่ห์เล่าที่ Binius ใช้ให้พิสูจน์บนฟิลด์ทวิภาคทำงานอย่างมีประสิทธิภาพอย่างนี้

Binius. โดยท้ายโพสต์นี้ คุณควรสามารถเข้าใจทุกส่วนของแผนภูมินี้

สรุป: ฟิลด์จำกัด

หนึ่งในงานหลักของระบบพิสูจน์ทางคริปโตกราฟิกคือการดำเนินการกับข้อมูลจำนวนมากในขณะเดียวกันที่ยังรักษาจำนวนเล็ก หากคุณสามารถบีบอัดคำบรรยายเกี่ยวกับโปรแกรมขนาดใหญ่เข้าสูตรคณิตศาสตร์ที่เกี่ยวข้องกับตัวเลขเพียงเล็กน้อย แต่ตัวเลขเหล่านั้นมีขนาดเท่ากับโปรแกรมต้นฉบับ คุณจึงไม่ได้รับประโยชน์ใด ๆ

ในการทําเลขคณิตที่ซับซ้อนในขณะที่รักษาจํานวนให้เล็กนักเข้ารหัสมักใช้เลขคณิตแบบแยกส่วน เราเลือก "โมดูลัส" ที่สําคัญ p. ตัวดําเนินการ % หมายถึง "ใช้ส่วนที่เหลือของ": 15 % 7 = 1, 53 % 10 = 3 เป็นต้น (โปรดทราบว่าคําตอบจะไม่เป็นลบเสมอดังนั้นตัวอย่างเช่น −1 % 10 = 9)

คุณอาจเห็นการทำเลขคณิตโมดูลาริทึมแล้วในบทบาทของการบวกและลบเวลา (เช่น หนึ่งทุ่มหลังจาก 9:00 คือเวลาอะไร?). แต่ที่นี่เราไม่เพียงแค่บวกและลบ modulo บางตัวเท่านั้น, เรายังคูณ, หาร และยกกำลังด้วย

เรากำหนดค่าใหม่:

กฎข้อกล่าวถึงทั้งหมดเป็นระบบอย่างมีเหตุผล ตัวอย่างเช่น ถ้า p=7, จะได้ว่า:

5+3=1 (because 8%7=1)

1-3=5 (because -2%7=5)

2*5=3

3/5=2

คำศัพท์ทั่วไปที่ใช้เรียกโครงสร้างประเภทนี้คือเขตจำกัด ซึ่งเขตจำกัดเป็นโครงสร้างทางคณิตศาสตร์ที่เชื่อฟังก์ชันทางคณิตศาสตร์ปกติ แต่มีค่าที่เป็นไปได้จำกัด ดังนั้นแต่ละค่าสามารถแทนด้วยขนาดที่คงที่

เลขคณิตแบบแยกส่วน (หรือเขตข้อมูลเฉพาะ) เป็นประเภทที่พบมากที่สุดของฟิลด์ จํากัด แต่ยังมีประเภทอื่น: ฟิลด์ส่วนขยาย คุณอาจเคยเห็นฟิลด์ส่วนขยายมาก่อน: จํานวนเชิงซ้อน เรา "จินตนาการ" องค์ประกอบใหม่ซึ่งเราติดป้ายกํากับ i และประกาศว่าเป็นไปตาม i2=−1 จากนั้นคุณสามารถใช้การรวมกันของตัวเลขปกติและ i และทําคณิตศาสตร์กับมัน: (3i + 2) ∗ (2i + 4) = 6i2 + 12i + 4i + 8 = 16i + 2 เราสามารถขยายสาขาที่สําคัญได้ในทํานองเดียวกัน เมื่อเราเริ่มทํางานกับฟิลด์ที่มีขนาดเล็กลงส่วนขยายของฟิลด์ที่สําคัญจะมีความสําคัญมากขึ้นสําหรับการรักษาความปลอดภัยและฟิลด์ไบนารี (ซึ่ง Binius ใช้) ขึ้นอยู่กับส่วนขยายทั้งหมดเพื่อให้มีประโยชน์ในทางปฏิบัติ

สรุป: การทำเลข

วิธีที่ SNARKs และ STARKs พิสูจน์เรื่องเกี่ยวกับโปรแกรมคอมพิวเตอร์คือผ่านการจำแนกเชิงคณิต: คุณแปลงคำอธิบายเกี่ยวกับโปรแกรมที่คุณต้องการพิสูจน์เป็นสมการทางคณิตศาสตร์ที่เกี่ยวข้องกับพหลโนมเส้น. การแก้สมการที่ถูกต้องสอดคล้องกับการดำเนินการที่ถูกต้องของโปรแกรม

เพื่อให้เห็นภาพง่าย ๆ กันครับ สมมติว่าฉันคำนวณหาจำนวน Fibonacci ลำดับที่ 100 แล้วฉันอยากพิสูจน์ให้คุณเห็นว่ามันคืออะไร ฉันสร้างพหุนาม 𝐹 ที่เข้ารหัสตัวเลข Fibonacci: ดังนั้น 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5, และต่อมาอีก 100 ขั้นตอน เงื่อนไขที่ฉันต้องการพิสูจน์คือ 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) ในช่วง 𝑥={0,1…98} ฉันสามารถทำให้คุณเชื่อนี้โดยการให้คุณเห็นตัวหาร:

ที่ Z(x) = (x-0) (x-1) …(x-98). . หากฉันสามารถพิสูจน์ได้ว่ามี F และ H ที่ทำให้สมการนี้เป็นจริง แล้ว F ต้องทำให้ F(x+2)-F(x+1)-F(x) อยู่ในช่วง หากฉันตรวจสอบเพิ่มเติมว่า F ทำให้ F(0)=F(1)=1 ได้ แล้ว F(100) จะต้องเป็นจริง ณ จุดที่ 100 ตามลำดับของ Fibonacci

หากคุณต้องการพิสูจน์สิ่งที่ซับซ้อนมากขึ้น คุณสามารถแทนที่ความสัมพันธ์ "ง่าย" 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) ด้วยสมการที่ซับซ้อนมากขึ้น ซึ่งพื้นฐานคือว่า "𝐹(𝑥+1) เป็นผลลัพธ์จากการเริ่มต้นเครื่องจำลองเสมือนด้วยสถานะ 𝐹(𝑥) และการทำงานขั้นตอนการคำนวณหนึ่งขั้น" คุณยังสามารถแทนที่ตัวเลข 100 ด้วยตัวเลขที่ใหญ่กว่า เช่น 100000000 เพื่อให้เหมาะสมกับขั้นตอนการทำงานมากขึ้น

SNARKs และ STARKs ทั้งหมดมาจากความคิดเชิงนี้ในการใช้สมการเรียบง่ายบนพหุนาม (หรือบางครั้งเวกเตอร์และเมตริกซ์) เพื่อแทนสมการจำนวนมากของความสัมพันธ์ระหว่างค่าบุคคล ไม่ใช่ทุกกรณีมีการตรวจสอบความเทียบเท่าระหว่างขั้นตอนการคำนวณที่อยู่ติดกันเช่นเดียวกับข้างต้น: PLONK ไม่ได้เช่นนั้น และ R1CS ก็เช่นเดียวกัน แต่หลายอย่างที่มีประสิทธิภาพสูงทำเช่นนี้ เนื่องจากการบังคับให้มีการตรวจสอบเดียวกัน (หรือการตรวจสอบไม่กี่ครั้งเท่านั้น) หลายครั้งทำให้ง่ายต่อการลดการใช้ทรัพยากรเพิ่มเติม

Plonky2: จาก SNARKs และ STARKs ขนาด 256 บิตถึง 64 บิต ... เฉพาะ STARKs เท่านั้น

ห้าปีที่ผ่านมาสรุปที่สมเหตุสมผลของการพิสูจน์ความรู้ศูนย์ประเภทต่างๆมีดังนี้ การพิสูจน์มีสองประเภท: SNARKs (ใช้เส้นโค้งวงรี) และ STARKs (ตามแฮช) ในทางเทคนิค STARKs เป็น SNARK ประเภทหนึ่ง แต่ในทางปฏิบัติเป็นเรื่องปกติที่จะใช้ "SNARK" เพื่ออ้างถึงเฉพาะความหลากหลายที่ใช้เส้นโค้งวงรีและ "STARK" เพื่ออ้างถึงโครงสร้างที่ใช้แฮช SNARKs มีขนาดเล็กและเพื่อให้คุณสามารถตรวจสอบได้อย่างรวดเร็วและพอดีกับพวกเขา onchain ได้อย่างง่ายดาย STARKs มีขนาดใหญ่ แต่ไม่จําเป็นต้องมีการตั้งค่าที่เชื่อถือได้และทนต่อควอนตัม

STARKs ทำงานโดยการจัดการข้อมูลเป็นพหุนาม คำนวณการประเมินของพหุนามนั้นในจุดจำนวนมาก และใช้ Merkle root ของข้อมูลเพิ่มเติมนั้นเป็น "การสร้างความผูกพันกับพหุนาม"

ประวัติที่สําคัญที่นี่คือ SNARKs ที่ใช้เส้นโค้งวงรีเข้ามาใช้อย่างแพร่หลายก่อน: ใช้เวลาจนถึงประมาณปี 2018 เพื่อให้ STARKs มีประสิทธิภาพเพียงพอที่จะใช้ด้วย FRI และตอนนั้น Zcash ได้ทํางานมานานกว่าหนึ่งปีแล้ว SNARKs ที่ใช้เส้นโค้งวงรีมีข้อ จํากัด ที่สําคัญ: หากคุณต้องการใช้ SNARKs ที่ใช้เส้นโค้งวงรีเลขคณิตในสมการเหล่านี้จะต้องทําด้วยจํานวนเต็มโมดูโลจํานวนจุดบนเส้นโค้งวงรี นี่เป็นตัวเลขขนาดใหญ่โดยปกติจะอยู่ใกล้ 2256: ตัวอย่างเช่นสําหรับเส้นโค้ง bn128 มัน 21888242871839275222246405745257275088548364400416034343698204186575808495617 แต่การคํานวณที่เกิดขึ้นจริงคือการใช้ตัวเลขขนาดเล็ก: ถ้าคุณคิดถึงโปรแกรม "จริง" ในภาษาที่คุณชื่นชอบส่วนใหญ่ของสิ่งที่มันทํางานด้วยคือตัวนับดัชนีในลูปตําแหน่งในโปรแกรมแต่ละบิตที่แสดงถึง True หรือ False และสิ่งอื่น ๆ ที่มักจะมีความยาวเพียงไม่กี่หลัก

แม้ว่าข้อมูล "ต้นฉบับ" ของคุณจะประกอบไปด้วย "ตัวเลข" ที่ "เล็ก" ๆ แต่กระบวนการการพิสูจน์ต้องคำนวณเศษค่า ส่วนขยาย การสร้างสมการเชิงเส้นแบบสุ่ม และการแปลงข้อมูลอื่น ๆ ซึ่งทำให้เกิดวัตถุที่มีจำนวนเท่ากับหรือมากกว่าของขนาดเต็มของฟิลด์ของคุณ สร้างประสิทธิภาพที่เป็นปัญหา: เพื่อพิสูจน์การคำนวณเกี่ยวกับค่า n ขนาดเล็ก คุณต้องทำการคำนวณมากขึ้นเกี่ยวกับค่า n ขนาดใหญ่มากขึ้น ในตอนแรก STARKs ได้รับมรดกจากการใช้ฟิลด์ 256 บิตจาก SNARKs และเจอปัญหาเดียวกัน

ส่วนขยายของ Reed-Solomon บางส่วนของการประเมินพหุนัย แม้ว่าค่าเริ่มต้นจะเล็ก แต่ค่าเพิ่มเติมทั้งหมดก็ขยายออกไปสู่ขนาดเต็มของเขต (ในกรณีนี้คือ 2 ยกกำลัง 31 -1)

ในปี 2022 เปิดตัว Plonky2 โดยสิ่งประดิษฐ์หลักของ Plonky2 คือการทำการคำนวณทางคณิตศาสตร์โดย modulo เศษเหลือที่น้อยกว่า: 2⁶⁴−2³²+1=18446744069414584321. ตอนนี้ การบวกหรือคูณทุกครั้งสามารถทำได้เสมอในไม่กี่คำสั่งบน CPU และการทำการแฮชข้อมูลทั้งหมดร่วมกันเร็วขึ้น 4 เท่า แต่นี้มาพร้อมกับข้อแตกต่าง: การใช้วิธีนี้ได้เฉพาะ STARK เท่านั้น หากคุณพยายามใช้ SNARK กับเส้นโค้งเรขาคณิตขนาดเล็ก เส้นโค้งเรขาคณิตกลายเป็นไม่ปลอดภัย

เพื่อความปลอดภัยต่อไป Plonky2 ยังต้องแนะนําฟิลด์ส่วนขยาย เทคนิคสําคัญในการตรวจสอบสมการเลขคณิตคือ "การสุ่มตัวอย่างที่จุดสุ่ม": ถ้าคุณต้องการตรวจสอบว่า H(x)∗Z(x) เท่ากับ F(x+2)−F(x+1)−F(x) หรือไม่ คุณสามารถเลือกพิกัดสุ่ม r ให้หลักฐานการเปิดข้อผูกมัดพหุนามที่พิสูจน์ H(r), Z(r), F(r), F(r+1) และ F(r+2), แล้วตรวจสอบว่า H(r)∗Z(r) เท่ากับ F(r+2)−F(r+1)−F(r) หรือไม่ หากผู้โจมตีสามารถเดาพิกัดล่วงหน้าผู้โจมตีสามารถหลอกระบบพิสูจน์ได้ - ด้วยเหตุนี้จึงต้องสุ่ม แต่นี่ก็หมายความว่าพิกัดจะต้องสุ่มตัวอย่างจากชุดที่มีขนาดใหญ่พอที่ผู้โจมตีไม่สามารถเดาได้โดยบังเอิญ หากโมดูลัสอยู่ใกล้ 2²⁵⁶, นี่เป็นเรื่องที่ชัดเจน แต่กับโมดูลัสของ 2⁶⁴−2³²+1, เรายังไม่ได้ถึงแก่จะเสียเวลาไปที่ 2³¹−1, มันแน่นอนไม่ใช่เหตุการณ์นั้น พยายามปลอมแปลงพิสูจน์สองพันล้านครั้งจนกว่าจะโชคดีอยู่ในขอบเขตของความสามารถของผู้โจมตี

เพื่อหยุดสิ่งนี้ เราจะสุ่ม 𝑟 จากฟิลด์ขยาย ตัวอย่างเช่น คุณสามารถกำหนด 𝑦 ที่นี่ 𝑦³=5, และเลือกสมการของ 1, 𝑦 และ 𝑦². นี่เพิ่มจำนวนรวมของพิกัดกลับไปอยู่ที่ประมาณ 2⁹³. จำนวนมากของพหุนามที่คำนวณโดยผู้พิสูจน์ไม่ได้เข้าไปในเขตสนามนานาชนิดนี้เลย พวกเขาเพียงใช้จำนวนเต็มร่วม 2³¹−1, และดังนั้นคุณยังคงได้รับประสิทธิภาพทั้งหมดจากการใช้เขตที่เล็กน้อย แต่การตรวจสอบจุดแบบสุ่ม และการคำนวณ FRI จะพาลงไปในเขตที่ใหญ่ขึ้น เพื่อให้ได้ความปลอดภัยที่จำเป็น

จากจำนวนเฉพาะขนาดเล็กไปสู่ไบนารี

คอมพิวเตอร์ทำการคำนวณโดยการแทนเลขที่ใหญ่ขึ้นเป็นลำดับของศูนย์และหนึ่ง และสร้าง "วงจร" บนบิตเหล่านั้นเพื่อคำนวณสิ่งเช่นการบวกและการคูณ คอมพิวเตอร์ได้รับการปรับแต่งโดยเฉพาะสำหรับการคำนวณด้วยจำนวนเต็ม 16 บิต 32 บิต และ 64 บิต โมดูลัสเหมือน 2⁶⁴−2³²+1 และ 2³¹−1 ถูกเลือกไม่เพียงเพราะว่ามันอยู่ภายในขอบเขตเหล่านั้น แต่ยังเพราะว่ามันสอดคล้องกันอย่างดีกับขอบเขตเหล่านั้น: คุณสามารถทำการคูณโมดูลออกมาเป็น 2⁶⁴−2³²+1 โดยการทำการคูณ 32 บิตเป็นปกติและเลื่อนและคัดลอกผลลัพธ์ทางบิตในหลายที่; บทความนี้อธิบายเทคนิคบางอย่างได้ดี

สิ่งที่ดีกว่าก็คือการคำนวณโดยตรงในระบบฐานสอง สมมติว่าการบวกสามารถเป็นเพียงการ XOR เท่านั้น โดยไม่ต้องกังวลเรื่องการ "ถือ" ค่าเกินจากการบวก 1 + 1 ในตำแหน่งบิตถัดไป สมมติว่าการคูณสามารถทำให้เป็นขนาดมากขึ้นในท่าเดียวกัน และประโยชน์เหล่านี้จะมาพร้อมกับความสามารถในการแทนค่า ค่า True/False ด้วยเพียงหนึ่งบิต

การจับประโยชน์เหล่านี้จากการคำนวณไบนารีโดยตรงคือสิ่งที่ Binius พยายามทำ ตารางจากการนำเสนอ zkSummit ทีม Binius แสดงถึงความเป็นไปได้ในการเพิ่มประสิทธิภาพ

หลังจากที่มีขนาดเท่ากันโดยประมาณ การดำเนินการในฟิลด์ไบนารี 32 บิตใช้ทรัพยากรในการคำนวณน้อยกว่า 5 เท่าของการดำเนินการในฟิลด์เมอเซนน์ 31 บิต

จากพหุนิพันธุ์ไปสู่ฮายเปอร์คิวบ์

สมมติว่าเราถูกโน้มน้าวโดยเหตุผลนี้ และต้องการทำทุกอย่างผ่านบิต (ศูนย์และหนึ่ง) จะทำยังไงให้มีการสร้างหรือสร้างเสร็จสมการพหุนามที่แทนด้วยหนึ่งล้านบิตจริงๆ?

ที่นี่เราเผชิญกับปัญหาทางปฏิบัติสองประการ

1. สำหรับโพลินอเมียลที่จะแทนค่ามากมาย ค่าเหล่านั้นต้องสามารถเข้าถึงได้ที่การประเมินโพลินอเมียล: ในตัวอย่างของเราในชุด Fibonacci ด้านบน 𝐹(0), 𝐹(1) … 𝐹(100), และในการคำนวณที่ใหญ่ขึ้น เลขดัชนีจะไปถึงล้าน และเขตของสนามที่เราใช้จำเป็นต้องมีเลขที่ขึ้นไปถึงขนาดนั้น

2. การพิสูจน์ค่าใด ๆ เกี่ยวกับข้อมูลที่เรากำลังติดตามในต้นไม้ Merkle (เช่นทุกอย่าง STARKs ทำ) ต้องการ Reed-Solomon ที่เข้ารหัส: การขยายค่า 𝑛 เป็น 8𝑛 ค่าเช่น ๆ โดยใช้ความไม่จำเป็นเพื่อป้องกันผู้พิสูจน์ที่ต่อเป็นที่จะโกงโดยการปลอมข้อมูลหนึ่งค่ากลางการคำนวณ นอกจากนี้ยังต้องการฟิลด์ที่ใหญ่พอ: เพื่อขยายค่าล้านค่าเป็น 8 ล้าน คุณต้องใช้จุดที่แตกต่างกัน 8 ล้านจุดที่จะประเมินพหลโนมีอล

แนวคิดหลักใน Binius คือการแก้ปัญหาทั้งสองนี้แยกกันและทําเช่นนั้นโดยการแสดงข้อมูลเดียวกันในสองวิธีที่แตกต่างกัน ประการแรกพหุนามเอง SNARKs ที่ใช้เส้นโค้งวงรี, STARKs ยุค 2019, Plonky2 และระบบอื่น ๆ โดยทั่วไปจะจัดการกับพหุนามมากกว่าตัวแปรเดียว: F(x) ในทางกลับกัน Binius ได้รับแรงบันดาลใจจากโปรโตคอลสปาร์ตันและทํางานร่วมกับพหุนามหลายตัวแปร: F (x1, x2 ... xk). ในความเป็นจริงเราแสดงร่องรอยการคํานวณทั้งหมดบน "ไฮเปอร์คิวบ์" ของการประเมินโดยที่แต่ละ xi เป็น 0 หรือ 1 ตัวอย่างเช่นหากเราต้องการแสดงลําดับของตัวเลขฟีโบนักชีและเรายังคงใช้ฟิลด์ที่มีขนาดใหญ่พอที่จะแทนพวกเขาเราอาจเห็นภาพสิบหกตัวแรกว่าเป็นเช่นนี้:

นั่นคือ, 𝐹(0,0,0,0) จะเป็น 1, 𝐹(1,0,0,0) ก็จะเป็น 1, 𝐹(0,1,0,0) จะเป็น 2, และเช่นนั้น, จนกระทั่งเราได้ 𝐹(1,1,1,1)=987. โดยมี hypercube ของการประเมินเช่นนี้, มีหนึ่ง polynomial multilinear (องศา 1 ในแต่ละตัวแปร) ที่สร้างการประเมินเหล่านั้น เราจึงสามารถคิดว่าเซ็ตของการประเมินนั้นแทน polynomial; เราไม่จำเป็นต้องคำนวณค่าความสัมพันธ์จริงๆ

ตัวอย่างนี้เป็นเพียงภาพประกอบเท่านั้น: ในทางปฏิบัติจุดรวมของการไปที่ไฮเปอร์คิวบ์คือการให้เราทํางานกับแต่ละบิต วิธี "Binius-native" ในการนับตัวเลข Fibonacci คือการใช้ลูกบาศก์ที่มีมิติสูงกว่าโดยใช้แต่ละชุดของ eg 16 บิตเพื่อเก็บหมายเลข สิ่งนี้ต้องใช้ความฉลาดในการใช้การเพิ่มจํานวนเต็มที่ด้านบนของบิต แต่ด้วย Binius มันไม่ยากเกินไป

ตอนนี้เรามาถึงการเขียนโค้ดการลบข้อมูลแบบ erasure coding วิธีที่ STARKs ทำงานคือ: คุณเอาค่า 𝑛 มา แล้ว Reed-Solomon ขยายให้มีค่ามากขึ้น (บ่อยครั้งเป็น 8𝑛, โดยทั่วไปอยู่ระหว่าง 2𝑛 และ 32𝑛), แล้วเลือกบางสาขา Merkle แบบสุ่มจากการขยายและดำเนินการตรวจสอบบางประเภทบนพวกเขา ลูกบริบทมีความยาว 2 ในแต่ละมิติ ดังนั้น มันไม่ Pr กที่จะขยายมันโดยตรง: มีพื้นที่ไม่เพียงพอสำหรับการสุ่มสาขา Merkle จาก 16 ค่า ดังนั้นเราจะทำอย่างไรแทน? เราทำเสมือนว่า hypercube เป็นสี่เหลี่ยม!

Simple Binius - ตัวอย่าง

ดูที่นี่สำหรับการประมวลผลด้วย Python ของโปรโตคอลนี้

เรามาดูตัวอย่างกัน โดยใช้จำนวนเต็มปกติเป็นฟิลด์ของเราเพื่อความสะดวก (ในการนำไปใช้จริงจะเป็นสมาชิกฟิลด์ทวิภาค) ก่อนอื่น เราจะเอาไฮเปอร์คิวบ์ที่เราต้องการที่จะยืนยันและเข้ารหัสให้เป็นสี่เหลี่ยม:

ตอนนี้เราขยาย Reed-Solomon จตุรัส นั่นคือเราจะจัดการกับแต่ละแถวให้เป็นพหุคณิตดีกรี 3 ที่ประเมินที่ x = {0, 1, 2, 3} และประเมินพหุคณิตเดียวกันที่ x = {4, 5, 6, 7}:

สังเกตว่าจำนวนเหล่านี้เพิ่มขึ้นอย่างรวดเร็ว! นี่คือเหตุผลที่ในการนำมาใช้ในโครงการจริงเรามักใช้เขตข้อมูลที่จำกัดสำหรับสิ่งนี้ แทนที่จะใช้จำนวนเต็มธรรมดา: หากเราใช้จำนวนเต็มโมดูลัส 11 ตัวอย่างเช่น การขยายของแถวแรกจะเป็น [3, 10, 0, 6] เท่านั้น

ถ้าคุณต้องการที่จะเล่นอยู่กับการขยายและตรวจสอบตัวเลขที่นี่เองสำหรับคุณเอง คุณสามารถใช้โค้ดส่วนขยาย Reed-Solomon ของฉันที่ง่าย.

ถัดไปเราจะจัดการส่วนขยายนี้เป็นคอลัมน์ และสร้างต้นไม้ Merkle ของคอลัมน์ รากของต้นไม้ Merkle คือความมั่นใจของเรา

ตอนนี้สมมติว่าผู้พิสูจน์ต้องการพิสูจน์การประเมินพหุนามนี้ในบางจุด r={r0,r1,r2,r3} มีความแตกต่างเล็กน้อยใน Binius ที่ทําให้มันค่อนข้างอ่อนแอกว่าแผนความมุ่งมั่นพหุนามอื่น ๆ : ผู้พิสูจน์ไม่ควรรู้หรือสามารถเดาได้จนกว่าพวกเขาจะมุ่งมั่นกับราก Merkle (กล่าวอีกนัยหนึ่ง r ควรเป็นค่าสุ่มหลอกที่ขึ้นอยู่กับราก Merkle) สิ่งนี้ทําให้โครงการไร้ประโยชน์สําหรับ "การค้นหาฐานข้อมูล" (เช่น. "ตกลงคุณให้ฉันราก Merkle ตอนนี้พิสูจน์ให้ฉัน P (0,0,1,0)!") แต่โปรโตคอลการพิสูจน์ความรู้เป็นศูนย์จริงที่เราใช้โดยทั่วไปไม่จําเป็นต้องมี "การค้นหาฐานข้อมูล" พวกเขาเพียงแค่ต้องตรวจสอบพหุนามที่จุดประเมินแบบสุ่ม ดังนั้นข้อ จํากัด นี้จึงไม่เป็นไรสําหรับวัตถุประสงค์ของเรา

สมมติว่าเราเลือก 𝑟={1,2,3,4} (พหุนามนี้ในจุดนี้คำนวณเป็น -137; คุณสามารถยืนยันได้ด้วยรหัสนี้). ตอนนี้เราเข้าสู่กระบวนการพิสูจน์จริง เราแบ่ง r ออกเป็นสองส่วน: ส่วนแรก {1,2} แสดงถึงการรวมกันของคอลัมน์เชิงเส้นภายในแถว และส่วนที่สอง {3,4} แสดงถึงการรวมกันของแถวเชิงเส้น เราคํานวณ "ผลิตภัณฑ์เทนเซอร์" ทั้งสําหรับส่วนคอลัมน์:

และสำหรับส่วนแถว:

สิ่งที่หมายถึงคือ: รายการของผลิตภัณฑ์ที่เป็นไปได้ทั้งหมดของค่าหนึ่งจากแต่ละชุด ในกรณีของแถวเราได้:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Use r={1,2,3,4} (so r2=3 and r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

ตอนนี้เราคำนวณ 'แถว' ใหม่ 𝑡′ โดยการเลือกสมการเชิงเส้นของแถวที่มีอยู่ นั่นคือ เราเลือก:

คุณสามารถดูสิ่งที่เกิดขึ้นที่นี่เหมือนการประเมินบางส่วน หากเราจะคูณผลเทนเซอร์ทั้งหมด ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) ด้วยเวกเตอร์เต็มของค่าทั้งหมด คุณจะได้การประเมิน 𝑃(1,2,3,4)=−137 ที่นี่เรากำลังคูณผลเทนเซอร์บางส่วนที่ใช้พิกัดประเมินครึ่งหนึ่งและเรากำลังลดกริดของค่า 𝑁 ให้กลายเป็นแถวของค่า 𝑁 หากคุณให้แถวนี้ให้คนอื่น พวกเขาสามารถใช้ผลเทนเซอร์ของครึ่งอีกของพิกัดประเมินเพื่อทำความเสร็จสิ้นคำนวณส่วนที่เหลือ

ผู้พิสูจน์จะให้ผู้ตรวจสอบด้วยแถวใหม่นี้, 𝑡′, และพิสูจน์ Merkle ของคอลัมน์บางคอลัมน์ที่สุ่มเลือก นี่คือข้อมูล 𝑂(𝑁) ในตัวอย่างของเรา เราจะให้ผู้พิสูจน์ให้คอลัมน์สุดท้ายเท่านั้น ในชีวิตจริงผู้พิสูจน์จะต้องให้คอลัมน์ไม่กี่ๆ คอลัมน์เพื่อความปลอดภัยที่เพียงพอ

ตอนนี้เราใช้ประโยชน์จากความเป็นเส้นตรงของรหัส Reed-Solomon คุณสมบัติหลักที่เราใช้คือ: การรวมกันเชิงเส้นของส่วนขยาย Reed-Solomon ให้ผลลัพธ์เช่นเดียวกับส่วนขยาย Reed-Solomon ของชุดค่าผสมเชิงเส้น "ความเป็นอิสระของคําสั่ง" ประเภทนี้มักเกิดขึ้นเมื่อคุณมีการดําเนินการสองอย่างที่เป็นเส้นตรง

ผู้ตรวจสอบทำแบบนี้อย่างแน่นอน พวกเขาคำนวณส่วนขยายของ 𝑡′ และพวกเขาคำนวณผลรวมเชิงเส้นเดียวกันของคอลัมน์ที่โปรเวอร์คำนวณก่อนหน้านี้ (แต่เฉพาะคอลัมน์ที่โปรเวอร์ให้), และตรวจสอบว่ากระบวนการสองกระบวนการนี้ให้คำตอบเดียวกัน

ในกรณีนี้ การขยาย 𝑡′ และการคำนวณผสมเชิงเส้นเดียวกัน ([6,−9,−8,12]) ของคอลัมน์ จะให้คำตอบเดียวกัน: −10746 นี้พิสูจน์ว่าราก Merkle ถูกสร้างขึ้น "ด้วยความซื่อสัตย์" (หรืออย่างน้อย "ใกล้เคียง") และมันตรงกับ 𝑡′: อย่างน้อยความสอดคล้องส่วนใหญ่ของคอลัมน์กันและกับ 𝑡′

แต่ผู้ตรวจสอบยังคงต้องตรวจสอบอีกสิ่งหนึ่ง: ตรวจสอบการประเมินพหุนามที่ {r0.. ร 3} จนถึงขณะนี้ยังไม่มีขั้นตอนใดของผู้ตรวจสอบขึ้นอยู่กับมูลค่าที่ผู้พิสูจน์กล่าวอ้าง ดังนั้นนี่คือวิธีที่เราทําการตรวจสอบนั้น เราใช้ผลิตภัณฑ์เทนเซอร์ของสิ่งที่เราระบุว่าเป็น "ส่วนคอลัมน์" ของจุดประเมิน:

ในตัวอย่างของเรา ที่ r={1,2,3,4} ดังนั้นครึ่งหนึ่งของคอลัมน์ที่เลือกคือ {1,2} นี้เท่ากับ:

ดังนั้นตอนนี้เราจะใช้การผสมเชิงเส้นนี้ของ 𝑡′:

ซึ่งเท่ากับคำตอบที่คุณได้หากคุณประเมิน多項式โดยตรง

ข้างต้นเป็นคำอธิบายที่ค่อนข้างเข้าใจง่ายของโปรโตคอล Binius ที่สมบูรณ์ สิ่งนี้มีข้อดีที่น่าสนใจบางประการอยู่แล้ว: เช่น เนื่องจากข้อมูลถูกแบ่งเป็นแถวและคอลัมน์ คุณจำเป็นต้องใช้เขตข้อมูลขนาดครึ่ง แต่สิ่งนี้ไม่ใกล้ชิดกับการเข้าใจประโยชน์ทั้งหมดจากการทำคำนวณในระบบความจริง สำหรับสิ่งนี้ เราจำเป็นต้องใช้โปรโตคอล Binius ที่สมบูรณ์ แต่ก่อนที่เราจะได้เข้าใจลึกลงเกี่ยวกับเขตข้อมูลทวิธทฺ

ฟิลด์ทวิภาค

ฟิลด์ที่เล็กที่สุดที่เป็นไปได้คือทางเลขคณิตโมดูล 2 ซึ่งเล็กมากที่เราสามารถเขียนตารางการบวกและการคูณของมันได้:

เราสามารถทำให้ฟิลด์ทวิภาคขนาดใหญ่ขึ้นได้โดยการนำส่วนขยาย: หากเราเริ่มต้นด้วย 𝐹2 (จำนวนเต็มโมดูล 2) แล้วกำหนด 𝑥 ที่ 𝑥2=𝑥+1 เราจะได้ตารางการบวกและการคูณต่อไปนี้:

พบว่าเราสามารถขยายฟิลด์ทวิภาคไปสู่ขนาดใดก็ได้โดยการทำซ้ำกันสร้าง. ไม่เหมือนกับจำนวนจำนวนความซับซ้อนที่มีอยู่จริงที่คุณสามารถเพิ่มฟิลด์ใหม่ 1 ตัว 𝑖, แต่คุณไม่สามารถเพิ่มตัวใดต่อไป (จำนวนจำนวนที่มีจริงมีอยู่แต่มันเป็นตัวเลขทางคณิตศาสตร์แปลก, เช่น 𝑎𝑏≠𝑏𝑎), กับฟิลด์จำกัดคุณสามารถเพิ่มส่วนขยายใหม่ได้ตลอดไป โดยเฉพาะเรากำหนดองค์ประกอบตามนี้:

และอื่นๆ ซึ่งบ่งบอกถึงการก่อสร้างอาคารที่บอกเพราะวิธีที่ส่วนขยายแต่ละส่วนสามารถมองเห็นได้ว่าการเพิ่มชั้นใหม่ให้กับอาคาร นี่ไม่ใช่วิธีเดียวที่สามารถก่อสร้างฟิลด์ทวิภาคไบนารี่ของขนาดอย่างไม่จำกัด แต่มันมีข้อดีที่เฉพาะเจาะจงบางประการที่บินิอุสใช้ประโยชน์

เราสามารถแสดงตัวเลขเหล่านี้ให้เป็นรายการของบิต เช่น 1100101010001111 บิตแรกแทนคูณของ 1 บิตที่สองแทนคูณของ 𝑥0 จากนั้นบิตต่อมาแทนคูณของ: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0, และอื่น ๆ การเข้ารหัสนี้ดีเพราะคุณสามารถแยกออกได้

นี่เป็นสัญญาณที่ไม่ค่อยพบแต่ฉันชอบการแทนสมาชิกฟิลด์ทวิภาคเป็นจำนวนเต็ม โดยใช้สัญลักษณ์บิตที่สำคัญมากกว่าไปทางขวา นั่นคือ 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19 และอื่น ๆ 1100101010001111 คือ 61779 ในการแสดงค่านี้

การบวกในฟิลด์ทวิภาคเพียงแค่ XOR (เช่นเดียวกับการลบ); โปรดทราบว่าสิ่งนี้หมายความว่า x+x=0 สำหรับทุก x ในการคูณสองสมาชิก x*y มีอัลกอริทึมเชิงกระจายที่ง่ายมาก: แยกตัวเลขแต่ละตัวที่ครึ่งหนึ่ง

แล้วแยกการคูณ:

ชิ้นสุดท้ายคือเรื่องที่เล็กน้อยเท่านั้น เพราะคุณต้องปรับใช้กฎการลดและแทน 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 ด้วย 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1) มีวิธีที่มีประสิทธิภาพมากกว่าในการคูณ ในรูปของอัลกอริทึม Karatsuba และการแปลงฟูเรียร์แบบเร็ว แต่ขอให้ผู้อ่านที่สนใจทดลองค้นหาเอง

การหารในฟิลด์ทวิภาคทำโดยการรวมการคูณและการสลับที่กล่าวถึง วิธี "ง่าย ๆ แต่ช้า" ในการทำการสลับคือการใช้ทฤษฎี Fermat ทั่วไป ยังมีอัลกอริทึมการสลับที่ซับซ้อนมากขึ้น แต่มีประสิทธิภาพมากขึ้น ซึ่งคุณสามารถค้นหาได้ที่นี่. คุณสามารถใช้ รหัสที่นี่เพื่อเล่นในการเพิ่ม การคูณ และการหารของฟิลด์ทวิภาคไปเอง

Left: ตารางการเพิ่มสำหรับสมาชิกในฟิลด์ไบนารีสี่บิต (คือ สมาชิกที่ประกอบด้วยเฉพาะการรวมกันของ 1, 𝑥₀，𝑥₁และ 𝑥₀𝑥₁)

Right: ตารางคูณสำหรับองค์ประกอบฟิลด์สี่บิต

สิ่งที่สวยงามเกี่ยวกับฟิลด์ไบนารีประเภทนี้คือมันรวมส่วนที่ดีที่สุดของจํานวนเต็ม "ปกติ" และเลขคณิตแบบแยกส่วน เช่นเดียวกับจํานวนเต็มทั่วไปองค์ประกอบของฟิลด์ไบนารีจะไม่มีขอบเขต: คุณสามารถขยายได้ไกลเท่าที่คุณต้องการ แต่เช่นเดียวกับเลขคณิตแบบแยกส่วนหากคุณดําเนินการเกินค่าภายในขีด จํากัด ขนาดที่กําหนดคําตอบทั้งหมดของคุณจะอยู่ในขอบเขตเดียวกัน ตัวอย่างเช่นหากคุณใช้พลังต่อเนื่องของ 42 คุณจะได้รับ:

หลังจาก 255 ขั้นตอน คุณกลับมาที่ 42²⁵⁵ = 1. เหมือนจำนวนเต็มบวกและการคำนวณโมดูลาริทึม เขาทำตามกฎคณิตศาสตร์ปกติ: ab=bเอ, เอ(b+c)=a b+a*c, มีบางกฎหมายใหม่ที่แปลกประหลาด

ในที่สุดฟิลด์ทวิภาคทำให้ง่ายต่อการจัดการบิต: หากคุณทำการคำนวณด้วยตัวเลขที่พอดี 2 ^k บิตจากนั้นเอาต์พุตทั้งหมดของคุณจะพอดีกับ 2 k บิต เพื่อหลีกเลี่ยงความอับอาย ใน EIP-4844 ของ Ethereum แต่ละ "บล็อก" ของ blob จะต้องเป็นโมดูลดิจิทัล 52435875175126190479447740508185965837690552500527637822603658699938581184513 ดังนั้นการเข้ารหัสข้อมูลไบนารีจึงต้องทิ้งพื้นที่บางส่วนและทําการตรวจสอบเพิ่มเติมเพื่อให้แน่ใจว่าแต่ละองค์ประกอบเก็บค่าน้อยกว่า 2²⁴⁸. นี่หมายความว่าการดำเนินการในฟิลด์ทวิภาคเป็นอย่างรวดเร็วบนคอมพิวเตอร์ - ทั้ง CPU และการออกแบบ FPGA และ ASIC ที่เป็นไปได้อย่างทฤษฎี

ทั้งหมดนี้หมายความว่าเราสามารถทําอะไรบางอย่างเช่นการเข้ารหัส Reed-Solomon ที่เราทําข้างต้นในลักษณะที่หลีกเลี่ยง "การระเบิด" ของจํานวนเต็มได้อย่างสมบูรณ์ดังที่เราเห็นในตัวอย่างของเราและในลักษณะที่ "ระเบิด" มาก วิธี "พื้นเมือง" ชนิดของคอมพิวเตอร์ที่คอมพิวเตอร์เก่ง แอตทริบิวต์ "แยก" ของฟิลด์ไบนารี - วิธีที่เราทํา 1100101010001111=11001010+10001111*x₃และแยกตามความต้องการของเราก็เป็นสิ่งสำคัญที่จะให้ความยืดหยุ่นมากมาย

เกต

ดูที่นี่สำหรับการนำไปใช้งานในภาษาไพธอนของโปรโตคอลนี้

ตอนนี้เราสามารถไปที่ "Binius เต็มรูปแบบ" ซึ่งปรับ "Binius อย่างง่าย" เป็น (i) ทํางานผ่านฟิลด์ไบนารีและ (ii) ให้เรายอมรับแต่ละบิต โปรโตคอลนี้ยากที่จะเข้าใจเพราะมันยังคงไปมาระหว่างวิธีการต่างๆในการดูเมทริกซ์ของบิต แน่นอนว่าฉันใช้เวลานานกว่าที่จะเข้าใจมากกว่าปกติในการทําความเข้าใจโปรโตคอลการเข้ารหัส แต่เมื่อคุณเข้าใจฟิลด์ไบนารีข่าวดีก็คือไม่มี "คณิตศาสตร์ที่ยากกว่า" ที่ Binius พึ่งพา นี่ไม่ใช่การจับคู่เส้นโค้งวงรีซึ่งมีรูกระต่ายที่ลึกและลึกกว่าของเรขาคณิตพีชคณิตที่จะลงไป ที่นี่ฟิลด์ไบนารีเป็นสิ่งที่คุณต้องการ

มาดูแผนภาพทั้งหมดอีกครั้ง:

ถึงตอนนี้คุณควรคุ้นเคยกับส่วนประกอบส่วนใหญ่ แนวคิดของการ "แบน" ไฮเปอร์คิวบ์เป็นตารางแนวคิดในการคํานวณชุดค่าผสมแถวและการรวมกันของคอลัมน์เป็นผลิตภัณฑ์เทนเซอร์ของจุดประเมินและแนวคิดในการตรวจสอบความเท่าเทียมกันระหว่าง "รีด - โซโลมอนขยายแล้วคํานวณชุดแถว" และ "การคํานวณชุดแถวแล้วขยายรีด - โซโลมอน" ล้วนอยู่ใน Binius ที่เรียบง่าย

มีอะไรใหม่ใน "เกต Binius" พื้นฐาน 3 ข้อ

• ค่าบุคคลในไฮเปอร์คิวบ์และในสี่เหลี่ยมต้องเป็นบิต (0 หรือ 1)
• กระบวนการขยายขยายบิตให้กลายเป็นบิตอื่น ๆ โดยการจัดกลุ่มบิตเป็นคอลัมน์และเสริมสร้างว่าพวกเขาเป็นองค์ประกอบฟิลด์ที่ใหญ่กว่าชั่วคราว
• หลังจากขั้นตอนการผสมแถว มีขั้นตอน "แยกส่วนเป็นบิต" ตามซึ่งแปลงการส่วนขยายกลับเป็นบิต

เราจะผ่านทั้งสองอย่างในทางกลับกัน ขั้นแรกให้ขยายเวลาใหม่ รหัส Reed-Solomon มีข้อจํากัดพื้นฐานที่ถ้าคุณขยายค่า n เป็นค่า k∗n คุณต้องทํางานในฟิลด์ที่มีค่า k∗n ที่แตกต่างกันซึ่งคุณสามารถใช้เป็นพิกัดได้ ด้วย F₂ (ที่เรียกว่า bits) คุณไม่สามารถทำเช่นนั้นได้ ดังนั้นสิ่งที่เราทำคือเรา “บรรจุ” ตัวอักษรที่อยู่ติดกัน 𝐹₂ องค์ประกอบรวมกันเป็นค่าที่ใหญ่กว่า ในตัวอย่างที่นี่เรากําลังบรรจุสองบิตในแต่ละครั้งเป็นองค์ประกอบใน {0,1,2,3} เนื่องจากส่วนขยายของเรามีจุดประเมินเพียงสี่จุดและนั่นก็เพียงพอแล้วสําหรับเรา ในการพิสูจน์ "จริง" เราอาจจะกลับมาครั้งละ 16 บิตด้วยกัน จากนั้นเราจะทํารหัส Reed-Solomon เหนือค่าที่บรรจุเหล่านี้และแกะออกอีกครั้งเป็นบิต

ตอนนี้การผสานแถว ในการทำให้ “การประเมินที่จุดสุ่ม” มีความปลอดภัยทางคริปโตเรียบร้อย เราต้องการให้จุดนั้นถูกสุ่มมาจากพื้นที่ที่ใหญ่มาก มากกว่าเฮไพเพอร์คิวบ์เอง ดังนั้น ในขณะที่จุดภายในเฮไพเพอร์คิวบ์เป็นบิต การประเมินภายนอกเฮไพเพอร์คิวบ์จะใหญ่มากกว่า เช่นเดียวกับตัวอย่างข้างต้นของเรา การผสานแถว จะสิ้นสุดที่ [11,4,6,1]

นี่เป็นปัญหา: เราทราบวิธีการรวมคู่ของบิตเป็นค่าที่ใหญ่ขึ้น แล้วทำการขยาย Reed-Solomon บนนั้น แต่จะทำอย่างไรกับคู่ของค่าที่ใหญ่มากกว่านั้น

เทคนิคใน Binius คือการทำ bitwise: เรามองไปที่บิตแต่ละตัวของค่าแต่ละตัว (เช่นสำหรับสิ่งที่เราตั้งชื่อว่า “11”, นั่นคือ [1,1,0,1]), แล้วเราขยายแถวตามแนวแนวคือเราดำเนินกระบวนการขยายบนแถว 1 ของแต่ละองค์ประกอบ จากนั้นต่อที่แถว 𝑥0 และต่อที่ “𝑥₁“ แถว จากนั้นบน 𝑥₀∗𝑥₁แถว และอื่น ๆ (ดีในตัวอย่างของของเล่นของเราเราหยุดที่นั่น แต่ในการปฏิบัติจรรยาบรรณจรรยาบรรณเราจะไปถึง 128 แถว (อันสุดท้ายคือ 𝑥₆∗ …∗ 𝑥₀)).

สรุป:

• เราเรียกบิตในไฮเปอร์คิวบ์และแปลงมันเป็นเส้นตาราง
• จากนั้นเราจะจัดการกลุ่มของบิตที่อยู่ติดกันบนแต่ละแถวเป็นองค์ประกอบขนาดใหญ่ และทำการคำนวณบนเขาของพวกเขาเพื่อขยายแถว Reed-Solomon
• จากนั้นเราจะเลือกการรวมแถวของแต่ละคอลัมน์ของบิต และได้รับคอลัมน์ของบิต (สำหรับสี่เหลี่ยมที่ใหญ่กว่า 4x4 เป็นมากกว่า) สำหรับแต่ละแถวเป็นเอาต์พุต
• จากนั้นเราจะดูที่เอาท์พุตเป็นเมทริกซ์ และจัดการบิตของมันเป็นแถวอีกครั้ง

ทำไมสิ่งนี้ถึงทำงาน? ในคณิตศาสตร์ “ปกติ” ความสามารถในการ (บ่อยครั้ง) ทำการบวกลบเสมอกันในลำดับใดก็ได้และได้ผลลัพธ์เดียวกันหยุดทำงานหากคุณเริ่มตัดตัวเลขของตัวเลขขึ้นมา เช่น ถ้าฉันเริ่มด้วยตัวเลข 345 และคูณด้วย 8 แล้วคูณด้วย 3 ฉันได้ 8280 และถ้าทำการทำงานสองขั้นตอนนี้ในลำดับตรงกันข้ามกัน ฉันยังคงทำ 8280 ได้ แต่หากฉันแทรก “แยกตามตัวเลข” ในระหว่างขั้นตอนสองขั้นตอน มันจะล้มเหลว: หากคุณทำ 8x แล้ว 3x คุณจะได้:

แต่ถ้าคุณทํา 3x แล้ว 8x คุณจะได้รับ:

แต่ในเขตบรรทัดที่สร้างขึ้นด้วยโครงสร้างทาวเวอร์ วิธีการนี้ก็ทำงานได้ สาเหตุที่อยู่ในความแยกต่างหาก: หากคุณคูณค่าที่ใหญ่ด้วยค่าที่เล็ก สิ่งที่เกิดขึ้นในแต่ละส่วนจะอยู่ในแต่ละส่วน หากเราคูณ 1100101010001111 ด้วย 11 นี่คือเหมือนกับการแยกปัจจัยแรกของ 1100101010001111 ซึ่งเป็นเหมือนกัน

และจากนั้นคูณทุกส่วนด้วย 11 แยกตาม

รวมเข้าด้วยกัน

โดยทั่วไประบบพิสูจน์ความรู้ศูนย์ทำงานโดยการทำคำแถลงเกี่ยวกับพหลมิเนียลซึ่งเขียนแทนคำแถลงเกี่ยวกับการประเมินหลัก: เช่นเดียวกับที่เราเห็นในตัวอย่างฟิโบนัจ 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) ทำการตรวจสอบทุกขั้นตอนของการคำนวณฟิโบนัจ เราตรวจสอบคำแถลงเกี่ยวกับพหลมิเนียลโดยการพิสูจน์การประเมินที่จุดสุ่ม การตรวจสอบนี้ที่จุดสุ่มนั้นแทนการตรวจสอบทั้งหมดของพหลมิเนียล หากสมการพหลมิเนียลไม่ตรงกัน โอกาสที่มันตรงกันที่พิกัดสุ่มเฉพาะนั้นเล็กมาก

ในความเป็นจริง แหล่งที่สำคัญของความไมประสิทธิภาพมาจากความเป็นจริงว่าในโปรแกรมจริง ๆ เราทำงานกับตัวเลขส่วนใหญ่ที่เล็ก: ดัชนีในลูป for, ค่า True/False, ตัวนับ และสิ่งที่คล้ายกัน แต่เมื่อเรา “ขยาย” ข้อมูลโดยใช้การเข้ารหัส Reed-Solomon เพื่อให้มีความซ้ำซ้อนที่จำเป็นเพื่อให้การตรวจสอบโดยใช้ Merkle proof เป็นปลอดภัย ส่วนใหญ่ของค่า “เพิ่มเติม” ล้วนจะใช้พื้นที่ขนาดเต็มของเขตบริเวณ แม้ว่าค่าเริ่มต้นจะเล็ก

เราต้องการทําให้สนามมีขนาดเล็กที่สุด Plonky2 ทําให้เราลดลงจากตัวเลข 256 บิตเป็นตัวเลข 64 บิตจากนั้น Plonky3 ก็เพิ่มขึ้นเป็น 31 บิต แต่ถึงอย่างนั้นก็ยังเหมาะสมที่สุด ด้วยฟิลด์ไบนารีเราสามารถทํางานกับแต่ละบิตได้ สิ่งนี้ทําให้การเข้ารหัส "หนาแน่น": หากข้อมูลพื้นฐานที่แท้จริงของคุณมีบิต n การเข้ารหัสของคุณจะมีบิต n และส่วนขยายจะมี 8 * n บิตโดยไม่มีค่าใช้จ่ายเพิ่มเติม

ตอนนี้เรามาดูแผนภาพอีกครั้งครั้งที่สาม:

ใน Binius เรากำลังมุ่งมั่นที่จะเป็นพหุนามหลายเส้น: hypercube 𝑃(x₀,x₁,…x_k) โดยที่การประเมินรายบุคคล P(0,0... 0), ป(0,0... 1) สูงถึง P (1,1,... 1) ถือครองข้อมูลที่เราสนใจ เพื่อพิสูจน์การประเมิน ณ จุดหนึ่งเรา "ตีความใหม่" ข้อมูลเดียวกันกับสี่เหลี่ยมจัตุรัส จากนั้นเราจะขยายแต่ละแถวโดยใช้การเข้ารหัส Reed-Solomon เหนือกลุ่มบิตเพื่อให้ข้อมูลมีความซ้ําซ้อนที่จําเป็นสําหรับการสืบค้นสาขา Merkle แบบสุ่มเพื่อให้ปลอดภัย จากนั้นเราจะคํานวณชุดค่าผสมเชิงเส้นแบบสุ่มของแถวด้วยค่าสัมประสิทธิ์ที่ออกแบบมาเพื่อให้แถวรวมใหม่มีการประเมินที่เราสนใจ ทั้งแถวที่สร้างขึ้นใหม่นี้ (ซึ่งถูกตีความใหม่เป็น 128 แถวของบิต) และคอลัมน์ที่เลือกแบบสุ่มสองสามคอลัมน์ที่มีสาขา Merkle จะถูกส่งผ่านไปยังผู้ตรวจสอบ

ผู้ตรวจสอบจากนั้นทำ "การผสมแถวของส่วนขยาย" (หรือจะพูดให้ละเอียดขึ้นคือ หลายคอลัมน์ของส่วนขยาย) และ "ส่วนขยายของการผสมแถว" และตรวจสอบว่าสองอย่างตรงกัน จากนั้นพวกเขาคำนวณการผสมคอลัมน์ และตรวจสอบว่ามันส่งกลับค่าที่พวกเขาประกาศไว้ และนี่คือระบบพิสูจน์ของเรา (หรือจะพูดให้ละเอียดขึ้นคือ ระบบการสัญญาการยืนยันโพลิโนเมียล ซึ่งเป็นส่วนสำคัญของระบบพิสูจน์)

เราไม่ได้ครอบคลุมอะไรบ้างหรือ

• อัลกอริทึมที่มีประสิทธิภาพในการขยายแถวที่จำเป็นในการเพิ่มประสิทธิภาพในการคำนวณของผู้ตรวจสอบ เราใช้การแปลงฟูรีเยร์เร็วบนเขตข้อมูลทวิภาคเป็นฐานสอง อธิบายที่นี่ (though the exact implementation will be different, because this post uses a less efficient construction not based on recursive extension).
• เลขคณิต พหุนามแบบตัวแปรเดียวนั้นสะดวกเพราะคุณสามารถทําสิ่งต่างๆเช่น F(X+2)-F(X+1)-F(X) = Z(X)*H(X) เพื่อเชื่อมโยงขั้นตอนที่อยู่ติดกันในการคํานวณ ในไฮเปอร์คิวบ์ "ขั้นตอนต่อไป" สามารถตีความได้น้อยกว่า "X+1" มาก คุณสามารถทํา X + k, พลังของ k แต่พฤติกรรมการกระโดดนี้จะเสียสละข้อดีที่สําคัญหลายประการของ Binius การแก้ปัญหาจะถูกนําเสนอใน Binius paper (ดูส่วน 4.3), แต่นี่เป็นรูปแบบของรูปแบบที่ลึกลงไปในตัวเอง
• วิธีการตรวจสอบค่าเฉพาะอย่างปลอดภัย ตัวอย่าง Fibonacci ต้องตรวจสอบเงื่อนไขขอบเขตที่สําคัญ: F(0)=F(1)=1 และค่า F(100) แต่ด้วย Binius "ดิบ" มันไม่ปลอดภัยที่จะตรวจสอบที่จุดประเมินที่รู้จักล่วงหน้า มีวิธีง่ายๆในการแปลงการตรวจสอบการประเมินที่รู้จักเป็นการตรวจสอบการประเมินที่ไม่รู้จักโดยใช้สิ่งที่เรียกว่าโปรโตคอลการตรวจสอบผลรวม แต่เราไม่ได้เข้าไปที่นี่
• โปรโตคอลการค้นหา, เป็นเทคโนโลยีอีกอย่างที่ได้รับการใช้งานมากขึ้นเร็ว ๆ ในเวลา ๆ นี้เพื่อทำให้ระบบการพิสูจน์ที่มีประสิทธิภาพสูงมากขึ้น บินิอัสสามารถรวมกับโปรโตคอลการค้นหาได้สำหรับการใช้งานหลายรูปแบบ
• ก้าวข้ามเวลาการตรวจสอบรากที่สอง รากที่สองมีราคาแพง: หลักฐาน Binius ของบิตมีความยาวประมาณ 11 MB คุณสามารถแก้ไขปัญหานี้ได้โดยใช้ระบบพิสูจน์อื่น ๆ เพื่อสร้าง "หลักฐานการพิสูจน์ Binius" จึงได้รับประสิทธิภาพของ Binius ในการพิสูจน์ข้อความหลักและขนาดการพิสูจน์ที่เล็ก อีกทางเลือกหนึ่งคือโปรโตคอล FRI-Binius ที่ซับซ้อนกว่ามากซึ่งสร้างหลักฐานขนาดโพลีลอการิทึม (เช่น FRI ปกติ)
• วิธีการที่ Binius มีผลต่อสิ่งที่นับว่าเป็น “SNARK-friendly” สรุปพื้นฐานคือว่าหากคุณใช้ Binius คุณจะไม่ต้องกังวลมากเกี่ยวกับการทำให้การคำนวณเป็น “arithmetic-friendly” อีกต่อไป: การสร้างแฮช “regular” จะไม่มีประสิทธิภาพมากกว่าแฮชเลขคณิตแบบดั้งเดิม, การคูณ modulo หรือ modulo จะไม่เป็นปัญหาใหญ่อีกต่อไปเมื่อเปรียบเทียบกับการคูณ modulo , และอื่นๆ แต่นี่เป็นหัวข้อที่ซับซ้อนมาก มีการเปลี่ยนแปลงมากมายเมื่อทุกอย่างถูกดำเนินการในรูปแบบไบนารี

ฉันคาดหวังว่าจะมีการปรับปรุงอีกมากมายในเทคนิคการพิสูจน์บนฟิลด์ทวิภาคในเดือนที่ผ่านมา

Disclaimer：

1. บทความนี้พิมพ์ซ้ําจาก [Panews]. Forward the Original Title‘Vitalik详解Binius：基于二进制字段的高效证明系统’. All copyrights belong to the original author [GateVitalik Buterin*]. If there are objections to this reprint, please contact the Gate Learnทีม และพวกเขาจะดำเนินการโดยเร็ว
2. คำชี้แจงความรับผิด: มุมมองและความคิดเห็นที่แสดงในบทความนี้เป็นเพียงของผู้เขียนเท่านั้น และไม่เป็นการให้คำแนะนำทางด้านการลงทุนใดๆ
3. การแปลบทความเป็นภาษาอื่นๆ ทำโดยทีม Gate Learn ห้ามคัดลอก แจกจ่าย หรือปลอมของบทความที่ถูกแปล นอกจากจะได้ระบุไว้