ผู้เขียนต้นฉบับ: Vitalik Buterin
การรวบรวมต้นฉบับ: Kate, MarsBit
บทความนี้มุ่งเป้าไปที่ผู้อ่านที่โดยทั่วไปคุ้นเคยกับการเข้ารหัสในยุค 2019 โดยเฉพาะ SNARK และ STARK หากคุณไม่ใช่ฉันขอแนะนำให้คุณอ่านบทความเหล่านี้ก่อน ขอขอบคุณเป็นพิเศษสำหรับ Justin Drake, Jim Posen, Benjamin Diamond และ Radi Cojbasic สำหรับคำติชมและความคิดเห็น
ในช่วงสองปีที่ผ่านมา STARK ได้กลายเป็นเทคโนโลยีที่สำคัญและไม่สามารถทดแทนได้ ซึ่งสามารถสร้างหลักฐานการเข้ารหัสลับที่ตรวจสอบได้อย่างง่ายดายของข้อความที่ซับซ้อนมาก (เช่น การพิสูจน์ว่าบล็อก Ethereum นั้นถูกต้อง) สาเหตุสำคัญประการหนึ่งคือขนาดฟิลด์เล็ก: SNARK ที่ใช้เส้นโค้งรูปไข่ต้องการให้คุณทำงานกับจำนวนเต็ม 256 บิตเพื่อความปลอดภัยที่เพียงพอ ในขณะที่ STARK อนุญาตให้คุณใช้ขนาดฟิลด์เล็กลง ซึ่งมีประสิทธิภาพมากกว่า ประการแรกคือฟิลด์ Goldilocks (จำนวนเต็ม 64 บิต) จากนั้น Mersenne 31 และ BabyBear (ทั้ง 31 บิต) เนื่องจากประสิทธิภาพเหล่านี้เพิ่มขึ้น Plonky 2 ที่ใช้ Goldilocks จึงเร็วกว่ารุ่นก่อนหลายร้อยเท่าในการพิสูจน์การคำนวณที่หลากหลาย
คำถามทั่วไปก็คือ เราจะนำแนวโน้มนี้ไปสู่ข้อสรุปเชิงตรรกะและสร้างระบบพิสูจน์ที่ทำงานเร็วขึ้นโดยดำเนินการโดยตรงกับศูนย์และค่าศูนย์ได้หรือไม่ นั่นคือสิ่งที่ Binius พยายามทำ โดยใช้เทคนิคทางคณิตศาสตร์มากมายที่ทำให้แตกต่างจาก SNARK และ STARK เมื่อสามปีที่แล้วอย่างมาก โพสต์นี้จะอธิบายว่าทำไมฟิลด์ขนาดเล็กจึงทำให้การสร้างการพิสูจน์มีประสิทธิภาพมากขึ้น เหตุใดฟิลด์ไบนารีจึงทรงพลังอย่างมีเอกลักษณ์ และเทคนิคที่ Binius ใช้เพื่อสร้างการพิสูจน์บนฟิลด์ไบนารีที่มีประสิทธิภาพมาก
Binius ในตอนท้ายของโพสต์นี้ คุณควรจะสามารถเข้าใจทุกส่วนของแผนภาพนี้ได้
ทบทวน: เขตข้อมูลจำกัด
งานหลักประการหนึ่งของระบบพิสูจน์การเข้ารหัสคือการดำเนินการกับข้อมูลจำนวนมากโดยรักษาตัวเลขให้น้อย หากคุณสามารถย่อข้อความเกี่ยวกับโปรแกรมขนาดใหญ่ให้เป็นสมการทางคณิตศาสตร์ที่มีตัวเลขจำนวนไม่กี่ตัวได้ แต่ตัวเลขเหล่านั้นมีขนาดใหญ่เท่ากับโปรแกรมดั้งเดิม คุณจะไม่มีทางไปไหนเลย
ในการทำการคำนวณทางคณิตศาสตร์ที่ซับซ้อนในขณะที่รักษาตัวเลขให้มีขนาดเล็ก นักเข้ารหัสมักใช้เลขคณิตแบบโมดูลาร์ เราเลือกจำนวนเฉพาะ โมดูโล p ตัวดำเนินการ % หมายถึง หาส่วนที่เหลือ: 15% 7 = 1, 53% 10 = 3 เป็นต้น (โปรดทราบว่าคำตอบนั้นไม่เป็นลบเสมอ เช่น -1% 10 = 9)
คุณอาจเคยเห็นเลขคณิตแบบโมดูลาร์ในบริบทของการบวกและการลบเวลา (เช่น เวลา 4 ชั่วโมงหลังจาก 9 โมงเช้า) แต่ที่นี่ เราไม่เพียงแค่เพิ่มและลบตัวเลขแบบโมดูโลเท่านั้น เรายังสามารถคูณได้อีกด้วย แล้วหารและรับเลขชี้กำลัง
เรากำหนดใหม่:
กฎข้างต้นทั้งหมดสอดคล้องกันในตัวเอง ตัวอย่างเช่น ถ้า p= 7 แล้ว:
5+ 3 = 1 (เพราะ 8% 7 = 1)
1-3 = 5 (เพราะ -2% 7 = 5)
2*5=3
3/5 = 2
คำที่กว้างกว่าสำหรับโครงสร้างนี้คือสนามที่มีขอบเขตจำกัด เขตข้อมูลจำกัดเป็นโครงสร้างทางคณิตศาสตร์ที่เป็นไปตามกฎทางคณิตศาสตร์ตามปกติ แต่มีค่าที่เป็นไปได้จำนวนจำกัด เพื่อให้แต่ละค่าสามารถแสดงด้วยขนาดคงที่ได้
ฟิลด์เลขคณิตแบบโมดูโล (หรือฟิลด์จำนวนเฉพาะ) เป็นฟิลด์จำกัดประเภทที่ใช้บ่อยที่สุด แต่มีอีกประเภทหนึ่ง: ฟิลด์ขยาย คุณอาจเคยเห็นฟิลด์ส่วนขยาย: พหูพจน์ เรา จินตนาการ องค์ประกอบใหม่ ตั้งชื่อมันว่า i และคำนวณองค์ประกอบนั้น: (3 i+ 2)*(2 i+ 4) = 6 i*i+ 12 i+ 4 i+ 8 = 16 i+ 2 เราก็ใช้ส่วนขยายของสนามของจำนวนเฉพาะได้เช่นกัน เมื่อเราเริ่มจัดการกับฟิลด์ที่มีขนาดเล็กลง การขยายฟิลด์หลักมีความสำคัญมากขึ้นในด้านความปลอดภัย ในขณะที่ฟิลด์ไบนารี (ใช้โดย Binius) อาศัยการขยายทั้งหมดเพื่อให้มีประโยชน์ในทางปฏิบัติ
ทบทวน: เลขคณิต
SNARK และ STARK วิธีการพิสูจน์โปรแกรมคอมพิวเตอร์คือการใช้เลขคณิต: คุณนำคำสั่งเกี่ยวกับโปรแกรมที่คุณต้องการพิสูจน์มาแปลงเป็นสมการทางคณิตศาสตร์ที่มีพหุนาม การแก้สมการที่มีประสิทธิภาพสอดคล้องกับการดำเนินการของโปรแกรมอย่างมีประสิทธิผล
ตัวอย่างง่ายๆ สมมติว่าฉันคำนวณเลขฟีโบนัชชีลำดับที่ 100 และฉันต้องการพิสูจน์ให้คุณเห็นว่ามันคืออะไร ฉันสร้างพหุนาม F ที่เข้ารหัสลำดับฟีโบนัชชี: ดังนั้น F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5 และอื่น ๆ รวม จำนวน 100 ก้าว เงื่อนไขที่ฉันต้องพิสูจน์คือ F(x+ 2)=F(x)+F(x+ 1) ในช่วงทั้งหมด x={ 0, 1 … 98 } ฉันสามารถโน้มน้าวคุณได้โดยให้ผลหารแก่คุณ:
โดยที่ Z(x) = (x-0) * (x-1) * …(x-98) ถ้าฉันสามารถระบุได้ว่ามี F และ H เป็นไปตามสมการนี้ F จะต้องเป็นไปตาม F(x+ 2)-F(x+ 1)-F(x) ในช่วง หากฉันตรวจสอบเพิ่มเติมว่า F(0)=F(1)=1 เป็นไปตามนั้น F(100) จะต้องเป็นเลขฟีโบนัชชีตัวที่ 100
หากคุณต้องการพิสูจน์บางสิ่งที่ซับซ้อนกว่านี้ ให้แทนที่ความสัมพันธ์ แบบง่าย F(x+ 2) = F(x) + F(x+ 1) ด้วยสมการที่ซับซ้อนมากขึ้น ซึ่งโดยพื้นฐานแล้วบอกว่า F(x+ 1) ) คือ ผลลัพธ์ของการเริ่มต้นเครื่องเสมือนด้วยสถานะ F(x) และรันขั้นตอนการคำนวณ คุณยังสามารถแทนที่ตัวเลข 100 ด้วยตัวเลขที่มากกว่าได้ เช่น 100000000 เพื่อรองรับขั้นตอนที่มากขึ้น
SNARK และ STARK ทั้งหมดมีพื้นฐานมาจากแนวคิดในการใช้สมการง่ายๆ บนพหุนาม (และบางครั้งเวกเตอร์และเมทริกซ์) เพื่อแสดงความสัมพันธ์ขนาดใหญ่ระหว่างค่าเดี่ยว อัลกอริธึมบางอันไม่ได้ตรวจสอบความเท่าเทียมกันระหว่างขั้นตอนการคำนวณที่อยู่ติดกันดังที่กล่าวมาข้างต้น: ตัวอย่างเช่น PLONK จะไม่ตรวจสอบ และ R 1 CS ก็ไม่ตรวจสอบ แต่การตรวจสอบที่มีประสิทธิภาพที่สุดหลายๆ รายการทำเช่นนี้ เนื่องจากการตรวจสอบเดียวกัน (หรือการตรวจสอบเดียวกัน 2-3 ครั้ง) หลายๆ ครั้งทำให้ง่ายต่อการลดค่าใช้จ่ายให้เหลือน้อยที่สุด
Plonky 2: จาก 256-bit SNARK และ STARK ถึง 64-bit... เท่านั้น STARK
เมื่อห้าปีที่แล้ว บทสรุปที่สมเหตุสมผลของการพิสูจน์ความรู้เป็นศูนย์ประเภทต่างๆ มีดังนี้ การพิสูจน์มีสองประเภท: (ตามเส้นโค้งรูปไข่) SNARK และ (ตามแฮช) STARK ในทางเทคนิคแล้ว STARK เป็นประเภทของ SNARK แต่ในทางปฏิบัติ SNARK มักจะใช้เพื่ออ้างถึงตัวแปรที่อิงเส้นโค้งรูปไข่ และ STARK ใช้เพื่ออ้างถึงโครงสร้างแบบแฮช SNARK มีขนาดเล็ก คุณจึงตรวจสอบได้อย่างรวดเร็วและติดตั้งบนโซ่ได้อย่างง่ายดาย STARK มีขนาดใหญ่ แต่ไม่ต้องการการตั้งค่าที่เชื่อถือได้ และทนทานต่อควอนตัม
STARK ทำงานโดยถือว่าข้อมูลเป็นแบบพหุนาม คำนวณการคำนวณของพหุนามนั้น และใช้ราก Merkel ของข้อมูลที่ขยายเป็น ความมุ่งมั่นแบบพหุนาม
ประวัติสำคัญที่นี่คือ SNARK ที่ใช้ elliptic curve ถูกนำมาใช้กันอย่างแพร่หลายเป็นครั้งแรก จนกระทั่งประมาณปี 2018 ที่ STARK มีประสิทธิภาพเพียงพอ ต้องขอบคุณ FRI และ Zcash ก็เปิดใช้งานมานานกว่าหนึ่งปีแล้ว SNARK ที่ใช้เส้นโค้งวงรีมีข้อจำกัดที่สำคัญ: หากคุณต้องการใช้ SNARK ที่ใช้เส้นโค้งวงรี การคำนวณในสมการเหล่านี้จะต้องทำโดยใช้โมดูลัสจุดบนเส้นโค้งวงรี นี่เป็นตัวเลขจำนวนมาก ซึ่งมักจะใกล้กับ 2 ยกกำลัง 256 เช่น เส้นโค้ง bn 128 คือ 21888242871839275222246405745257275088548364400416034343698204186575808495617 แต่การคำนวณตามจริงจะใช้ตัวเลขเพียงเล็กน้อย: หากคุณนึกถึงโปรแกรม ของจริง ในภาษาที่คุณชื่นชอบ สิ่งที่โปรแกรมส่วนใหญ่ใช้คือตัวนับ การจัดทำดัชนีสำหรับลูป ตำแหน่งในโปรแกรมซึ่งเป็นตัวแทนของ True หรือ False บิตเดียว และสิ่งอื่นๆ ที่มักจะมีความยาวเพียงไม่กี่หลักเท่านั้น
แม้ว่าข้อมูล ดั้งเดิม ของคุณจะประกอบด้วยตัวเลข น้อย แต่กระบวนการพิสูจน์ต้องใช้ผลหารในการคำนวณ การขยาย การรวมกันเชิงเส้นแบบสุ่ม และการแปลงข้อมูลอื่น ๆ ซึ่งจะส่งผลให้มีออบเจ็กต์จำนวนเท่ากันหรือมากกว่านั้นซึ่งมีขนาดโดยเฉลี่ยเท่ากับ ขนาดฟิลด์ทั้งหมดของคุณมีขนาดเท่ากัน สิ่งนี้ทำให้เกิดความไร้ประสิทธิภาพที่สำคัญ: เพื่อพิสูจน์การคำนวณสำหรับค่าที่น้อย n ค่า คุณต้องทำการคำนวณเพิ่มเติมสำหรับค่าที่มากกว่า n ค่ามาก ในตอนแรก STARK สืบทอดนิสัยของ SNARK ในการใช้ฟิลด์ 256 บิต และดังนั้นจึงประสบปัญหาจากความไร้ประสิทธิภาพเช่นเดียวกัน
ส่วนขยาย Reed-Solomon บางส่วนไปสู่การประเมินพหุนาม แม้ว่าค่าเดิมจะมีน้อย แต่ค่าเพิ่มเติมใดๆ จะถูกขยายเป็นขนาดเต็มของฟิลด์ (ในกรณีนี้คือ 2^31-1)
ในปี 2022 Plonky 2 จะเปิดตัว นวัตกรรมหลักของ Plonky 2 คือโมดูโลทางคณิตศาสตร์ซึ่งเป็นจำนวนเฉพาะที่น้อยกว่า: 2 ยกกำลัง 64 – 2 ยกกำลัง 32 + 1 = 18446744067414584321 ตอนนี้ การเพิ่มหรือการคูณแต่ละครั้งสามารถทำได้โดยใช้คำสั่งไม่กี่คำบน CPU และการแฮชข้อมูลทั้งหมดเข้าด้วยกันจะเร็วขึ้นกว่าเดิม 4 เท่า แต่มีปัญหาอยู่: วิธีการนี้ใช้ได้กับ STARK เท่านั้น หากคุณพยายามใช้ SNARK เส้นโค้งวงรีจะไม่ปลอดภัยสำหรับเส้นโค้งวงรีขนาดเล็กดังกล่าว
เพื่อความมั่นใจในความปลอดภัย Plonky 2 จำเป็นต้องแนะนำฟิลด์ส่วนขยายด้วย เทคนิคสำคัญในการตรวจสอบสมการทางคณิตศาสตร์คือ การสุ่มตัวอย่างจุดสุ่ม: หากคุณต้องการตรวจสอบว่า 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 ยกกำลัง 256 แต่สำหรับปริมาณโมดูลัสที่เป็น 2 ยกกำลัง 64 - 2 ยกกำลัง 32 + 1 เรายังไปไม่ถึง และถ้าเราลงไปที่ 2 ยกกำลัง 31 - 1 นั่นไม่ใช่กรณีนั้นอย่างแน่นอน . การพยายามปลอมแปลงหลักฐาน 2 พันล้านครั้งจนกว่าจะโชคดีนั้นอยู่ในความสามารถของผู้โจมตีอย่างแน่นอน
เพื่อป้องกันสิ่งนี้ เราสุ่มตัวอย่าง r จากฟิลด์ขยาย ตัวอย่างเช่น คุณสามารถกำหนด y โดยที่ y 3 = 5 และนำผลรวมของ 1, y, y 2 สิ่งนี้จะเพิ่มจำนวนพิกัดทั้งหมดเป็นประมาณ 2^93 พหุนามส่วนใหญ่ที่ผู้พิสูจน์คำนวณไม่ได้อยู่ในโดเมนขยายนี้ เป็นเพียงจำนวนเต็มแบบโมดูโล 2^31-1 ดังนั้น คุณยังคงได้รับประสิทธิภาพทั้งหมดจากการใช้โดเมนขนาดเล็ก แต่การตรวจสอบจุดสุ่มและการคำนวณ FRI จะเจาะลึกเข้าไปในขอบเขตที่ใหญ่กว่านี้จริงๆ เพื่อให้ได้ความปลอดภัยที่คุณต้องการ
จากจำนวนเฉพาะน้อยไปจนถึงเลขฐานสอง
คอมพิวเตอร์ดำเนินการทางคณิตศาสตร์โดยแสดงตัวเลขที่มากขึ้นเป็นลำดับของ 0 และ 1 และสร้าง วงจร ไว้บนบิตเหล่านี้เพื่อดำเนินการต่างๆ เช่น การบวกและการคูณ คอมพิวเตอร์ได้รับการปรับให้เหมาะสมโดยเฉพาะสำหรับจำนวนเต็ม 16 บิต 32 บิต และ 64 บิต ตัวอย่างเช่น 2 ยกกำลัง 64 - 2 ยกกำลัง 32 + 1 และ 2 ยกกำลัง 31 - 1 ถูกเลือกไม่เพียงเพราะมันเข้ากับขอบเขตเหล่านี้เท่านั้น แต่ยังเป็นเพราะพวกมันเข้ากับขอบเขตเหล่านี้ได้ดีอีกด้วย: คุณสามารถทำได้ โดยการดำเนินการคูณแบบ 32 บิตแบบปกติเพื่อทำการคูณแบบโมดูโล 2^64 - 2^32 + 1 และเลื่อนระดับบิตและคัดลอกเอาต์พุตในหลาย ๆ ที่ บทความนี้จะอธิบายเทคนิคบางอย่างได้ดี
อย่างไรก็ตาม วิธีที่ดีกว่าคือการคำนวณโดยตรงในรูปแบบไบนารี จะเกิดอะไรขึ้นถ้าการบวกอาจเป็น แค่ XOR โดยไม่ต้องกังวลกับการ แบก โอเวอร์โฟลว์จากการเพิ่ม 1 + 1 จากบิตหนึ่งไปยังอีกบิตหนึ่ง จะเกิดอะไรขึ้นถ้าการคูณสามารถขนานกันมากขึ้นในลักษณะเดียวกันได้? ข้อดีเหล่านี้ทั้งหมดขึ้นอยู่กับความสามารถในการใช้หนึ่งบิตเพื่อแสดงค่าจริง/เท็จ
การจับภาพข้อดีเหล่านี้ของการคำนวณไบนารี่โดยตรงคือสิ่งที่ Binius พยายามทำ ทีม Binius สาธิตการปรับปรุงประสิทธิภาพในการพูดของพวกเขาที่ zkSummit:
แม้ว่า ขนาด จะใกล้เคียงกัน แต่การดำเนินการภาคสนามแบบไบนารี 32 บิตต้องการทรัพยากรในการคำนวณน้อยกว่าการดำเนินการภาคสนาม Mersenne แบบ 31 บิตถึง 5 เท่า
จากพหุนามไปจนถึงไฮเปอร์คิวบ์
สมมติว่าเราเชื่อเหตุผลนี้และต้องการทำทุกอย่างด้วยบิต (0 และ 1) เราจะใช้พหุนามเพื่อแทนพันล้านบิตได้อย่างไร
ที่นี่เราประสบปัญหาในทางปฏิบัติสองประการ:
1. เพื่อให้พหุนามเป็นตัวแทนของค่าจำนวนมาก ค่าเหล่านี้จะต้องสามารถเข้าถึงได้ในระหว่างการประเมินพหุนาม: ในตัวอย่างฟีโบนัชชีด้านบน F( 0), F( 1) … F( 100) ใน ในการคำนวณจำนวนมาก เลขชี้กำลังสามารถเข้าถึงหลักล้านได้ ฟิลด์ที่เราใช้ต้องมีตัวเลขถึงขนาดนี้
2. การพิสูจน์ค่าใดๆ ที่เราส่งในแผนผัง Merkle (เช่นเดียวกับ STARK ทั้งหมด) จำเป็นต้องมีการเข้ารหัส Reed-Solomon: เช่น การขยายค่าจาก n เป็น 8n โดยใช้ความซ้ำซ้อนเพื่อป้องกันไม่ให้ผู้พิสูจน์เจตนาร้ายทำการโกงโดยการปลอมค่าระหว่างการคำนวณ นอกจากนี้ยังต้องมีฟิลด์ที่ใหญ่เพียงพอ: หากต้องการขยายจากหนึ่งล้านค่าเป็น 8 ล้าน คุณต้องมีจุดที่แตกต่างกัน 8 ล้านจุดเพื่อประเมินพหุนาม
แนวคิดหลักของ Binius คือการแก้ปัญหาทั้งสองนี้แยกกัน และดำเนินการดังกล่าวโดยการแสดงข้อมูลเดียวกันในสองวิธีที่แตกต่างกัน ประการแรก พหุนามนั้นเอง ระบบต่างๆ เช่น SNARK ที่ใช้เส้นโค้งรูปไข่, STARK ในยุคปี 2019 และ Plonky 2 มักจะจัดการกับพหุนามในตัวแปรเดียว: F(x) ในทางกลับกัน Binius ได้รับแรงบันดาลใจจากโปรโตคอล Spartan และใช้พหุนามหลายตัวแปร: F(x 1, x 2,… xk) ที่จริงแล้ว เราเป็นตัวแทนของวิถีการคำนวณทั้งหมดบน ไฮเปอร์คิวบ์ เชิงคำนวณ โดยที่ xi แต่ละตัวมีค่าเป็น 0 หรือ 1 ตัวอย่างเช่น หากเราต้องการแสดงลำดับฟีโบนัชชี และเรายังคงใช้ช่องที่ใหญ่พอที่จะแสดงลำดับฟีโบนัชชี เราสามารถนึกถึง 16 ลำดับแรกได้ดังนี้:
กล่าวคือ F(0, 0, 0, 0) ควรเป็น 1, F(1, 0, 0, 0) ควรเป็น 1 ด้วย, F(0, 1, 0, 0) ควรเป็น 2 และดังนั้น จนกระทั่ง F(1, 1, 1, 1)= 987 เมื่อพิจารณาถึงการคำนวณแบบไฮเปอร์คิวบ์ดังกล่าว จะมีพหุนามเชิงเส้นหลายตัวแปร (ระดับ 1 สำหรับแต่ละตัวแปร) ที่สร้างการคำนวณเหล่านี้ ดังนั้นเราจึงคิดว่าค่าชุดนี้เป็นตัวแทนของพหุนาม เราไม่จำเป็นต้องคำนวณค่าสัมประสิทธิ์
แน่นอนว่าตัวอย่างนี้เป็นเพียงภาพประกอบเท่านั้น ในทางปฏิบัติ จุดรวมของการเข้าสู่ไฮเปอร์คิวบ์คือให้เราจัดการกับแต่ละบิต วิธี Binius Native ในการคำนวณตัวเลขฟีโบนัชชีคือการใช้ลูกบาศก์มิติสูง โดยใช้แต่ละกลุ่ม เช่น 16 บิตในการจัดเก็บตัวเลข ต้องใช้ความฉลาดบางประการในการบวกจำนวนเต็มเล็กน้อย แต่สำหรับ Binius ก็ไม่ยากเกินไป
ตอนนี้เรามาดูการเข้ารหัสการลบ วิธีการทำงานของ STARK คือ: คุณรับค่า n ค่า Reed-Solomon จะขยายค่าเหล่านั้นเป็นค่าที่มากขึ้น (โดยปกติคือ 8n โดยปกติจะอยู่ระหว่าง 2n ถึง 32n) จากนั้นสุ่มเลือกสาขา Merkle บางสาขาจากส่วนขยาย และพวกเขาทำการตรวจสอบบางประเภท ความยาวของไฮเปอร์คิวบ์คือ 2 ในแต่ละมิติ ดังนั้นการขยายโดยตรงจึงไม่สามารถทำได้จริง เนื่องจากไม่มี พื้นที่ เพียงพอที่จะสุ่มตัวอย่างสาขา Merkle จาก 16 ค่า ดังนั้นสิ่งที่เราจะทำ? สมมติว่าไฮเปอร์คิวบ์เป็นสี่เหลี่ยมจัตุรัส!
Simple Binius - ตัวอย่าง
ดู ที่นี่ สำหรับการใช้หลามของโปรโตคอลนี้
ลองดูตัวอย่าง โดยใช้จำนวนเต็มปกติเป็นฟิลด์ของเราเพื่อความสะดวก (ในการใช้งานจริง จะใช้องค์ประกอบฟิลด์ไบนารี) ขั้นแรก เราเข้ารหัสไฮเปอร์คิวบ์ที่เราต้องการส่งเป็นสี่เหลี่ยมจัตุรัส:
ตอนนี้เราขยายจัตุรัสโดยใช้ Reed-Solomon นั่นคือ เราถือว่าแต่ละแถวเป็นพหุนามระดับที่ 3 ที่ประเมินที่ x ={ 0, 1, 2, 3 } และประเมินพหุนามเดียวกันที่ x ={ 4, 5, 6, 7 }:
ระวังตัวเลขอาจขยายตัวอย่างรวดเร็ว! นั่นเป็นเหตุผลว่าทำไมในการใช้งานจริง เรามักจะใช้ฟิลด์ที่มีขอบเขตจำกัด แทนที่จะเป็นจำนวนเต็มปกติ เช่น หากเราใช้จำนวนเต็มโมดูโล 11 การขยายบรรทัดแรกจะเป็นเพียง [3, 10, 0, 6]
หากคุณต้องการลองใช้ส่วนขยายและยืนยันตัวเลขที่นี่ด้วยตัวคุณเอง คุณสามารถใช้โค้ดส่วนขยาย Reed-Solomon แบบง่ายๆ ของฉันได้ที่นี่
ต่อไป เราจะถือว่าส่วนขยายนี้เป็นคอลัมน์และสร้างแผนผัง Merkle ของคอลัมน์ รากฐานของต้นแมร์เคิลคือความมุ่งมั่นของเรา
ตอนนี้ ให้เราสมมติว่าผู้พิสูจน์ต้องการพิสูจน์ ณ จุดใดจุดหนึ่งถึงการคำนวณของพหุนามนี้ r={r 0, r 1, r 2, r 3} มีความแตกต่างเล็กน้อยใน Binius ที่ทำให้แผนนี้อ่อนแอกว่าแผนการผูกมัดพหุนามอื่นๆ: ผู้พิสูจน์ไม่ควรรู้หรือไม่สามารถเดา s ได้ก่อนที่จะยอมรับรากของ Merkle (กล่าวอีกนัยหนึ่ง r ควรเป็นค่าหลอกเทียม) สิ่งนี้ทำให้รูปแบบไม่มีประโยชน์สำหรับ การค้นหาฐานข้อมูล (เช่น เอาล่ะ คุณให้ราก Merkle แก่ฉัน ตอนนี้แสดง P(0, 0, 1, 0) ให้ฉันดู! แต่โปรโตคอลการพิสูจน์ความรู้เป็นศูนย์ที่เราใช้จริง ๆ มักไม่ต้องการ การค้นหาฐานข้อมูล เพียงตรวจสอบพหุนามที่จุดประเมินแบบสุ่ม ดังนั้นข้อจำกัดนี้จึงตอบสนองวัตถุประสงค์ของเรา
สมมติว่าเราเลือก r={ 1, 2, 3, 4 } (ค่าพหุนามมีค่าเท่ากับ -137 คุณสามารถใช้โค้ดนี้เพื่อยืนยันได้) ตอนนี้เราเข้าสู่กระบวนการพิสูจน์แล้ว เราแบ่ง r ออกเป็นสองส่วน ส่วนแรก {1, 2} แสดงถึงผลรวมเชิงเส้นของคอลัมน์ภายในแถว และส่วนที่สอง {3, 4} แสดงถึงผลรวมเชิงเส้นของแถว เราคำนวณ ผลิตภัณฑ์เทนเซอร์ สำหรับส่วนคอลัมน์:
สำหรับส่วนของเส้น:
ซึ่งหมายความว่า: รายการของผลิตภัณฑ์ที่เป็นไปได้ทั้งหมดของค่าในแต่ละชุด ในกรณีแถวเราได้รับ:
[( 1-r 2)*( 1-r 3), ( 1-r 3), ( 1-r 2)*r 3, R 2*r 3 ]
ใช้ r={1, 2, 3, 4} (ดังนั้น r 2 = 3 และ r 3 = 4):
[( 1-3)*( 1-4), 3*( 1-4),( 1-3)* 4, 3* 4 ] = [ 6, -9 -8 -12 ]
ตอนนี้ เราคำนวณ แถว t ใหม่โดยหาผลรวมเชิงเส้นของแถวที่มีอยู่ นั่นคือเราใช้:
คุณสามารถนึกถึงสิ่งที่เกิดขึ้นที่นี่เป็นการประเมินเพียงบางส่วนได้ หากเราคูณผลคูณเมตริกซ์เต็มด้วยเวกเตอร์เต็มของค่าทั้งหมด คุณจะได้การคำนวณ P(1, 2, 3, 4) = -137 ที่นี่เราจะคูณผลิตภัณฑ์เทนเซอร์บางส่วนโดยใช้เพียงครึ่งหนึ่งของพิกัดที่ประเมิน และลดความซับซ้อนของตารางค่า N ให้เป็นแถวของค่า root-N หากคุณให้เส้นนี้แก่ผู้อื่น พวกเขาสามารถคำนวณส่วนที่เหลือได้โดยใช้ผลคูณเทนเซอร์ของอีกครึ่งหนึ่งของพิกัดที่ประเมิน
เครื่องพิสูจน์จะให้เครื่องยืนยันพร้อมหลักฐาน Merkle ของแถวใหม่ต่อไปนี้: t และคอลัมน์สุ่มตัวอย่างบางคอลัมน์ ในตัวอย่างของเรา เราจะให้ผู้พิสูจน์ระบุเฉพาะคอลัมน์สุดท้าย ในชีวิตจริง ผู้พิสูจน์จะต้องจัดเตรียมคอลัมน์หลายสิบคอลัมน์เพื่อให้เกิดความปลอดภัยที่เพียงพอ
ตอนนี้ เราใช้ประโยชน์จากความเป็นเส้นตรงของโค้ดรีด-โซโลมอน คุณสมบัติหลักที่เราใช้คือการหาผลรวมเชิงเส้นของส่วนขยายรีด-โซโลมอน ให้ผลลัพธ์เช่นเดียวกับการขยายรีด-โซโลมอนของผลรวมเชิงเส้น ความเป็นอิสระของคำสั่ง นี้มักจะเกิดขึ้นเมื่อการดำเนินการทั้งสองเป็นแบบเส้นตรง
ผู้ตรวจสอบทำสิ่งนี้ทุกประการ พวกเขาคำนวณ t และผลรวมเชิงเส้นของคอลัมน์เดียวกันกับที่ผู้พิสูจน์คำคำนวณก่อนหน้านี้ (แต่เฉพาะคอลัมน์ที่จัดทำโดยผู้พิสูจน์อักษร) และตรวจสอบว่าทั้งสองขั้นตอนให้คำตอบเดียวกัน
ในกรณีนี้ การขยาย t โดยคำนวณผลรวมเชิงเส้นเดียวกัน ([6,-9,-8, 12] ทั้งคู่ให้คำตอบเดียวกัน: -10746 นี่พิสูจน์ว่ารากของแมร์เคิลถูกสร้างขึ้นด้วย ค่าความนิยม (หรืออย่างน้อย ปิด เพียงพอ) และตรงกับ t: อย่างน้อยคอลัมน์ส่วนใหญ่ก็เข้ากันได้
แต่ผู้ตรวจสอบจำเป็นต้องตรวจสอบอีกสิ่งหนึ่ง: ตรวจสอบการประเมินพหุนาม {r 0 …r 3 } จนถึงขณะนี้ไม่มีขั้นตอนใดของผู้ตรวจสอบขึ้นอยู่กับมูลค่าที่ผู้พิสูจน์อ้างสิทธิ์ นี่คือวิธีที่เราตรวจสอบ เรานำผลิตภัณฑ์เทนเซอร์ของ ส่วนคอลัมน์ ที่เราระบุว่าเป็นจุดคำนวณ:
ในตัวอย่างของเรา โดยที่ r={ 1, 2, 3, 4 } ดังนั้นครึ่งหนึ่งของคอลัมน์ที่เลือกคือ { 1, 2 }) ซึ่งเท่ากับ:
ตอนนี้เราใช้ผลรวมเชิงเส้นนี้ t:
นี่เป็นผลลัพธ์เดียวกับการแก้พหุนามโดยตรง
ข้อมูลข้างต้นใกล้เคียงกับคำอธิบายที่สมบูรณ์ของโปรโตคอล Binius แบบง่าย มาก สิ่งนี้มีข้อดีที่น่าสนใจอยู่แล้ว เช่น เนื่องจากข้อมูลถูกแบ่งออกเป็นแถวและคอลัมน์ คุณจึงต้องการเพียงฟิลด์เดียวที่มีขนาดเพียงครึ่งหนึ่ง อย่างไรก็ตาม สิ่งนี้ไม่ได้ตระหนักถึงคุณประโยชน์ของการคำนวณแบบไบนารี่อย่างเต็มที่ สำหรับสิ่งนี้ เราจำเป็นต้องมีโปรโตคอล Binius ที่สมบูรณ์ แต่ก่อนอื่น เรามาดูรายละเอียดเกี่ยวกับเขตข้อมูลไบนารี่กันก่อน
สนามไบนารี
โดเมนที่เล็กที่สุดเท่าที่จะเป็นไปได้คือเลขคณิตโมดูโล 2 ซึ่งเล็กมากจนเราสามารถเขียนตารางการบวกและสูตรคูณได้:
เราสามารถได้รับเขตข้อมูลไบนารีที่ใหญ่ขึ้นโดยการขยาย: ถ้าเราเริ่มจาก F 2 (จำนวนเต็มโมดูโล 2) แล้วกำหนด x โดยที่ x กำลังสอง = x + 1 เราจะได้ตารางการบวกและสูตรคูณต่อไปนี้:
ปรากฎว่าเราสามารถปรับขนาดสนามไบนารี่ให้ใหญ่ขึ้นได้โดยพลการโดยทำซ้ำโครงสร้างนี้ ต่างจากจำนวนเชิงซ้อนมากกว่าจำนวนจริง ซึ่งคุณสามารถเพิ่มองค์ประกอบใหม่ได้ แต่ไม่มีองค์ประกอบใดอีกแล้ว I (ควอเทอร์เนียนมีอยู่จริง แต่มีความแปลกทางคณิตศาสตร์ เช่น ab ไม่เท่ากับ ba) ใช้ช่องจำกัด คุณสามารถเพิ่มใหม่ได้เสมอ ส่วนขยาย โดยเฉพาะเรากำหนดองค์ประกอบดังนี้:
ฯลฯ....... สิ่งนี้มักเรียกว่าโครงสร้างหอคอยเพราะแต่ละส่วนขยายที่ต่อเนื่องกันสามารถมองเห็นได้ว่าเป็นการเพิ่มเลเยอร์ใหม่ให้กับหอคอย นี่ไม่ใช่วิธีเดียวที่จะสร้างเขตข้อมูลไบนารี่ที่มีขนาดตามใจชอบ แต่ก็มีข้อดีเฉพาะบางประการที่ Binius ใช้ประโยชน์
เราสามารถแสดงตัวเลขเหล่านี้เป็นรายการบิตได้ ตัวอย่างเช่น 1100101010001111 หลักแรกแทนผลคูณของ 1 หลักที่สองแทนผลคูณของ x 0 จากนั้นหลักที่ตามมาแทนผลคูณของตัวเลข x 1 ต่อไปนี้: x 1, x 1*x 0, x 2, x 2*x 0 และ เร็วๆ นี้. การเข้ารหัสนี้ดีเพราะคุณสามารถแยกย่อยได้:
นี่เป็นสัญลักษณ์ที่ค่อนข้างไม่ธรรมดา แต่ฉันชอบแสดงองค์ประกอบสนามไบนารี่เป็นจำนวนเต็ม โดยมีบิตที่มีประสิทธิภาพมากกว่าอยู่ทางด้านขวา นั่นคือ 1 = 1, x 0 = 01 = 2, 1+x 0 = 11 = 3, 1+x 0+x 2 = 11001000 = 19 และอื่นๆ ในนิพจน์นี้คือ 61779
การบวกในฟิลด์ไบนารีเป็นเพียง XOR (และการลบก็เช่นกัน) โปรดทราบว่านี่หมายถึง x+x= 0 สำหรับ x ใดๆ ในการคูณสององค์ประกอบ x*y มีอัลกอริธึมการเรียกซ้ำที่ง่ายมาก: แบ่งแต่ละตัวเลขออกครึ่งหนึ่ง:
จากนั้นแยกการคูณ:
ส่วนสุดท้ายเป็นส่วนเดียวที่ยุ่งยากเล็กน้อย เนื่องจากคุณต้องใช้กฎการทำให้เข้าใจง่าย มีวิธีคูณที่มีประสิทธิภาพมากกว่า คล้ายกับอัลกอริธึมของคารัตสึบะและการแปลงฟูเรียร์แบบเร็ว แต่ผมจะทิ้งเอาไว้เป็นแบบฝึกหัดให้ผู้อ่านที่สนใจได้คิดหาคำตอบ
การหารในฟิลด์ไบนารีทำได้โดยการรวมการคูณและการผกผัน วิธีการกลับตัวที่ เรียบง่ายแต่ช้า เป็นการประยุกต์ใช้ทฤษฎีบทเล็กๆ ของแฟร์มาต์ทั่วไป นอกจากนี้ยังมีอัลกอริธึมการผกผันที่ซับซ้อนกว่าแต่มีประสิทธิภาพมากกว่าที่คุณสามารถหาได้ที่นี่ คุณสามารถใช้โค้ดที่นี่เพื่อเล่นกับการบวก การคูณ และการหารของเขตข้อมูลไบนารี่
ซ้าย: ตารางเพิ่มเติมสำหรับองค์ประกอบช่องไบนารี่สี่หลัก (เช่น ประกอบด้วย 1, x 0, x 1, x 0x 1 เท่านั้น) ขวา: ตารางสูตรคูณสำหรับองค์ประกอบเขตข้อมูลไบนารีสี่หลัก
ความงดงามของสนามไบนารี่ประเภทนี้คือการที่รวมส่วนที่ดีที่สุดของจำนวนเต็ม ปกติ และเลขคณิตแบบโมดูโลเข้าด้วยกัน เช่นเดียวกับจำนวนเต็มปกติ องค์ประกอบเขตข้อมูลไบนารี่ไม่มีขอบเขต คุณสามารถขยายได้ตามต้องการ แต่เช่นเดียวกับเลขคณิตแบบโมดูโล หากคุณดำเนินการกับค่าภายในขีดจำกัดขนาดที่กำหนด ผลลัพธ์ทั้งหมดของคุณก็จะยังอยู่ในช่วงเดียวกัน ตัวอย่างเช่น หากคุณใช้พลังติดต่อกัน 42 แต้ม คุณจะได้รับ:
หลังจากผ่านไป 255 ก้าว คุณจะกลับมาที่ 42 ยกกำลัง 255 = 1 เช่นเดียวกับจำนวนเต็มบวกและเลขคณิตแบบแยกส่วน พวกมันเป็นไปตามกฎทางคณิตศาสตร์ทั่วไป: a*b=b*a, a*(b+c)=a * b+a*c มีกฎหมายใหม่ๆ แปลกๆ ด้วยซ้ำ
สุดท้ายนี้ ฟิลด์ไบนารีทำให้ง่ายต่อการจัดการบิต หากคุณคำนวณด้วยตัวเลขที่พอดีกับ 2 k บิต ผลลัพธ์ทั้งหมดของคุณก็จะพอดีกับ 2 k บิตด้วย สิ่งนี้จะหลีกเลี่ยงความลำบากใจ ใน EIP-4844 ของ Ethereum แต่ละ บล็อก ของ Blob จะต้องเป็นโมดูลดิจิทัล 52435875175126190479447740508185965837690552500527637822603658699938581184513 ดังนั้นการเข้ารหัสข้อมูลไบนารีจะต้องทิ้งพื้นที่บางส่วนและทำการตรวจสอบเพิ่มเติม เพื่อให้แน่ใจว่าแต่ละองค์ประกอบเก็บค่าน้อยกว่า 2 ยกกำลัง 248 . นอกจากนี้ยังหมายความว่าการดำเนินการภาคสนามแบบไบนารีนั้นรวดเร็วเป็นพิเศษบนคอมพิวเตอร์ ทั้ง CPU และการออกแบบ FPGA และ ASIC ที่เหมาะสมตามหลักทฤษฎี
ทั้งหมดนี้หมายความว่าเราสามารถทำบางอย่างเช่นการเข้ารหัสรีด-โซโลมอนที่เราทำข้างต้น ในลักษณะที่หลีกเลี่ยงการ ระเบิด ของจำนวนเต็มโดยสิ้นเชิง ดังที่เราเห็นในตัวอย่างของเรา และในลักษณะ ระเบิด อย่างมาก Native ซึ่งเป็นคอมพิวเตอร์ประเภทหนึ่งที่คอมพิวเตอร์เชี่ยวชาญ คุณลักษณะ แยก ของเขตข้อมูลไบนารี - วิธีที่เราทำ 1100101010001111 = 11001010+ 10001111*x 3 แล้วแยกตามความต้องการของเราก็เป็นสิ่งสำคัญเช่นกันเพื่อให้บรรลุความยืดหยุ่นอย่างมาก
ทำบิเนียสให้สมบูรณ์
ดู ที่นี่ สำหรับการใช้หลามของโปรโตคอลนี้
ตอนนี้เราสามารถย้ายไปยัง Full Binius ซึ่งปรับ Simple Binius เป็น (i) ทำงานกับเขตข้อมูลไบนารี่และ (ii) ให้เราส่งบิตเดียว โปรโตคอลนี้เข้าใจยากเพราะมันสลับไปมาระหว่างวิธีต่างๆ ในการดูเมทริกซ์บิต แน่นอนว่าฉันใช้เวลาทำความเข้าใจนานกว่าปกติในการทำความเข้าใจโปรโตคอลการเข้ารหัส แต่เมื่อคุณเข้าใจเขตข้อมูลไบนารีแล้ว ข่าวดีก็คือว่า คณิตศาสตร์ที่ยากกว่า ที่ Binius อาศัยนั้นไม่มีอยู่จริง นี่ไม่ใช่การจับคู่เส้นโค้งวงรี ซึ่งมีรูกระต่ายเรขาคณิตพีชคณิตที่ลึกกว่าเดิมให้เจาะ ตรงนี้ คุณแค่ต้องมีช่องไบนารี่
มาดูแผนภูมิแบบเต็มอีกครั้ง:
ถึงตอนนี้ คุณน่าจะคุ้นเคยกับส่วนประกอบส่วนใหญ่แล้ว แนวคิดในการ ทำให้ไฮเปอร์คิวบ์แบน ลงในตาราง แนวคิดในการคำนวณการรวมแถวและการรวมคอลัมน์เป็นผลิตภัณฑ์เทนเซอร์ของจุดประเมิน และการทดสอบ การขยายรีด-โซโลมอน แล้วคำนวณการรวมแถว และ การคำนวณการรวมแถว แล้วรีด- แนวคิดเรื่องความเท่าเทียมกันระหว่างส่วนขยายของโซโลมอนถูกนำไปใช้ใน Binius แบบง่าย
มีอะไรใหม่ใน Complete Binius? โดยพื้นฐานแล้วสามสิ่ง:
แต่ละค่าในไฮเปอร์คิวบ์และสี่เหลี่ยมต้องเป็นบิต (0 หรือ 1)
กระบวนการขยายจะขยายบิตออกเป็นบิตมากขึ้นโดยการจัดกลุ่มออกเป็นคอลัมน์และสมมติว่าเป็นองค์ประกอบฟิลด์ที่ใหญ่กว่าชั่วคราว
หลังจากขั้นตอนการรวมแถว จะมีขั้นตอน แยกย่อยเป็นบิต ตามองค์ประกอบซึ่งจะแปลงการขยายกลับเป็นบิต
เราจะหารือทั้งสองกรณีตามลำดับ ประการแรก กระบวนการขยายใหม่ รหัส Reed-Solomon มีข้อจำกัดพื้นฐาน หากคุณต้องการขยาย n ถึง k*n คุณต้องทำงานในฟิลด์ที่มีค่าต่างกัน k*n ซึ่งสามารถใช้เป็นพิกัดได้ ด้วย F 2 (หรืออีกนัยหนึ่ง) คุณไม่สามารถทำเช่นนั้นได้ สิ่งที่เราทำคือ รวม องค์ประกอบของ F 2 ที่อยู่ติดกันเข้าด้วยกันเพื่อสร้างค่าที่มากขึ้น ในตัวอย่างนี้ เราบรรจุครั้งละสองบิตลงในองค์ประกอบ { 0 , 1 , 2 , 3 } ซึ่งเพียงพอสำหรับเราเนื่องจากส่วนขยายของเรามีจุดคำนวณเพียงสี่จุดเท่านั้น ในการพิสูจน์ ของจริง เราอาจส่งคืนครั้งละ 16 บิต จากนั้นเราจะรันโค้ด Reed-Solomon กับค่าที่แพ็กเหล่านี้แล้วแตกออกเป็นบิตอีกครั้ง
ตอนนี้การรวมแถว เพื่อให้การตรวจสอบ ประเมินที่จุดสุ่ม มีความปลอดภัยในการเข้ารหัส เราจำเป็นต้องสุ่มตัวอย่างจุดจากพื้นที่ที่ค่อนข้างใหญ่ (ใหญ่กว่าไฮเปอร์คิวบ์มาก) ดังนั้นในขณะที่จุดภายในไฮเปอร์คิวบ์เป็นบิต ค่าที่คำนวณได้ภายนอกไฮเปอร์คิวบ์จะมีขนาดใหญ่กว่ามาก ในตัวอย่างข้างต้น ชุดค่าผสมแถว จะกลายเป็น [11, 4, 6, 1]
สิ่งนี้ทำให้เกิดคำถาม: เรารู้วิธีรวมบิตให้เป็นค่าที่มากขึ้น จากนั้นจึงทำส่วนขยาย Reed-Solomon นอกเหนือจากนั้น แต่เราจะทำสิ่งเดียวกันสำหรับคู่ที่มีมูลค่ามากกว่าได้อย่างไร
เคล็ดลับของ Binius คือการทำงานเป็นบิต: เราดูที่บิตเดียวของแต่ละค่า (เช่น สำหรับสิ่งที่เราเรียกว่า 11 นั่นคือ [1, 1, 0, 1]) แล้วจึงขยายตามแถว ดำเนินการกระบวนการขยายบนออบเจ็กต์ นั่นคือเราทำกระบวนการขยายในแถวที่ 1 ของแต่ละองค์ประกอบจากนั้นในแถว x 0 จากนั้นในแถว x 1 จากนั้นในแถว x 0x 1 และอื่น ๆ (ในของเล่นของเรา ตัวอย่างที่เราหยุดอยู่ตรงนั้น แต่ในการใช้งานจริงเราจะถึง 128 บรรทัด (อันสุดท้ายคือ x 6*…*x 0))
ทบทวน:
เราแปลงบิตในไฮเปอร์คิวบ์ให้เป็นตาราง
จากนั้นเราจะถือว่ากลุ่มบิตที่อยู่ติดกันในแต่ละแถวเป็นองค์ประกอบของฟิลด์ที่ใหญ่กว่า และดำเนินการทางคณิตศาสตร์กับพวกมันเพื่อให้ Reed-Solomon ขยายแถว
จากนั้นเราจะนำการรวมแถวของบิตสำหรับแต่ละคอลัมน์และรับคอลัมน์บิตสำหรับแต่ละแถวเป็นเอาต์พุต (เล็กกว่ามากสำหรับกำลังสองที่มีขนาดใหญ่กว่า 4 x 4)
จากนั้น เราจะดูเอาต์พุตเป็นเมทริกซ์ และบิตของมันคือแถว
ทำไมจึงเป็นเช่นนี้? ในคณิตศาสตร์ ทั่วไป หากคุณเริ่มแบ่งตัวเลขออกเป็นบิต ความสามารถ (โดยปกติ) ดำเนินการเชิงเส้นในลำดับใดๆ ก็ได้และได้ผลลัพธ์เดียวกันจะพังทลายลง ตัวอย่างเช่น ถ้าฉันเริ่มต้นด้วยตัวเลข 345 แล้วคูณด้วย 8 แล้วคูณด้วย 3 ฉันจะได้ 8280 ถ้าฉันย้อนกลับการดำเนินการทั้งสองนี้ ฉันจะได้ 8280 ด้วย แต่หากฉันแทรกการดำเนินการ แยกทีละบิต ระหว่างสองขั้นตอน มันจะพัง: ถ้าคุณทำ 8x และ 3x คุณจะได้รับ:
แต่ถ้าคุณทำ 3 ครั้ง และ 8 ครั้ง คุณจะได้:
แต่ในสนามไบนารี่ที่สร้างด้วยโครงสร้างหอคอย วิธีการนี้ใช้ได้ผล เหตุผลอยู่ที่ความสามารถในการแยกออกจากกัน: หากคุณคูณค่าที่มากด้วยค่าที่น้อย สิ่งที่เกิดขึ้นในแต่ละส่วนจะยังคงอยู่ในแต่ละส่วน ถ้าเราคูณ 1100101010001111 ด้วย 11 ก็จะเหมือนกับการสลายตัวครั้งแรกของ 1100101010001111 ซึ่งก็คือ
จากนั้นคูณแต่ละส่วนประกอบด้วย 11 เดียวกัน
รวบรวมไว้ด้วยกัน
โดยทั่วไป ระบบพิสูจน์ความรู้เป็นศูนย์ทำงานโดยสร้างข้อความเกี่ยวกับพหุนามในขณะเดียวกันก็แสดงข้อความเกี่ยวกับการประเมินที่สำคัญไปพร้อมๆ กัน ดังที่เราเห็นในตัวอย่าง Fibonacci F(X+ 2)-F(X+ 1)-F(X) = Z( X)*H(X) ตรวจสอบทุกขั้นตอนของการคำนวณ Fibonacci พร้อมกัน เราตรวจสอบข้อความเกี่ยวกับพหุนามโดยการพิสูจน์การประเมินที่จุดสุ่ม การตรวจสอบจุดสุ่มนี้แสดงถึงการตรวจสอบพหุนามทั้งหมด: หากสมการพหุนามไม่ตรงกัน ก็มีโอกาสเล็กน้อยที่สมการนั้นจะตรงกันที่พิกัดสุ่มเฉพาะ
ในทางปฏิบัติ สาเหตุหลักประการหนึ่งของความไร้ประสิทธิภาพคือในโปรแกรมจริง ตัวเลขส่วนใหญ่ที่เราจัดการมีขนาดเล็ก: ดัชนีใน for loops ค่า True/False ตัวนับ และสิ่งที่คล้ายกัน อย่างไรก็ตาม เมื่อเราใช้การเข้ารหัสรีด-โซโลมอนเพื่อ ขยาย ข้อมูลเพื่อให้เกิดความซ้ำซ้อนที่จำเป็นในการทำให้การตรวจสอบแบบพิสูจน์อักษรของ Merkle มีความปลอดภัย ค่า พิเศษ ส่วนใหญ่จะกินพื้นที่ทั้งหมดของฟิลด์ แม้กระทั่ง หากค่าเดิมมีน้อย
เพื่อแก้ไขปัญหานี้ เราต้องการทำให้ฟิลด์นี้มีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้ Plonky 2 นำเราจากตัวเลข 256 บิตลงมาเป็นตัวเลข 64 บิต จากนั้น Plonky 3 ก็ลดตัวเลขลงไปอีกเป็นตัวเลข 31 บิต แต่ถึงกระนั้นนี่ก็ไม่เหมาะสมที่สุด การใช้เขตข้อมูลไบนารีเราสามารถจัดการกับบิตเดี่ยวได้ สิ่งนี้ทำให้การเข้ารหัส หนาแน่น: หากข้อมูลที่แท้จริงของคุณมี n บิต การเข้ารหัสของคุณจะเป็น n บิต และส่วนขยายจะเป็น 8 * n บิต โดยไม่มีค่าใช้จ่ายเพิ่มเติม
ตอนนี้เรามาดูแผนภูมินี้เป็นครั้งที่สาม:
ใน Binius เราทำงานกับพหุนามหลายเส้น: ไฮเปอร์คิวบ์ P(x 0, x 1,…xk) โดยที่การประเมินแต่ละรายการ P( 0, 0, 0, 0), P( 0, 0, 0, 1 ) จนถึง P (1, 1, 1, 1) บันทึกข้อมูลที่เราสนใจ เพื่อสาธิตการคำนวณ ณ จุดใดจุดหนึ่ง เราจะ ตีความ ข้อมูลเดิมใหม่เป็นสี่เหลี่ยมจัตุรัส จากนั้นเราจะขยายแต่ละแถวโดยใช้การเข้ารหัส Reed-Solomon เพื่อให้ข้อมูลซ้ำซ้อนที่จำเป็นสำหรับการรักษาความปลอดภัยของการสืบค้นสาขา Merkle แบบสุ่ม จากนั้นเราคำนวณชุดค่าผสมเชิงเส้นแบบสุ่มของแถว โดยออกแบบค่าสัมประสิทธิ์เพื่อให้แถวที่รวมใหม่มีค่าที่คำนวณได้ที่เราสนใจจริงๆ แถวที่สร้างขึ้นใหม่นี้ (ตีความใหม่เป็น 128 แถวของบิต) และคอลัมน์ที่เลือกแบบสุ่มบางคอลัมน์ที่มีสาขา Merkle จะถูกส่งผ่านไปยังเครื่องมือตรวจสอบ
จากนั้นเครื่องมือตรวจสอบความถูกต้องจะดำเนินการ ชุดค่าผสมแถวที่ขยาย (หรือถ้าให้เจาะจงกว่านั้นคือชุดค่าผสมของแถวที่ขยาย) และ ชุดค่าผสมของแถวที่ขยาย และตรวจสอบว่าทั้งสองตรงกัน จากนั้นคำนวณการรวมคอลัมน์และตรวจสอบว่าส่งคืนค่าที่ผู้พิสูจน์อ้างสิทธิ์หรือไม่ นี่คือระบบพิสูจน์ของเรา (หรือค่อนข้างจะเป็นโครงการข้อผูกพันพหุนามซึ่งเป็นองค์ประกอบสำคัญของระบบพิสูจน์)
สิ่งที่เรายังไม่ได้ครอบคลุมยัง?
อัลกอริธึมที่มีประสิทธิภาพในการขยายแถว ซึ่งจำเป็นในการปรับปรุงประสิทธิภาพการคำนวณของเครื่องมือตรวจสอบความถูกต้อง เราใช้การแปลงฟูเรียร์แบบเร็วบนฟิลด์ไบนารี ตามที่อธิบายไว้ที่นี่ (แม้ว่าการใช้งานที่แน่นอนจะแตกต่างกันไป เนื่องจากโพสต์นี้ใช้โครงสร้างที่มีประสิทธิภาพน้อยกว่าซึ่งไม่ได้ขึ้นอยู่กับการขยายแบบเรียกซ้ำ)
เลขคณิต พหุนามตัวแปรเดียวมีความสะดวกเนื่องจากคุณสามารถทำสิ่งต่างๆ เช่น F(X+ 2)-F(X+ 1)-F(X) = Z(X)*H(X) เพื่อเชื่อมโยงขั้นตอนที่อยู่ติดกันในการคำนวณ ในไฮเปอร์คิวบ์ ขั้นตอนต่อไป สามารถตีความได้น้อยกว่า X+1 มาก คุณสามารถทำ X+k พลังของ k ได้ แต่พฤติกรรมการกระโดดนี้จะเสียสละข้อดีที่สำคัญหลายประการของ Binius วิธีแก้ปัญหานี้แสดงอยู่ในรายงานของ Binius ดูหัวข้อ 4.3) แต่นี่เป็นโพรงกระต่ายที่ลึกในตัวเอง
วิธีตรวจสอบค่าเฉพาะอย่างปลอดภัย ตัวอย่าง Fibonacci จำเป็นต้องตรวจสอบเงื่อนไขขอบเขตหลัก: F(0)=F(1)=1 และค่าของ F(100) แต่ด้วย Binius ดิบ การตรวจสอบจุดคำนวณที่ทราบจึงไม่ปลอดภัย มีวิธีที่ค่อนข้างง่ายในการแปลงเช็คการคำนวณที่รู้จักไปเป็นเช็คการคำนวณที่ไม่รู้จัก โดยใช้สิ่งที่เรียกว่าโปรโตคอลการตรวจสอบผลรวม แต่เราจะไม่ครอบคลุมถึงวิธีเหล่านั้นในที่นี้
โปรโตคอลการค้นหาซึ่งเป็นอีกเทคนิคหนึ่งที่ใช้กันอย่างแพร่หลายเมื่อเร็ว ๆ นี้ ถูกนำมาใช้เพื่อสร้างระบบพิสูจน์อักษรที่มีประสิทธิภาพสูง Binius สามารถใช้ร่วมกับโปรโตคอลการค้นหาแอปพลิเคชันต่างๆ ได้
เกินเวลาการตรวจสอบรากที่สอง รากที่สองมีราคาแพง: การพิสูจน์ Binius ของ Bit ที่เป็น 2 ยกกำลัง 32 มีความยาวประมาณ 11 MB คุณสามารถชดเชยปัญหานี้ได้โดยใช้ระบบการพิสูจน์อื่นๆ เพื่อสร้าง การพิสูจน์การพิสูจน์ Binius ซึ่งจะทำให้ได้รับประสิทธิภาพของการพิสูจน์ Binius และขนาดการพิสูจน์ที่เล็กลง อีกทางเลือกหนึ่งคือโปรโตคอล FRI-binius ที่ซับซ้อนกว่า ซึ่งสร้างการพิสูจน์ที่มีขนาดพหุลอการิทึม (เช่นเดียวกับ FRI ทั่วไป)
Binius ส่งผลต่อ ความเป็นมิตรของ SNARK อย่างไร บทสรุปพื้นฐานคือ หากคุณใช้ Binius คุณไม่จำเป็นต้องกังวลเกี่ยวกับการคำนวณ เป็นมิตรกับเลขคณิต อีกต่อไป: การแฮชแบบ ปกติ จะไม่มีประสิทธิภาพมากกว่าการแฮชทางคณิตศาสตร์แบบเดิมอีกต่อไป การคูณโมดูโล 2 ยกกำลัง 32 หรือโมดูโล 2 256 ไม่ปวดหัวอีกต่อไปเมื่อเทียบกับโมดูลัสการคูณและอื่นๆ แต่นี่เป็นหัวข้อที่ซับซ้อน มีหลายสิ่งหลายอย่างเปลี่ยนไปเมื่อทุกอย่างเสร็จสิ้นในรูปแบบไบนารี
ฉันหวังว่าจะมีการปรับปรุงเพิ่มเติมสำหรับเทคนิคการพิสูจน์ภาคสนามแบบไบนารีในอีกไม่กี่เดือนข้างหน้า
