原文:Güvenli ve Sağlam — STARK Güvenliğine Derin Bir Bakış
Çeviri ve redaksiyon: "Starknet Çin Topluluğu"
Öne Çıkan Kısa Bilgiler
Etkileşimli olmayan STARK, rastgele oracle modelinde etkileşimli olmayan bir kanıt halinde derlenen Etkileşimli Oracle Kanıtından (IOP) türetilmiştir.
Bu makale ethSTARK belgelerindeki en son güncellemeleri açıklamakta ve rastgele oracle modelinde ethSTARK protokolünün güvenliğinin kapsamlı ve ayrıntılı bir analizini sunmaktadır.
STARK güvenliğinin ayrıntılı açıklaması
STARK kanıt sistemi veya ölçeklenebilir şeffaf bilgi argümanı, hesaplama bütünlüğü için güçlü bir araçtır: kamuya açık veriler üzerinde gerçekleştirilen hesaplamaların doğruluğunun güvenilir bir şekilde doğrulanmasına olanak tanır. Bu makalede STARK kanıtlarının sağladığı güvenliği derinlemesine inceleyeceğiz, bunları tanımlayacağız ve şemaların güvenliğini kanıtlamaya yönelik teknikleri araştıracağız.
(Ayrıntılar için ethSTARK belgelerinin (versiyon 1.2) 6. bölümünü ve ayrıca Block ve arkadaşlarının bu konuyla ilgili önemli ve kapsamlı bağımsız çalışmasını okuyun).
Güvenlik analitiğiyle neyi başarmaya çalışıyoruz? Yanlış bir beyanın ve bu (yanlış) beyana yanıt olarak STARK doğrulayıcısı tarafından kabul edilen STARK kanıtının neden olduğu STARK sistemine yönelik "başarılı saldırıları" önlemek istiyoruz. Yanlış beyanlar tehlikeli olduğundan ve her boyutta ve biçimde olabileceğinden, bunların hepsine karşı güvende olmak istiyoruz. 1+1=3 kadar önemsiz bile olsa herhangi bir yanlış beyan, bir STARK doğrulayıcısı tarafından kabul edilen bir STARK kanıtıyla birleştirildiğinde, sisteme yapılan başarılı bir saldırı olarak kabul edilecektir. (Kriptografi geçmişi olanlar, STARK'ın bilgi güvenilirliği gibi daha güçlü güvenlik kavramlarını da karşılayabildiğini bilmek isteyebilirler, ancak basitlik adına bu makale güvenilirlikle ilgili basit durumlara odaklanacaktır).
Bir STARK sisteminin güvenliğini resmi olarak nasıl tanımlarız? Bunu "güvenilirlik hatası" analiziyle belirliyoruz. "Güvenilirlik hatası" kabaca bir saldırganın başarılı bir saldırı başlatmasının maliyetinin beklenen "maliyetini" ölçer (yani, yanlış bir beyan için bir STARK kanıtı bulun, ancak kanıt STARK doğrulayıcısı tarafından kabul edilir). Matematiksel olarak konuşursak, güvenilirlik hatası, girdisi saldırganın bir saldırı başlatmak için harcamak istediği hesaplama süresini temsil eden zaman parametresi t olan ve çıktısı da saldırganın saldırısının başarılı olma olasılığı olan bir fonksiyondur (t). yanlış ifadeler ikna edici kanıt). Saldırganın harcamak istediği "maliyet" ne kadar büyük olursa, başarı olasılığı da o kadar yüksek olur.
Şu ana kadar STARK'ın güvenliğini bir fonksiyon (t) olarak tanımladık; bu, herkesin kripto Twitter'da güvenliği her gün tartışmasından farklı. Twitter'da şöyle bir şey duyabilirsiniz: "Bu çözümün 96 bit güvenliği var." Bu bizim güvenlik tanımımıza nasıl yansıyor? İnsanlar "x bit güvenlik" ifadesini biraz farklı anladıkları için bunun tek bir cevabı yok:
Kesin olarak yorumlandığında bu, 1 ile 2⁹⁶ arasındaki herhangi bir t için güvenilirlik hatasının (t) 2⁹⁶ olduğu anlamına gelir. Çalışma süresi 2⁹⁶ veya daha az olan bir saldırganın başarı olasılığı çok küçüktür, 2⁹⁶'den azdır, bu da milyarda 1 çarpı milyarda 1'den azdır.
Daha gevşek ve belki de daha yaygın bir yorum, 96 bit güvenliğin herhangi bir t için t/(t) 2⁹⁶ olduğu bir durum olduğu anlamına geldiğidir. Bu, başarı olasılığının çalışma süresiyle (ters) doğrusal olduğu anlamına gelir. Saldırganın koşma süresi 2⁸⁶ ise, başarı olasılığı en fazla 2¹⁰ olur.
Bu yazıda ikinci seçeneği tartışacağız.
96 bit güvenlikle IOP'tan STARK'a
Peki bir çözümün 96 bit güvenliğe sahip olduğunu nasıl kanıtlayacağız? Bu soruyu cevaplamak için STARK'ın üzerine inşa edildiği üst düzey yapıyı anlamamız gerekiyor. STARK üç ana bölümden oluşur: IOP (Etkileşimli Oracle Proof), Merkle ağacı ve Fiat-Shamir hash; ana odak noktamız IOP'dur. Bu bileşen parçaları belirlendikten sonra bunları bir STARK oluşturmak için derleyebiliriz. Ne oldukları ve birbirlerine nasıl uydukları da dahil olmak üzere bu bileşenleri ayrıntılı olarak inceleyeceğiz.
İnceleyeceğimiz ilk bileşen IOP'tur: IOP, kanıtlayıcı ve doğrulayıcının birden fazla tur boyunca etkileşimde bulunduğu standart etkileşimli kanıta benzer (doğrulayıcının kanıtlayıcıya yalnızca rastgele zorluklar gönderdiği genel para protokolleriyle sınırlıdır). Bir IOP'de doğrulayıcı, kanıtlayıcının mesajını tam olarak okumaz, bunun yerine her kanıtlayıcının mesajındaki bitlerin küçük bir kısmını örnekler. Daha sonra derlenen STARK'ın basitliğe ulaşmasının nedeni budur.
IOP göz önüne alındığında, ondan nasıl bir STARK oluşturabilirim? Kanıtlayıcının mesajları çok uzun olabilir (aslında hesaplamanın kendisinden daha uzundurlar). Bu bilgiyi sıkıştırmak için Merkle ağaçlarını kullanıyoruz. Merkle ağacı, her yaprak düğümünün IOP'deki bir sorguyu veya yanıtı temsil ettiği ikili bir karma ağacıdır. Kökler tüm mesajın vaadidir. Doğrulayıcı bir mesajdaki belirli bir konumu okumak istediğinde, kanıtlayıcı bu konumun değerini ve doğrulama yolunu sağlar. Doğrulayıcı daha sonra değerin doğru olduğunu doğrulamak için bu yolu kullanabilir. IOP doğrulayıcısı, kanıtlayıcı bilgilerinden yalnızca küçük miktarda konum bilgisini okur. Bu nedenle Merkle ağaçları kullanılarak kısa protokoller (düşük iletişim hacmine sahip protokoller) uygulanabilir.
Sıkıştırma turları
Etkileşimli STARK'ı seçebiliriz, ancak STARK oluşturma sürecini basitleştirmek için genellikle etkileşimli olmayan STARK'ı seçeriz, böylece doğrulayıcının STARK'ı oluştururken harici bilgileri beklemesine gerek kalmaz. Aslında mevcut tüm STARK sistemleri bu şekilde konuşlandırılıyor ve ethSTARK protokolü bu şekilde oluşturuluyor. Etkileşimli olmayan STARK'lar aynı zamanda şeffaf SNARK'ların özel bir durumudur (şeffaflık, bunları başlatmak için hiçbir güvenilir kurulumun gerekli olmadığı anlamına gelir; "Arthur Merlin Protokolü" veya "Public Coin IOP"). Bunu yapmak için son adım, birden fazla etkileşim turunu tek bir mesaja sıkıştırmak için Fiat-Shamir algoritmasını uygulamaktır; buna STARK kanıtı adını veriyoruz. Fiat-Shamir dönüşümü, etkileşimli bir protokolü etkileşimli olmayan bir protokole dönüştürme yöntemidir. Kanıtlayıcı, karma işleviyle konuşurken etkileşimli bir protokolü simüle eder. i. tur için rastgele mücadeleyi türetmek amacıyla, kanıtlayıcı i. tur için kısmi kaydı hashler ve çıktıyı bir sonraki zorluk olarak yorumlar.
Bu, kanıtlayıcının, meydan okuma oluşturulduktan sonra cevabını değiştirememesini sağlar. Ancak hileyi kanıtlayan kişinin, etkileşimli GİB'lerde bulunmayan bazı yeni stratejik yolları vardır. Kanıtlayıcı, son kanıtlayıcı bilgisini değiştirerek doğrulayıcı sorgulamasını yeniden oluşturabilir, böylece yeni bir kayıt ve dolayısıyla yeni bir sorgulama elde eder. IOP'nin standart güvenilirlik konseptinin, Fiat-Shamir dönüşümünün güvenliğini kanıtlamak için yetersiz olduğu ortaya çıktı.
Örneğin, 96 turluk bir IOP'ye sahip olun ve doğrulayıcıya aşağıdaki hack'i ekleyin: Doğrulayıcının rastgeleliğinin ilk biti 96 turun her birinde 0 ise, doğrulayıcı bunu kabul edecektir (herhangi bir kanıt görmeden). Bu hack'i doğrulayıcıya eklemenin, GİB'in güvenilirlik hatasına yalnızca 2⁹⁶ terim eklediğini görebiliriz. Ancak Fiat-Shamir dönüşümünden sonra bir saldırgan, her karma değerinin 0 ile başlamasını sağlayacak şekilde kanıtlayıcı bilgisini kolaylıkla değiştirebilir ve bu sayede çok kısa sürede sisteme girebilir. İçiniz rahat olsun, bu korkunç senaryo yalnızca teorik bir örnektir ve konuşlandırılmış STARK'lar için geçerli değildir. Öyleyse STARK'ımızın neden güvenli olduğuna bir göz atalım. Kısaca saldırganın en fazla t adımda koştuğunu ve saldırının başarılı olma olasılığının en fazla (t) t 2⁹⁶ olduğunu göstereceğiz.
GİB ve her yönüyle güvenilirlik
STARK'ın güvenliği, temeldeki GİB'e bağlıdır. Peki bir IOP'nin 96 bit güvenliğe sahip olması ne anlama gelir? Standart tanım gereği, GİB'in güvenilirlik hatası 2⁹⁶'dir: bu, herhangi bir saldırganın (çalışma süresine bakılmaksızın) doğrulayıcıyı kandırma olasılığının en fazla 2-96 olduğu anlamına gelir. Ancak tartıştığımız gibi, IOP'nin güvenilirliği üç bileşenden yalnızca biridir ve bu, üç adımın tamamından derlenen bir STARK'tan 96 bitlik güvenlik elde etmek için yeterli değildir. Buna karşılık, derlenmiş STARK'ın güvenliği, STARK'ın 96 bitlik her turda bir güvenilirlik hatasına sahip olduğu varsayılarak kanıtlanmıştır (bazen durum kurtarma güvenilirliği olarak adlandırılan benzer bir tanım kullanılır).
Sezgisel olarak "her turda sağlamlık", yalnızca tüm protokolün değil, her turun 96 bit güvenliğe sahip olduğu anlamına gelir. Daha spesifik olmak gerekirse, her turda güvenilirlik, protokol kaydının bir kısmını elde edebilen ve bize bu kaydın "aldatıcı" olup olmadığını söyleyebilen bir yüklemin varlığını ifade eder: "boş kayıt" "aldatıcı" değildir ve Ve kaydın tamamı yalnızca doğrulayıcı tarafından kabul edildiğinde "aldatıcıdır". Son olarak, doğrulayıcıyı "sahtekarlık" yapmayan herhangi bir kısmi kayıt için, kaydın bir sonraki turda "sahtekarlık" haline gelme olasılığı en fazla 2⁹⁶'dir. Bu özelliklere sahip bir yüklem varsa, protokolün 96 bitlik yuvarlaktan-tura güvenilirliğe sahip olduğunu söyleriz (bu yüklem verimli hesaplama gerektirmez).
Çoğu durumda insanlar yalnızca GİB'in güvenilirliğini analiz eder, genel güvenilirliğini analiz etmez. Kuşkusuz, standart güvenilirliğe sahip ancak genel güvenilirliğe sahip olmayan bir IOP örneğini (üretilen örnekler hariç) düşünmek zordur. Bununla birlikte, belirli güvenlik sınırlarını türetirken ikisi arasında farklılıklar ortaya çıkabilir ve her bit önemlidir. Bu nedenle, sıkı ve spesifik sınırlar elde etmek için GİB'in her yönüyle güvenilirliğinin titiz bir analizi gereklidir. FRI protokolü ve STARK IOP'nin dayandığı ethSTARK IOP ile yaptığımız şey tam olarak budur. Analizin kendisi önemsiz olmaktan uzaktır ve bu makalenin kapsamı dışındadır. Yeni analizi kullanarak kanıtımız için kesin parametreler belirleyebiliriz.
Her yönüyle güvenilirlik bize gerçekten ihtiyacımız olan güvenceyi veriyor. Kanıtlayıcı, meydan okumayı birçok kez yeniden oluşturabilir, ancak herhangi bir turda hileli bir kayıt oluşturma olasılığının 2⁹⁶ olduğunu biliyoruz.Bu nedenle, eğer kanıtlayıcının t katı varsa (hash çağrılarının sayısıyla ölçülür), o zaman şunu deneyebilir: Başarı olasılığını (t) t 2⁹⁶ ile sınırlayan aldatıcı bir kayıt elde etmek için çoğu t kez.
Tüm hata öğelerini ekle
Son olarak, tüm bunların doğru olması için kanıtlayıcının Merkle ağacına müdahale edemeyeceğinden emin olmamız gerekir. Kanıtlayıcı hash fonksiyonunda hiçbir çarpışma bulamadığı sürece Merkle ağacında hile yapamayacağını gösterebiliriz. Bir saldırganın t çağrıları (rastgele karma işlevi) kullanarak bir çarpışma bulma olasılığı en fazla t2/2'dir, bu da karma işlevinin çıkış uzunluğudur ("Doğum Günü Paradoksu" nedeniyle oluşur). karma işlevi Uzunluk gerekli güvenliğin iki katıdır.Yani eğer çıkış uzunluğu 192 olan bir karma işlevimiz ve 96 bitlik her turda güvenilirliğe sahip bir IOP'miz varsa, güvenilir bir derlenmiş STARK elde ederiz Cinsel hata (t) )=t2-⁹⁶ + t2 2¹⁹⁶.t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵ olduğundan, bu şemada 95 bitlik güvenlik cinsiyeti vardır.
Özetle
Birlikte ele alındığında STARK, kamuya açık veriler üzerinde gerçekleştirilen hesaplamaların doğruluğunu güvenilir bir şekilde doğrulamak için güçlü bir yöntem sağlar. STARK'ın güvenliği genellikle "güvenilirlik hatası" ile ölçülür; bu, bir saldırganın başarıyla yanlış bir beyanda bulunması ve doğrulayıcıyı bir kanıtla ikna etmesi olasılığını temsil eder. 96 bit gibi gerekli güvenlik seviyesine ulaşmak için, her turda yüksek güvenlik seviyelerinin korunmasını sağlamak amacıyla temel IOP'nin her turda güvenilirliği karşılaması gerekir. Belirli güvenlik sınırlarını türetmek için STARK'ımızın temel aldığı GİB'lerin güvenilirliğini her yönüyle analiz ettik.
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.
STARK'ın tam güvenliğinin derinlemesine analizi
原文:Güvenli ve Sağlam — STARK Güvenliğine Derin Bir Bakış
Çeviri ve redaksiyon: "Starknet Çin Topluluğu"
Öne Çıkan Kısa Bilgiler
STARK güvenliğinin ayrıntılı açıklaması
STARK kanıt sistemi veya ölçeklenebilir şeffaf bilgi argümanı, hesaplama bütünlüğü için güçlü bir araçtır: kamuya açık veriler üzerinde gerçekleştirilen hesaplamaların doğruluğunun güvenilir bir şekilde doğrulanmasına olanak tanır. Bu makalede STARK kanıtlarının sağladığı güvenliği derinlemesine inceleyeceğiz, bunları tanımlayacağız ve şemaların güvenliğini kanıtlamaya yönelik teknikleri araştıracağız.
(Ayrıntılar için ethSTARK belgelerinin (versiyon 1.2) 6. bölümünü ve ayrıca Block ve arkadaşlarının bu konuyla ilgili önemli ve kapsamlı bağımsız çalışmasını okuyun).
Güvenlik analitiğiyle neyi başarmaya çalışıyoruz? Yanlış bir beyanın ve bu (yanlış) beyana yanıt olarak STARK doğrulayıcısı tarafından kabul edilen STARK kanıtının neden olduğu STARK sistemine yönelik "başarılı saldırıları" önlemek istiyoruz. Yanlış beyanlar tehlikeli olduğundan ve her boyutta ve biçimde olabileceğinden, bunların hepsine karşı güvende olmak istiyoruz. 1+1=3 kadar önemsiz bile olsa herhangi bir yanlış beyan, bir STARK doğrulayıcısı tarafından kabul edilen bir STARK kanıtıyla birleştirildiğinde, sisteme yapılan başarılı bir saldırı olarak kabul edilecektir. (Kriptografi geçmişi olanlar, STARK'ın bilgi güvenilirliği gibi daha güçlü güvenlik kavramlarını da karşılayabildiğini bilmek isteyebilirler, ancak basitlik adına bu makale güvenilirlikle ilgili basit durumlara odaklanacaktır).
Bir STARK sisteminin güvenliğini resmi olarak nasıl tanımlarız? Bunu "güvenilirlik hatası" analiziyle belirliyoruz. "Güvenilirlik hatası" kabaca bir saldırganın başarılı bir saldırı başlatmasının maliyetinin beklenen "maliyetini" ölçer (yani, yanlış bir beyan için bir STARK kanıtı bulun, ancak kanıt STARK doğrulayıcısı tarafından kabul edilir). Matematiksel olarak konuşursak, güvenilirlik hatası, girdisi saldırganın bir saldırı başlatmak için harcamak istediği hesaplama süresini temsil eden zaman parametresi t olan ve çıktısı da saldırganın saldırısının başarılı olma olasılığı olan bir fonksiyondur (t). yanlış ifadeler ikna edici kanıt). Saldırganın harcamak istediği "maliyet" ne kadar büyük olursa, başarı olasılığı da o kadar yüksek olur.
Şu ana kadar STARK'ın güvenliğini bir fonksiyon (t) olarak tanımladık; bu, herkesin kripto Twitter'da güvenliği her gün tartışmasından farklı. Twitter'da şöyle bir şey duyabilirsiniz: "Bu çözümün 96 bit güvenliği var." Bu bizim güvenlik tanımımıza nasıl yansıyor? İnsanlar "x bit güvenlik" ifadesini biraz farklı anladıkları için bunun tek bir cevabı yok:
Bu yazıda ikinci seçeneği tartışacağız.
96 bit güvenlikle IOP'tan STARK'a
Peki bir çözümün 96 bit güvenliğe sahip olduğunu nasıl kanıtlayacağız? Bu soruyu cevaplamak için STARK'ın üzerine inşa edildiği üst düzey yapıyı anlamamız gerekiyor. STARK üç ana bölümden oluşur: IOP (Etkileşimli Oracle Proof), Merkle ağacı ve Fiat-Shamir hash; ana odak noktamız IOP'dur. Bu bileşen parçaları belirlendikten sonra bunları bir STARK oluşturmak için derleyebiliriz. Ne oldukları ve birbirlerine nasıl uydukları da dahil olmak üzere bu bileşenleri ayrıntılı olarak inceleyeceğiz.
İnceleyeceğimiz ilk bileşen IOP'tur: IOP, kanıtlayıcı ve doğrulayıcının birden fazla tur boyunca etkileşimde bulunduğu standart etkileşimli kanıta benzer (doğrulayıcının kanıtlayıcıya yalnızca rastgele zorluklar gönderdiği genel para protokolleriyle sınırlıdır). Bir IOP'de doğrulayıcı, kanıtlayıcının mesajını tam olarak okumaz, bunun yerine her kanıtlayıcının mesajındaki bitlerin küçük bir kısmını örnekler. Daha sonra derlenen STARK'ın basitliğe ulaşmasının nedeni budur.
IOP göz önüne alındığında, ondan nasıl bir STARK oluşturabilirim? Kanıtlayıcının mesajları çok uzun olabilir (aslında hesaplamanın kendisinden daha uzundurlar). Bu bilgiyi sıkıştırmak için Merkle ağaçlarını kullanıyoruz. Merkle ağacı, her yaprak düğümünün IOP'deki bir sorguyu veya yanıtı temsil ettiği ikili bir karma ağacıdır. Kökler tüm mesajın vaadidir. Doğrulayıcı bir mesajdaki belirli bir konumu okumak istediğinde, kanıtlayıcı bu konumun değerini ve doğrulama yolunu sağlar. Doğrulayıcı daha sonra değerin doğru olduğunu doğrulamak için bu yolu kullanabilir. IOP doğrulayıcısı, kanıtlayıcı bilgilerinden yalnızca küçük miktarda konum bilgisini okur. Bu nedenle Merkle ağaçları kullanılarak kısa protokoller (düşük iletişim hacmine sahip protokoller) uygulanabilir.
Sıkıştırma turları
Etkileşimli STARK'ı seçebiliriz, ancak STARK oluşturma sürecini basitleştirmek için genellikle etkileşimli olmayan STARK'ı seçeriz, böylece doğrulayıcının STARK'ı oluştururken harici bilgileri beklemesine gerek kalmaz. Aslında mevcut tüm STARK sistemleri bu şekilde konuşlandırılıyor ve ethSTARK protokolü bu şekilde oluşturuluyor. Etkileşimli olmayan STARK'lar aynı zamanda şeffaf SNARK'ların özel bir durumudur (şeffaflık, bunları başlatmak için hiçbir güvenilir kurulumun gerekli olmadığı anlamına gelir; "Arthur Merlin Protokolü" veya "Public Coin IOP"). Bunu yapmak için son adım, birden fazla etkileşim turunu tek bir mesaja sıkıştırmak için Fiat-Shamir algoritmasını uygulamaktır; buna STARK kanıtı adını veriyoruz. Fiat-Shamir dönüşümü, etkileşimli bir protokolü etkileşimli olmayan bir protokole dönüştürme yöntemidir. Kanıtlayıcı, karma işleviyle konuşurken etkileşimli bir protokolü simüle eder. i. tur için rastgele mücadeleyi türetmek amacıyla, kanıtlayıcı i. tur için kısmi kaydı hashler ve çıktıyı bir sonraki zorluk olarak yorumlar.
Bu, kanıtlayıcının, meydan okuma oluşturulduktan sonra cevabını değiştirememesini sağlar. Ancak hileyi kanıtlayan kişinin, etkileşimli GİB'lerde bulunmayan bazı yeni stratejik yolları vardır. Kanıtlayıcı, son kanıtlayıcı bilgisini değiştirerek doğrulayıcı sorgulamasını yeniden oluşturabilir, böylece yeni bir kayıt ve dolayısıyla yeni bir sorgulama elde eder. IOP'nin standart güvenilirlik konseptinin, Fiat-Shamir dönüşümünün güvenliğini kanıtlamak için yetersiz olduğu ortaya çıktı.
Örneğin, 96 turluk bir IOP'ye sahip olun ve doğrulayıcıya aşağıdaki hack'i ekleyin: Doğrulayıcının rastgeleliğinin ilk biti 96 turun her birinde 0 ise, doğrulayıcı bunu kabul edecektir (herhangi bir kanıt görmeden). Bu hack'i doğrulayıcıya eklemenin, GİB'in güvenilirlik hatasına yalnızca 2⁹⁶ terim eklediğini görebiliriz. Ancak Fiat-Shamir dönüşümünden sonra bir saldırgan, her karma değerinin 0 ile başlamasını sağlayacak şekilde kanıtlayıcı bilgisini kolaylıkla değiştirebilir ve bu sayede çok kısa sürede sisteme girebilir. İçiniz rahat olsun, bu korkunç senaryo yalnızca teorik bir örnektir ve konuşlandırılmış STARK'lar için geçerli değildir. Öyleyse STARK'ımızın neden güvenli olduğuna bir göz atalım. Kısaca saldırganın en fazla t adımda koştuğunu ve saldırının başarılı olma olasılığının en fazla (t) t 2⁹⁶ olduğunu göstereceğiz.
GİB ve her yönüyle güvenilirlik
STARK'ın güvenliği, temeldeki GİB'e bağlıdır. Peki bir IOP'nin 96 bit güvenliğe sahip olması ne anlama gelir? Standart tanım gereği, GİB'in güvenilirlik hatası 2⁹⁶'dir: bu, herhangi bir saldırganın (çalışma süresine bakılmaksızın) doğrulayıcıyı kandırma olasılığının en fazla 2-96 olduğu anlamına gelir. Ancak tartıştığımız gibi, IOP'nin güvenilirliği üç bileşenden yalnızca biridir ve bu, üç adımın tamamından derlenen bir STARK'tan 96 bitlik güvenlik elde etmek için yeterli değildir. Buna karşılık, derlenmiş STARK'ın güvenliği, STARK'ın 96 bitlik her turda bir güvenilirlik hatasına sahip olduğu varsayılarak kanıtlanmıştır (bazen durum kurtarma güvenilirliği olarak adlandırılan benzer bir tanım kullanılır).
Sezgisel olarak "her turda sağlamlık", yalnızca tüm protokolün değil, her turun 96 bit güvenliğe sahip olduğu anlamına gelir. Daha spesifik olmak gerekirse, her turda güvenilirlik, protokol kaydının bir kısmını elde edebilen ve bize bu kaydın "aldatıcı" olup olmadığını söyleyebilen bir yüklemin varlığını ifade eder: "boş kayıt" "aldatıcı" değildir ve Ve kaydın tamamı yalnızca doğrulayıcı tarafından kabul edildiğinde "aldatıcıdır". Son olarak, doğrulayıcıyı "sahtekarlık" yapmayan herhangi bir kısmi kayıt için, kaydın bir sonraki turda "sahtekarlık" haline gelme olasılığı en fazla 2⁹⁶'dir. Bu özelliklere sahip bir yüklem varsa, protokolün 96 bitlik yuvarlaktan-tura güvenilirliğe sahip olduğunu söyleriz (bu yüklem verimli hesaplama gerektirmez).
Çoğu durumda insanlar yalnızca GİB'in güvenilirliğini analiz eder, genel güvenilirliğini analiz etmez. Kuşkusuz, standart güvenilirliğe sahip ancak genel güvenilirliğe sahip olmayan bir IOP örneğini (üretilen örnekler hariç) düşünmek zordur. Bununla birlikte, belirli güvenlik sınırlarını türetirken ikisi arasında farklılıklar ortaya çıkabilir ve her bit önemlidir. Bu nedenle, sıkı ve spesifik sınırlar elde etmek için GİB'in her yönüyle güvenilirliğinin titiz bir analizi gereklidir. FRI protokolü ve STARK IOP'nin dayandığı ethSTARK IOP ile yaptığımız şey tam olarak budur. Analizin kendisi önemsiz olmaktan uzaktır ve bu makalenin kapsamı dışındadır. Yeni analizi kullanarak kanıtımız için kesin parametreler belirleyebiliriz.
Her yönüyle güvenilirlik bize gerçekten ihtiyacımız olan güvenceyi veriyor. Kanıtlayıcı, meydan okumayı birçok kez yeniden oluşturabilir, ancak herhangi bir turda hileli bir kayıt oluşturma olasılığının 2⁹⁶ olduğunu biliyoruz.Bu nedenle, eğer kanıtlayıcının t katı varsa (hash çağrılarının sayısıyla ölçülür), o zaman şunu deneyebilir: Başarı olasılığını (t) t 2⁹⁶ ile sınırlayan aldatıcı bir kayıt elde etmek için çoğu t kez.
Tüm hata öğelerini ekle
Son olarak, tüm bunların doğru olması için kanıtlayıcının Merkle ağacına müdahale edemeyeceğinden emin olmamız gerekir. Kanıtlayıcı hash fonksiyonunda hiçbir çarpışma bulamadığı sürece Merkle ağacında hile yapamayacağını gösterebiliriz. Bir saldırganın t çağrıları (rastgele karma işlevi) kullanarak bir çarpışma bulma olasılığı en fazla t2/2'dir, bu da karma işlevinin çıkış uzunluğudur ("Doğum Günü Paradoksu" nedeniyle oluşur). karma işlevi Uzunluk gerekli güvenliğin iki katıdır.Yani eğer çıkış uzunluğu 192 olan bir karma işlevimiz ve 96 bitlik her turda güvenilirliğe sahip bir IOP'miz varsa, güvenilir bir derlenmiş STARK elde ederiz Cinsel hata (t) )=t2-⁹⁶ + t2 2¹⁹⁶.t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵ olduğundan, bu şemada 95 bitlik güvenlik cinsiyeti vardır.
Özetle
Birlikte ele alındığında STARK, kamuya açık veriler üzerinde gerçekleştirilen hesaplamaların doğruluğunu güvenilir bir şekilde doğrulamak için güçlü bir yöntem sağlar. STARK'ın güvenliği genellikle "güvenilirlik hatası" ile ölçülür; bu, bir saldırganın başarıyla yanlış bir beyanda bulunması ve doğrulayıcıyı bir kanıtla ikna etmesi olasılığını temsil eder. 96 bit gibi gerekli güvenlik seviyesine ulaşmak için, her turda yüksek güvenlik seviyelerinin korunmasını sağlamak amacıyla temel IOP'nin her turda güvenilirliği karşılaması gerekir. Belirli güvenlik sınırlarını türetmek için STARK'ımızın temel aldığı GİB'lerin güvenilirliğini her yönüyle analiz ettik.