"Blockchain zayıflama yöntemi" RSA akümülatörünün derinlemesine araştırılması
Önsöz: RSA akümülatörü ile ilgili olarak, bir önceki makalede "RSA Akümülatörü, bir blok zinciri zayıflama eseri mi? "Ethereum'un kurucusu Vitalik'in hesaplamasıyla, RSA akümülatörünü kullandıktan sonra, orijinal 2.5 GB Plazma alt zinciri verisi 3.6 MB'a sıkıştırılabilir ve sıkıştırma oranı şaşırtıcı bir şekilde% 99.856'ya ulaştı.
Bununla birlikte, bu teknoloji, orijinal tasarımında güvenilir ayarlar gerektirir ve Stanford Üniversitesi'nden Applied Cryptography Group, "IOP ve Stateless Blockchain için Akümülatör Toplu İşleme" başlıklı bir makale yayınladı. Teknoloji "belgesi, bir tür Sınıf grubu ve Güvenilir ayar gerekmez Akümülatör yöntemi, bu akümülatörler, durumsuz bir blok zinciri oluşturmak için (hangi blokların geçerli olduğundan emin olmak için tüm durumu depolaması gerekmeyen düğümlere atıfta bulunur) ve verimli UTXO taahhüdü elde etmek için kullanılabilir.
Bu makalede, Ethereum blockchain ölçeklenebilirliği ve güvenlik araştırmacısı Georgios Konstantopoulos, makaleyi gözden geçirip ilgili bir özet çıkardı.
(Resim: pexels.com)
Bu makalede, RSA akümülatörünü derinlemesine keşfetmeye çalışacağız ve Stanford Üniversitesi Uygulamalı Kriptografi Grubu tarafından yakın zamanda yayınlanan makaleyi gözden geçireceğiz.Bu çok önemli makale Benedikt Bunz, Ben Fisch ve Dan Boneh tarafından ortaklaşa yazılmıştır ve başlığı "GİB ve durum bilgisiz blok zinciri için akümülatör toplu teknolojisi".
Bu tekniği daha iyi anlamak için herkesin matematiği gözden geçirmesi şiddetle tavsiye edilir.
arka fon
1994 yılından bu yana akümülatör, akademide büyük ilgi gören bir konu haline geldi. Merkle Ağacı'na benzer ve bir veri setinin bilgisini kriptografik olarak vaat etmek için kullanılır. Daha sonra, veri setinin bir alt kümesinin üyeliğini kanıtlamak için bir sertifika verilebilir. Merkle Ağacı yapısında, kanıt Merkle dalı (veya Merkel kanıtı) olarak adlandırılır ve taahhüt verilerinin boyutu logaritma olarak büyür.
Öte yandan, akümülatörler, sabit bir boyutta üyelik kanıtına ve birden çok öğenin toplu ispatına izin verir (Merkel ağacında bu özellik yoktur).
Bu makalenin odak noktası, RSA akümülatörlerinin blokları nasıl oluşturduklarını, üyelik ve üyelik olmama kanıtlarının nasıl oluşturulacağını ve bunları birden çok blok arasında nasıl gruplandırılacağını açıklamaktır. Bu özel teknolojinin UTXO tabanlı Plazma uygulamaları da vardır ve ortaya çıkan Plazma birincil varyantları üretilmiştir. UTXO setlerinin Plazmada sıkıştırılmasına izin veren bir akümülatör tasarlamak çok çaba gerektirir.
Sorumluluk Reddi: Basitlik adına, yazar bu makaledeki yorumları kararttı (örneğin, G $ 'da $ U, W \ veya modüler aritmetikte mod N içermez).
Sözlük (tanım kaynağı):
akümülatör : "Bir dizi öğe için kısa vadeli bağlayıcı taahhütler ve ayrıca setteki herhangi bir öğe için kısa vadeli üyelik ve üyelik dışı sertifikalar oluşturan bir kriptografik biriktirici."
Dinamik akümülatör : "Toplanan eleman sayısıyla ilgisi olmayan, O (1) maliyetine sahip eleman biriktiricileri ekleme ve silme desteği."
Genel akümülatör : "Üyeliği ve üye olmayan tanımlamayı destekleyen dinamik bir biriktirici."
Toplu işlem : N sertifikanın toplu doğrulaması, tek bir sertifikanın doğrulanmasından n kat daha hızlıdır.
polimerizasyon : Sabit büyüklükte bir provada n üye ispatı toplayın.
Bilinmeyen sıra grubu : Grubun sırası, koleksiyonundaki öğelerin sayısıdır. Sağlanan ispatın güvenliğini sağlamak için, bir dizi bilinmeyen dizinin üretilmesi gerekir (aksi takdirde toplayıcıda kullanılan modülün bilinen bir çarpanlara ayırması vardır ve yanlış bir kanıt yaratılabilir). Bunun oluşturulması çoklu hesaplamalarla yapılabilir, ancak jeneratör üretilen sayının faktöriyelini almak için bir araya gelirse güvenli değildir. Sınıf grubu kullanılarak güvenilir ayarlar olmadan oluşturulabilir (not: bu çok önemlidir).
Örtülü sipariş grubunun kısa kanıtı
Wesolowski, üstel şemanın bilgi kanıtını önerdi. Kanıtlayıcı, doğrulayıcıyı bir x sayısını bildiklerine ikna etmeye çalışır, böylece u ^ x = w, bilinen bir u tabanı ile kurulur.
Bir örnek alalım, 2'yi taban olarak alalım (u = 2), w = 16, sonra x = 4. Biz ne yaptık? Doğrulayıcıya X'i göndeririz, 2 ^ 4 gerçekleştirmeleri ve sonucu W'ye karşı kontrol etmeleri gerekir. Eğer eşleşirlerse buna inanacaklar. Aşağıdaki iki adım aşikardır:
Bu zorluğu hangi anlaşmanın çözebileceğini görelim. Bu protokoller etkileşimlidir, yani doğrulayıcı ve kanıtlayıcı birbirine "meydan okumalar" gönderir.Bu zorluklar, protokolün güvenliğini sağlamak için protokolün sonraki adımlarında kullanılacaktır.
Üs alma kanıtı (PoE, Bölüm 3.1)
İlk olarak, tüm üs alma işlemini çalıştırmadan doğrulayıcıları nasıl ikna edeceğimize bakalım.
Üs alma kanıtı (Not: Makalenin geçerli sürümünde küçük bir hata var. 8. sayfada yazar u ^ q yerine q = g ^ q ayarlıyor.
"Bu protokol, yalnızca doğrulayıcı r'yi u ^ x'ten daha hızlı hesaplayabildiğinde yararlıdır. Üs alma sorununu çözer, ancak yine de kanıtlayıcının doğrulayıcıya potansiyel büyük bir x iletmesini gerektirir veya x herkese açıksa nın-nin."Ayrık logaritmaların bilgi kanıtı (PoKE, bölüm 3.3)
X'i iletmek yerine r'yi iletebiliriz. İspat (Q, r) olur ve doğrulayıcı ek olarak r'nin l'den (PoKE * protokolü) küçük olup olmadığını kontrol etmelidir. Rakip üssü seçmekte özgür olduğunda, bu güvensiz olacaktır!
Doğrulayıcı, kanıtlayıcı tarafından kandırılır, z: u ^ z = w'yi bilirler, ancak z'yi değil!
Burada protokolü kırmanın ayrıntıları, kanıtlayanın u = g ^ x tabanını seçmesidir, bu nedenle x ve l eş-asaldır.Yukarıdaki anlaşmanın Ortak Referans Dizisindeki (CRS) kodlanmış ve sabit taban g için geçerli olduğundan emin olabiliriz Basitçe ifade etmek gerekirse, taraflar taban g üzerinde önceden anlaşır ve rakip tarafından keyfi olarak seçilemez.
Anlaşma aşağıdaki şekillerde onarılabilir:
Dolayısıyla nihai anlaşma (PoKE):
Artık iki grup Q ve Q 'unsurunun olduğunu kanıtlayın. Daha iyisini yapabilir miyiz?
İspatı bir grup öğesine indirgeyerek, bu, diğer etkileşimli adımlar eklenerek yapılabilir:
Doğrulayıcının, doğrulayıcının sahte sertifika oluşturamaması için ek bir sorgulama \ alpha göndermesi gerekir.
Etkileşimli provadan etkileşimli olmayan provaya
Rastgele Oracle modelinde, Fiat-Shamir buluşsal yöntemini kullanarak, herhangi bir etkileşimli protokol etkileşimli olmayabilir (güvenli bir kriptografik karma işlevi gibi güvenli bir rastgele oluşturucumuz olduğu varsayılarak).
PoKE2 iki etkileşimli adım gerektirir; biri doğrulayıcı tarafından kanıtlayıcıya seçilen g, diğeri ise sorgulama değerleri l ve a göndermektir. Bunun yerine, mevcut "transkripti" hash edebiliriz ve çıktıyı bu değerler olarak kullanabiliriz. Rastgele bir Oracle modelinde çalıştığımız için, bu değerlerin doğrulayıcı tarafından seçilmesi arasında bir fark yoktur (kanıtlayıcı hile yapması veya bir hash fonksiyonundan gelmesi durumunda), çünkü ikisi istatistiksel olarak uyumsuzdur. Ayırt etmek!
Karma işlevi ve protokolün mevcut transkripti her kullanıldığında, tarafların her biri etkileşim olmadan sorgulama parametreleri oluşturur
Yukarıdaki teknik, w = f (x) = u ^ x (skaler değer) fonksiyonunun ön görüntüsünün bilgisini kanıtlamayı içerir.
Bu teknikler aynı zamanda homomorfik ön görüntü bilgisinin kanıtını desteklemek için, yani (x) = w olacak şekilde uzunluk n vektörü x bilgisini kanıtlamak için genişletilebilir.Sıfır bilgi ile de yürütülebilirler. Bilinen g için PoKE'nin g ^ x göndermesi gerekir. Protokolün doğruluğunu doğrularken, doğrulama içeriğini x anlayarak g ^ x'i simüle edebilen bir simülatör olduğunu varsayıyoruz. Bu bilgi sızdıracaktır, bu yüzden sıfır bilgi değildir! Makalenin yazarları tarafından kullanılan teknikler, Schnorr benzeri bir protokol ve Pedersen Commitments teknolojisi kullanılarak doğrulanan ekranlama girdilerini içerir. Bu terimlere aşina değilseniz, önce onları ziyaret edebilirsiniz.
RSA akümülatör
Sözlükte akümülatör tanımını verdik. Şimdi, toplu üyelik kanıtlarını ve üyelik olmayan kanıtları destekleyen genel bir akümülatörün yapımını tartışacağız.
Akümülatörü oluşturmak için, bilinmeyen bir dizi diziden bir modül N seçmeniz gerekir.N modülü, RSA grubundan seçilebilir (örneğin, RSA laboratuvarına güveniyorsanız, bu RSA-2048'dir) veya güvenilir ayarlar tarafından oluşturulabilir .
RSA akümülatörünün ilk durumu, g grubundan bilinmeyen sırada örneklenen bir jeneratördür, bu, akümülatördeki eleman listesinin boş olduğu anlamına gelir.
Bahsedildiği gibi, akümülatör yarı-değişmeli matematiksel özelliklere sahip olmalıdır.
İki elementin yarı-değişmeli doğası.
Toplayıcı a'ya x öğesi eklemek, toplayıcıyı A '= A ^ x mod N öğesine yükseltmek suretiyle yapılır. (Basit olması için burada mod N'yi atlıyoruz)
Üyelik kanıtı
Toplayıcıdaki bir elemanın üyeliğini kanıtlamak için, elemanın değerini ve doğrulama faktörünü görüntülemeniz gerekir.
Doğrulama faktörü veya ortak faktör, akümülatördeki tüm değerlerin ürünüdür (kanıtladığımız içerilen değer hariç)
(Değer, doğrulama faktörü) çifti, setin içerdiği kanıttır.
"Değer büyük bir sayı ise, doğrulayıcıya iletin ve üs alma maliyeti göz ardı edilebilir mi?"Bu, yukarıdaki NI-PoKE2 protokolünün kökenidir. Yukarıdaki kanıtı göndermekle karşılaştırıldığında, geçerli bir kanıt sağlayacak olan doğrulama faktörünün bilgisini kanıtlayabiliriz! Bu pek olası görünmüyor, çünkü örneğimiz basit, ancak aşağıdaki toplu üyelik sertifikası bölümünde neler olabileceğini göreceğiz.
Üye olmamanın kanıtı
Üyeliksiz kanıtı, ispatladığımız elemanların ve setteki elemanların Bezout katsayısının çarpımını hesaplamalıdır. Burada bu konuda mükemmel bir rehber bulabiliriz.
Üye olmayan bir doğrulama faktörü oluşturun
Üye olmayan bir doğrulama faktörünü doğrulayın
İşte bir örnek:
Hash asal
Tek asal sayılar (yani, 2'siz asal sayılar) hem bilgi ispat protokolü hem de toplayıcı eleman için kullanılmalıdır. Birikmiş öğe bir asal sayı değilse, rakip, öğe kümede olmadığında öğeyi dahil etmesi için doğrulayıcıyı kandırabilir.
Kümülatif olmayan unsurlar için geçerli üyelik sertifikası!
Bu nedenle, kümülatif öğeyi bir asal sayı ile sınırlandırmalıyız, aksi takdirde rakip kümülatif öğeyi içeren herhangi bir faktörü kanıtlayabilir (bu durumda, ispat 3'ü içerir, çünkü bu 6'nın bir faktörüdür).
Ek olarak, NI-PoKE2'deki l sorgulama değeri asal bir sayı değilse, saldırganın doğrulayıcıyı PoKE * saldırısına benzer bir öğe içerecek şekilde kandırmak için q ve r'yi hesaplayabileceği başka bir işbirlikçi faktör saldırısı alacağız. .
Toplama kanıtı ve toplu işlem
Tanımı hatırlayın:
polimerizasyon: Birden çok provayı sabit boyutta bir provada birleştirin;
Toplu işlem: Tüm sertifikaları tek seferde doğrulamak yerine birden çok sertifikayı aynı anda doğrulayın;
Toplama ve toplu üyelik doğrulaması çok basittir, sadece kanıtlanmış değerleri çarpın ve onlara ortak bir faktör sağlayın:
Toplam üyeliğin kanıtı
Birçok öğe için toplu üyelik kanıtları oluşturmak istersek, değerin iletildiğinde daha büyük olacağını ve doğrulayıcının pahalı üstel hesaplamalar yapması gerekeceğini çabucak görebiliriz. Bu amaçla, doğrulayıcıya 231 göndermeden g ^ 65 faktörünü bildiğimizi kanıtlamak için NI-PoKE2 kullanıyoruz ve doğrulayıcının pahalı indeks hesaplamaları yapmasına gerek yok (toplu doğrulama elde ettik!)
Üye olmayan grup sertifikasyonu, elemanların ürününün (a , b) Bezout katsayısı hesaplanarak tamamlanır ve daha sonra önceki ile aynı ispata (g ^ a , b) sahiptir. Birleşik doğrulama faktörünün boyutu, iki bağımsız doğrulama faktörü sağlamanınkiyle kabaca aynıdır.
Bu, ispat (g ^ a , A ^ b) olarak ayarlanarak çözülebilir. Güvenliği sağlamak için, kanıtlayıcı aynı zamanda b 'bilgisini kanıtlamak için bir NI-PoKE2 sağlamalıdır.
3. adımdaki NI-PoKE2 güvenlik nedenleriyle yapılır, aksi takdirde rakip v = g * d ^ (- xy) ayarlayabilir ve b bilmeden doğrulayıcıyı kandırabilir.
Bu, NI-PoE uygulayarak verimliliği artırabilir, böylece doğrulayıcının son adımda üs alma yapması gerekmez.
Sabit bir boyut doğrulama faktörü olması durumunda, şu anda üye olmayan sertifikaları toplamak için etkili bir algoritma bulunmamaktadır.
Güvenilir ayarları kaldırın
Tüm üstel işlemler, bilinmeyen asal çarpanlara ayırmaya sahip bir sayı olan modulo N hakkındadır. Bunun nedeni, sağlanan tüm kanıtların bilinmeyen sıra gruplarının genel grup modelinde olması (sayfa 2) ve güçlü RSA varsayımları ve uyarlanabilir kök varsayımları gerektirmesidir.
İlgili özel anahtarı bilmeden bir genel anahtar oluşturmak zordur. Yazının 2. sayfasında belirtildiği gibi, gerekli sayıları oluşturmak için güvenli çok taraflı hesaplamalar yapabiliriz, ancak güvenilir kurulumda yer alan tarafların sırrı almak için işbirliği yapmadığına inanmalıyız. Wesolowski, sözde "sınıf grupları" aracılığıyla başka bir seçenek önermektedir:
"Daha iyi bir yöntem, hayali ikinci dereceden sırayı kullanmaktır. Aslında, rastgele bir ayırt edici seçerek, kolayca hayali bir ikinci dereceden düzen oluşturabiliriz. Ayırıcı yeterince büyük olduğunda, Kümelerin sırası hesaplanamaz. "Şu anda, Chia bu tür "sınıfların" etkili bir şekilde hesaplanması için rekabet ediyor ve aynı zamanda arkasında gerekli teori hakkında kapsamlı bir makale sunuyor.
sonuç olarak
Burayı görebiliyorsanız, tebrikler!
RSA akümülatörünün çalışma prensibini ve akümülatördeki öğelerin üyeliğini ve üyeliğini etkili bir şekilde kanıtlamak için bir planın nasıl oluşturulacağını kısaca tanıttık. Orijinal makalenin yazarı, Merkel ağaçlarının bir özelliği olmayan, farklı indekslerde yığın açıklıklarına sahip vektör vaatlerinin oluşturulması için bir yöntem de sağlamıştır. Yazar, O (1) açılmasını sağlayabilen ilk vektör taahhüt şemasını oluşturmuştur (burada açılış, vaatte belirli bir göstergede belirli bir öğenin değerini kanıtlamayı ifade eder).
Uygulama örneği
Bu toplayıcılar, durum bilgisiz blok zincirleri oluşturmak için kullanılabilir (bu, düğümlerin hangi blokların geçerli olduğundan emin olmak için tüm durumu depolaması gerekmediği anlamına gelir). Ayrıca, verimli UTXO taahhütlerini uygulamak için de kullanılabilirler ve kullanıcıların tüm UTXO setini bilmeden işlemleri göndermelerine olanak tanır. Son olarak, vektör vaatleri, Merkle Ağacı yapılarını kullanmaktan daha verimli bir süreç olan kısa etkileşimli Oracle provaları oluşturmak için kullanılabilir.
Sıradaki ne?
Bu çok iyi bir makale, blockchain yapısının ölçeklenebilirliği için kullanılabilecek birçok ilkeli tanıtmakta ve resmileştirmektedir.
Özellikle, RSA akümülatörü, onu UTXO Plasma Cash geçmişini sıkıştırmak için kullanmaya çalışan Plazma araştırma topluluğu üyelerinin dikkatini çekmiştir. Son zamanlarda, bunun nasıl yapılandırılacağına dair ethresear.ch üzerinde birçok makale var. Bu nedenle, bir sonraki makalede, mevcut çözümleri, avantajlarını ve dezavantajlarını ve hangisinin en etkili olduğunu değerlendireceğiz.
Vektör vaatlerini kullanan homojen olmayan Plazma yapısıyla da çok ilgileniyorum.
Kim bilir, belki birisi bunu zaten yapıyor?
Bu konuda, bir sonraki makalenin başlığı şöyle olacaktır: Plazmada RSA akümülatör sınıflandırması.
