Birbirimize güvenmezsek rastgele sayılar üretmek mümkün müdür? Bölüm 1

Ey Habr!

Bu yazımda birbirlerine güvenmeyen katılımcıların sahte rastgele sayılar üretmesinden bahsedeceğim. Aşağıda göreceğimiz gibi, "neredeyse" iyi bir jeneratörü hayata geçirmek oldukça basittir, ancak çok iyi bir jeneratörü uygulamak zordur.

Birbirine güvenmeyen katılımcılar arasında rastgele sayılar üretmek neden gerekli olsun ki? Bir uygulama alanı merkezi olmayan uygulamalardır. Örneğin, bir katılımcıdan bahis kabul eden ve tutarı %49 olasılıkla ikiye katlayan veya %51 olasılıkla geri alan bir uygulama, ancak tarafsız bir şekilde rastgele bir sayı alabiliyorsa işe yarayacaktır. Eğer bir saldırgan rastgele sayı üretecinin sonucunu etkileyebilirse ve hatta uygulamada ödeme alma şansını biraz bile arttırabilirse, onu kolayca mahvedecektir.

Dağıtılmış bir rastgele sayı üretme protokolü tasarladığımızda bunun üç özelliğe sahip olmasını isteriz:

1. Tarafsız olması gerekir. Başka bir deyişle, hiçbir katılımcı rastgele sayı üretecinin sonucunu hiçbir şekilde etkilememelidir.

2. Tahmin edilemez biri olmalı. Başka bir deyişle, hiçbir katılımcı hangi sayının üretileceğini tahmin edememeli (veya bu sayının herhangi bir özelliğini çıkaramamalıdır).

3. Protokolün geçerli olması, yani katılımcıların belirli bir yüzdesinin ağ bağlantısını kesmesine veya protokolü kasıtlı olarak durdurmaya çalışmasına karşı dayanıklı olması gerekir.

Bu yazıda iki yaklaşıma bakacağız: RANDAO + VDF ve kod silme yaklaşımı. Bir sonraki bölümde eşik imzalara dayalı yaklaşımı detaylı olarak inceleyeceğiz.

Ancak önce uygulanabilir, tahmin edilemeyen ancak önyargılı, basit ve yaygın olarak kullanılan bir algoritmaya bakalım.

RANDAO

RANDAO, rastgelelik oluşturmaya yönelik çok basit ve dolayısıyla oldukça yaygın olarak kullanılan bir yaklaşımdır. Tüm ağ katılımcıları önce yerel olarak sözde rastgele bir sayı seçer, ardından her katılımcı seçilen sayının bir karmasını gönderir. Daha sonra katılımcılar sırayla seçtikleri sayıları ortaya çıkarır ve ortaya çıkan sayılar üzerinde XOR işlemi gerçekleştirir ve bu işlemin sonucu protokolün sonucu olur.

Saldırganın diğer katılımcıların numaralarını gördükten sonra kendi numarasını seçememesi için rakamları açıklamadan önce karmaların yayınlanması adımı gereklidir. Bu, rastgele sayı üretecinin çıktısını neredeyse tek başına belirlemesine olanak tanıyacaktı.

Protokol süresince katılımcıların iki kez ortak bir karara (sözde konsensüs) varmaları gerekir: seçilen sayıları ne zaman açıklamaya başlayacak ve dolayısıyla karmaları kabul etmeyi bırakacaklar ve seçilen sayıları kabul etmeyi ve sonuçta ortaya çıkan rastgele hesaplamayı ne zaman bırakacaklar? sayı. Birbirlerine güvenmeyen katılımcılar arasında bu tür kararların alınması, başlı başına kolay bir iş değildir ve bu konuya gelecek yazılarda döneceğiz; bu yazıda böyle bir konsensüs algoritmasının elimizde olduğunu varsayacağız.

RANDAO yukarıda anlattığımız özelliklerden hangisine sahiptir? Tahmin edilemez, temel konsensüs protokolüyle aynı canlılığa sahiptir, ancak taraflıdır. Özellikle, bir saldırgan ağı gözlemleyebilir ve diğer katılımcılar numaralarını açıkladıktan sonra XOR'larını hesaplayabilir ve sonucu etkilemek için numarasını açıklayıp açıklamayacağına karar verebilir. Bu, saldırganın rastgele sayı üretecinin çıktısını tek başına belirlemesini engellese de ona yine de 1 bitlik etki sağlar. Saldırganlar birden fazla katılımcıyı kontrol ediyorsa, kontrol ettikleri bit sayısı, kontrolleri altındaki katılımcı sayısına eşit olacaktır.

Katılımcıların sayıları sırayla açıklamaları istenerek saldırganların etkisi büyük ölçüde azaltılabilir. Daha sonra saldırgan, ancak en son açıldığında sonucu etkileyebilecektir. Etki önemli ölçüde daha az olsa da algoritma hala önyargılıdır.

RANDAO+VDF

RANDAO'yu tarafsız kılmanın bir yolu şudur: Tüm sayılar ortaya çıktıktan ve XOR hesaplandıktan sonra, sonucu bir fonksiyonun girişine beslenir, hesaplaması çok uzun zaman alır ancak hesaplamanın doğruluğunu kontrol etmenize olanak tanır. çok hızlı hesaplama.

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

Bu fonksiyona Doğrulanabilir Gecikme Fonksiyonu veya VDF denir. Nihai sonucun hesaplanması sayının açıklanması aşamasından daha uzun sürerse, saldırgan numarasını göstermenin veya gizlemenin etkisini tahmin edemeyecek ve dolayısıyla sonucu etkileme fırsatını kaybedecektir.

İyi VDF'ler geliştirmek son derece zordur. Son zamanlarda birçok atılım gerçekleşti; bu и bu bu da VDF'yi pratikte daha pratik hale getirdi ve Ethereum 2.0, uzun vadede rastgele sayı kaynağı olarak VDF ile RANDAO'yu kullanmayı planlıyor. Bu yaklaşımın öngörülemez ve tarafsız olmasının yanı sıra, ağda en az iki katılımcının mevcut olması durumunda geçerli olma gibi ek bir faydası da vardır (kullanılan fikir birliği protokolünün bu kadar az sayıda katılımcıyla çalışıldığında geçerli olduğu varsayılarak).

Bu yaklaşımın en büyük zorluğu VDF'yi, çok pahalı özel donanıma sahip bir katılımcının bile keşif aşamasının bitiminden önce VDF'yi hesaplayamayacağı şekilde ayarlamaktır. İdeal durumda algoritmanın önemli bir güvenlik marjına (örneğin 10x) sahip olması gerekir. Aşağıdaki şekil, RANDAO onayını ortaya çıkarmak için ayrılan süreden daha hızlı bir VDF çalıştırmasını sağlayan özel bir ASIC'e sahip bir aktörün saldırısını göstermektedir. Böyle bir katılımcı yine de nihai sonucu numarasını kullanarak veya kullanmayarak hesaplayabilir ve ardından hesaplamaya dayanarak bunu gösterip göstermemeyi seçebilir.

Yukarıda bahsedilen VDF ailesi için özel bir ASIC'in performansı, geleneksel donanıma göre 100'den fazla kat daha yüksek olabilir. Dolayısıyla, dağıtım aşaması 10 saniye sürerse, böyle bir ASIC üzerinde hesaplanan VDF'nin 100 kat güvenlik marjına sahip olması için 10 saniyeden fazla sürmesi gerekir ve dolayısıyla ticari donanımda hesaplanan aynı VDF'nin 100 x 100 saniye = ~3 saat sürmesi gerekir.

Ethereum Vakfı, halka açık kendi ücretsiz ASIC'lerini oluşturarak bu sorunu çözmeyi planlıyor. Bu gerçekleştiğinde, diğer tüm protokoller de bu teknolojiden yararlanabilir ancak o zamana kadar, kendi ASIC'lerini geliştirmeye yatırım yapamayan protokoller için RANDAO+VDF yaklaşımı geçerli olmayacaktır.

VDF ile ilgili birçok makale, video ve diğer bilgiler şu adreste toplanmıştır: bu site.

Silme kodlarını kullanıyoruz

Bu bölümde rastgele sayı üretme protokolüne bakacağız. kodları silme. Hayatta kalarak ⅓'e kadar saldırganı tolere edebilir ve sonucu tahmin etmeden veya etkilemeden önce ⅔'ye kadar saldırganın var olmasına izin verir.

Protokolün ana fikri şu şekildedir. Kolaylık olması açısından tam olarak 100 katılımcının olduğunu varsayalım. Ayrıca tüm katılımcıların yerel olarak bazı özel anahtarlara sahip olduğunu ve tüm katılımcıların genel anahtarlarının tüm katılımcılar tarafından bilindiğini varsayalım:

1. Her katılımcı yerel olarak uzun bir dizeyle gelir, onu 67 parçaya böler, herhangi 100'si dizeyi kurtarmak için yeterli olacak şekilde 67 paylaşım elde etmek için silme kodları oluşturur, 100 paylaşımın her birini katılımcılardan birine atar ve bunları şifreler. aynı katılımcının ortak anahtarı. Daha sonra tüm kodlanmış paylaşımlar yayınlanır.

2. Katılımcılar, belirli 67 katılımcının kodlanmış kümeleri üzerinde anlaşmaya varmak için bir tür fikir birliğine varırlar.

3. Mutabakata varıldığında, her katılımcı 67 setin her birindeki şifrelenmiş paylaşımları kendi genel anahtarıyla şifreleyerek alır, tüm bu paylaşımların şifresini çözer ve bu şifresi çözülmüş tüm paylaşımları yayınlar.

4. 67 katılımcı (3) adımını tamamladıktan sonra, üzerinde anlaşmaya varılan tüm kümelerin kodu, silme kodlarının özelliklerinden dolayı tamamen çözülebilir ve yeniden oluşturulabilir ve son sayı, katılımcıların (1)'de başladığı ilk satırların XOR'u olarak elde edilebilir. .

Bu protokolün tarafsız ve öngörülemez olduğu gösterilebilir. Ortaya çıkan rastgele sayı, fikir birliğine varıldıktan sonra belirlenir, ancak katılımcıların ⅔'ü kendi genel anahtarlarıyla şifrelenmiş parçaların kodunu çözene kadar kimse tarafından bilinmez. Böylece rastgele sayı, onu yeniden yapılandırmaya yetecek bilgi yayınlanmadan önce belirlenir.

Adım (1)'de katılımcılardan biri diğer katılımcılara bazı dizeler için doğru silme kodu olmayan kodlanmış paylaşımlar gönderirse ne olur? Ek değişiklikler olmadan, farklı katılımcılar ya dizeyi hiç kurtaramayacak ya da farklı dizeleri kurtaracak, bu da farklı katılımcıların farklı bir rastgele sayı almasıyla sonuçlanacaktır. Bunu önlemek için şunları yapabilirsiniz: Her katılımcı, kodlanmış paylaşımlara ek olarak ayrıca hesaplar. Merkla ağacı tüm bu paylaşımlar ve her katılımcıya hem kodlanmış paylaşımın kendisini hem de merkle ağacının kökünü ve paylaşımın merkle ağacına dahil edildiğine dair kanıtı gönderir. Adım (2)'deki fikir birliğine varıldığında, katılımcılar sadece bir dizi set üzerinde değil, aynı zamanda bu tür ağaçların bir dizi spesifik kökü üzerinde de anlaşmaya varırlar (eğer bazı katılımcılar protokolden sapmış ve farklı katılımcılara farklı merkle ağacı kökleri göndermişse, ve bu tür iki kök fikir birliği sırasında gösterilir, onun satırı sonuç kümesine dahil edilmez). Mutabakatın bir sonucu olarak, 67 kodlanmış çizgiye ve merkle ağacının karşılık gelen köklerine sahip olacağız, böylece 67 satırın her biri için en az 67 katılımcı (ilgili satırları önerenlerin aynısı olması gerekmez) olacak. silme kodunun bir paylaşımını içeren bir mesaj ve ilgili ağaçtaki paylaşımlarının soluklaştığının kanıtı.

Adım (4)'te katılımcı belirli bir tel için 67 vuruşun şifresini çözdüğünde ve orijinal teli bunlardan yeniden oluşturmaya çalıştığında, seçeneklerden biri mümkündür:

1. Dize geri yüklenir ve daha sonra tekrar silinerek kodlanırsa ve yerel olarak hesaplanan paylaşımlar için Merkle ağacı hesaplanırsa kök, üzerinde fikir birliğine varılan ağaçla çakışır.

2. Satır geri yüklenir, ancak yerel olarak hesaplanan kök, fikir birliğine varılan kökle eşleşmiyor.

3. Satır geri yüklenmedi.

Yukarıdaki seçeneklerden en az bir katılımcı için (1) seçeneğinin gerçekleşmesi durumunda, (1) seçeneğinin tüm katılımcılar için gerçekleştiğini ve tam tersi, (2) veya (3) seçeneğinin en az bir katılımcı için gerçekleşmesi halinde, o zaman bunun tersini göstermek kolaydır. tüm katılımcılar için (2) veya (3) numaralı seçenek gerçekleşecektir. Böylece, setteki her satır için, ya tüm katılımcılar onu başarıyla kurtaracak ya da tüm katılımcılar onu kurtaramayacak. Ortaya çıkan rastgele sayı, yalnızca katılımcıların kurtarabildiği satırların bir XOR'udur.

Eşik imzaları

Rastgeleliğe başka bir yaklaşım, BLS eşik imzaları olarak adlandırılanları kullanmaktır. Eşik imzalarına dayalı bir rastgele sayı üreteci, yukarıda açıklanan silme kodu tabanlı algoritmayla tamamen aynı garantilere sahiptir, ancak üretilen her sayı için ağ üzerinden gönderilen asimptotik mesaj sayısı önemli ölçüde daha düşüktür.

BLS imzaları, birden fazla katılımcının bir mesaj için ortak bir imza oluşturmasına olanak tanıyan bir tasarımdır. Bu imzalar genellikle birden fazla imzanın gönderilmesini gerektirmediğinden alan ve bant genişliğinden tasarruf etmek için kullanılır. 

Rastgele sayılar üretmenin yanı sıra, blockchain protokollerindeki BLS imzaları için yaygın bir uygulama, BFT protokollerindeki blok imzalamadır. Diyelim ki 100 katılımcı blok oluşturuyor ve 67'sinin imzaladığı blok nihai kabul ediliyor. Hepsi BLS imzasının kendi kısımlarını gönderebilir ve bazı fikir birliği algoritmaları kullanarak 67 tanesi üzerinde anlaşabilir ve ardından bunları tek bir BLS imzasında birleştirebilir. Nihai imzayı oluşturmak için herhangi bir 67 (veya daha fazla) parça kullanılabilir; bu, hangi 67 imzanın birleştirildiğine bağlı olacaktır ve bu nedenle farklılık gösterebilir, ancak 67 katılımcının farklı seçimleri farklı bir imza oluşturacaktır; bu tür herhangi bir imza geçerli olacaktır. Blok için imza. Geriye kalan katılımcıların ağ üzerinden 67 imza yerine blok başına yalnızca bir imza alması ve doğrulaması gerekiyor, bu da ağ üzerindeki yükü önemli ölçüde azaltıyor.

Katılımcıların kullandığı özel anahtarlar belirli bir şekilde oluşturulmuşsa, hangi 67 imzanın (veya daha fazla, ancak daha az değil) bir araya toplandığı önemli değil, ortaya çıkan imzanın aynı olacağı ortaya çıktı. Bu bir rastgelelik kaynağı olarak kullanılabilir: katılımcılar ilk önce imzalayacakları bir mesaj üzerinde anlaşırlar (bu RANDAO'nun çıktısı olabilir veya sadece son bloğun karması olabilir, her seferinde değiştiği sürece gerçekten önemli değil) ve tutarlıdır) ve bunun için bir BLS imzası oluşturun. Üretimin sonucu, 67 katılımcı kendi rolünü sağlayana kadar tahmin edilemez olacak ve bundan sonra çıktı zaten önceden belirlenmiş olacak ve herhangi bir katılımcının eylemlerine bağlı olamayacak.

Rastgeleliğe yönelik bu yaklaşım, çevrimiçi katılımcıların en az ⅔'sinin protokolü takip ettiği sürece geçerlidir ve katılımcıların en az ⅓'ü protokolü takip ettiği sürece tarafsız ve öngörülemezdir. Katılımcıların ⅓'ünden fazlasını ancak ⅔'sinden azını kontrol eden bir saldırganın protokolü durdurabileceğini ancak çıktısını tahmin edemeyeceğini veya etkileyemeyeceğini unutmamak önemlidir.

Eşik imzalarının kendisi oldukça ilginç bir konudur. Makalenin ikinci bölümünde bunların nasıl çalıştığını ve eşik imzalarının rastgele sayı üreteci olarak kullanılabilmesi için katılımcı anahtarlarının tam olarak nasıl oluşturulması gerektiğini ayrıntılı olarak analiz edeceğiz.

Sonuç olarak

Bu makale bir dizi teknik blog makalesinin ilkidir NEAR. NEAR, son kullanıcılar için geliştirme kolaylığı ve kullanım kolaylığına önem veren, merkezi olmayan uygulamalar geliştirmeye yönelik bir blockchain protokolü ve platformudur.

Protokol kodu açık, uygulamamız Rust'ta yazılmış, bulunabilir burada.

NEAR'a yönelik geliştirmenin nasıl göründüğünü görebilir ve çevrimiçi IDE'de denemeler yapabilirsiniz. burada.

Tüm haberleri Rusça olarak takip edebilirsiniz. telgraf grubu ve VKontakte'de grupve resmi olarak İngilizce olarak heyecan.

Yakında görüşürüz!

Kaynak: habr.com