เป็นไปได้ไหมที่จะสุ่มตัวเลขหากเราไม่ไว้ใจกัน? ส่วนที่ 2

เฮ้ ฮับ!

В ส่วนแรก ในบทความนี้ เราได้พูดคุยกันว่าทำไมจึงจำเป็นต้องสร้างตัวเลขสุ่มสำหรับผู้เข้าร่วมที่ไม่ไว้วางใจซึ่งกันและกัน ข้อกำหนดใดบ้างที่ถูกหยิบยกขึ้นมาสำหรับตัวสร้างตัวเลขสุ่มดังกล่าว และพิจารณาสองแนวทางในการนำไปปฏิบัติ

ในส่วนนี้ของบทความนี้ เราจะมาดูวิธีการอื่นที่ใช้ลายเซ็นเกณฑ์อย่างละเอียดยิ่งขึ้น

การเข้ารหัสเล็กน้อย

เพื่อให้เข้าใจวิธีการทำงานของลายเซ็นตามเกณฑ์ คุณต้องเข้าใจการเข้ารหัสขั้นพื้นฐานเล็กน้อย เราจะใช้สองแนวคิด: สเกลาร์ หรือเพียงแค่ตัวเลข ซึ่งเราจะแสดงด้วยตัวอักษรพิมพ์เล็ก (x, y) และจุดบนเส้นโค้งวงรี ซึ่งเราจะแสดงด้วยอักษรตัวใหญ่

เพื่อทำความเข้าใจพื้นฐานของลายเซ็นเกณฑ์ คุณไม่จำเป็นต้องเข้าใจว่าเส้นโค้งวงรีทำงานอย่างไร นอกเหนือจากสิ่งพื้นฐานบางประการ:

1. จุดบนเส้นโค้งวงรีสามารถบวกและคูณด้วยสเกลาร์ได้ (เราจะแทนการคูณด้วยสเกลาร์เป็น xGแม้ว่าสัญกรณ์ Gx มักใช้ในวรรณคดีด้วย) ผลลัพธ์ของการบวกและการคูณด้วยสเกลาร์คือจุดบนเส้นโค้งรูปวงรี

2. รู้แต่ประเด็นเท่านั้น G และผลคูณของมันด้วยสเกลาร์ xG ไม่สามารถคำนวณได้ x.

เราจะใช้แนวคิดเรื่องพหุนามด้วย พี(x) องศา k-1. โดยเฉพาะอย่างยิ่ง เราจะใช้คุณสมบัติของพหุนามต่อไปนี้ ถ้าเรารู้ค่า พี(x) เพื่อสิ่งใดๆ k ต่าง x (และเราไม่มีข้อมูลเพิ่มเติมเกี่ยวกับ พี(x)) เราก็สามารถคำนวณได้ พี(x) สำหรับคนอื่น x.

สิ่งที่น่าสนใจคือสำหรับพหุนามใดๆ พี(x) และจุดใดจุดหนึ่งบนเส้นโค้ง Gรู้ความหมาย พี(x)จี เพื่อสิ่งใดๆ k ความหมายที่แตกต่างกัน xเราก็สามารถคำนวณได้เช่นกัน พี(x)จี เพื่อสิ่งใดๆ x.

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

เครื่องกำเนิดตัวเลขสุ่มบนลายเซ็นเกณฑ์

เอาเป็นว่า n ผู้เข้าร่วมต้องการสร้างตัวเลขสุ่มและเราต้องการให้ทุกคนเข้าร่วม k มีมากพอที่จะสร้างจำนวนได้ แต่เพื่อให้ผู้โจมตีที่ควบคุมได้ kผู้เข้าร่วม -1 หรือน้อยกว่าไม่สามารถคาดเดาหรือมีอิทธิพลต่อจำนวนที่สร้างขึ้นได้

สมมติว่ามีพหุนามดังกล่าว พี(x) องศา k-1 สิ่งที่ผู้เข้าร่วมคนแรกรู้ P (1)คนที่สองรู้ พี(2) และอื่นๆ (n-รู้แล้ว พี(n)). เรายังถือว่าเป็นเช่นนั้นสำหรับจุดที่กำหนดไว้ล่วงหน้า G ทุกคนรู้ พี(x)จี สำหรับทุกค่า x. เราจะโทร พี(ฉัน) “องค์ประกอบส่วนตัว” iผู้เข้าร่วม (เพราะเท่านั้น iผู้เข้าร่วมคนที่รู้จักเธอ) และ หมู “องค์ประกอบสาธารณะ” i-ผู้เข้าร่วมคนที่ (เพราะผู้เข้าร่วมทุกคนรู้จักเธอ) เท่าที่จำได้ความรู้ หมู ไม่เพียงพอต่อการฟื้นฟู พี(ฉัน)

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

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

H = สเกลาร์ToPoint(h)

จากนั้นผู้เข้าร่วมแต่ละคน i คำนวณและเผยแพร่ สวัสดี = p(i)H พวกเขาทำอะไรได้บ้างเพราะพวกเขารู้ p(i) และ H. การเปิดเผย Hฉันไม่อนุญาตให้ผู้เข้าร่วมรายอื่นกู้คืนองค์ประกอบส่วนตัว iผู้เข้าร่วมรายนั้น ดังนั้นส่วนประกอบส่วนตัวหนึ่งชุดจึงสามารถนำมาใช้จากบล็อกหนึ่งไปอีกบล็อกหนึ่งได้ ดังนั้น อัลกอริธึมการสร้างพหุนามราคาแพงที่อธิบายไว้ด้านล่างนี้จะต้องดำเนินการเพียงครั้งเดียวเท่านั้น

เมื่อ k ผู้เข้าร่วมถูกชันสูตรพลิกศพ สวัสดี = p(i)H ทุกคนสามารถคำนวณได้ Hx= พี(x)เอช เพื่อทุกสิ่ง x ต้องขอบคุณคุณสมบัติของพหุนามที่เราพูดถึงไปแล้วในหัวข้อที่แล้ว ในขณะนี้ผู้เข้าร่วมทั้งหมดกำลังคำนวณ H0 = พี(0)เอช, และนี่คือผลลัพธ์ของตัวเลขสุ่ม โปรดทราบว่าไม่มีใครรู้ พี(0) และเป็นวิธีเดียวที่จะคำนวณได้ พี(0)เอช – นี่คือการแก้ไข พี(x)เอช, ซึ่งจะเป็นไปได้ก็ต่อเมื่อเท่านั้น k ค่า พี(ไอ)เอช เป็นที่รู้จัก. การเปิดปริมาณที่น้อยลง พี(ไอ)เอช ไม่ได้ให้ข้อมูลใด ๆ เกี่ยวกับ พี(0)ซ.

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

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

ค่าที่แตกต่างกันของ H_1 ที่ส่งโดยผู้เข้าร่วมคนแรกนำไปสู่ผลลัพธ์ H_0 ที่แตกต่างกัน

มีอย่างน้อยสองวิธีในการพิสูจน์ความถูกต้อง Hฉัน เราจะพิจารณามันหลังจากที่เราวิเคราะห์การสร้างพหุนามแล้ว

การสร้างพหุนาม

ในส่วนสุดท้าย เราถือว่าเรามีพหุนามเช่นนั้น พี(x) องศา k-1 ว่าผู้เข้าร่วม i รู้ พี(ฉัน)และไม่มีใครมีข้อมูลใดๆ เกี่ยวกับค่านี้ ในส่วนถัดไป เราจะต้องใช้สิ่งนั้นสำหรับจุดที่กำหนดไว้ล่วงหน้าด้วย G ทุกคนรู้ พี(x)จี เพื่อทุกสิ่ง x.

ในส่วนนี้ เราจะถือว่าผู้เข้าร่วมแต่ละคนมีคีย์ส่วนตัวอยู่ในเครื่อง ซี เพื่อให้ทุกคนรู้กุญแจสาธารณะที่เกี่ยวข้อง Xi.

โปรโตคอลการสร้างพหุนามที่เป็นไปได้ประการหนึ่งมีดังนี้:

1. ผู้เข้าร่วมแต่ละคน i ภายในเครื่องจะสร้างพหุนามตามอำเภอใจ พาย(x) องศา k-1 จากนั้นพวกเขาก็ส่งผู้เข้าร่วมแต่ละคน j มูลค่า pi(j) เข้ารหัสด้วยกุญแจสาธารณะ เอ็กซ์จ. ดังนั้นเท่านั้น i-TH и j-TH ผู้เข้าร่วมรู้ pฉัน(เจ) ผู้เข้าร่วม i ประกาศต่อสาธารณะด้วย ปี่(เจ)จี เพื่อทุกสิ่ง j จาก 1 ไปยัง k รวมทั้ง

2. ผู้เข้าร่วมทุกคนใช้ฉันทามติในการเลือก k ผู้เข้าร่วมซึ่งจะใช้พหุนาม เนื่องจากผู้เข้าร่วมบางคนอาจออฟไลน์ เราจึงไม่สามารถรอจนกว่าทุกคนจะถึง n ผู้เข้าร่วมจะเผยแพร่พหุนาม ผลลัพธ์ของขั้นตอนนี้คือเซต Z ประกอบด้วยอย่างน้อย k พหุนามที่สร้างในขั้นตอน (1).

3. ผู้เข้าร่วมต้องแน่ใจว่าค่านิยมที่พวกเขารู้ pi(j) สอดคล้องกับประกาศต่อสาธารณะ ปี่(เจ)จี หลังจากก้าวเข้ามาแล้ว. Z พหุนามเฉพาะที่ส่งแบบส่วนตัวเท่านั้น pi(j) สอดคล้องกับประกาศต่อสาธารณะ ปี่(เจ)จี

4. ผู้เข้าร่วมแต่ละคน j คำนวณองค์ประกอบส่วนตัว พี(เจ) เป็นผลรวม pฉัน(เจ) สำหรับทุกคน i в Z. ผู้เข้าร่วมแต่ละคนจะคำนวณค่าทั้งหมดด้วย พี(x)จี เป็นผลรวม pi(x)G สำหรับทุก i в Z.

โปรดทราบว่า พี(เอ็กซ์) – มันเป็นพหุนามจริงๆ เค-1, เพราะมันคือผลรวมของแต่ละบุคคล pi(x) ซึ่งแต่ละค่าเป็นพหุนามของดีกรี k-1. แล้วสังเกตว่าในขณะที่ผู้เข้าร่วมแต่ละคน j รู้ พี(เจ) พวกเขาไม่มีข้อมูลเกี่ยวกับ พี(x) สำหรับ x ≠ เจ. แน่นอนว่าในการคำนวณค่านี้ พวกเขาจำเป็นต้องรู้ทุกอย่าง ปี่(x) และตราบใดที่ผู้เข้าร่วม j ไม่ทราบพหุนามที่เลือกอย่างน้อยหนึ่งรายการ เนื่องจากมีข้อมูลไม่เพียงพอ พี(เอ็กซ์)

นี่คือกระบวนการสร้างพหุนามทั้งหมดที่จำเป็นในส่วนสุดท้าย ขั้นตอนที่ 1, 2 และ 4 ข้างต้นมีการดำเนินการที่ค่อนข้างชัดเจน แต่ขั้นตอนที่ 3 ไม่ใช่เรื่องเล็กน้อย

โดยเฉพาะเราต้องสามารถพิสูจน์ได้ว่ามีการเข้ารหัส pi(j) สอดคล้องกับสิ่งที่เผยแพร่จริงๆ ปี่(เจ)จี หากเราไม่สามารถพิสูจน์ได้ ผู้โจมตี i อาจส่งขยะแทนได้ pฉัน (j) ถึงผู้เข้าร่วม jและผู้เข้าร่วม j จะไม่สามารถเข้าใจความหมายที่แท้จริงได้ ปี่(เจ) และจะไม่สามารถคำนวณองค์ประกอบส่วนตัวได้.

มีโปรโตคอลการเข้ารหัสที่ช่วยให้คุณสามารถสร้างข้อความเพิ่มเติมได้ พิสูจน์i(j) เพื่อให้ผู้เข้าร่วมคนใดคนหนึ่งมีคุณค่าบางอย่าง e, ตลอดจน พิสูจน์อักษร(j) и pi(j)G สามารถตรวจสอบได้ในเครื่อง e - มันเป็นจริงๆ ปี่(เจ) เข้ารหัสด้วยรหัสของผู้เข้าร่วม j. น่าเสียดายที่หลักฐานดังกล่าวมีขนาดใหญ่อย่างไม่น่าเชื่อ และเนื่องจากจำเป็นต้องเผยแพร่ โอ(น) หลักฐานดังกล่าวไม่สามารถนำมาใช้เพื่อจุดประสงค์นี้ได้

แทนที่จะพิสูจน์ว่า ปี่(เจ) สอดคล้องกับ pi(j)G เราสามารถจัดสรรระยะเวลาที่ยาวนานมากในโปรโตคอลการสร้างพหุนาม ในระหว่างที่ผู้เข้าร่วมทุกคนตรวจสอบการเข้ารหัสที่ได้รับ ปี่(เจ) และหากข้อความที่ถอดรหัสไม่ตรงกับสาธารณะ pฉัน(j)G พวกเขาเผยแพร่หลักฐานการเข้ารหัสว่าข้อความที่เข้ารหัสที่พวกเขาได้รับนั้นไม่ถูกต้อง พิสูจน์ว่าข้อความนั้น ไม่ สอดคล้องกับ หมู) ง่ายกว่าการพิสูจน์ว่ามันเข้ากันมาก ควรสังเกตว่าผู้เข้าร่วมแต่ละคนต้องปรากฏออนไลน์อย่างน้อยหนึ่งครั้งในช่วงเวลาที่กำหนดเพื่อสร้างหลักฐานดังกล่าว และอาศัยสมมติฐานที่ว่าหากพวกเขาเผยแพร่หลักฐานดังกล่าว ก็จะเข้าถึงผู้เข้าร่วมรายอื่นทั้งหมดในเวลาที่กำหนดเดียวกัน

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

หลักฐานความถูกต้องของ H_i

ส่วนสุดท้ายที่ยังต้องหารือกันคือจะพิสูจน์ความถูกต้องของการตีพิมพ์ได้อย่างไร Hฉันคือสิ่งนั้น สวัสดี = p(i)H โดยไม่ต้องเปิด พี(ฉัน)

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

dlog(p(i)G, G) = dlog(Hi, H)

โดยไม่มีการเปิดเผย พี(ฉัน). การก่อสร้างหลักฐานดังกล่าวมีอยู่ เป็นต้น พิธีสาร Schnorr.

ด้วยการออกแบบนี้ผู้เข้าร่วมแต่ละคนพร้อมด้วย Hi ส่งหลักฐานความถูกต้องตามแบบ

เมื่อสร้างหมายเลขสุ่มแล้ว ผู้เข้าร่วมอื่น ๆ มักจะจำเป็นต้องใช้หมายเลขนั้นนอกเหนือจากผู้สร้างหมายเลขนั้น ผู้เข้าร่วมดังกล่าวพร้อมทั้งจำนวนจะต้องส่งทั้งหมด Hi และหลักฐานที่เกี่ยวข้อง

ผู้อ่านที่อยากรู้อยากเห็นอาจถามว่า: เนื่องจากตัวเลขสุ่มสุดท้ายคือ H0 และ พี(0)ก – นี่เป็นข้อมูลสาธารณะ ทำไมเราจึงต้องมีหลักฐานสำหรับแต่ละบุคคล Hฉันทำไมไม่ส่งหลักฐานนั้นมาแทน

ดีล็อก(พี(0)G, G) = dlog(H0, H)

ปัญหาคือไม่สามารถสร้างการพิสูจน์ดังกล่าวได้โดยใช้ Schnorr Protocol เนื่องจากไม่มีใครรู้คุณค่า P (0)จำเป็นในการสร้างการพิสูจน์ และยิ่งไปกว่านั้น ตัวสร้างตัวเลขสุ่มทั้งหมดจะขึ้นอยู่กับข้อเท็จจริงที่ว่าไม่มีใครรู้ค่านี้ ดังนั้นจึงจำเป็นต้องมีค่าทั้งหมด Hi และหลักฐานส่วนบุคคลเพื่อพิสูจน์ความถูกต้อง H0.

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

H0 × G = p(0)G × H

หากเส้นโค้งที่เลือกรองรับ การจับคู่เส้นโค้งวงรีหลักฐานนี้ใช้งานได้ ในกรณีนี้ H0 ไม่ใช่แค่ผลลัพธ์ของเครื่องกำเนิดตัวเลขสุ่มเท่านั้น ซึ่งสามารถตรวจสอบได้โดยผู้เข้าร่วมที่รู้ จี เอช и พี(0)ก. ชม0 ยังเป็นลายเซ็นบนข้อความที่ใช้เป็นเมล็ดพันธุ์ยืนยันว่า k и n ผู้เข้าร่วมลงนามข้อความนี้ ดังนั้นหาก เมล็ดพันธุ์ – คือแฮชของบล็อกในโปรโตคอลบล็อคเชนแล้ว H0 เป็นทั้งลายเซ็นหลายลายเซ็นบนบล็อกและเป็นตัวเลขสุ่มที่ดีมาก

ในข้อสรุป

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

รหัสโปรโตคอลเปิดอยู่ การใช้งานของเราเขียนด้วยภาษา Rust ซึ่งสามารถพบได้ ที่นี่.

คุณสามารถดูการพัฒนาสำหรับ NEAR และทดลองได้ใน IDE ออนไลน์ ที่นี่.

สามารถติดตามข่าวสารภาษารัสเซียทั้งหมดได้ที่ กลุ่มโทรเลข และ กลุ่มบน VKontakteและภาษาอังกฤษอย่างเป็นทางการ พูดเบาและรวดเร็ว.

พบกันเร็ว ๆ นี้!

ที่มา: will.com