Sıfır bilgi kanıtı teknolojisinde devrim niteliğinde ilerleme: Nova algoritmasının derinlemesine incelenmesi

Bir süre önce sıfır bilgi kanıtı teknolojisi üzerine bir kitap çeviriyordum. Temel içerik geçen ayın sonunda çevrildi. Çeviri beklediğimden çok daha uzun sürdü. Şu anda kitaptaki bazı yazım hatalarını yazarla tartışıyoruz ve son taslağa hazırlanıyoruz.

Neyse, sonunda yeni bir şeye bakacak zamanım oldu. Nova algoritmasıyla başlayalım~

Nova algoritmasıyla ilgili bilgiler

Üç bilgi parçası Nova algoritmasının anlaşılmasına yardımcı olabilir:

  1. Nova makalesi:
  2. Nova potansiyel saldırıları ve ilgili düzeltmeler:
  3. Nova'nın potansiyel saldırılarına ilişkin anlayışın özeti:

Bu makale yukarıdaki bilgilerin anlaşılması ve özetidir. **Bu yazıdaki bazı resimler yukarıdaki bilgilerden alınmıştır ve bu yazıda tek tek etiketlenmeyecektir. **

IVC ile başlayın

Nova algoritması, IVC (Artımlı Doğrulanabilir Hesaplama) için yeni bir sıfır bilgi kanıtı algoritmasıdır. IVC, yani aynı fonksiyon yinelemeli olarak önceki çıktıyı bir sonraki girdi olarak hesaplar. F fonksiyonunun yinelemeli hesaplama süreci aşağıdaki gibidir:

z0 ilk giriştir ve F fonksiyonu hesaplamasıyla oluşturulan sonuç, bir sonraki F fonksiyonunun girişi olarak kullanılır.

Rahat R1CS ve Gevşek Taahhüt R1CS

Hepimizin bildiği gibi R1CS, sıfır bilgi kanıtı teknolojisindeki devre kısıtlamalarının bir temsilidir. Gevşetilmiş R1CS, R1CS'nin genişletilmiş bir formu olarak görülebilir. R1CS temelinde, bir skaler u ve bir hata vektörü E eklenir. Gevşetilmiş R1CS'nin bir örneği (E, u, x) ile temsil edilir.

Gevşetilmiş taahhüt R1CS, gevşetilmiş R1CS'ye dayalı olarak E ve W vektörlerini taahhüt eder. R1CS gevşek taahhüdünün bir örneği (\bar{E}, u, \bar{W}, x) ile temsil edilir; burada x ve u genel değişkenlerdir.

Katlama şeması için R1CS'den rahat R1CS'ye genişletme. Rahat R1CS açısından bakıldığında, R1CS'nin bunun özel bir durumu olduğunu unutmayın. Başka bir deyişle, R1CS aynı zamanda "özel" bir gevşek R1CS'dir.

Katlama Şeması

Sezgisel olarak konuşursak, bir R ilişkisi için bir katlama şeması, R ilişkisine uyan iki örneği, R bileşik ilişkisinin yeni bir örneğine "çöktürmektir". Slack R1CS/Relax Commitment R1CS benzer katlamalar gerçekleştirebilir. Katlama işlemi her ikisi için de benzerdir. Slack Commitment R1CS'nin katlama şeması aşağıdaki gibidir:

Katlama şemasının tamamı 4 adımdan oluşur. İlk adımda, P kanıtlayıcısı doğrulayıcıya T çapraz öğesinin \bar{T} taahhüdünü gönderir. İkinci adımda doğrulayıcı, kanıtlayıcıya rastgele bir r sorgulaması gönderir. Üçüncü adım, hem kanıtlayıcının hem de doğrulayıcının gerçekleştirmesi gereken taahhüdün katlanmasıdır. Dördüncü adımda ispatlayıcı tek başına işlem yapar ve iki örneğin E ve W vektörlerini katlar.

Artırılmış fonksiyon F' (Argümanlanmış Fonksiyon)

Şemayı daraltın, daraltılmış R1CS örneği gevşetildi. Peki bu rahat R1CS örnekleriyle kanıtlanan hesaplamalar nelerdir? Açıkçası bu hesaplamalar katlama hesaplamalarını da içeriyor. Bu hesaplamalar IVC hesaplamalarındaki sadece F fonksiyonu değildir, aynı zamanda artırılmış F' fonksiyonları olarak da adlandırılır. Arttırılmış F' fonksiyonunun hesaplanması esas olarak iki bölümden oluşur:

IVC'de 1/ F işlevi

2/ R1CS örneğinin katlama hesaplaması

İdeal görünüm

Yukarıdaki anlayışla katlama işlemini hayal edebilirsiniz:

Bunların arasında devre, artırılmış F' fonksiyonuna karşılık gelen devredir. acc{1,2,3,4,5,6} bir gevşek taahhüt R1CS örneğidir. Devrenin iki hesaplaması vardır: 1/R1CS örneğinin taahhüdünün katlanmasını gevşetin, örneğin acc1+acc2->acc3. 2/F fonksiyonunu hesaplayın, durumu durum1'den durum2'ye ve ardından durum2'den durum3'e vb. değiştirin.

Arttırılmış F' fonksiyonuna karşılık gelen devrenin kendisinin bir R1CS örneği olduğuna ve bunun rahat bir R1CS örneği olarak ifade edilebileceğine dikkat edin. Resimdeki acc4 ve acc6'dır. "özetleme", bir gevşek R1CS örneğini, bir gevşek taahhütlü R1CS örneğine dönüştürmektir.

İkinci devrenin girişine dikkatlice bakıldığında acc3, katlama sonrasındaki gevşetilmiş taahhüt R1CS örneğidir ve acc4, acc3'ün doğru katlama sonucu olduğunu kanıtlayan gevşetilmiş taahhüt R1CS örneğidir. Bu iki örnek bir sonraki katlamaya girecek ve acc5'i oluşturacaktır. Acc3 ve acc4'ün karşılanabilir gevşek taahhüt R1CS örnekleri olması durumunda, acc3'ün iki karşılanabilir gevşek taahhüt R1CS örneğinden katlandığı anlamına geldiğini düşünebilirsiniz. Başka bir deyişle, acc1 ve acc2 karşılanabilir gevşek taahhütler R1CS örneğidir. Bu tür bir güvenilirlik adım adım "ileri" olarak çıkarılabilir, böylece her devredeki F fonksiyonu hesaplamasının doğru olduğu kanıtlanır. Genel olarak, belirli bir devreye karşılık gelen iki gevşek taahhüt R1CS örneğinin karşılanması sayesinde, önceki tüm IVC hesaplamalarının doğru olduğu kanıtlanabilir.

Gerçek görünüm

Sıfır bilgi kanıtlarına aşina olan arkadaşlar, eliptik eğrilerin polinom bağlılık şemalarında sıklıkla kullanıldığını biliyorlar. Skaler alandaki karşılık gelen polinom bağlılığı, eliptik eğrinin taban alanıyla temsil edilir. R1CS devreleri genellikle skaler alanla temsil edilir. Dikkatli bakın, yukarıdaki resimdeki "özetleme", alan adı dönüşümünü içeriyor. Yani, bir devreye karşılık gelen gevşek taahhüt R1CS örneğini katlamak istiyorsanız, bunu başka bir devrede "katlamanız" gerekir. Şu anda, bir eliptik eğri döngüsünün tanıtılması gerekiyor.İki veya daha fazla eliptik eğri arasında, bir eğrinin skaler alanı, diğer eğrinin taban alanıyla aynıdır.Tesadüfen, bu eğrinin skaler alanı, ile aynıdır. önceki eğrinin temel alanı. Böyle bir eliptik eğri döngüsü kullanılarak "ideal görünüm" gerçekleştirilebilir:

Katlama işleminin tamamı katlama için iki devreye bölünmüştür. Üst kısım Devre 1'in kıvrımı, alt kısım ise Devre 2'nin kıvrımı olarak adlandırılabilir. İki devre arasındaki ilişkinin resmi bir temsili "Nova'ya Olası Saldırılar ve İlgili Düzeltmeler" makalesinin 8. sayfasında yer almaktadır. U katlanmış örneği temsil eder ve u, bir R1CS örneğine karşılık gelen gevşetilmiş örneği temsil eder. Devre 1'in, Devre 2'ye karşılık gelen gevşek taahhüt R1CS örneğini daralttığını, Devre 2'nin ise Devre 1'e karşılık gelen gevşek taahhüt R1CS örneğini daralttığını unutmayın. Devre 2'nin temel amacı Devre1'e karşılık gelen R1CS örneğinin gevşek taahhüdünü çökertmektir ve devresindeki fonksiyon hesaplaması anlamsızdır. Bunun yerine F fonksiyonu Devre 1'de uygulanır. "İdeal görünüm" ile birleştirildiğinde, U{i+2}^2, u{i+2}^1, u{i+2}^2, U{i+2}^1'in karşılanabilirliğini kabaca tahmin edebiliriz. kanıtın önemli bir parçasıdır.

Çünkü "devre" iki parçaya bölünür ve ilgili devre diğer devrenin içine katlanır. Örnekler arasında birkaç bağlama sorunu vardır: u ve U örnekleri arasındaki bağlanma ve iki devre arasından geçen u örneklerinin bağlanması. Bu bağlama sorunlarını çözmek için, devreye x_0/x_1 genel değişkenleri tanıtılır; burada x_1, u örneğine bağlı devre çıkışı U örneğini ve mevcut F fonksiyonunun çıkışını belirtir (sırasıyla Şekilde gösterilmeyen devre yapısını basitleştirin). U örneğinin H_1 sonucu devreye dahil edilirse, u örneği karşılanabilirse, x_0/x_1'in hem gerçek hem de güvenilir olduğunu, yani U'ya "bağlı" olduğunu düşünüyorsunuz. x_0, u girişi ile U arasındaki bağlanma ilişkisini kurar ve x_1, u ve U çıkışı arasındaki bağlanma ilişkisini kurar.

Örneğin u{i+1}^1 devrenin ikinci yarısının girişi olarak kullanıldığında Devre 2'den geçer ve çıkışı u{i+1}^2.x0 = u{i+1 }^1.x1, yani devrenin üst kısmına giriş yapıldığında, eğer u{i+1}^2 karşılanabiliyorsa, o zaman x_0, U_{i'nin H1 sonucuna eşit olmalıdır. +1}^2. Bu, Devre 1'de kontrol edilir. Bu şekilde iki devre arasında doğru örneğin iletilmesi garanti edilir.

IVC Kanıtı

Belirli bir yinelemede IVC'nin doğru hesaplandığını kanıtlamak için aşağıdaki bilgilerin mantıksal olarak kanıtlanması gerekir:

Dört örneğin karşılanabileceğini kanıtlamanın yanı sıra, aşağıdaki şekilde gösterildiği gibi iki x1 arasındaki bağlayıcı ilişkinin de kanıtlanması gerekir:

Bu bilginin doğru olup olmadığı ek kanıt devresi uygulamasını gerektirir. Yani IVC hesaplamasının ispatı devrenin ispatıdır. Çok sayıda yinelemeli bir hesaplama söz konusu olduğunda, bu yinelemelerin başlangıçta devrede tek tek gerçekleştirilmesi gerektiği, ancak artık tatmin edilebilirlik ve bağlayıcı ilişkiler açısından yalnızca dört devre örneğinin doğrulanmasının gerekli olduğu düşünülebilir. Performans artışı çok büyük.

Saldırı ve Algoritma Düzeltme

Yukarıdaki resmi görünce bir sezgiye sahibim: Üst ve alt devrelerin örneklerinin "ayrılmış" olduğunu ve hiçbir bağlayıcılığı olmadığını hissediyorum. Aslında saldırının yapısı bu şekilde.

Dövme U_i^1 ve U{i+1}^2, sahte olmalarına rağmen karşılanabilir örneklerdir. u{i+1}^1'i oluşturun, x_0 ve x_1'i sahte U örneğine karşılık gelecek şekilde değiştirin. Açıkçası u{i+1}^1 örneği tatmin edici değil. Tatmin edilmemesine rağmen Devre 2'nin devresi hala karşılanabilir ancak U{i+1}^1 örneğinin çıkışı karşılanmaz. Eğer u{i+1}^2 başarıyla oluşturulursa, Devre 1 tatmin edici u{i+2}^1 ve U_{i+2}^2'yi oluşturabilir ve x1'in bağlayıcı ilişkisini sağlayabilir. Bu şekilde nihai sahtecilik delilinin yarısı ilk önce oluşturulur. Simetri sayesinde alt yarının çıktı örneği oluşturulabilir. İki yapının sonuçlarının "birleştirilmesiyle" IVC hesaplamasının kanıtı oluşturulabilir.

Revize edilen kontrol mantığı aşağıdaki gibidir:

"Nova'ya Olası Saldırılar ve İlgili Düzeltmeler" başlıklı makalenin 6. Bölümünde ayrıntılı bir güvenlik analizi sunulmaktadır. İlgilenen arkadaşlar orijinal makaleyi kendileri kontrol edebilirler.

Nova'nın temel fikri devre örneklerini bir katlama şeması yoluyla katlamaktır. Mantık oldukça karmaşıktır ve devre katlama süreci ve devredeki bağlayıcı ilişkiler hakkında dikkatli düşünmeyi gerektirir.

Bunu tanımlayacak tek kelime: Mutlak~

View Original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
  • Reward
  • 1
  • Share
Comment
0/400
GateUser-a962ed6fvip
· 2023-09-11 15:38
Şaşkın gir, şaşkın çık
View OriginalReply0
Trade Crypto Anywhere Anytime
qrCode
Scan to download Gate app
Community
  • 简体中文
  • English
  • Tiếng Việt
  • 繁體中文
  • Español
  • Русский
  • Français (Afrique)
  • Português (Portugal)
  • Bahasa Indonesia
  • 日本語
  • بالعربية
  • Українська
  • Português (Brasil)