giriiş

Bir önceki yazımızda SNARK kavramını ve gerekli olan temel özellikleri tanıtmıştık. Bu gönderi dizisinin ana hedefi olan herhangi bir hesaplama için zk-SNARK'ların nasıl oluşturulacağını göz önünde bulundurarak, bu gönderide bir polinom bilgisini kanıtlamak için bir SNARK oluşturulmasını tanıtıyoruz. Tüm gereksinimleri karşılamayan tek bir yapıdan yola çıkarak ve “tam” sıfır bilgi SNARK olacak bir protokolü sonlandırarak adım adım yapacağız.

Polinomlar için ZK-SNARK'lar

SNARK olmayan daha basit bir yapıdan başlayarak adım adım bir zk-SNARK inşa edeceğiz ve ardından hedeflerimize ulaşana kadar yeni tekniklerle geliştireceğiz.

İlk adım: Schwartz — Zippel lemma

Bir kanıtlayıcı P'nin bir doğrulayıcı V'yi sonlu bir F alanındaki katsayılarla n dereceli belirli bir polinomun bilgisine ikna etmesini sağlayan bir protokol oluşturmak istiyoruz. Diğer bir deyişle, P, V'yi şu şekilde bir polinom bildiğine ikna etmek istiyor:

a_1, a_2, … , a_n ∈ F'nin bu polinomun n kökü olduğunu varsayalım, dolayısıyla p(x) şu şekilde yazılabilir:

V'nin p(x) polinomunun d < n kökünü bildiğini varsayalım.

O zaman problemimizi yeniden formüle edebiliriz: şimdi P, V'ye bir h(x) polinomunu bildiğini kanıtlamak istiyor, öyle ki:

t(x) polinomu hedef polinom olarak adlandırılacaktır. şekline sahip olduğuna dikkat edin.

zk-SNARK'ımızın ilk versiyonu, Schwartz — Zippel lemmasına dayanmaktadır: F bir alan olsun ve f: F^m → F, n dereceli çok değişkenli bir polinom olsun. O halde, herhangi bir sonlu S ⊆ F kümesi için:

Önermenin gösterdiği şey, u ∈ Sm'yi rasgele düzgün olarak alırsak, u'nun f için bir kökler kümesi olma olasılığının en fazla n / |S| olduğudur. S'yi sonlu F alanı olarak kabul edersek, bu olasılığın küçük olduğunu gözlemleyin. Alan boyutu, n'ye kıyasla çok büyük olacaktır.

Çelişkili görünebilir, ancak bu lemma bir f polinomunun bilgisini kanıtlamamıza izin verir. p'nin tüm katsayılarını bildiğimizi kanıtlamamız gerekmez, yalnızca herhangi bir s ∈ Fm için (s, f(s)) çiftini nasıl hesaplayacağımızı bildiğimizi kanıtlamamız gerekir. Schwartz — Zippel lemma, zk-SNARK'ımızda gereken verimliliği sağlar.

İlk protokol

P'nin p(x) polinomunu bildiğini ve V'nin p(x)'in d < n kökünü bildiğini veya eşdeğer olarak V'nin hedef polinom t(x)'i bildiğini hatırlıyoruz. P ayrıca t(x)'i de bilir.

İlk yaklaşımımız şu şekildedir:

1. V rastgele bir s değeri alır ve t = t(s)'yi hesaplar. V, P'ye s gönderir.
2. P polinomu hesaplar

4. V eşitliğinin p = t · h olup olmadığını kontrol eder.

Bu protokol doğrudur, çünkü P, p(x) polinomunu biliyorsa, h(x)'i hesaplayabilir ve dolayısıyla P, h ve p değerlerini p = h · t olacak şekilde hesaplayabilir. Öte yandan, Schwartz - Zippel lemması nedeniyle bu protokol de verimlidir.

Bununla birlikte, kanıtlayıcı, P p(x)'i bilmese bile hedef polinomu kullanarak t = t(s)'yi hesaplayabildiğinden, bu protokol sağlam değildir. Rastgele bir h alabilir ve p = h · t'yi hesaplayabilir ve (h, p) çiftini, çifti geçerli olarak kabul edecek olan V'ye gönderebilir.

P'nin V'yi kandırmasına izin veren kritik noktanın, P'nin s değerlendirme noktasını bilmesi olduğunu gözlemliyoruz. P, s değerlendirme noktasını bilmeden p'yi değerlendirebilseydi, bu numara imkansız olurdu. Bu bizi ikinci adıma götürür: homomorfik gizleme veya homomorfik gizleme.

İkinci adım: homomorfik karartma

Protokolümüzü sağlam kılmak için, bir polinomu bir nokta üzerinde, o noktayı bilmeden değerlendirebilmeliyiz.

Bunu ayrık logaritma probleminin sertliğine dayanarak yapacağız. Klasik bir bilgisayar için, ayrık logaritma problemi hesaplama açısından mümkün değildir: p mertebesinden ve bir g öğesi tarafından oluşturulan bir döngüsel G grubunda, bilinen bir için = ga (mod p) olacak şekilde bir a öğesinin belirlenmesi.

Dolayısıyla, ayrık logaritma polinomunun sertliğini varsayarak, = ga (mod p) hesaplayarak bir a değerini karartabiliriz. alıcısı tek başına a değerini öğrenemez. Bu tekniğin ilginç yanı, üs almanın bazı homomorfik özelliklere sahip olmasıdır:

İki gizlenmiş değerin çarpımı, net olarak ilişkili değerlerin toplanmasının karartılmasıyla aynıdır.

Bir polinomu değerlendirmek istiyorsak

Değerlendiricinin tam noktayı bilmesine izin vermeden x = s noktasında, tüm polinomu gizlememiz gerekir:

Ayrıca, 1'den polinomun derecesine kadar, x = r için gizlenmiş tüm değerlerin kuvvetlerini hesaplamamız gerekir, yani:

Tüm bu öğelerle, p polinomunun bir x = r noktasında bulanık değerlendirmesini artık hesaplayabileceğimizi gözlemleyin. Aslında:

Homomorfik saklanmaya bir örnek

F = ℤ127 ve g = 3 sonlu alanını bir üreteç olarak ele alalım. P'nin p(x) = 4x2 + 3x + 1 polinomunu bildiğini ve V'nin, P'nin noktayı bilmesine izin vermeden x = 2 noktasında polinomu değerlendirmesini istediğini varsayalım. Bunu aşağıdaki adımlarla yapabiliriz:

1. V, x = 2'nin tüm güçlerini 0'dan polinomun derecesine kadar hesaplar, n = 2:

1.b. 32 (mod 127) = 9

1.c. 34 (mod 127) = 81

ve çifti (9, 81) P'ye gönderir.

2. P, x = 2 üzerindeki p(x) değerlendirmesini x'in değerini bilmeden hesaplayabilir, aslında V'den aldığı bilgiyi kullanarak hesaplayabilir:

İkinci protokol

Kanıtlayıcının bu karartılan noktadaki polinomu değerlendirebilmesi için noktaları nasıl karartacağımızı artık bildiğimize göre, ilk protokolü geliştireceğiz. P'nin p(x) polinomunu bildiğini ve V'nin p(x)'in d < n kökünü bildiğini veya eşdeğer olarak V'nin hedef polinom t(x)'i bildiğini hatırlıyoruz. P ayrıca t(x)'i de bilir.

İkinci protokolümüz ise şu şekilde:

1. V rastgele bir s değeri alır ve t = t(s)'yi hesaplar.
2. V, aşağıdaki güçleri hesaplar ve P'ye gönderir:

4. değerlerini kullanan P, önceki örneğin talimatlarını kullanarak g^p = g^{p(s)} ve g^h = g*{h(s)}'yi hesaplar.

5. P, V'ye g^p ve g^h gönderir.

6. V, aşağıdaki kimliğin geçerli olup olmadığını kontrol eder: g^p = (g^h)^t

İlk protokolde tespit edilen kusurun değiştirildiğini, ancak bu ikinci protokolün henüz sağlam olmadığını gözlemleyin. Aslında P hala zp ve zh değerlerini z_p = (z_h)^t olacak şekilde kullanabilir ve sanki g^p ve g^h gibi V'ye gönderebilir. P bunu rastgele bir r alarak, z_h = g^r hesaplayarak ve z_p = (g^t)^r ayarlayarak yapabilir. Z_p değeri, V tarafından gönderilen karartılmış güçler kullanılarak hesaplanabilir.

Bu durumu önlemek için, g^p ve g^h'nin yalnızca V tarafından gönderilen gizlenmiş kuvvetler kullanılarak hesaplandığından emin olmamız gerekir.

Üçüncü adım: üssün bilgisi varsayımı

Bir SNARK'ı tanımlarken ortak bir varsayım vardır: 2q + 1'in de bir asal sayı olduğu q asal sayısını ele alalım. ℤ_{2q + 1}'nin ga üretecini ele alalım. q, g ve g' = g^ verildiğinde, x ≠ g, y ≠ g' ve y = x^ olacak şekilde bir (x, y) çifti bulmak istiyoruz. Üs bilgisi varsayımı (KEA), (x, y) çiftini bulmanın tek yolunun c ∈ ℤ_q değerini almak, önce x = g^c'yi hesaplamak ve ardından y = (g')^ almak olduğunu söyler. C.

KEA, eğer biri (x, y) çiftini elde etmek istiyorsa, bunu yapmanın tek yolunun x = g^c olacak şekilde bir c üssünü bilmek olduğu anlamına gelir. Başka bir deyişle, KEA özelliğine sahip (x, y) çiftini ancak g'nin kuvvetlerini kullanarak elde edebiliriz.

KEA'yı kullanan aşağıdaki protokol, P'nin, V tarafından iletilen çarpımsal bir alt grubun üreteci olan g'nin belirli bir gücünü döndürmesini sağlar:

1. V rastgele bir değeri alır ve g' = g^ (mod 2q + 1) hesaplar.
2. V, (g, g') çiftini P'ye gönderir ve (b, b') = (g, g') olacak şekilde bir (b, b') çifti ister.
3. P bir c değeri alır ve b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1)'i hesaplar ve (b, b') çiftini V'ye gönderir.
4. V, b' = b^ (mod 2q + 1) olup olmadığını kontrol eder.

P, hem g hem de g' için aynı c kuvvetini kullandı ve yalnızca V tarafından sağlanan değerleri kullanabildi.

Üçüncü protokol

Kanıtlayıcı P'nin gizlenmiş etki alanında s değerlerinin güçlerini çıkarmasını sağlayacak uygun bir protokol oluşturmaya hazırız.

1. V rastgele bir s değeri alır ve t = t(s)'yi hesaplar.
2. V rastgele bir değeri alır ve t( · s)'yi hesaplar.
3. V, aşağıdaki gizlenmiş değerler serisini hesaplar ve bunları P'ye gönderir.
4. V, aşağıdaki gizlenmiş değerler serisini hesaplar

5. P, h(x) polinomunu hesaplar.

6. kullanarak P, p(s) ve h(s)'yi g^p = g^{p(s)} ve g^h = g^{h(s)} ile birlikte hesaplar.

7. kullanarak P, p(s) ve h(s)'yi g^{p'} = g^{p( · s)} ile birlikte hesaplar.

8. P, V'ye g^p, g^h ve g^{p'} gönderir.

9. V, P'nin yalnızca kendisine gönderdiği bilgileri kullanarak karartılmış değerlerin hesaplamalarını yaptığını kontrol eder. Bunu yapmak için V, g^p = g^{p'} olup olmadığını kontrol eder.

10. V, aşağıdaki kimliğin geçerli olup olmadığını kontrol eder: g^p = (g^h)^{t(s)}.

Bu protokol artık bir SNARK'ın gerektirdiği özellikleri karşılıyor: doğru, sağlam ve verimli. Sonraki bölümler, etkileşimsizlik ve sıfır bilgi ile ilgilenecektir.

Açıklama: Yukarıdaki protokoldeki 6. ve 7. adımlar, homomorfik gizleme örneğine göre yapılır.

sıfır bilgi

Buraya kadar sunduğumuz protokolde, P tarafından bilinen polinomun ci katsayıları çok spesifiktir ve V, P'den gelen gp, gh ve gp' kullanarak onlar hakkında bazı bilgiler öğrenmeye çalışabilir. Bu nedenle, P'yi emin kılmak için V hiçbir şey öğrenmeyecek, P'nin bu değerleri saklaması gerekiyor.

P tarafından gönderilen değerleri gizleme stratejisi daha önce kullanılan adımları takip eder: P rastgele bir alır ve bunu V ile iletişimde gönderilen değerleri gizlemek için kullanır. Kesin olmak gerekirse, g^p, g^h ve g göndermek yerine ^{p'}, P hesaplar ve (g^p)^, (g^h)^ ve (g^{p'})^ gönderir. Ardından V, doğrulamayı altında gizlenen değerler üzerinde çalıştırır.

V'nin çalıştırması gereken doğrulama prosedürü, aslında bu gizleme ile hala geçerlidir:

Böylece üçüncü protokolü sıfır bilgi yapmak için, adım 8 değiştirilir, böylece P gizlenmiş değerleri gönderebilir.

Etkileşimsiz

Sunduğumuz farklı protokoller, kanıtlayıcı ile doğrulayıcı arasındaki etkileşimi gerektirir ve bunun nedeni, protokollerin doğruluğunun, doğrulayıcı tarafından seçilen s ve gizli değerlerine dayanmasıdır.

Yukarıdaki protokollerden herhangi birini başka bir doğrulayıcı V', V' ile tekrarlamak istiyorsak, yeni değerler s' ve ' seçmemiz gerekir. V tarafından üretilen değerlerin kullanılması, V ile işbirliği yaparsa P'nin hile yapmasına izin verebilir ve V, s ve değerlerini P'ye gösterir.

Yukarıdaki durumdan kaçınmak için, protokolümüzün etkileşimsiz olmasına ihtiyacımız var ve bunu genel, güvenilir ve yeniden kullanılabilir parametreler kullanarak başarabiliriz. Bu, bir jeneratör g kullanılarak bu parametrelerin karartılmasıyla gerçekleştirilebilir. Bununla birlikte, kullanılan gizleme teknikleri homomorfik olsa bile, yalnızca gizli değerlerin çarpımını kullanarak net mesajların eklenmesine izin verirler, ancak gizlenmiş alanda net değerlerin çarpımını gerçekleştirmeye izin vermezler ve bu adım, doğrulama sırasında çok önemlidir. polinomun ve köklerinin doğruluğu.

Bu sorunu çözmek için eşleştirmeleri tanıtacağız. Bir eşleştirmenin aşağıdaki özelliklere sahip olduğunu hatırlayalım:

Bu özellik, karartılmış etki alanındaki ürünlerin eşitliğinin kontrol edilmesini sağlar.

Dolayısıyla, protokollerimizi etkileşimsiz hale getirmek için ilk adım, gizli rasgele değerler olan s ve 'ı alıp bunları karartmaktır: g^, ve .

Bu güçleri hesapladığımızda, s ve gizli değerlerinden kurtulabilir ve Ortak Referans Dizisi (CRS) olarak bilinen bulanık değerlerini yayınlayabiliriz. CRS değerleri genellikle şu şekilde saklanır:

1. Değerlendirme anahtarı: (, ).
2. Doğrulama anahtarı: (g^, g^{t(s)}).

Nihai protokol: bir polinom bilgisi için zk-SNARK

Şimdi bir hedef polinom t(x) verildiğinde n dereceli bir polinom p(x) hakkındaki bilgiyi kanıtlamak için bir zk-SNARK tanımlıyoruz.

Parametre ayarı

1. Her bir taraf rastgele iki gizli değer olan s ve alır.
2. Her taraf g, ve 'yi hesaplar.
3. s ve değerleri yok edilir.
4. Değerlendirme anahtarı ( ve ) yayınlanır.
5. Biri g^, g^{t(s)} doğrulama anahtarını yayınlar.

1. P'nin p(x)'i bildiğini varsayarak, P polinomu h(x)'i hesaplar.
2. P, p(x) ve h(x)'i değerlendirir ve değerlendirme anahtarında bulunan değerleri kullanarak gp(s) ve gh(s)'yi hesaplar.
3. P, değerlendirme anahtarını kullanarak g^{p( · s)} değerini hesaplar.
4. P rastgele bir değeri alır.
5. P ispatı yayınlar π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

V'nin π = (g^{ · p}, g^{ · h}, g^{ · p'}'ye erişimi olduğunu varsayarak), olup olmadığını kontrol eder.

Bir zk-SNARK tanımında gerekli olan tüm özellikleri karşılayan bir protokol oluşturmayı başardık: özlülük (kanıt sadece bir noktada bir polinomu kontrol ettiği için), sıfır bilgi ve etkileşimsiz (bir CRS kullandığı için) ).

CRS'nin oluşturulması

Zk-SNARK'lar, Ortak Referans Dizisi (CRS) olarak bilinen bir dizi gizli değer kullanılarak etkileşimsiz hale getirilebilir. Bizim durumumuzda ve biçiminde olan bu gizli değerler, gizli değerler türetildikten sonra yok edilmesi gereken gizli değerlerden, s ve gelir. CRS neslinin kritik olduğunu gözlemleyin, çünkü eğer birisi neslini üçüncü bir katılımcıya devrederse, herkesin katılımcının s ve değerlerini yok edeceğine güvenmesi gerekir. Üçüncü taraf, tek bir başarısızlık noktasını temsil eder.

Tek bir başarısızlık noktasından kaçınmak istiyorsak, s ve değerlerinin geri alınamayacağını garanti etmek için tek bir dürüst katılımcının yeterli olduğu CRS'yi oluşturmak için dağıtılmış bir yola ihtiyacımız var.

Önceki örneğimizde oluşturduğumuz SNARK için CRS'yi kullanalım. s ve 'yi sır olarak kullanarak g^, ve gizli değerlerini ve güçlerini hesaplamamız gerektiğini hatırlıyoruz.

Yeni protokolümüzde, tek bir üçüncü tarafça oluşturulan s ve değerlerini üç A, B ve C kullanıcısı tarafından oluşturulan s_{ABC} ve _{ABC} değerleriyle değiştireceğiz. Mekanizmayı n kullanıcıya genişletmek basittir .

Protokol aşağıdaki gibidir:

1. Kullanıcı A (sA, A) çiftini oluşturur, hesaplar ve yayınlar:

3. B yayınları:

4. C, rastgele bir çift (sC, C) alır, hesaplar ve yayınlar:

Bu protokol, s_{ABC} = s_A · s_B · s_C ve _{ABC} = _A · _B · _C için gizli değerleri üretir ve hiçbir katılımcı bu değer çiftini bilmez.

Yine de, katılımcıların bu gizli değerlerin doğru hesaplanıp hesaplanmadığını kontrol etmelerini sağlayan bir protokole ihtiyacımız var. Her kullanıcı tarafından oluşturulan değerlerin gereksinimleri karşıladığından, yani değerler kümesinin her kullanıcının s-değeri için gs'nin kuvvetleri olduğundan ve kümesinin doğru hesaplandığından emin olmamız gerekir. Bunu yapmak için, her (g^s)^i'nin gs'nin i'inci kuvveti olduğunu kontrol ederiz. Bu, aşağıdaki eşitliklerin sağlandığını kontrol ederek yapılabilir. Bu kontrol, her bir katılımcı U ile ilişkili tüm sU ve U değerleri için her katılımcı tarafından gerçekleştirilir:

Gerekli olan tek doğrulama bu değil. Ayrıca, her katılımcının bir önceki katılımcının doğru değerlerini kullanıp kullanmadığını kontrol etmemiz gerekir. Bunu yapmak için her katılımcı, bir kullanıcının gizli genel parametrelerini başka bir katılımcının çıktılarıyla birleştirerek kullanacaktır. Örneğin C, aşağıdakileri doğrulayarak A'dan gelen CRS bilgilerini kullanarak B tarafından üretilen CRS'nin ara değerlerini kontrol edebilir:

Çözüm

Şimdiye kadar, bir polinom bilgisini kanıtlamak için sıfırdan ve tüm ayrıntılarıyla bir SNARK oluşturmayı öğrendik. Bir sonraki yazımızda, sonuncusunda, yukarıdaki yapıyı herhangi bir hesaplamaya genişleteceğiz. Bunu yapmak için iki temel kavramı tanıtacağız: ikinci dereceden aritmetik programlar, QAP'ler ve sıra-1 kısıtlama sistemleri, R1CS, ancak ikincisi özel olarak tanıtılmayacaktır (bilinçaltı mesajı olarak görünecektir).

Referanslar

Jordi Herrera Joancomartí, Cristina Pérez Solà, Gelişmiş Kriptografi. Ders Notları. Katalonya Açık Üniversitesi, 2022.