วิทาลิก บูเตริน ผ่านทาง บล็อกของ Vitalik Buterin
นี่คือกระจกของการโพสต์ที่ https://medium.com/@VitalikButerin/การสำรวจ-elliptic-curve-pairings-c73c1864e627
คำเตือนทริกเกอร์: คณิตศาสตร์
หนึ่งในหลักการเข้ารหัสลับที่สำคัญเบื้องหลังโครงสร้างต่างๆ รวมถึงลายเซ็นเกณฑ์ที่กำหนด, zk-SNARKs และการพิสูจน์ความรู้ที่ไม่มีศูนย์ในรูปแบบที่เรียบง่ายกว่าอื่นๆ คือการจับคู่เส้นโค้งวงรี การจับคู่เส้นโค้งวงรี (หรือ “แผนที่บิลิเนียร์”) เป็นส่วนเสริมล่าสุดจากประวัติศาสตร์ยาวนาน 30 ปีของการใช้เส้นโค้งวงรีสำหรับแอปพลิเคชันการเข้ารหัส รวมถึงการเข้ารหัสและลายเซ็นดิจิทัล การจับคู่ทำให้เกิดรูปแบบของ "การคูณแบบเข้ารหัส" ซึ่งขยายสิ่งที่โปรโตคอลที่ใช้เส้นโค้งวงรีสามารถทำได้อย่างมาก วัตถุประสงค์ของบทความนี้คือเพื่อเจาะลึกการจับคู่เส้นโค้งวงรีโดยละเอียด และอธิบายโครงร่างทั่วไปเกี่ยวกับวิธีการทำงาน
คุณไม่จำเป็นต้องเข้าใจทุกสิ่งที่นี่ในครั้งแรกที่อ่าน หรือแม้แต่ครั้งที่สิบ สิ่งนี้เป็นเรื่องยากจริงๆ แต่หวังว่าบทความนี้จะให้แนวคิดแก่คุณอย่างน้อยเกี่ยวกับสิ่งที่เกิดขึ้นภายใต้ประทุน
เส้นโค้งรูปวงรีนั้นเป็นหัวข้อที่ไม่ต้องทำความเข้าใจมากนัก และโดยทั่วไปบทความนี้จะถือว่าคุณรู้วิธีการทำงานของเส้นโค้ง ถ้าคุณไม่ทำ ฉันขอแนะนำบทความนี้ที่นี่เป็นไพรเมอร์: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. โดยสรุปโดยย่อ การเข้ารหัสเส้นโค้งวงรีเกี่ยวข้องกับวัตถุทางคณิตศาสตร์ที่เรียกว่า "จุด" (นี่คือจุดสองมิติตามตัวอักษรที่มีพิกัด (�,�)) โดยมีสูตรพิเศษสำหรับการเพิ่มและการลบวัตถุเหล่านั้น (เช่น สำหรับการคำนวณพิกัดของ �= �+�) และคุณยังสามารถคูณจุดด้วยจำนวนเต็มได้ (เช่น �⋅�=�+�+…+� แม้ว่าจะมีวิธีที่เร็วกว่ามากในการคำนวณหาก � ใหญ่)
ต่อไปนี้คือลักษณะของการเพิ่มจุดแบบกราฟิก
มีจุดพิเศษที่เรียกว่า "จุดที่อนันต์" (�) ซึ่งเทียบเท่ากับศูนย์ในเลขคณิตแบบจุด เป็นกรณีที่ �+�=� เสมอ นอกจากนี้ เส้นโค้งยังมี “ใบสั่ง“; มีตัวเลข � โดยที่ �⋅�=� สำหรับ � ใดๆ (และแน่นอน �⋅(�+1)=�, �⋅(7⋅�+5)=�⋅5 และอื่นๆ) นอกจากนี้ยังมีบางจุดที่ตกลงกันโดยทั่วไปเกี่ยวกับ "จุดกำเนิด" � ซึ่งเข้าใจกันว่าเป็นตัวแทนหมายเลข 1 ในแง่ทฤษฎีแล้ว จุดใดๆ บนเส้นโค้ง (ยกเว้น �) อาจเป็น �; สิ่งที่สำคัญก็คือ � เป็นมาตรฐาน
การจับคู่ก้าวไปอีกขั้นโดยทำให้คุณสามารถตรวจสอบสมการที่ซับซ้อนบางประเภทบนจุดเส้นโค้งวงรีได้ — ตัวอย่างเช่น หาก �=�⋅�, �=�⋅� และ �=�⋅� คุณสามารถตรวจสอบได้ว่า ไม่ใช่ �⋅�=� โดยมีเพียง �,� และ � เป็นอินพุต นี่อาจดูเหมือนการรับประกันความปลอดภัยพื้นฐานของเส้นโค้งวงรีกำลังถูกทำลาย เนื่องจากข้อมูลเกี่ยวกับ � รั่วไหลจากการรู้จัก P แต่ปรากฎว่าการรั่วไหลนั้นมีอยู่ในระดับสูง โดยเฉพาะ ปัญหาการตัดสินใจของดิฟฟี่ เฮลแมน เป็นเรื่องง่าย แต่ปัญหาการคำนวณ Diffie Hellman (การรู้ � และ � ในตัวอย่างข้างต้น การคำนวณ �=�⋅�⋅�) และ ปัญหาลอการิทึมไม่ต่อเนื่อง (การกู้คืน � จาก �) ยังคงเป็นไปไม่ได้ในการคำนวณ (อย่างน้อย ถ้าเป็นเมื่อก่อน)
วิธีที่สามในการดูว่าการจับคู่ทำอะไรได้บ้าง และวิธีที่อาจให้ความกระจ่างมากที่สุดสำหรับกรณีการใช้งานส่วนใหญ่ที่เรากำลังพูดถึงก็คือ ถ้าคุณมองว่าจุดเส้นโค้งวงรีเป็นตัวเลขที่เข้ารหัสทางเดียว (นั่นคือ �� �(�)=�⋅�=�) ในขณะที่คณิตศาสตร์วงรีแบบดั้งเดิมให้คุณตรวจสอบได้ เชิงเส้น ข้อจำกัดของตัวเลข (เช่น ถ้า �=�⋅�,�=�⋅� และ �=�⋅� การตรวจสอบ 5⋅�+7⋅�=11⋅� คือ จริงๆ ตรวจสอบว่า 5⋅�+7⋅�=11⋅�) การจับคู่ช่วยให้คุณตรวจสอบได้ กำลังสอง ข้อจำกัด (เช่น การตรวจสอบ �(�,�)⋅�(�,�⋅5)=1 คือ จริงๆ กำลังตรวจสอบว่า �⋅�+5=0) และการขึ้นไปสู่กำลังสองก็เพียงพอที่จะให้เราทำงานกับลายเซ็นเกณฑ์ที่กำหนด โปรแกรมเลขคณิตกำลังสอง และสิ่งดีๆ อื่นๆ ทั้งหมด
ทีนี้ โอเปอเรเตอร์ �(�,�) ตลกๆ ที่เราแนะนำข้างต้นคืออะไร? นี่คือการจับคู่ นักคณิตศาสตร์บางครั้งเรียกมันว่า a แผนที่ไบลิเนียร์; คำว่า “ไบลิเนียร์” ในที่นี้หมายถึงว่าเป็นไปตามข้อจำกัด:
)
)
โปรดทราบว่า + และ ⋅ สามารถเป็นตัวดำเนินการได้ตามต้องการ เมื่อคุณสร้างวัตถุทางคณิตศาสตร์รูปแบบใหม่ที่สวยงาม พีชคณิตเชิงนามธรรมจะไม่สนใจว่า + และ ⋅ เป็นอย่างไร กำหนดตราบเท่าที่มันสอดคล้องกันในลักษณะปกติเช่น �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) และ (�⋅�)+(�⋅�)=(�+�)⋅�.
ถ้า �, �, � และ � เป็นแบบธรรมดา ตัวเลขจากนั้นการจับคู่แบบง่ายๆ ก็เป็นเรื่องง่าย: เราสามารถทำได้ �(�,�)=2�� จากนั้นเราจะเห็นได้ว่า:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
มันเป็นไบลิเนียร์!
อย่างไรก็ตาม การจับคู่แบบง่าย ๆ ดังกล่าวไม่เหมาะสำหรับการเข้ารหัส เนื่องจากอ็อบเจ็กต์ที่จับคู่นั้นเป็นจำนวนเต็มธรรมดาและวิเคราะห์ง่ายเกินไป จำนวนเต็มทำให้ง่ายต่อการหาร คำนวณลอการิทึม และคำนวณอื่นๆ มากมาย จำนวนเต็มธรรมดาไม่มีแนวคิดเรื่อง "กุญแจสาธารณะ" หรือ "ฟังก์ชันทางเดียว" นอกจากนี้ ด้วยการจับคู่ที่อธิบายไว้ข้างต้น คุณสามารถย้อนกลับได้ โดยรู้ � และรู้ �(�,�) คุณก็สามารถคำนวณการหารและลอการิทึมเพื่อกำหนด � ได้ เราต้องการวัตถุทางคณิตศาสตร์ที่อยู่ใกล้กับ "กล่องดำ" มากที่สุด ซึ่งคุณสามารถเพิ่ม ลบ คูณ และหารได้ แต่อย่าทำอะไรอย่างอื่นเลย. นี่คือที่มาของการจับคู่เส้นโค้งวงรีและเส้นโค้งวงรี
ปรากฎว่ามีความเป็นไปได้ที่จะสร้างแผนที่ไบลิเนียร์เหนือจุดเส้นโค้งวงรี นั่นคือ ฟังก์ชัน �(�,�) โดยที่อินพุต � และ � เป็นจุดเส้นโค้งวงรี และที่เอาต์พุตคือสิ่งที่เรียกว่า (��)องค์ประกอบ 12 องค์ประกอบ (อย่างน้อยในกรณีเฉพาะที่เราจะกล่าวถึงที่นี่ ข้อมูลเฉพาะจะแตกต่างกันไปขึ้นอยู่กับรายละเอียดของเส้นโค้ง ซึ่งจะเพิ่มเติมในภายหลัง) แต่คณิตศาสตร์ที่อยู่เบื้องหลังการทำเช่นนี้ค่อนข้างซับซ้อน
ขั้นแรก เรามาครอบคลุมฟิลด์เฉพาะและฟิลด์ส่วนขยาย เส้นโค้งรูปวงรีสวยๆ ในภาพก่อนหน้าในโพสต์นี้จะมีลักษณะเช่นนั้นหากคุณถือว่าสมการเส้นโค้งถูกกำหนดโดยใช้จำนวนจริงปกติ อย่างไรก็ตาม หากเราใช้จำนวนจริงปกติในการเข้ารหัส คุณสามารถใช้ลอการิทึมเพื่อ "ย้อนกลับ" และทุกอย่างจะพัง นอกจากนี้ จำนวนพื้นที่ที่จำเป็นในการจัดเก็บและเป็นตัวแทนของตัวเลขอาจเพิ่มขึ้นตามอำเภอใจ ดังนั้นเราจึงใช้ตัวเลขใน a แทน เขตสำคัญ.
สนามเฉพาะประกอบด้วยเซตของตัวเลข 0,1,2…�−1 โดยที่ � เป็นจำนวนเฉพาะ และการดำเนินการต่างๆ มีการกำหนดไว้ดังนี้:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
โดยพื้นฐานแล้ว คณิตศาสตร์ทั้งหมดจะทำแบบโมดูโล � (ดู โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม สำหรับการแนะนำคณิตศาสตร์โมดูลาร์) กองเป็นกรณีพิเศษ โดยปกติ 32 ไม่ใช่จำนวนเต็ม และในที่นี้เราต้องการจัดการกับเฉพาะจำนวนเต็ม ดังนั้นเราจึงพยายามค้นหาตัวเลข � แทน โดยที่ �⋅2=3 โดยที่ ⋅ หมายถึงการคูณแบบแยกส่วนตามที่กำหนดไว้ข้างต้น ขอบคุณ ทฤษฎีบทเล็กๆ ของแฟร์มาต์เคล็ดลับการยกกำลังที่แสดงด้านบนใช้ได้ผล แต่ก็มีวิธีที่เร็วกว่าด้วย โดยใช้ อัลกอริทึมแบบยุคลิดแบบขยาย. สมมติว่า �=7; นี่เป็นตัวอย่างบางส่วน:
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
หากคุณลองเล่นกับคณิตศาสตร์ประเภทนี้ คุณจะสังเกตเห็นว่ามันสอดคล้องกันอย่างสมบูรณ์แบบและเป็นไปตามกฎปกติทั้งหมด สองตัวอย่างสุดท้ายด้านบนแสดงให้เห็นว่า (�/�)⋅�=�; คุณจะเห็นได้ว่า (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅� และอัตลักษณ์พีชคณิตระดับมัธยมศึกษาตอนปลายอื่นๆ ทั้งหมดที่คุณรู้จักและชื่นชอบจะดำเนินต่อไป ให้ถือเป็นความจริงเช่นกัน ในเส้นโค้งวงรีในความเป็นจริง จุดและสมการมักจะคำนวณในช่องเฉพาะ
ตอนนี้มาพูดถึงกัน ฟิลด์ส่วนขยาย. คุณอาจเคยเห็นฟิลด์ส่วนขยายมาก่อนแล้ว ตัวอย่างที่พบบ่อยที่สุดที่คุณพบในตำราคณิตศาสตร์คือช่องของจำนวนเชิงซ้อน โดยที่ช่องของจำนวนจริงจะ "ขยาย" โดยมีองค์ประกอบเพิ่มเติม −1=� โดยพื้นฐานแล้ว ฟิลด์ส่วนขยายจะทำงานโดยนำฟิลด์ที่มีอยู่แล้ว "ประดิษฐ์" องค์ประกอบใหม่และกำหนดความสัมพันธ์ระหว่างองค์ประกอบนั้นกับองค์ประกอบที่มีอยู่ (ในกรณีนี้ �2+1=0) ตรวจสอบให้แน่ใจว่าสมการนี้ไม่เป็นจริง สำหรับตัวเลขใดๆ ที่อยู่ในช่องเดิม และดูที่ชุดของผลรวมเชิงเส้นทั้งหมดขององค์ประกอบของช่องเดิมกับองค์ประกอบใหม่ที่คุณเพิ่งสร้างขึ้น
เราสามารถขยายขอบเขตของไพรม์ฟิลด์ได้เช่นกัน ตัวอย่างเช่น เราสามารถขยาย mod7 ของไพรม์ฟิลด์ที่เราอธิบายไว้ข้างต้นด้วย � แล้วเราก็สามารถทำได้:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
ผลลัพธ์สุดท้ายนั้นอาจเป็นเรื่องยากที่จะเข้าใจ สิ่งที่เกิดขึ้นคือขั้นแรกเราแบ่งผลิตภัณฑ์ออกเป็น 4�⋅2+4�⋅� ซึ่งให้ 8�−4 จากนั้นเนื่องจากเรากำลังทำงานในคณิตศาสตร์ mod7 ที่กลายเป็น �+3 ในการแบ่ง เราทำ:
�/�:(�⋅�(�2−2)) % �
โปรดทราบว่าเลขชี้กำลังของทฤษฎีบทเล็กๆ ของแฟร์มาต์ตอนนี้คือ �2 แทนที่จะเป็น � แต่อีกครั้งหากเราต้องการให้มีประสิทธิภาพมากขึ้น เราก็สามารถขยายอัลกอริทึมแบบยูคลิดแบบขยายออกไปแทนเพื่อทำงานแทนได้ โปรดทราบว่า ��2−1=1 สำหรับ � ใดๆ ในช่องนี้ เราจึงเรียก �2−1 ว่า “ลำดับของกลุ่มการคูณในช่องนี้”
ด้วยจำนวนจริง ทฤษฎีบทพื้นฐานของพีชคณิต ทำให้แน่ใจว่าส่วนขยายกำลังสองที่เราเรียกว่าจำนวนเชิงซ้อนนั้น "สมบูรณ์" คุณไม่สามารถขยายออกไปได้อีก เพราะสำหรับความสัมพันธ์ทางคณิตศาสตร์ใดๆ (อย่างน้อย ความสัมพันธ์ทางคณิตศาสตร์ใดๆ ที่กำหนดโดยสูตรพีชคณิต) ที่คุณสามารถนำมาใช้ระหว่างองค์ประกอบใหม่บางอย่างได้ � และจำนวนเชิงซ้อนที่มีอยู่ อาจได้จำนวนเชิงซ้อนอย่างน้อยหนึ่งตัวที่ตรงกับความสัมพันธ์นั้นแล้ว อย่างไรก็ตาม สำหรับเขตข้อมูลเฉพาะ เราไม่มีปัญหานี้ และดังนั้นเราจึงสามารถไปต่อและสร้างส่วนขยายลูกบาศก์ได้ (โดยที่ความสัมพันธ์ทางคณิตศาสตร์ระหว่างองค์ประกอบใหม่บางตัว � และองค์ประกอบของสนามที่มีอยู่คือสมการลูกบาศก์ ดังนั้น 1,� และ �2 จึงเท่ากับ ทั้งหมดเป็นอิสระเชิงเส้นจากกัน) ส่วนขยายลำดับที่สูงกว่า ส่วนขยายของส่วนขยาย ฯลฯ และมันคือจำนวนเชิงซ้อนโมดูลาร์ที่อัดแน่นเกินไปประเภทนี้ที่สร้างการจับคู่เส้นโค้งวงรี
สำหรับผู้ที่สนใจดูคณิตศาสตร์ที่เกี่ยวข้องในการเขียนการดำเนินการทั้งหมดนี้ด้วยโค้ด ฟิลด์เฉพาะและส่วนขยายของฟิลด์จะถูกนำไปใช้ที่นี่: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
ตอนนี้ไปที่การจับคู่เส้นโค้งรูปไข่ การจับคู่เส้นโค้งวงรี (หรือรูปแบบเฉพาะของการจับคู่ที่เราจะสำรวจที่นี่ นอกจากนี้ยังมีการจับคู่ประเภทอื่นๆ แม้ว่าตรรกะจะค่อนข้างคล้ายกัน) คือแผนที่ �2×�1→�� โดยที่:
- �1 เป็นเส้นโค้งรูปวงรี โดยที่จุดเป็นไปตามสมการในรูปแบบ �2=�3+� และโดยที่พิกัดทั้งสองเป็นองค์ประกอบของ �� (กล่าวคือ เป็นตัวเลขธรรมดา ยกเว้นเลขคณิตที่ทำแบบโมดูโลเป็นจำนวนเฉพาะบางตัว)
- �2 เป็นเส้นโค้งรูปวงรี โดยที่จุดต่างๆ เป็นไปตามสมการเดียวกับ �1 ยกเว้นในกรณีที่พิกัดเป็นองค์ประกอบของ (��)12 (กล่าวคือ เป็นจำนวนเชิงซ้อนที่มีประจุมากเกินไปที่เราพูดถึงข้างต้น เรากำหนด "เลขมหัศจรรย์" ใหม่ ” � ซึ่งถูกกำหนดโดยพหุนามดีกรี 12 เช่น �12−18⋅�6+82=0)
- �� คือประเภทของวัตถุที่ป้อนผลลัพธ์ของเส้นโค้งวงรี ในเส้นโค้งที่เราดู �� คือ (��)12 (จำนวนเชิงซ้อนซูเปอร์ชาร์จแบบเดียวกับที่ใช้ใน �2)
คุณสมบัติหลักที่ต้องปฏิบัติตามคือความเป็นไบลิเนียริตี้ ซึ่งในบริบทนี้หมายความว่า:
- )
- )
มีเกณฑ์สำคัญอีกสองประการ:
- ความสามารถในการคำนวณที่มีประสิทธิภาพ (เช่น เราสามารถจับคู่ได้ง่าย ๆ โดยเพียงแค่เอาลอการิทึมแยกของทุกจุดแล้วคูณเข้าด้วยกัน แต่การคำนวณนี้ยากพอๆ กับการถอดรหัสการเข้ารหัสแบบวงรีตั้งแต่แรก จึงไม่นับรวม)
- การไม่เสื่อมถอย (แน่นอนว่า คุณสามารถกำหนด �(�,�)=1 ได้ แต่นั่นไม่ใช่การจับคู่ที่มีประโยชน์อย่างยิ่ง)
ดังนั้นเราจะทำเช่นนี้ได้อย่างไร?
คณิตศาสตร์เบื้องหลังว่าทำไมฟังก์ชันการจับคู่จึงค่อนข้างยุ่งยากและเกี่ยวข้องกับพีชคณิตขั้นสูงเล็กน้อยที่นอกเหนือไปจากที่เราเคยเห็นมา แต่ฉันจะให้ข้อมูลโครงร่าง ก่อนอื่น เราต้องนิยามแนวคิดของ a ก่อน dividerโดยพื้นฐานแล้วเป็นอีกทางเลือกหนึ่งของการแสดงฟังก์ชันบนจุดเส้นโค้งวงรี ตัวหารของฟังก์ชันโดยพื้นฐานแล้วจะนับศูนย์และอนันต์ของฟังก์ชัน หากต้องการดูว่าสิ่งนี้หมายถึงอะไร เรามาดูตัวอย่างกัน ขอให้เราแก้ไขบางจุด �=(��,��) และพิจารณาฟังก์ชันต่อไปนี้:
�(�,�)=�−��
ตัวหารคือ [�]+[−�]−2⋅[�] (วงเล็บเหลี่ยมใช้เพื่อแสดงข้อเท็จจริงที่เราอ้างถึง การมีอยู่ของจุด � ในชุดศูนย์และอนันต์ของฟังก์ชันไม่ใช่จุด P เอง [�]+[�] คือ ไม่ เช่นเดียวกับ [�+�]) การให้เหตุผลมีดังนี้:
- ฟังก์ชันจะมีค่าเท่ากับศูนย์ที่ � เนื่องจาก � is �� ดังนั้น �−��=0
- ฟังก์ชันนี้มีค่าเท่ากับศูนย์ที่ −� เนื่องจาก −� และ � มีพิกัด � เหมือนกัน
- ฟังก์ชันจะไปสู่อนันต์เมื่อ � ไปถึงอนันต์ เราจึงบอกว่าฟังก์ชันนี้มีค่าเท่ากับอนันต์ที่ � มีเหตุผลทางเทคนิคว่าทำไมจึงต้องนับอนันต์นี้สองครั้ง ดังนั้น � จะถูกบวกด้วย “การคูณ” เป็น −2 (ลบเพราะว่ามันเป็นอนันต์และไม่ใช่ศูนย์ สองเนื่องจากการนับซ้ำนี้)
เหตุผลทางเทคนิคคร่าวๆ ก็คือ เนื่องจากสมการของเส้นโค้งคือ �3=�2+� จะไปถึงอนันต์ “เร็วกว่า � 1.5 เท่า” เพื่อให้ �2 ตามทัน �3; ดังนั้น หากฟังก์ชันเชิงเส้นรวมเฉพาะ � ก็แสดงว่าเป็นค่าอนันต์ของการคูณ 2 แต่ถ้ามี � แสดงว่ามีค่าอนันต์ของการคูณ 3
ตอนนี้ พิจารณา "ฟังก์ชันเส้น":
��+��+�=0
โดยที่ �, � และ � ถูกเลือกอย่างระมัดระวังเพื่อให้เส้นผ่านจุด � และ � เนื่องจากวิธีการทำงานของการเพิ่มเส้นโค้งวงรี (ดูแผนภาพด้านบน) นี่ก็หมายความว่าการบวกดังกล่าวผ่าน −�−� ด้วยเช่นกัน และมันขึ้นไปถึงอนันต์โดยขึ้นอยู่กับทั้ง � และ � ดังนั้นตัวหารจึงกลายเป็น [�]+[�]+[−�−�]−3⋅[�]
เรารู้ว่า “ฟังก์ชันตรรกยะ” ทุกอัน (เช่น ฟังก์ชันที่กำหนดโดยใช้จำนวนจำกัดของ +,−,⋅ และ / การดำเนินการบนพิกัดของจุด) จะสอดคล้องกับตัวหารบางตัวโดยเฉพาะ จนถึงการคูณด้วยค่าคงที่ (เช่น ถ้าสองฟังก์ชัน � และ � มีตัวหารเท่ากัน ดังนั้น �=�⋅� สำหรับค่าคงที่บางค่า �)
สำหรับสองฟังก์ชันใดๆ � และ � ตัวหารของ �⋅� จะเท่ากับตัวหารของ � บวกตัวหารของ � (ในตำราคณิตศาสตร์ คุณจะเห็น (�⋅�)=(�)+(�)) ตัวอย่างเช่น ถ้า �(�,�)=��−� แล้ว (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � และ −� นั้น “นับสามเท่า” เพื่อพิจารณาข้อเท็จจริงที่ว่า �3 เข้าใกล้ 0 ที่จุดเหล่านั้น “เร็วกว่าสามเท่า” ในแง่คณิตศาสตร์บางประการ
โปรดทราบว่ามีทฤษฎีบทที่ระบุว่าหากคุณ “ลบวงเล็บเหลี่ยม” ออกจากตัวหารของฟังก์ชัน จุดต่างๆ จะต้องรวมกันได้ �([�]+[�]+[−�−�]−3⋅[ �] เหมาะสมอย่างชัดเจน เนื่องจาก �+�−�−�−3⋅�=�) และตัวหารใดๆ ที่มีคุณสมบัตินี้ก็คือตัวหารของฟังก์ชัน
ตอนนี้เราพร้อมที่จะดูการจับคู่ Tate แล้ว พิจารณาฟังก์ชันต่อไปนี้ ซึ่งกำหนดโดยตัวหาร:
- (��)=�⋅[�]−�⋅[�] โดยที่ � คือลำดับของ �1 กล่าวคือ �⋅�=� สำหรับใดๆ �
- (]
- (]
ตอนนี้เรามาดูผลิตภัณฑ์กัน ��⋅��⋅��. ตัวหารคือ:
]
ซึ่งลดความซับซ้อนลงอย่างเรียบร้อยเป็น:
]
โปรดสังเกตว่าตัวหารนี้มีรูปแบบเดียวกับตัวหารของ �� และ �� ด้านบนทุกประการ ดังนั้น ��⋅��⋅��=��+�
ตอนนี้ เราแนะนำกระบวนการที่เรียกว่าขั้นตอน “การยกกำลังสุดท้าย” โดยที่เราจะนำผลลัพธ์ของฟังก์ชันด้านบน (��,�� ฯลฯ) และเพิ่มกำลัง �=(�12−1)/�, โดยที่ �12−1 คือลำดับของกลุ่มการคูณใน (��)12 (เช่น สำหรับ ใด �∈(��)12,�(�12−1)=1). โปรดสังเกตว่าหากคุณใช้การยกกำลังนี้กับผลลัพธ์ใดๆ ที่มี แล้ว เมื่อยกกำลัง � คุณจะได้เลขยกกำลัง �12−1 ดังนั้นผลลัพธ์จึงกลายเป็น 1 ดังนั้น หลังจากการยกกำลังสุดท้าย �� ตัดออก และเราจะได้ ���⋅���=( ��+�)�. มีความมีสองด้านสำหรับคุณ
ทีนี้ หากคุณต้องการสร้างฟังก์ชันที่เป็นไบลิเนียร์ในอาร์กิวเมนต์ทั้งสอง คุณต้องเข้าสู่วิชาคณิตศาสตร์ที่น่ากลัวมากขึ้น โดยที่แทนที่จะรับ �� ของค่าโดยตรง คุณจะหา �� ของ a dividerและนั่นคือที่มาของ "การจับคู่ Tate" อย่างเต็มรูปแบบ เพื่อพิสูจน์ผลลัพธ์เพิ่มเติม คุณต้องจัดการกับแนวคิดเช่น "ความสมมูลเชิงเส้น" และ "การตอบแทนซึ่งกันและกันของ Weil" และโพรงกระต่ายดำเนินต่อไปจากจุดนั้น คุณสามารถค้นหาเนื้อหาการอ่านเพิ่มเติมเกี่ยวกับเรื่องทั้งหมดนี้ได้ โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม และ โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม.
สำหรับการนำการจับคู่ Tate เวอร์ชันดัดแปลงมาใช้ ซึ่งเรียกว่าการจับคู่ Ate ที่เหมาะสมที่สุด ดูที่นี่. รหัสนำไปใช้ อัลกอริทึมของมิลเลอร์ซึ่งจำเป็นสำหรับการคำนวณ �� จริงๆ
โปรดทราบว่าข้อเท็จจริงที่การจับคู่เช่นนี้เป็นไปได้นั้นค่อนข้างจะเกิดผลหลายอย่าง ในแง่หนึ่ง หมายความว่าโปรโตคอลทั้งหมดที่เราสามารถทำได้กับการจับคู่นั้นเป็นไปได้ แต่ก็หมายความว่าเราต้องระมัดระวังให้มากขึ้นเกี่ยวกับเส้นโค้งวงรีแบบใด เราใช้.
เส้นโค้งวงรีทุกเส้นมีค่าที่เรียกว่า an การฝังระดับ; โดยพื้นฐานแล้ว ค่าที่เล็กที่สุด � โดยที่ ��−1 เป็นผลคูณของ � (โดยที่ � คือจำนวนเฉพาะที่ใช้สำหรับสนาม และ � คือลำดับเส้นโค้ง) ในฟิลด์ด้านบน �=12 และในฟิลด์ที่ใช้สำหรับ ECC แบบดั้งเดิม (เช่น โดยที่เราไม่สนใจเกี่ยวกับการจับคู่) ระดับการฝังมักจะมีขนาดใหญ่มาก จนถึงจุดที่การจับคู่ไม่สามารถคำนวณได้ในเชิงคำนวณ อย่างไรก็ตาม หากเราไม่ระวัง เราก็สามารถสร้างฟิลด์โดยที่ �=4 หรือแม้แต่ 1 ได้
ถ้า �=1 ดังนั้นปัญหา “ลอการิทึมแบบไม่ต่อเนื่อง” สำหรับเส้นโค้งวงรี (โดยพื้นฐานแล้ว การกู้คืน � รู้เพียงจุด �=�⋅� ปัญหาที่คุณต้องแก้ไขเพื่อ “ถอดรหัส” คีย์ส่วนตัวของเส้นโค้งวงรี) ก็สามารถลดลงได้ เข้าสู่โจทย์คณิตศาสตร์ที่คล้ายกันในส่วน �� โดยที่ปัญหาจะง่ายขึ้นมาก (ซึ่งเรียกว่า การโจมตี MOV); การใช้เส้นโค้งที่มีระดับการฝัง 12 หรือสูงกว่าช่วยให้แน่ใจว่าการลดลงนี้จะไม่สามารถใช้งานได้ หรือการแก้ปัญหาบันทึกที่ไม่ต่อเนื่องเหนือผลลัพธ์การจับคู่นั้นอย่างน้อยก็ยากเท่ากับการกู้คืนคีย์ส่วนตัวจากคีย์สาธารณะ "วิธีปกติ" (เช่น เป็นไปไม่ได้ในการคำนวณ) ไม่ต้องกังวล; พารามิเตอร์เส้นโค้งมาตรฐานทั้งหมดได้รับการตรวจสอบอย่างละเอียดสำหรับปัญหานี้
คอยติดตามคำอธิบายทางคณิตศาสตร์เกี่ยวกับวิธีการทำงานของ zk-SNARK ได้เร็วๆ นี้
ขอขอบคุณเป็นพิเศษสำหรับ Christian Reitwiessner, Ariel Gabizon (จาก Zcash) และ Alfred Menezes สำหรับการตรวจสอบและทำการแก้ไข
- เนื้อหาที่ขับเคลื่อนด้วย SEO และการเผยแพร่ประชาสัมพันธ์ รับการขยายวันนี้
- PlatoData.Network Vertical Generative Ai เพิ่มพลังให้กับตัวเอง เข้าถึงได้ที่นี่.
- เพลโตไอสตรีม. Web3 อัจฉริยะ ขยายความรู้ เข้าถึงได้ที่นี่.
- เพลโตESG. คาร์บอน, คลีนเทค, พลังงาน, สิ่งแวดล้อม แสงอาทิตย์, การจัดการของเสีย. เข้าถึงได้ที่นี่.
- เพลโตสุขภาพ เทคโนโลยีชีวภาพและข่าวกรองการทดลองทางคลินิก เข้าถึงได้ที่นี่.
- BlockOffsets การปรับปรุงการเป็นเจ้าของออฟเซ็ตด้านสิ่งแวดล้อมให้ทันสมัย เข้าถึงได้ที่นี่.
- ที่มา: เพลโต ดาต้า อินเทลลิเจนซ์