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

ჰეი ჰაბრ!

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

რატომ იქნება საჭირო შემთხვევითი რიცხვების გენერირება მონაწილეთა შორის, რომლებიც არ ენდობიან ერთმანეთს? განაცხადის ერთ-ერთი სფეროა დეცენტრალიზებული აპლიკაციები. მაგალითად, აპლიკაცია, რომელიც იღებს ფსონს მონაწილისგან და ან აორმაგებს თანხას 49%-იანი ალბათობით, ან წაართმევს 51%-იანი ალბათობით, იმუშავებს მხოლოდ იმ შემთხვევაში, თუ მას შეუძლია მიუკერძოებლად მიიღოს შემთხვევითი ნომერი. თუ თავდამსხმელს შეუძლია გავლენა მოახდინოს შემთხვევითი რიცხვების გენერატორის შედეგზე და თუნდაც ოდნავ გაზარდოს აპლიკაციაში ანაზღაურების მიღების შანსი, ის ადვილად გაანადგურებს მას.

როდესაც ჩვენ ვქმნით განაწილებული შემთხვევითი რიცხვების წარმოქმნის პროტოკოლს, გვინდა, რომ მას ჰქონდეს სამი თვისება:

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

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

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

ამ სტატიაში განვიხილავთ ორ მიდგომას: RANDAO + VDF და წაშლის კოდების მიდგომას. შემდეგ ნაწილში, ჩვენ დეტალურად განვიხილავთ მიდგომას, რომელიც დაფუძნებულია ბარიერის ხელმოწერებზე.

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

რანდაო

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

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

პროტოკოლის მსვლელობისას მონაწილეებმა ორჯერ უნდა მივიდნენ საერთო გადაწყვეტილებამდე (ე.წ. კონსენსუსი): როდის უნდა დაიწყონ არჩეული ნომრების გამოვლენა და, შესაბამისად, შეწყვიტონ ჰეშების მიღება და როდის შეწყვიტონ შერჩეული რიცხვების მიღება და შედეგად მიღებული შემთხვევითობის გამოთვლა. ნომერი. ასეთი გადაწყვეტილებების მიღება მონაწილეებს შორის, რომლებიც ერთმანეთს არ ენდობიან, თავისთავად იოლი საქმე არ არის და მას მომავალ სტატიებში დავუბრუნდებით; ამ სტატიაში ვივარაუდებთ, რომ ასეთი კონსენსუსის ალგორითმი ჩვენთვის ხელმისაწვდომია.

ზემოთ აღწერილი თვისებებიდან რომელი აქვს RANDAO-ს? ის არაპროგნოზირებადია, აქვს იგივე სიცოცხლისუნარიანობა, როგორც ძირითადი კონსენსუსის პროტოკოლი, მაგრამ არის მიკერძოებული. კონკრეტულად, თავდამსხმელს შეუძლია დააკვირდეს ქსელს და მას შემდეგ, რაც სხვა მონაწილეები გამოავლენენ თავიანთ ნომრებს, მას შეუძლია გამოთვალოს მათი XOR და გადაწყვიტოს გამოავლინოს თუ არა მისი ნომერი, რათა გავლენა მოახდინოს შედეგზე. მიუხედავად იმისა, რომ ეს ხელს უშლის თავდამსხმელს შემთხვევითი რიცხვების გენერატორის გამომავალი ცალმხრივად განსაზღვრაში, ის მაინც აძლევს მას 1 ბიტის გავლენას. და თუ თავდამსხმელები აკონტროლებენ რამდენიმე მონაწილეს, მაშინ მათ მიერ კონტროლირებადი ბიტების რაოდენობა იქნება მათი კონტროლის ქვეშ მყოფი მონაწილეთა რაოდენობის ტოლი.

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

RANDAO+VDF

RANDAO-ს მიუკერძოებლობის გაკეთების ერთ-ერთი გზა შემდეგია: მას შემდეგ რაც ყველა რიცხვი გამოვლინდება და XOR გამოითვლება, მისი შედეგი შედის ფუნქციის შეყვანაში, რომლის გამოთვლას ძალიან დიდი დრო სჭირდება, მაგრამ საშუალებას გაძლევთ შეამოწმოთ სისწორე. გაანგარიშება ძალიან სწრაფად.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

ამ ფუნქციას ეწოდება Verifiable Delay Function, ან VDF. თუ საბოლოო შედეგის გამოთვლას მეტი დრო სჭირდება, ვიდრე რიცხვის გამჟღავნების ეტაპს, მაშინ თავდამსხმელი ვერ შეძლებს მისი ნომრის ჩვენების ან დამალვის ეფექტს წინასწარ განსაზღვროს და, შესაბამისად, ის დაკარგავს შედეგზე გავლენის მოხდენის შესაძლებლობას.

კარგი VDF-ების შემუშავება ძალიან რთულია. ბოლო დროს რამდენიმე გარღვევა მოხდა, მაგ. ამ и ეს, რამაც VDF პრაქტიკაში უფრო პრაქტიკული გახადა და Ethereum 2.0 გეგმავს გამოიყენოს RANDAO VDF-თან ერთად, როგორც შემთხვევითი რიცხვების წყარო გრძელვადიან პერსპექტივაში. გარდა იმისა, რომ ეს მიდგომა არაპროგნოზირებადი და მიუკერძოებელია, მას აქვს დამატებითი სარგებელი, რომ იყოს სიცოცხლისუნარიანობა, თუ მინიმუმ ორი მონაწილე ხელმისაწვდომია ქსელში (თუ ვივარაუდებთ, რომ გამოყენებული კონსენსუსის პროტოკოლი სიცოცხლისუნარიანია, როდესაც საქმე გვაქვს მონაწილეთა ასეთ მცირე რაოდენობასთან).

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

ზემოთ ნახსენები VDF ოჯახისთვის, გამოყოფილი ASIC-ის შესრულება შეიძლება იყოს 100+ ჯერ უფრო მაღალი ვიდრე ჩვეულებრივი აპარატურა. ასე რომ, თუ განლაგების ფაზა გრძელდება 10 წამი, მაშინ ასეთ ASIC-ზე გამოთვლილ VDF-ს უნდა დასჭირდეს 100 წამზე მეტი, რომ ჰქონდეს 10x უსაფრთხოების ზღვარი და, შესაბამისად, იგივე VDF, რომელიც გამოთვლილია სასაქონლო აპარატურაზე, უნდა დასჭირდეს 100x 100 წამი = ~ 3 საათი.

Ethereum Foundation გეგმავს ამ პრობლემის მოგვარებას საკუთარი საჯაროდ ხელმისაწვდომი, უფასო ASIC-ების შექმნით. როგორც კი ეს მოხდება, ყველა სხვა პროტოკოლმაც შეიძლება ისარგებლოს ამ ტექნოლოგიით, მაგრამ მანამდე RANDAO+VDF მიდგომა არ იქნება ისეთივე სიცოცხლისუნარიანი პროტოკოლებისთვის, რომლებსაც არ შეუძლიათ ინვესტიცია საკუთარი ASIC-ების შემუშავებაში.

ბევრი სტატია, ვიდეო და სხვა ინფორმაცია VDF-ის შესახებ შეგროვდა ამ საიტზე.

ჩვენ ვიყენებთ წაშლის კოდებს

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

პროტოკოლის მთავარი იდეა შემდეგია. სიმარტივისთვის, დავუშვათ, რომ არის ზუსტად 100 მონაწილე. მოდით ასევე ვივარაუდოთ, რომ ადგილობრივ ყველა მონაწილეს აქვს გარკვეული პირადი გასაღები და ყველა მონაწილის საჯარო გასაღებები ცნობილია ყველა მონაწილისთვის:

1. თითოეულ მონაწილეს ლოკალურად გამოაქვს გრძელი სტრიქონი, ყოფს მას 67 ნაწილად, ქმნის წაშლის კოდებს 100 გაზიარების მისაღებად ისე, რომ ნებისმიერი 67 საკმარისია სტრიქონის აღსადგენად, ანიჭებს 100 გაზიარებას თითოეულ მონაწილეს და შიფრავს მათ იგივე მონაწილის საჯარო გასაღები. შემდეგ ქვეყნდება ყველა კოდირებული აქცია.

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

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

4. მას შემდეგ, რაც 67 მონაწილე დაასრულებს საფეხურს (3), ყველა შეთანხმებული ნაკრები შეიძლება მთლიანად გაშიფრული და რეკონსტრუირებული იყოს წაშლის კოდების თვისებების გამო და საბოლოო რიცხვი შეიძლება მიღებულ იქნეს საწყისი მწკრივების XOR-ად, რომლითაც მონაწილეებმა დაიწყეს (1) .

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

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

როდესაც (4) საფეხურზე მონაწილე გაშიფრავს 67 დარტყმას გარკვეული სიმისთვის და ცდილობს მათგან ორიგინალური სტრიქონის რეკონსტრუქციას, შესაძლებელია ერთ-ერთი ვარიანტი:

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

2. მწკრივი აღდგენილია, მაგრამ ადგილობრივად გამოთვლილი ფესვი არ ემთხვევა იმას, რომელზეც მიღწეული იქნა კონსენსუსი.

3. რიგი არ არის აღდგენილი.

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

ბარიერი ხელმოწერები

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

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

BLS ხელმოწერების საერთო აპლიკაცია ბლოკჩეინის პროტოკოლებში, შემთხვევითი რიცხვების გენერირების გარდა, არის BFT პროტოკოლებში ბლოკირების ხელმოწერა. ვთქვათ, 100 მონაწილე ქმნის ბლოკებს და ბლოკი ითვლება საბოლოო, თუ მათგან 67 მოაწერს ხელს. მათ ყველას შეუძლიათ წარადგინონ BLS ხელმოწერის თავიანთი ნაწილები და გამოიყენონ კონსენსუსის ალგორითმი, რომ შეთანხმდნენ 67 მათგანზე და შემდეგ გააერთიანონ ისინი ერთ BLS ხელმოწერაში. ნებისმიერი 67 (ან მეტი) ნაწილი შეიძლება გამოყენებულ იქნას საბოლოო ხელმოწერის შესაქმნელად, რაც დამოკიდებული იქნება იმაზე, თუ რომელი 67 ხელმოწერა იყო გაერთიანებული და, შესაბამისად, შეიძლება განსხვავდებოდეს, თუმცა 67 მონაწილის განსხვავებული არჩევანი შექმნის განსხვავებულ ხელმოწერას, ნებისმიერი ასეთი ხელმოწერა იქნება მოქმედი. ხელმოწერა ბლოკისთვის. შემდეგ დარჩენილ მონაწილეებს მხოლოდ ერთი ხელმოწერის მიღება და გადამოწმება სჭირდებათ თითო ბლოკზე, 67-ის ნაცვლად, ქსელში, რაც მნიშვნელოვნად ამცირებს ქსელის დატვირთვას.

გამოდის, რომ თუ კერძო გასაღებები, რომლებსაც მონაწილეები იყენებენ, გენერირებულია გარკვეული გზით, მაშინ არ აქვს მნიშვნელობა რომელი 67 ხელმოწერა (ან მეტი, მაგრამ არანაკლებ) იქნება აგრეგირებული, მიღებული ხელმოწერა იგივე იქნება. ეს შეიძლება გამოვიყენოთ შემთხვევითობის წყაროდ: მონაწილეები ჯერ თანხმდებიან რაღაც შეტყობინებაზე, რომელსაც მოაწერენ ხელს (ეს შეიძლება იყოს RANDAO-ს შედეგი ან უბრალოდ ბოლო ბლოკის ჰეში, არ აქვს მნიშვნელობა, სანამ ის ყოველ ჯერზე იცვლება. და თანმიმდევრულია) და შექმენით მისთვის BLS ხელმოწერა. თაობის შედეგი არაპროგნოზირებადი იქნება მანამ, სანამ 67 მონაწილე არ მოგვაწოდებს თავის ნაწილებს და ამის შემდეგ გამომავალი უკვე წინასწარ არის განსაზღვრული და ვერ იქნება დამოკიდებული რომელიმე მონაწილის ქმედებებზე.

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

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

დასასრულს

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

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

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

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

Მალე გნახავ!

წყარო: www.habr.com