შესაძლებელია თუ არა შემთხვევითი რიცხვების გენერირება, თუ ერთმანეთს არ ვენდობით? Ნაწილი 2

ჰეი ჰაბრ!

В პირველი ნაწილი ამ სტატიაში განვიხილეთ, თუ რატომ შეიძლება იყოს საჭირო შემთხვევითი რიცხვების გენერირება იმ მონაწილეებისთვის, რომლებიც არ ენდობიან ერთმანეთს, რა მოთხოვნებია წამოყენებული ასეთი შემთხვევითი რიცხვების გენერატორებისთვის და განვიხილეთ მათი განხორციელების ორი მიდგომა.

სტატიის ამ ნაწილში ჩვენ უფრო დეტალურად განვიხილავთ სხვა მიდგომას, რომელიც იყენებს ბარიერის ხელმოწერებს.

ცოტა კრიპტოგრაფია

იმისათვის, რომ გაიგოთ, თუ როგორ მუშაობს ბარიერი ხელმოწერები, თქვენ უნდა გესმოდეთ პატარა ძირითადი კრიპტოგრაფია. ჩვენ გამოვიყენებთ ორ ცნებას: სკალარები, ან უბრალოდ რიცხვები, რომლებსაც აღვნიშნავთ მცირე ასოებით (x, y) და წერტილები ელიფსურ მრუდზე, რომელსაც აღვნიშნავთ დიდი ასოებით.

ბარიერის ხელმოწერის საფუძვლების გასაგებად, თქვენ არ გჭირდებათ იმის გაგება, თუ როგორ მუშაობს ელიფსური მრუდები, გარდა რამდენიმე ძირითადი საკითხისა:

1. ელიფსური მრუდის წერტილები შეიძლება დაემატოს და გავამრავლოთ სკალარით (გამრავლება სკალარზე აღვნიშნავთ როგორც xG, თუმცა აღნიშვნა Gx ასევე ხშირად გამოიყენება ლიტერატურაში). სკალარით შეკრებისა და გამრავლების შედეგი არის ელიფსური მრუდის წერტილი.

2. მხოლოდ აზრის ცოდნა G და მისი პროდუქტი სკალარით xG გამოთვლა შეუძლებელია x.

ჩვენ ასევე გამოვიყენებთ მრავალწევრის ცნებას პ (x) გრადუსი k-1. კერძოდ, გამოვიყენებთ მრავალწევრების შემდეგ თვისებას: თუ ვიცით მნიშვნელობა პ (x) ნებისმიერისთვის k სხვადასხვა x (და მეტი ინფორმაცია არ გვაქვს პ (x)), შეგვიძლია გამოვთვალოთ პ (x) სხვისთვის x.

საინტერესოა, რომ ნებისმიერი მრავალწევრისთვის პ (x) და რაღაც წერტილი მრუდზე Gმნიშვნელობის ცოდნა p(x)G ნებისმიერისთვის k სხვადასხვა მნიშვნელობა x, ასევე შეგვიძლია გამოვთვალოთ p(x)G ნებისმიერისთვის x.

ეს არის საკმარისი ინფორმაცია იმისთვის, რომ გაეცნოთ დეტალებს, თუ როგორ მუშაობს ბარიერის ხელმოწერები და როგორ გამოვიყენოთ ისინი შემთხვევითი რიცხვების გენერირებისთვის.

შემთხვევითი რიცხვების გენერატორი ბარიერის ხელმოწერებზე

ვთქვათ, რომ n მონაწილეებს სურთ შემთხვევითი ნომრის გენერირება და ჩვენ გვინდა, რომ ნებისმიერმა მიიღოს მონაწილეობა k იყო საკმარისი რაოდენობის გენერირება, მაგრამ ისე, რომ თავდამსხმელები, რომლებიც აკონტროლებენ k-1 ან ნაკლებმა მონაწილემ ვერ იწინასწარმეტყველა ან გავლენა მოახდინა გენერირებულ რიცხვზე.

დავუშვათ, არსებობს ასეთი მრავალწევრი პ (x) გრადუსი k-1 რაც პირველმა მონაწილემ იცის გვ (1)მეორემ იცის p(2), და ასე შემდეგ (n- იცის p(n)). ჩვენ ასევე ვვარაუდობთ, რომ გარკვეული წინასწარ განსაზღვრული წერტილისთვის G ყველამ იცის p(x)G ყველა ღირებულებისთვის x. ჩვენ დავურეკავთ p(i) "პირადი კომპონენტი" iმე-XNUMX მონაწილე (რადგან მხოლოდ iმე-ე მონაწილე იცნობს მას) და p(i)G "საზოგადოებრივი კომპონენტი" i-ე მონაწილე (რადგან ყველა მონაწილე იცნობს მას). როგორც გახსოვთ, ცოდნა p(i)G არ არის საკმარისი აღდგენისთვის p(i).

ისეთი მრავალწევრის შექმნა, რომ მხოლოდ i-პირველმა მონაწილემ და სხვამ არავინ იცოდა მისი პირადი კომპონენტი - ეს პროტოკოლის ყველაზე რთული და საინტერესო ნაწილია და მას ქვემოთ გავაანალიზებთ. ახლა, დავუშვათ, რომ გვაქვს ასეთი პოლინომი და ყველა მონაწილემ იცის მათი პირადი კომპონენტები.

როგორ გამოვიყენოთ ასეთი პოლინომი შემთხვევითი რიცხვის შესაქმნელად? დასაწყისისთვის, ჩვენ გვჭირდება გარკვეული სტრიქონი, რომელიც ადრე არ იყო გამოყენებული გენერატორის შესატანად. ბლოკჩეინის შემთხვევაში, ბოლო ბლოკის ჰეში h კარგი კანდიდატია ასეთი ხაზისთვის. მიეცით საშუალება მონაწილეებს შექმნან შემთხვევითი რიცხვი გამოყენებით h როგორც თესლი. მონაწილეები პირველ რიგში გარდაიქმნებიან h მრუდის წერტილამდე ნებისმიერი წინასწარ განსაზღვრული ფუნქციის გამოყენებით:

H = scalarToPoint(h)

შემდეგ თითოეული მონაწილე i ითვლის და აქვეყნებს გამარჯობა = p(i)H, რა შეუძლიათ გააკეთონ, რადგან იციან p(i) და H. გამჟღავნება Hმე არ ვაძლევ უფლებას სხვა მონაწილეებს აღადგინონ პირადი კომპონენტი iმონაწილე და, შესაბამისად, კერძო კომპონენტების ერთი ნაკრები შეიძლება გამოყენებულ იქნას ბლოკიდან ბლოკამდე. ამრიგად, ქვემოთ აღწერილი ძვირადღირებული პოლინომიური გენერირების ალგორითმი მხოლოდ ერთხელ უნდა შესრულდეს.

როდესაც k მონაწილეებს აუტოფსია ჩაუტარდათ გამარჯობა = p(i)H, ყველას შეუძლია გამოთვლა Hx = p(x)H ყველასთვის x მრავალწევრების თვისების წყალობით, რომელიც განვიხილეთ ბოლო ნაწილში. ამ მომენტში ყველა მონაწილე ითვლის H0 = p(0)H, და ეს არის შემთხვევითი რიცხვი. გთხოვთ გაითვალისწინოთ, რომ არავინ იცის p(0), და, შესაბამისად, გამოთვლის ერთადერთი გზა p(0)H – ეს არის ინტერპოლაცია p(x)H, რაც შესაძლებელია მხოლოდ მაშინ, როცა k ღირებულებები p(i)H ცნობილია. ნებისმიერი მცირე რაოდენობის გახსნა p(i)H შესახებ არ გვაწვდის ინფორმაციას p(0)H.

ზემოთ მოცემულ გენერატორს აქვს ყველა ის თვისება, რაც ჩვენ გვინდა: მხოლოდ თავდამსხმელები აკონტროლებენ k-1 ან ნაკლებ მონაწილეს არ აქვს ინფორმაცია ან გავლენა დასკვნაზე, ხოლო რომელიმე k მონაწილეებს შეუძლიათ გამოთვალონ მიღებული რიცხვი და ნებისმიერი ქვეჯგუფი k მონაწილეები ყოველთვის მიდიან ერთსა და იმავე შედეგამდე ერთი და იგივე თესლისთვის.

არის ერთი პრობლემა, რომელსაც ზემოთ ფრთხილად ავიცილეთ თავიდან. იმისათვის, რომ ინტერპოლაცია იმუშაოს, მნიშვნელოვანია, რომ მნიშვნელობა Hi რომელიც გამოქვეყნდა თითოეული მონაწილის მიერ i ნამდვილად იგივე იყო p(i)H. ვინაიდან არავის გარდა i- მონაწილემ არ იცის p(i), არავის გარდა i-მონაწილეს არ შეუძლია ამის გადამოწმება Hi რეალურად გათვლილი სწორად და ყოველგვარი კრიპტოგრაფიული მტკიცებულების გარეშე Hმე თავდამსხმელს შეუძლია გამოაქვეყნოს ნებისმიერი მნიშვნელობა როგორც Hi, და თვითნებურად გავლენას ახდენს შემთხვევითი რიცხვების გენერატორის გამოსავალზე:

პირველი მონაწილის მიერ გაგზავნილი H_1-ის განსხვავებული მნიშვნელობები იწვევს განსხვავებულ შედეგებს H_0

სისწორის დასამტკიცებლად სულ მცირე ორი გზა არსებობს Hi, განვიხილავთ მათ მას შემდეგ, რაც გავაანალიზებთ მრავალწევრის გენერაციას.

პოლინომიური თაობა

ბოლო განყოფილებაში ვივარაუდეთ, რომ გვაქვს ასეთი მრავალწევრი პ (x) გრადუსი k-1 რომ მონაწილე i იცის p(i), და სხვას არავის აქვს ინფორმაცია ამ ღირებულების შესახებ. შემდეგ ნაწილში ჩვენ ასევე დაგვჭირდება ეს გარკვეული წინასწარ განსაზღვრული წერტილისთვის G ყველამ იცოდა p(x)G ყველასთვის x.

ამ განყოფილებაში ჩვენ ვივარაუდებთ, რომ თითოეულ მონაწილეს აქვს გარკვეული პირადი გასაღები xi, ისე, რომ ყველამ იცოდეს შესაბამისი საჯარო გასაღები Xi.

პოლინომიური წარმოქმნის ერთი შესაძლო პროტოკოლი შემდეგია:

1. თითოეული მონაწილე i ლოკალურად ქმნის თვითნებურ მრავალწევრს pi(x) ხარისხი k-1. შემდეგ ისინი აგზავნიან თითოეულ მონაწილეს j ღირებულება pi(j), დაშიფრულია საჯარო გასაღებით Xj. ამგვარად მხოლოდ i-ე и j-ე მონაწილემ იცის pi(j). Მონაწილე i ასევე საჯაროდ აცხადებს პი(ჯ)გ ყველასთვის j საწყისი 1 დან k ინკლუზიური

2. ყველა მონაწილე იყენებს გარკვეულ კონსენსუსს არჩევისთვის k მონაწილეები, რომელთა მრავალწევრები იქნება გამოყენებული. ვინაიდან ზოგიერთი მონაწილე შეიძლება იყოს ხაზგარეშე, ჩვენ ვერ დაველოდებით ყველას n მონაწილეები გამოაქვეყნებენ მრავალწევრებს. ამ ნაბიჯის შედეგი არის ნაკრები Z შედგება სულ მცირე k პოლინომები შექმნილი საფეხურზე (1).

3. მონაწილეები დარწმუნდებიან, რომ მათ იციან ღირებულებები pi(j) შეესაბამება საჯაროდ გამოცხადებულს პი(ჯ)გ. ამ ნაბიჯის შემდეგ Z მხოლოდ პოლინომები, რომლებისთვისაც კერძო გადაცემულია pi(j) შეესაბამება საჯაროდ გამოცხადებულს პი(ჯ)გ.

4. თითოეული მონაწილე j ითვლის მის პირად კომპონენტს p(j) ჯამის სახით pi(j) ყველასთვის i в Z. თითოეული მონაწილე ასევე ითვლის ყველა მნიშვნელობას p(x)G ჯამის სახით pi(x)G ყველა i в Z.

გთხოვთ გაითვალისწინოთ, რომ p(x) - ეს ნამდვილად პოლინომია k-1, რადგან ეს არის ინდივიდის ჯამი pi(x), რომელთაგან თითოეული არის ხარისხის მრავალწევრი k-1. შემდეგ, გაითვალისწინეთ, რომ სანამ თითოეული მონაწილე j იცის p(j), მათ არ აქვთ ინფორმაცია პ (x) ამისთვის x ≠ j. მართლაც, ამ მნიშვნელობის გამოსათვლელად, მათ ყველაფერი უნდა იცოდნენ პი (x), და სანამ მონაწილე j არ იცის არჩეული მრავალწევრებიდან ერთი მაინც, არ აქვს საკმარისი ინფორმაცია ამის შესახებ p(x).

ეს არის პოლინომიური წარმოქმნის მთელი პროცესი, რომელიც საჭირო იყო ბოლო განყოფილებაში. ზემოთ 1, 2 და 4 ნაბიჯებს საკმაოდ აშკარა განხორციელება აქვთ. მაგრამ ნაბიჯი 3 არც ისე ტრივიალურია.

კონკრეტულად, ჩვენ უნდა შევძლოთ დავამტკიცოთ, რომ დაშიფრულია pi(j) ნამდვილად შეესაბამება გამოქვეყნებულებს პი(ჯ)გ. თუ ამას ვერ დავამტკიცებთ, თავდამსხმელი i სანაცვლოდ შეიძლება ნაგვის გაგზავნა pი(კ) მონაწილეს jდა მონაწილე j ვერ მიიღებს რეალურ ღირებულებას პი (ჯ), და ვერ შეძლებს მისი პირადი კომპონენტის გამოთვლას.

არსებობს კრიპტოგრაფიული პროტოკოლი, რომელიც საშუალებას გაძლევთ შექმნათ დამატებითი შეტყობინება მტკიცებულებაi(j), ისეთი, რომ რომელიმე მონაწილე, რომელსაც აქვს გარკვეული მნიშვნელობა e, აგრეთვე მტკიცებულება (j) и pi(j)G, შეუძლია ადგილობრივად გადაამოწმოს ეს e - მართლა ასეა პი (ჯ), დაშიფრულია მონაწილის გასაღებით j. სამწუხაროდ, ასეთი მტკიცებულებების ზომა წარმოუდგენლად დიდია და იმის გათვალისწინებით, რომ აუცილებელია გამოქვეყნება O(nk) ასეთი მტკიცებულება არ შეიძლება გამოყენებულ იქნას ამ მიზნით.

ამის დამტკიცების ნაცვლად pi(j) შეესაბამება pi(j)G ჩვენ შეგვიძლია გამოვყოთ დროის ძალიან დიდი პერიოდი პოლინომიური წარმოქმნის პროტოკოლში, რომლის დროსაც ყველა მონაწილე ამოწმებს მიღებულ დაშიფრულს. პი (ჯ), ხოლო თუ გაშიფრული შეტყობინება არ შეესაბამება საზოგადოებას pi(j)G, ისინი აქვეყნებენ კრიპტოგრაფიულ მტკიცებულებას, რომ მათ მიერ მიღებული დაშიფრული შეტყობინება არასწორია. დაამტკიცეთ, რომ გაგზავნა არარის შეესაბამება პი (G) ბევრად უფრო ადვილია, ვიდრე იმის დამტკიცება, რომ ემთხვევა. უნდა აღინიშნოს, რომ ეს მოითხოვს თითოეულ მონაწილეს ინტერნეტში ერთხელ მაინც გამოცხადდეს ასეთი მტკიცებულების შესაქმნელად გამოყოფილი დროის განმავლობაში და ეყრდნობა ვარაუდს, რომ თუ ისინი გამოაქვეყნებენ ასეთ მტკიცებულებას, ის მიაღწევს ყველა სხვა მონაწილეს იმავე დანიშნულ დროში.

თუ მონაწილე არ გამოჩნდა ონლაინ ამ პერიოდის განმავლობაში და მას ჰქონდა მინიმუმ ერთი არასწორი კომპონენტი, მაშინ ეს კონკრეტული მონაწილე ვერ მიიღებს მონაწილეობას რიცხვების შემდგომ გენერირებაში. პროტოკოლი მაინც იმუშავებს, თუ მაინც არსებობს k მონაწილეები, რომლებმაც უბრალოდ მიიღეს სწორი კომპონენტები, ან შეძლეს დატოვონ უზუსტობის მტკიცებულება გამოყოფილ დროში.

H_i-ის სისწორის მტკიცებულებები

ბოლო ნაწილი, რომელიც განსახილველია, არის ის, თუ როგორ დავამტკიცოთ გამოქვეყნებული სისწორე Hმე, კერძოდ ის გამარჯობა = p(i)H, გახსნის გარეშე p(i).

გავიხსენოთ, რომ ღირებულებები H, G, p(i)G საჯარო და ყველასთვის ცნობილი. ოპერაციის მიღება p(i) იცის p(i)G и G დისკრეტული ლოგარითმი, ან დლოგი, და ჩვენ გვინდა დავამტკიცოთ, რომ:

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

გამჟღავნების გარეშე p(i). ასეთი მტკიცებულებების კონსტრუქციები არსებობს, მაგალითად შნორის პროტოკოლი.

ამ დიზაინით, თითოეულ მონაწილესთან ერთად Hi აგზავნის სისწორის მტკიცებულებას დიზაინის მიხედვით.

შემთხვევითი რიცხვის გენერირების შემდეგ, ის ხშირად უნდა გამოიყენონ სხვა მონაწილეებმა, გარდა მათ, ვინც შექმნა იგი. ასეთმა მონაწილეებმა ნომერთან ერთად უნდა გაგზავნონ ყველა Hi და მასთან დაკავშირებული მტკიცებულებები.

ცნობისმოყვარე მკითხველმა შეიძლება იკითხოს: რადგან საბოლოო შემთხვევითი რიცხვია H0 და p(0)G - ეს არის საჯარო ინფორმაცია, რატომ გვჭირდება მტკიცებულება თითოეული ინდივიდისთვის Hმე, რატომ არ გამოგიგზავნო ამის საბუთი

dlog(p(0)G, G) = dlog(H0, H)

პრობლემა ის არის, რომ ასეთი მტკიცებულება არ შეიძლება შეიქმნას შნორის პროტოკოლის გამოყენებით, რადგან არავინ იცის მნიშვნელობა გვ (0)მტკიცებულების შესაქმნელად აუცილებელია და უფრო მეტიც, მთელი შემთხვევითი რიცხვების გენერატორი ეფუძნება იმ ფაქტს, რომ არავინ იცის ეს მნიშვნელობა. ამიტომ აუცილებელია ყველა ღირებულების არსებობა Hi და მათი ინდივიდუალური მტკიცებულებები სისწორის დასამტკიცებლად H0.

თუმცა, თუ იყო რაიმე ოპერაცია ელიფსურ მრუდეებზე წერტილებზე, რომლებიც სემანტიკურად გამრავლების მსგავსია, სისწორის მტკიცებულება H0 ტრივიალური იქნებოდა, ჩვენ უბრალოდ დავრწმუნდით

H0 შესახებ G = p(0)G × H

თუ არჩეული მრუდი მხარს უჭერს ელიფსური მრუდის წყვილები, ეს მტკიცებულება მუშაობს. Ამ შემთხვევაში H0 არ არის მხოლოდ შემთხვევითი რიცხვების გენერატორის გამომავალი, რომელიც შეიძლება გადაამოწმოს ნებისმიერმა მონაწილემ, რომელმაც იცის გ, ჰ и p(0)G. ჰ0 ასევე არის ხელმოწერა იმ შეტყობინებაზე, რომელიც გამოყენებული იყო როგორც თესლი, რომელიც ადასტურებს ამას k и n მონაწილეებმა ხელი მოაწერეს ამ შეტყობინებას. ამრიგად, თუ თესლი - არის ბლოკის ჰეში ბლოკჩეინის პროტოკოლში, მაშინ H0 არის როგორც მრავალხელმოწერა ბლოკზე, ასევე ძალიან კარგი შემთხვევითი ნომერი.

დასასრულს

ეს სტატია ტექნიკური ბლოგის სერიის ნაწილია ახლო. NEAR არის ბლოკჩეინის პროტოკოლი და პლატფორმა დეცენტრალიზებული აპლიკაციების შემუშავებისთვის, აქცენტით განვითარების სიმარტივეზე და საბოლოო მომხმარებლებისთვის გამოყენების მარტივობაზე.

პროტოკოლის კოდი ღიაა, ჩვენი იმპლემენტაცია ჩაწერილია Rust-ში, მისი ნახვა შესაძლებელია აქ.

თქვენ შეგიძლიათ ნახოთ, როგორ გამოიყურება NEAR-ის განვითარება და ექსპერიმენტი გააკეთოთ ონლაინ IDE-ში აქ.

თქვენ შეგიძლიათ თვალი ადევნოთ ყველა სიახლეს რუსულ ენაზე ტელეგრამის ჯგუფი და ჯგუფი VKontakte-ზე, და ინგლისურად ოფიციალურში twitter.

Მალე გნახავ!

წყარო: www.habr.com