Shoal çerçevesi: Aptos'taki Bullshark gecikme süresini nasıl azaltır

Genel Bakış

Aptos laboratuvarları, DAG BFT'deki iki önemli açık problemi çözdü, gecikme süresini büyük ölçüde azalttı ve belirli gerçek protokollerde zaman aşımına olan ihtiyacı ilk kez ortadan kaldırdı. Genel olarak, arızasız durumlarda Bullshark'ın gecikmesi %40, arızalı durumlarda ise %80 oranında iyileştirildi.

Shoal, Narwhal tabanlı konsensüs protokolünü ( gibi DAG-Rider, Tusk, Bullshark), akış hattı ve lider reputasyonu ile güçlendiren bir çerçevedir. Akış hattı, her turda referans noktaları ekleyerek DAG sıralama gecikmesini azaltır, lider reputasyonu ise referans noktalarının en hızlı doğrulama düğümleriyle ilişkilendirilmesini sağlayarak gecikmeyi daha da iyileştirir. Ayrıca, lider reputasyonu, Shoal'ın tüm senaryolar için zaman aşımını ortadan kaldırmak amacıyla asenkron DAG yapısını kullanmasına olanak tanır. Bu, Shoal'ın genellikle gereken iyimser yanıtları içeren evrensel yanıt olarak adlandırdığımız özelliği sunmasını sağlar.

Tekniğimiz oldukça basit, temel protokollerin sıralı olarak çalıştırıldığı birden fazla örneği içeriyor. Bu nedenle, Bullshark ile örneklendirildiğinde, bir grup "köpekbalığı"nın bayrak yarışı yaptığı bir durum elde ediyoruz.

Motif

Kişiler, blok zinciri ağlarının yüksek performansını hedeflerken iletişim karmaşıklığını azaltmaya odaklanmışlardır. Ancak, bu yaklaşım önemli bir throughput artışı sağlamamıştır. Örneğin, Diem'in erken versiyonunda uygulanan Hotstuff yalnızca 3500 TPS gerçekleştirmiştir, bu da 100k+ TPS hedefine kıyasla oldukça düşüktür.

Son dönemdeki atılım, veri iletiminin liderlerin protokollerine dayandığını ve paralelleşmeden fayda sağlanabileceğini anlamaktan kaynaklanıyor. Narwhal sistemi veri iletimini ana konsensüs mantığından ayırarak, tüm doğrulayıcıların aynı anda veri ilettiği ve konsensüs bileşeninin yalnızca az sayıda meta veriyi sıraladığı bir mimari öneriyor. Narwhal belgesi 160.000 TPS'lik bir verimlilik bildirmektedir.

Daha önce Quorum Store'u tanıttık, yani Narwhal uygulamamızın verileri nasıl dağıttığını ve konsensüsü nasıl ayırdığını, ayrıca bunu mevcut konsensüs protokolü Jolteon'u genişletmek için nasıl kullandığını. Jolteon, Tendermint'in lineer hızlı yolu ve PBFT tarzı görünüm değişikliklerini birleştiren lider tabanlı bir protokoldür ve Hotstuff gecikmesini %33 oranında azaltır. Ancak, lider tabanlı konsensüs protokolleri Narwhal'ın throughput potansiyelinden tam olarak yararlanamaz. Verilerin dağıtımını ve konsensüsü ayırmış olmasına rağmen, throughput arttıkça Hotstuff/Jolteon'un lideri hala sınırlıdır.

Bu nedenle, Bullshark'ı, sıfır iletişim maliyetine sahip bir konsensüs protokolü olarak Narwhal DAG'ın üzerine dağıtmaya karar verdik. Ne yazık ki, Bullshark'ın yüksek işlem hacmini destekleyen DAG yapısı %50 gecikme süresi maliyetine neden oldu.

Bu makalede Shoal'un Bullshark gecikme süresini nasıl önemli ölçüde azalttığı açıklanmaktadır.

DAG-BFT Arka Planı

Narwhal DAG'daki her bir düğüm bir tur ile ilişkilidir. r. tura girmek için, doğrulayıcı öncelikle r-1. tura ait n-f düğümünü elde etmelidir. Her doğrulayıcı her turda bir düğüm yayabilir ve her düğüm en az bir önceki turdaki n-f düğümünü referans almalıdır. Ağın asenkron olması nedeniyle, farklı doğrulayıcılar herhangi bir anda DAG'ın farklı yerel görünümlerini gözlemleyebilir.

DAG'ın bir ana özelliği belirsizlik olmamasıdır: Eğer iki doğrulama düğümü DAG'ın yerel görünümünde aynı v tepe noktasına sahipse, o zaman onların v'nin nedensel geçmişi tamamen aynıdır.

Tam Sıralama

DAG'daki tüm düğümlerin toplam sırası, ek iletişim maliyeti olmadan uzlaşma sağlanabilir. Bunun için, DAG-Rider, Tusk ve Bullshark'taki doğrulayıcılar, DAG yapısını bir uzlaşma protokolü olarak yorumlar; burada düğümler önerileri, kenarlar ise oylamayı temsil eder.

DAG yapısındaki topluluk kesişim mantığı farklı olsa da, mevcut tüm Narwhal tabanlı konsensüs protokolleri aşağıdaki yapıya sahiptir:

1. önceden belirlenmiş nokta: her birkaç turda ( Bullshark'taki iki turda ) bir önceden belirlenmiş lider vardır, liderin zirvesi nokta olarak adlandırılır;

2. Sıralama bağlantı noktası: doğrulayıcılar bağımsız olarak ancak kesin bir şekilde hangi bağlantı noktalarının sıralanacağını ve hangi bağlantı noktalarının atlanacağını belirler;

3. sıralama neden-sonuç geçmişi: doğrulayıcılar sırayla sıralı referans noktası listesini işler, her referans noktası için, neden-sonuç geçmişindeki tüm önceki düzensiz düğümleri bazı belirleyici kurallara göre sıralar.

Güvenliğin anahtarı, adım (2)'de, tüm dürüst doğrulayıcı düğümlerin oluşturduğu sıralı köprü listesinin aynı öneki paylaşmasını sağlamaktır. Shoal'da, yukarıda belirtilen tüm protokollerle ilgili aşağıdaki gözlemleri yapıyoruz:

Tüm doğrulayıcılar ilk sıralı bağlantıya katılır.

Bullshark gecikme süresi

Bullshark'ın gecikme süresi, DAG içindeki sıralı sabit noktalar arasındaki tur sayısına bağlıdır. Bullshark'ın en pratik kısmı, senkron versiyonunun asenkron versiyona göre daha iyi gecikmeye sahip olmasıdır, ancak bu hala en iyi değildir.

Soru 1: Ortalama blok gecikme süresi. Bullshark'ta, her çift turda bir ana nokta vardır, her tek turdaki tepe noktası ise oy verme olarak yorumlanır. Yaygın durumlarda, ana noktaları sıralamak için iki tur DAG gereklidir, ancak ana noktanın nedensel geçmişindeki tepe noktalarının sıralanması için daha fazla tura ihtiyaç vardır. Yaygın durumlarda, tek turdaki tepe noktaları üç tura, çift turdaki ana nokta olmayan tepe noktaları ise dört tura ihtiyaç duyar.

Soru 2: Arıza durumu gecikme süresi, yukarıdaki gecikme analizi arızasız durumlar için geçerlidir, öte yandan, eğer bir turdaki lider yeterince hızlı bir şekilde referans noktalarını yayınlayamazsa, referans noktaları sıralanamaz ( bu nedenle atlanır ), bu nedenle önceki turlardaki tüm sıralanmamış zirveler bir sonraki referans noktasının sıralanmasını beklemek zorundadır. Bu, coğrafi çoğaltma ağının performansını önemli ölçüde azaltır, özellikle Bullshark lideri beklemek için zaman aşımı kullandığından.

Shoal çerçevesi

Shoal, bu iki gecikme süresini çözdü; Bullshark( veya herhangi bir Narwhal tabanlı BFT protokolü ) üzerinden, her turda bir referans noktası olmasını sağlayarak, DAG'deki tüm referans noktası olmayan düğümlerin gecikmesini üç tura indirdi. Shoal ayrıca DAG'de sıfır maliyetli lider itibar mekanizması tanıttı, bu da seçimlerin hızlı liderlere yönelmesini sağlıyor.

Mücadele

DAG protokolü bağlamında, boru hattı ve liderlerin itibarı zor sorunlar olarak kabul edilmektedir, sebepleri şunlardır:

1. Önceki üretim hattı, temel Bullshark mantığını değiştirmeye çalıştı, ancak bu temelde imkansız görünüyor.

2. Liderlerin itibarı, DiemBFT içinde tanıtılmış ve Carousel'de resmileştirilmiştir, bu, doğrulayıcıların geçmiş performansına dayanarak gelecekteki liderlerin dinamik seçimidir. ( Bullshark'taki referans noktası olan ) fikridir. Liderlik kimliğinde bir ayrılık olması bu protokollerin güvenliğini ihlal etmez, ancak Bullshark'ta tamamen farklı bir sıralama ile sonuçlanabilir, bu da sorunun özünü gündeme getirir; yani dinamik ve belirleyici bir şekilde döngü referansını seçmek, uzlaşmayı sağlamak için gereklidir ve doğrulayıcıların gelecekteki referans noktalarını seçmek için sıralı tarih üzerinde uzlaşmaları gerekir.

Sorun zorluğunun bir kanıtı olarak, Bullshark'ın uygulanmasına dikkat ettik; şu anda üretim ortamında bulunan uygulama, bu özellikleri desteklememektedir.

Protokol

Yukarıda belirtilen zorluklara rağmen, çözüm basitliğin içinde gizlidir.

Shoal'da, DAG üzerinde yerel hesaplama yapabilme yeteneğine güveniyoruz ve önceki turların bilgilerini saklama ve yeniden yorumlama yeteneğini gerçekleştirdik. Tüm doğrulayıcıların ilk sıralı referans noktasını kabul etmesi temel içgörüsü ile, Shoal birden fazla Bullshark örneğini sıralı bir şekilde birleştirerek bunları ardışık işleme tabi tutar, böylece ( ilk sıralı referans noktası örneklerin geçiş noktasıdır ve ) referans noktasının nedensel geçmişi liderin itibarını hesaplamak için kullanılır.

Akış Şeması

V haritalaması vardır. Shoal, her bir örnek için bağlantı noktalarının F haritalaması ile önceden belirlendiği şekilde, Bullshark'ın örneklerini birer birer çalıştırır. Her örnek bir bağlantı noktasını sıralar ve bu, bir sonraki örneğe geçişi tetikler.

İlk olarak, Shoal, DAG'ın ilk turunda Bullshark'ın ilk örneğini başlattı ve bunu ilk sıralı sabit nokta belirlenene kadar çalıştırdı, örneğin r. turda. Tüm doğrulayıcılar bu sabit noktayı kabul etti. Bu nedenle, tüm doğrulayıcılar r+1. turdan itibaren DAG'ı yeniden yorumlamada kesin olarak hemfikir olabilirler. Shoal, sadece r+1. turda yeni bir Bullshark örneğini başlattı.

En iyi durumda, bu, Shoal'ın her turda bir ana nokta sıralamasına olanak tanır. İlk turda ana noktalar ilk örneğe göre sıralanır. Ardından, Shoal ikinci turda yeni bir örnek başlatır, bu örneğin kendisi bir ana noktaya sahiptir, bu ana nokta o örneğe göre sıralanır, sonra başka bir yeni örnek üçüncü turda ana noktayı sıralar, ardından bu süreç devam eder.

Liderlerin Ünü

Bullshark sıralama sırasında, ankraj noktalarını atlamak gecikme süresini artırır. Bu durumda, önceki örnek sıralama ankraj noktasından önce yeni örneklerin başlatılması imkansız olduğundan, pipeline teknolojisi bir şey yapamaz. Shoal, her doğrulama düğümünün son aktivitelerinin tarihine dayalı bir puan atayarak, gelecekte kaybolan ankraj noktalarını işlemek için ilgili liderlerin seçilme olasılığını azaltmayı sağlar. Protokole yanıt veren ve katılan doğrulayıcılar yüksek puan alacak, aksi takdirde doğrulama düğümleri çökebileceği, yavaşlayabileceği veya kötü niyetli olabileceği için düşük puan alacaktır.

Felsefesi, her puan güncellemesinde, belirli bir şekilde liderlere önceden tanımlanmış F haritalamasını yeniden hesaplamak ve daha yüksek puan alan liderlere yönelmektir. Doğrulayıcıların yeni haritalama üzerinde uzlaşabilmesi için, puanlar üzerinde uzlaşmaları ve böylece puan türetiminde kullanılan tarihte uzlaşmaları gerekmektedir.

Shoal'da, akış hattı ve liderlik itibarı doğal olarak bir araya gelebilir, çünkü her ikisi de DAG'ı ilk sıralı sabit nokta üzerinde uzlaşma sağlandıktan sonra yeniden yorumlamak için aynı temel teknolojiyi kullanır.

Aslında, tek fark, r. turda referans noktalarının sıralandıktan sonra, doğrulayıcıların yalnızca r. turda sıralı referans noktalarının nedensel geçmişine dayanarak r+1. turdan itibaren yeni bir harita F' hesaplaması gerektiğidir. Ardından, doğrulama düğümleri r+1. turdan itibaren güncellenmiş referans noktası seçim fonksiyonu F' kullanarak Bullshark'ın yeni bir örneğini gerçekleştirir.

Daha fazla zaman aşımı yok

Zaman aşımı, lider tabanlı belirleyici kısmi senkronizasyon BFT uygulamalarında kritik bir rol oynamaktadır. Ancak, bunların getirdiği karmaşıklık, yönetilmesi ve gözlemlenmesi gereken iç durumların sayısını artırmakta, bu da hata ayıklama sürecinin karmaşıklığını artırmakta ve daha fazla gözlemlenebilirlik tekniği gerektirmektedir.

Zaman aşımı, gecikme süresini önemli ölçüde artıracaktır, çünkü bunları uygun şekilde yapılandırmak çok önemlidir ve genellikle dinamik olarak ayarlanması gerekir, çünkü bu, çevre ( ağına ) yüksek derecede bağımlıdır. Protokol, bir sonraki liderine geçmeden önce arızalı lider için tam zaman aşımı gecikme cezasını ödeyecektir. Bu nedenle,