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

Ey Habr!

В birinci bölüm Bu yazıda, birbirlerine güvenmeyen katılımcılar için rastgele sayılar üretmenin neden gerekli olabileceğini, bu tür rastgele sayı üreteçleri için hangi gereksinimlerin öne sürüldüğünü tartıştık ve bunların uygulanmasına yönelik iki yaklaşımı ele aldık.

Yazının bu bölümünde eşik imzaları kullanan başka bir yaklaşıma daha yakından bakacağız.

Biraz kriptografi

Eşik imzalarının nasıl çalıştığını anlamak için biraz temel kriptografiyi anlamanız gerekir. İki kavram kullanacağız: küçük harflerle göstereceğimiz skalerler veya basitçe sayılar (x, y) ve eliptik eğri üzerinde büyük harflerle göstereceğimiz noktalar.

Eşik imzalarının temellerini anlamak için birkaç temel şey dışında eliptik eğrilerin nasıl çalıştığını anlamanıza gerek yoktur:

1. Eliptik bir eğri üzerindeki noktalar bir skalerle toplanabilir ve çarpılabilir (çarpmayı bir skalerle şu şekilde göstereceğiz: xGnotasyonu olmasına rağmen Gx literatürde de sıklıkla kullanılmaktadır). Toplamanın ve bir skalerle çarpmanın sonucu eliptik bir eğri üzerinde bir noktadır.

2. Sadece asıl noktayı bilmek G ve bunun skaler çarpımı xG hesaplanamaz x.

Ayrıca polinom kavramını da kullanacağız. p(x) степени k-1. Özellikle polinomların aşağıdaki özelliğini kullanacağız: eğer değerini biliyorsak p(x) herhangi k farklı x (ve hakkında daha fazla bilgimiz yok) p(x)), hesaplayabiliriz p(x) başkası için x.

Herhangi bir polinom için ilginçtir p(x) ve eğri üzerinde bir nokta Ganlamını bilmek p(x)G herhangi k Farklı anlamlar xayrıca hesaplayabiliriz p(x)G herhangi x.

Bu, eşik imzalarının nasıl çalıştığına ve bunların rastgele sayılar oluşturmak için nasıl kullanılacağına ilişkin ayrıntılara girmek için yeterli bilgidir.

Eşik imzalarında rastgele sayı üreteci

Diyelim ki n katılımcılar rastgele bir sayı oluşturmak istiyor ve biz de herkesin katılmasını istiyoruz k bir sayı oluşturmaya yetecek kadar sayıda vardı, ancak kontrolü elinde bulunduran saldırganlar k-1 veya daha az katılımcı, oluşturulan sayıyı tahmin edemedi veya etkileyemedi.

Diyelim ki böyle bir polinom var p(x) степени k-1 ilk katılımcının bildikleri p (1)ikincisi biliyor p(2), ve benzeri (n-th biliyor p(n)). Ayrıca önceden belirlenmiş bir nokta için şunu varsayıyoruz: G herkes bilir p(x)G tüm değerler için x. Arayacağız p(i) “özel bileşen” ikatılımcı (çünkü yalnızca ikatılımcı onu tanıyor) ve domuz “kamu bileşeni” i-inci katılımcı (çünkü tüm katılımcılar onu tanıyor). Hatırlayacağınız gibi, bilgi domuz geri yüklemek için yeterli değil p(i).

Böyle bir polinom oluşturmak, böylece yalnızca i-İlk katılımcı ve hiç kimse onun özel bileşenini bilmiyordu - bu, protokolün en karmaşık ve ilginç kısmıdır ve bunu aşağıda analiz edeceğiz. Şimdilik böyle bir polinomumuz olduğunu ve tüm katılımcıların kendi özel bileşenlerini bildiğini varsayalım.

Böyle bir polinomu rastgele bir sayı oluşturmak için nasıl kullanabiliriz? Başlangıç ​​olarak, daha önce jeneratöre girdi olarak kullanılmamış bir diziye ihtiyacımız var. Blockchain durumunda son bloğun karması h böyle bir hat için iyi bir adaydır. Katılımcıların aşağıdakileri kullanarak rastgele bir sayı oluşturmak istemesine izin verin: h tohum gibi. Katılımcılar ilk önce dönüşür h önceden tanımlanmış herhangi bir fonksiyonu kullanarak eğri üzerindeki bir noktaya:

H = skalerToPoint(h)

Daha sonra her katılımcı i hesaplar ve yayınlar Merhaba = p(i)H, ne yapabilirler çünkü biliyorlar p(i) ve H. ifşa Hdiğer katılımcıların özel bileşeni geri yüklemesine izin vermiyorum ikatılımcıdır ve bu nedenle bloktan bloğa bir dizi özel bileşen kullanılabilir. Bu nedenle, aşağıda açıklanan pahalı polinom oluşturma algoritmasının yalnızca bir kez yürütülmesi gerekir.

Ne zaman k katılımcılara otopsi yapıldı Merhaba = p(i)H, herkes hesaplayabilir Hx = p(x)H herkes için x Son bölümde tartıştığımız polinomların özelliği sayesinde. Şu anda tüm katılımcılar hesaplıyor H0 = p(0)H, ve bu elde edilen rastgele sayıdır. Lütfen kimsenin bilmediğini unutmayın p(0), ve bu nedenle hesaplamanın tek yolu p(0)H – bu enterpolasyondur p(x)H, bu ancak şu durumlarda mümkündür k değerler p(i)H bilinen. Daha küçük miktarların açılması p(i)H hakkında herhangi bir bilgi vermiyor p(0)H.

Yukarıdaki oluşturucu istediğimiz tüm özelliklere sahiptir: yalnızca saldırganların kontrolü k-1 veya daha az katılımcının sonuç üzerinde hiçbir bilgisi veya etkisi yoktur. k katılımcılar ortaya çıkan sayıyı ve bunların herhangi bir alt kümesini hesaplayabilir. k katılımcılar her zaman aynı tohum için aynı sonuca ulaşacaktır.

Yukarıda dikkatle kaçındığımız bir sorun var. Enterpolasyonun çalışması için değerin olması önemlidir. Hher katılımcı tarafından yayınlanan i i gerçekten aynıydı p(i)H. Kimse dışında kimse olmadığı için i-inci katılımcı bilmiyor p(i), dışında hiç kimse i-katılımcı bunu doğrulayamıyor Hi aslında doğru bir şekilde hesaplanmış ve herhangi bir kriptografik doğruluk kanıtı olmadan Hbir saldırgan herhangi bir değeri şu şekilde yayınlayabilir: Merhaba, ve rastgele sayı üretecinin çıktısını keyfi olarak etkiler:

İlk katılımcı tarafından gönderilen farklı H_1 değerleri, farklı sonuçtaki H_0'a yol açar

Doğruluğunu kanıtlamanın en az iki yolu vardır HPolinomun oluşturulmasını analiz ettikten sonra bunları dikkate alacağız.

Polinom üretimi

Son bölümde böyle bir polinomumuz olduğunu varsaydık. p(x) степени k-1 katılımcının i O biliyor p(i)ve bu değer hakkında kimsenin bilgisi yok. Bir sonraki bölümde önceden belirlenmiş bir nokta için buna da ihtiyacımız olacak. G herkes biliyordu p(x)G herkes için x.

Bu bölümde her katılımcının yerel olarak bazı özel anahtarlara sahip olduğunu varsayacağız. xi, öyle ki herkes karşılık gelen genel anahtarı bilsin Xi.

Olası bir polinom oluşturma protokolü aşağıdaki gibidir:

1. Her katılımcı i yerel olarak keyfi bir polinom oluşturur pi(x) derece k-1. Daha sonra her katılımcıya gönderirler j değer pi(j), genel anahtarla şifrelenmiş Xj. Böylece yalnızca i-inci и j-inci katılımcı biliyor pi(j). Katılımcı i ayrıca kamuoyuna duyurulur pi(j)G herkes için j itibaren 1 karşı k dahil.

2. Tüm katılımcılar seçim yapmak için bir fikir birliği kullanır k polinomları kullanılacak katılımcılar. Bazı katılımcılar çevrimdışı olabileceğinden herkes bitene kadar bekleyemeyiz. n katılımcılar polinomları yayınlayacak. Bu adımın sonucu bir kümedir Z en azından oluşan k (1) adımda oluşturulan polinomlar.

3. Katılımcılar bildikleri değerlerin doğru olduğundan emin olurlar. pi(j) kamuya duyurulanlara karşılık gelir pi(j)G. Bu adımdan sonra Z yalnızca özel olarak iletilen polinomlar pi(j) kamuya duyurulanlara karşılık gelir pi(j)G.

4. Her katılımcı j özel bileşenini hesaplar p(j) toplam olarak pi(j) herkes için i в Z. Her katılımcı ayrıca tüm değerleri hesaplar p(x)G toplam olarak tüm i için pi(x)G в Z.

Lütfen dikkat: p(x) – bu gerçekten bir polinom k-1, çünkü bu bireyin toplamıdır pi(x), her biri derece polinomudur k-1. Daha sonra, her katılımcının j O biliyor p(j), hakkında hiçbir bilgileri yok p(x) için x ≠j. Aslında bu değeri hesaplamak için her şeyi bilmeleri gerekiyor. pi(x), ve katılımcı olduğu sürece j Seçilen polinomlardan en az birini bilmiyor, hakkında yeterli bilgiye sahip değil p(x).

Bu, son bölümde ihtiyaç duyulan polinom oluşturma sürecinin tamamıdır. Yukarıdaki 1, 2 ve 4. adımların oldukça açık bir uygulaması vardır. Ancak 3. adım o kadar da önemsiz değil.

Özellikle şifrelenmiş olduğunu kanıtlayabilmemiz gerekiyor. pi(j) gerçekten yayınlananlara karşılık geliyor pi(j)G. Kanıtlayamazsak saldırgan i bunun yerine çöp gönderebilir pi(j) katılımcıya jve katılımcı j gerçek anlamını bulamayacak pi(j), ve özel bileşenini hesaplayamayacak.

Ek bir mesaj oluşturmanıza olanak tanıyan bir şifreleme protokolü vardır kanıti(j), öyle ki herhangi bir katılımcının bir değeri vardır e, hem de kanıt(j) и pi(j)G, bunu yerel olarak doğrulayabilir e - gerçek pi(j), katılımcının anahtarıyla şifrelenir j. Ne yazık ki, bu tür kanıtların boyutu inanılmaz derecede büyüktür ve yayınlanmasının gerekli olduğu göz önüne alındığında, O(nk) Bu deliller bu amaçla kullanılamaz.

Bunu kanıtlamak yerine pi(j) maçlar pi(j)G'de polinom oluşturma protokolüne, tüm katılımcıların alınan şifrelenmiş verileri kontrol ettiği çok geniş bir zaman dilimi ayırabiliriz. pi(j), ve şifresi çözülen mesaj halka karşılık gelmiyorsa pi(j)G, aldıkları şifreli mesajın yanlış olduğuna dair kriptografik bir kanıt yayınlıyorlar. Mesajın olduğunu kanıtla hayır maçlar domuz) eşleştiğini kanıtlamaktan çok daha kolaydır. Bunun, her katılımcının bu tür kanıtları oluşturmak için ayrılan süre içinde en az bir kez çevrimiçi görünmesini gerektirdiği ve böyle bir kanıtı yayınlamaları halinde bunun diğer tüm katılımcılara aynı ayrılan sürede ulaşacağı varsayımına dayandığı unutulmamalıdır.

Bir katılımcı bu süre zarfında çevrimiçi görünmediyse ve en az bir hatalı bileşene sahipse, bu durumda söz konusu katılımcı daha sonraki sayı oluşturmaya katılamayacaktır. Bununla birlikte, en azından bir şey varsa, protokol yine de işlev görecektir. k Doğru bileşenleri yeni alan veya ayrılan süre içinde yanlışlık kanıtını bırakmayı başaran katılımcılar.

H_i'nin doğruluğunun kanıtları

Tartışılması gereken son kısım, yayınlanan bilgilerin doğruluğunun nasıl kanıtlanacağıdır. Hben yani Merhaba = p(i)H, açmadan p(i).

Değerleri hatırlayalım. H, G, p(i)G kamuoyuna açık ve herkes tarafından biliniyor. Alma işlemi p(i) bilme domuz и G ayrık logaritma denir veya günlük, ve şunu kanıtlamak istiyoruz:

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

ifşa edilmeden p(i). Bu tür kanıtların yapıları mevcuttur, örneğin Schnorr Protokolü.

Bu tasarımla her katılımcı, Hi Tasarıma göre doğruluğunun kanıtını gönderir.

Rastgele bir sayı üretildiğinde, genellikle onu üretenler dışındaki katılımcılar tarafından kullanılması gerekir. Bu tür katılımcılar numarayla birlikte tümünü göndermelidir. Hi ve ilgili kanıtlar.

Meraklı bir okuyucu şunu sorabilir: Son rastgele sayı olduğundan H0 ve p(0)G – Bu kamuya açık bir bilgi, neden her birey için kanıta ihtiyacımız var? Hben, neden bunun yerine kanıt göndermiyorsun?

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

Sorun şu ki böyle bir kanıt Schnorr Protokolü kullanılarak oluşturulamıyor çünkü kimse değerini bilmiyor p (0)Kanıtı oluşturmak için gerekli olan rasgele sayı üretecinin tamamı, bu değeri kimsenin bilmediği gerçeğine dayanmaktadır. Bu nedenle tüm değerlerin olması gerekir Hi ve doğruluğunu kanıtlayacak bireysel kanıtları H0.

Ancak eliptik eğriler üzerindeki noktalarda semantik olarak çarpma işlemine benzeyen bazı işlemler yapılmışsa doğruluğun ispatı H0 önemsiz olurdu, sadece bundan emin olurduk

H0 × G = p(0)G × H

Seçilen eğri destekliyorsa eliptik eğri eşleşmeleri, bu kanıt işe yarıyor. Bu durumda H0 yalnızca rastgele sayı üretecinin çıktısı değildir ve bunu bilen herhangi bir katılımcı tarafından doğrulanabilir. G, H и p(0)G. H0 aynı zamanda tohum olarak kullanılan mesajdaki imzadır ve şunu doğrular: k и n katılımcılar bu mesajı imzaladılar. Böylece eğer tohum - blockchain protokolündeki bloğun karması, o zaman H0 hem bir blokta çoklu imza hem de çok iyi bir rastgele sayıdır.

Sonuç olarak

Bu makale teknik blog serisinin bir parçasıdır 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