Vitalik: Binius การพิสูจน์ประสิทธิภาพสำหรับเขตข้อมูลไบนารี

บทความต้นฉบับโดย: 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 บิต) เนื่องจากประสิทธิภาพเหล่านี้กAIns, 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 และคำนวณองค์ประกอบนั้น: (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+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, 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 จะไม่ตรวจสอบ และ R1CS ก็เช่นกัน แต่การตรวจสอบที่มีประสิทธิภาพมากที่สุดหลายๆ รายการก็ทำเช่นนั้น เนื่องจากเป็นการง่ายกว่าที่จะลดค่าใช้จ่ายให้เหลือน้อยที่สุดโดยดำเนินการตรวจสอบเดียวกัน (หรือตรวจสอบสองสามครั้งเหมือนกัน) หลายๆ ครั้ง

Plonky 2: จาก SNARK และ STARK 256 บิต ไปจนถึง 64 บิต... มีเพียง STARK เท่านั้น

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

STARK ทำงานโดยถือว่าข้อมูลเป็นแบบพหุนาม คำนวณการคำนวณของพหุนามนั้น และใช้ราก Merkle ของข้อมูลที่ขยายเป็น "ความมุ่งมั่นแบบพหุนาม"

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

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

การขยายตัวของรีด-โซโลมอนของการประเมินพหุนามบางส่วน แม้ว่าค่าเดิมจะมีน้อย ค่าเพิ่มเติมจะถูกขยายจนเต็มขนาดฟิลด์ (ในกรณีนี้ 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. ผู้โจมตีสามารถปลอมแปลงหลักฐานสองพันล้านครั้งจนกว่าจะโชคดี

เพื่อป้องกันสิ่งนี้ เราสุ่มตัวอย่าง 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 ถูกเลือกไม่เพียงเพราะมันพอดีกับขอบเขตเหล่านั้น แต่ยังเพราะมันเข้ากันได้ดีภายในขอบเขตเหล่านั้นด้วย: การคูณแบบโมดูโล 2^64 – 2^32 + 1 สามารถทำได้โดยการคูณแบบ 32 บิตปกติ และเลื่อนระดับบิตและคัดลอกเอาต์พุตในบางแห่ง บทความนี้จะอธิบายเทคนิคบางอย่างอย่างดี

อย่างไรก็ตาม วิธีที่ดีกว่ามากคือการคำนวณโดยตรงในรูปแบบไบนารี จะเกิดอะไรขึ้นถ้าการบวกอาจเป็นเพียง 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 คือการใช้คิวบ์ที่มีมิติสูงกว่า โดยจัดเก็บหนึ่งหมายเลขต่อกลุ่ม เช่น 16 บิต สิ่งนี้ต้องใช้ความฉลาดบางประการในการบวกจำนวนเต็มเพียงเล็กน้อย แต่สำหรับ Binius มันไม่ยากเกินไป

ตอนนี้เรามาดูรหัสการลบ วิธีการทำงานของ STARK คือคุณรับค่า n ค่า รีด-โซโลมอนจะขยายค่าเหล่านั้นเป็นค่าที่มากขึ้น (ปกติจะเป็น 8n ซึ่งโดยปกติจะอยู่ระหว่าง 2n ถึง 32n) จากนั้นสุ่มเลือกสาขา Merkle บางสาขาจากส่วนขยาย และทำการตรวจสอบบางอย่างกับค่าเหล่านั้น ไฮเปอร์คิวบ์มีความยาว 2 ในแต่ละมิติ ดังนั้นจึงไม่เหมาะสมที่จะขยายโดยตรง: ไม่มีพื้นที่เพียงพอที่จะสุ่มตัวอย่างสาขา Merkle จาก 16 ค่า แล้วเราจะทำอย่างไร? สมมติว่าไฮเปอร์คิวบ์เป็นสี่เหลี่ยมจัตุรัส!

Simple Binius – ตัวอย่าง

ดู ที่นี่ สำหรับการนำโปรโตคอลไปใช้หลาม

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

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

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

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

ต่อไป เราจะถือว่าส่วนขยายนี้เป็นคอลัมน์และสร้างแผนผัง Merkle ของคอลัมน์ รากฐานของต้น 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 เหลือแถวเดียวของค่ารากที่สองของค่า N หากคุณให้แถวนี้แก่ผู้อื่น พวกเขาสามารถคำนวณส่วนที่เหลือได้โดยใช้ผลคูณเทนเซอร์ของอีกครึ่งหนึ่งของพิกัดการประเมิน

เครื่องพิสูจน์จัดเตรียมแถวใหม่ต่อไปนี้ให้ผู้ตรวจสอบ: t และการพิสูจน์ Merkle ของคอลัมน์สุ่มตัวอย่างบางคอลัมน์ ในตัวอย่างภาพประกอบของเรา เราจะให้สุภาษิตระบุเฉพาะคอลัมน์สุดท้ายเท่านั้น ในชีวิตจริง ผู้พิสูจน์จะต้องจัดเตรียมคอลัมน์หลายสิบคอลัมน์เพื่อให้เกิดความปลอดภัยที่เพียงพอ

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

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

ในกรณีนี้ เราขยาย t และคำนวณผลรวมเชิงเส้นเดียวกัน ([6,-9,-8, 12]) ซึ่งทั้งคู่ให้คำตอบเดียวกัน: -10746 นี่เป็นการพิสูจน์ว่ารากของ Merkle ถูกสร้างขึ้นโดยสุจริต (หรืออย่างน้อยก็ใกล้เคียงเพียงพอ) และตรงกับ 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 บิตที่สองแทนค่าทวีคูณของ x0 จากนั้นบิตต่อไปนี้แทนค่าทวีคูณของ x1: x1, x1*x0, x2, x2*x0 และอื่นๆ การเข้ารหัสนี้ดีเพราะคุณสามารถแยกย่อยได้:

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

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

จากนั้นแยกการคูณ:

ส่วนสุดท้ายเป็นส่วนเดียวที่ยุ่งยากเล็กน้อย เนื่องจากคุณต้องใช้กฎการทำให้เข้าใจง่าย มีวิธีที่มีประสิทธิภาพมากกว่าในการคูณ คล้ายกับอัลกอริธึม Karatsubas และ Fast Fourier Transforms แต่ฉันจะปล่อยให้เป็นแบบฝึกหัดให้ผู้อ่านที่สนใจได้คิดออก

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

ซ้าย: ตารางเพิ่มเติมสำหรับองค์ประกอบฟิลด์ไบนารีสี่บิต (เช่น เพียง 1, x 0, x 1, x 0x 1) ขวา: ตารางสูตรคูณสำหรับองค์ประกอบฟิลด์ไบนารีสี่บิต

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

หลังจากผ่านไป 255 ก้าว คุณจะกลับมาที่ 42 ยกกำลัง 255 = 1 และเช่นเดียวกับจำนวนเต็มบวกและการดำเนินการแบบแยกส่วน พวกมันจะเป็นไปตามกฎทางคณิตศาสตร์ตามปกติ: a*b=b*a, a*(b+c)= a*b+a*c และแม้แต่กฎหมายใหม่ๆ แปลกๆ บ้าง

สุดท้ายนี้ เขตข้อมูลไบนารี่สะดวกสำหรับการจัดการบิต: ถ้าคุณคำนวณด้วยตัวเลขที่พอดีใน 2k ผลลัพธ์ทั้งหมดของคุณก็จะพอดีกับ 2,000 บิตเช่นกัน สิ่งนี้จะหลีกเลี่ยงความอึดอัดใจ ใน Ethereums EIP-4844 แต่ละบล็อกของ Blob ต้องเป็นตัวเลขแบบโมดูโล 52435875175126190479447740508185965837690552500527637822603658699938581184513 ดังนั้นการเข้ารหัสข้อมูลไบนารีจึงต้องทิ้งพื้นที่บางส่วนและทำการตรวจสอบเพิ่มเติมที่ ชั้นแอปพลิเคชันเพื่อให้แน่ใจว่าค่าที่เก็บไว้ในแต่ละองค์ประกอบจะน้อยกว่า 2248 นี้ ยังหมายความว่าการดำเนินการภาคสนามแบบไบนารีนั้นรวดเร็วเป็นพิเศษบนคอมพิวเตอร์ ทั้ง CPU และการออกแบบ FPGA และ ASIC ที่เหมาะสมตามหลักทฤษฎี

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

ทำบิเนียสให้สมบูรณ์

ดู ที่นี่ สำหรับการนำโปรโตคอลไปใช้หลาม

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

มาดูแผนภูมิฉบับเต็มอีกครั้ง:

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

มีอะไรใหม่ใน Complete Binius? โดยพื้นฐานแล้วสามสิ่ง:

• แต่ละค่าในไฮเปอร์คิวบ์และสี่เหลี่ยมต้องเป็นบิต (0 หรือ 1)

• กระบวนการขยายจะขยายบิตออกเป็นบิตมากขึ้นโดยการจัดกลุ่มออกเป็นคอลัมน์และสมมติว่าเป็นองค์ประกอบของฟิลด์ที่ใหญ่กว่าชั่วคราว

• หลังจากขั้นตอนการรวมแถว จะมีการแบ่งแยกองค์ประกอบเป็นขั้นตอนบิตซึ่งจะแปลงการขยายกลับเป็นบิต

ค่อยหารือกันทั้งสองกรณีตามลำดับ ขั้นแรกให้ขยายขั้นตอนใหม่ รหัสรีด-โซโลมอนมีข้อจำกัดพื้นฐาน หากคุณต้องการขยาย 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 แถวของแต่ละองค์ประกอบ จากนั้นในแถว x0 จากนั้นในแถว x1 จากนั้นในแถว x0x1 และอื่น ๆ (ในตัวอย่างของเล่นของเรา เราหยุดอยู่แค่นั้น แต่ในความเป็นจริง นำไปปฏิบัติสูงสุด 128 แถว (อันสุดท้ายคือ x6*…*x0))

ทบทวน:

• เราแปลงบิตในไฮเปอร์คิวบ์ให้เป็นตาราง

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

• จากนั้นเราจะนำการรวมแถวของแต่ละคอลัมน์ของบิตและรับคอลัมน์ของบิตสำหรับแต่ละแถวเป็นเอาต์พุต (เล็กกว่ามากสำหรับสี่เหลี่ยมที่มีขนาดใหญ่กว่า 4 x 4)

• จากนั้นเราพิจารณาเอาต์พุตเป็นเมทริกซ์และบิตของมันคือแถว

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

แต่ถ้าคุณทำ 3x แล้วก็ 8x คุณจะได้:

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

จากนั้นคูณแต่ละองค์ประกอบด้วย 11

วางมันทั้งหมดเข้าด้วยกัน

โดยทั่วไป ระบบพิสูจน์ความรู้เป็นศูนย์ทำงานโดยสร้างข้อความเกี่ยวกับพหุนามที่แสดงถึงข้อความเกี่ยวกับการประเมินที่สำคัญในเวลาเดียวกัน: เช่นเดียวกับที่เราเห็นในตัวอย่างฟีโบนักชี F(X+ 2)-F(X+ 1)-F( X) = Z(X)*H(X) ในขณะที่ตรวจสอบทุกขั้นตอนของการคำนวณ Fibonacci เราตรวจสอบข้อความเกี่ยวกับพหุนามโดยการพิสูจน์การประเมินที่จุดสุ่ม การตรวจสอบจุดสุ่มนี้แสดงถึงการตรวจสอบพหุนามทั้งหมด หากสมการพหุนามไม่ตรงกัน ก็มีโอกาสเล็กน้อยที่สมการจะตรงกันที่พิกัดสุ่มเฉพาะ

ในทางปฏิบัติ สาเหตุหลักประการหนึ่งของความไร้ประสิทธิภาพคือในโปรแกรมจริง ตัวเลขส่วนใหญ่ที่เราจัดการมีขนาดเล็ก เช่น ดัชนีใน for loops ค่า True/False ตัวนับ และอะไรทำนองนั้น อย่างไรก็ตาม เมื่อเราขยายข้อมูลด้วยการเข้ารหัส Reed-Solomon เพื่อให้เกิดความซ้ำซ้อนที่จำเป็นในการทำให้การตรวจสอบแบบ Merkle-proof มีความปลอดภัย ค่าพิเศษส่วนใหญ่จะกินพื้นที่ทั้งขนาดฟิลด์ แม้ว่าค่าเดิมจะน้อยก็ตาม

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

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

ใน Binius เราทำงานกับพหุนามหลายเส้น: ไฮเปอร์คิวบ์ P(x0, x1,…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 ขนาด 2^32 บิตจะมีความยาวประมาณ 11 MB คุณสามารถชดเชยสิ่งนี้ได้โดยใช้ระบบพิสูจน์อื่นๆ เพื่อสร้างข้อพิสูจน์ของการพิสูจน์ Binius ซึ่งจะทำให้คุณได้รับประสิทธิภาพของการพิสูจน์ Binius ด้วยขนาดการพิสูจน์ที่เล็กลง อีกทางเลือกหนึ่งคือโปรโตคอล FRI-Binius ที่ซับซ้อนกว่า ซึ่งสร้างการพิสูจน์ขนาดหลายลอการิทึม (เช่นเดียวกับ FRI ทั่วไป)

• Binius ส่งผลต่อความเป็นมิตรต่อ SNARK อย่างไร บทสรุปพื้นฐานคือ หากคุณใช้ Binius คุณไม่จำเป็นต้องใส่ใจกับการคำนวณที่เป็นมิตรต่อการคำนวณอีกต่อไป การแฮชแบบปกติจะไม่มีประสิทธิภาพมากกว่าการแฮชทางคณิตศาสตร์แบบดั้งเดิมอีกต่อไป การคูณโมดูโล 2 ยกกำลัง 32 หรือโมดูโล 2 ยกกำลัง 256 จะไม่เจ็บปวดเท่ากับการคูณโมดูโล 2 อีกต่อไป ฯลฯ แต่นี่เป็นหัวข้อที่ซับซ้อน มีหลายสิ่งหลายอย่างเปลี่ยนไปเมื่อทุกอย่างเสร็จสิ้นในรูปแบบไบนารี

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

บทความนี้มาจากอินเทอร์เน็ต: Vitalik: Binius การพิสูจน์ที่มีประสิทธิภาพสำหรับเขตข้อมูลไบนารี

ที่เกี่ยวข้อง: เหรียญ BNB แสดงสัญญาณการฟื้นตัว: จุดสูงสุดใหม่ประจำปีที่เห็น

โดยสรุป ราคา BNB ดีดตัวกลับจาก $550 เข้าใกล้แนวต้าน $593 อีกนิ้ว ตัวชี้วัดราคาฟื้นโมเมนตัมขาขึ้น ซึ่งสนับสนุนการเพิ่มขึ้น 8% Sharpe Ratio ที่ 4.03 มีแนวโน้มที่จะผลักดันนักลงทุนรายใหม่ให้หันมาใช้โทเค็นการแลกเปลี่ยน เดือนมีนาคมเป็นเดือนที่ดีสำหรับ BNB Coin โดยสกุลเงินดิจิทัลบรรลุจุดสูงสุดใหม่สองครั้งในรอบปีภายในเพียงไม่กี่วันก่อนที่จะมีการปรับฐาน หลังจากการฟื้นตัวเกือบสองสัปดาห์ BNB Coin กำลังแสดงสัญญาณที่อาจถึงระดับสูงสุดใหม่ในปี 2024 แต่เหตุการณ์สำคัญดังกล่าวจะเกิดขึ้นได้หรือไม่ BNB ดูมีแนวโน้มดี หลังจากการดีดตัวจากระดับแนวรับ $550 มูลค่าของ BNB Coin ได้เพิ่มขึ้นเป็น $581 ในขณะที่ทำการวิเคราะห์นี้ การปรับปรุงนี้สะท้อนให้เห็นถึงการฟื้นตัวของโปรไฟล์ผลตอบแทนความเสี่ยงของ altcoin...