Shoal çerçevesi: Aptos üzerindeki Bullshark gecikme süresinde büyük bir düşüş

Aptos Labs, son zamanlarda DAG BFT'deki iki önemli açık problemi çözdü, gecikmeyi önemli ölçüde düşürdü ve belirleyici gerçek protokollerde zaman aşımı gereksinimini ilk kez ortadan kaldırdı. Genel olarak, arızasız durumlarda Bullshark'ın gecikmesi %40 oranında iyileşirken, arızalı durumlarda %80 oranında iyileşti.

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

Tekniğimiz oldukça basit, temel protokollerin birden fazla örneğini sırayla çalıştırmayı içeriyor. Bu nedenle, Bullshark'ı örneklendirirken, bir grup "köpekbalığı"nın devam eden bir bayrak yarışı yaptığını görüyoruz.

Motivasyon

Blok zinciri ağlarının yüksek performansını hedeflerken, insanlar iletişim karmaşıklığını azaltmaya odaklandı. Ancak, bu yöntem önemli bir artırma sağlamadı. Örneğin, Diem'in erken sürümlerinde uygulanan Hotstuff yalnızca 3500 TPS sağladı, bu da 100k+ TPS hedefimize göre oldukça düşük.

Ancak, son dönemdeki atılım, veri yayılımının liderlik protokolüne dayalı ana engel olduğunu ve paralelleşmeden faydalanabileceğini anlamaktan kaynaklanmaktadır. Narwhal sistemi veri yayılımını ana konsensüs mantığından ayırmakta ve tüm doğrulayıcıların aynı anda veri yaydığı, konsensüs bileşeninin yalnızca daha az miktarda meta veriyi sıraladığı bir mimari önermektedir. Narwhal makalesi 160.000 TPS'lik bir verimliliği rapor etmiştir.

Önceki makalede Quorum Store'u tanıttık. Narwhal uygulamamız veri yayılımını konsensüsten ayırıyor ve bunu mevcut konsensüs protokolü Jolteon'u genişletmek için nasıl kullandığımızı anlatıyoruz. Jolteon, Tendermint'in doğrusal hızlı yolu ile PBFT tarzı görünüm değişikliklerini birleştiren liderliğe dayalı bir protokoldür ve Hotstuff'un gecikmesini %33 oranında düşürür. Ancak, liderliğe dayalı konsensüs protokolünün Narwhal'ın işleme potansiyelinden tam olarak yararlanamadığı açık. Veri yayılımını konsensüsten ayırmış olsak da, işleme kapasitesi arttıkça Hotstuff/Jolteon'un liderleri hala sınırlıdır.

Bu nedenle, Bullshark'ı, sıfır iletişim maliyetine sahip bir konsensüs protokolü olarak Narwhal DAG'ın üstüne dağıtmaya karar verdik. Ne yazık ki, Jolteon ile karşılaştırıldığında, Bullshark'ın yüksek verimliliği destekleyen DAG yapısı %50'lik bir gecikme süresi maliyeti getirdi.

Bu makalede, Shoal'un Bullshark gecikme süresini önemli ölçüde nasıl azaltacağını tanıtıyoruz.

DAG-BFT Arka Planı

Bu makalenin ilgili arka planını anlamakla başlayalım.

Narwhal DAG'daki her tepe noktası bir tur ile ilişkilidir. r.turuna girmek için, doğrulayıcının önce r-1.turuna ait n-f tepe noktasını elde etmesi gerekir. Her doğrulayıcı her turda bir tepe noktasını yayınlayabilir, her tepe noktası en az bir önceki turun n-f tepe noktasını referans almalıdır. Ağın asenkron olmasından dolayı, farklı doğrulayıcılar herhangi bir zamanda DAG'ın farklı yerel görüntülerini gözlemleyebilir.

DAG'ın bir ana özelliği belirsiz değildir: Eğer iki doğrulayıcı düğüm, DAG yerel görünümlerinde aynı v tepe noktasına sahipse, o zaman tamamen aynı v nedensel geçmişine sahiptirler.

Genel Sıralama

DAG'daki tüm düğümlerin toplam sırasını 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ı düğümlerin önerileri, kenarların ise oylamaları temsil ettiği bir uzlaşma protokolü olarak yorumlar.

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. Belirlenen Kilit Nokta: Her birkaç turda (, örneğin, Bullshark'taki iki turda ), önceden belirlenmiş bir lider olacaktır, liderin zirvesine kilit nokta denir;

2. Sıralama Bağlantısı: Doğrulayıcılar bağımsız ancak belirleyici bir şekilde hangi bağlantıları sıralayacaklarına ve hangi bağlantıları atlayacaklarına karar verir;

3. Sebep-sonuç tarihinin sıralanması: Doğrulayıcılar, sıralı referans noktası listesini tek tek işler ve her bir referans noktası için, kesin kurallar aracılığıyla sebep-sonuç tarihindeki tüm önceki düzensiz köşeleri sıralar.

Güvenlik sağlamak için anahtar, yukarıdaki adım (2)'de, tüm dürüst doğrulayıcı düğümlerin aynı ön eki paylaşacak şekilde sıralı bir sabit nokta listesi oluşturmasını sağlamaktır. Shoal'de, yukarıdaki tüm protokollerle ilgili aşağıdaki gözlemleri yapıyoruz:

Tüm doğrulayıcılar ilk sıralı referans noktasında hemfikirdir.

Bullshark gecikme süresi

Bullshark'ın gecikme süresi, DAG içindeki sıralı sabit noktalar arasındaki döngü sayısına bağlıdır. Bullshark'ın en pratik kısım senkron versiyonu, asenkron versiyona göre daha iyi bir gecikme süresine sahip olmasına rağmen, bu en iyi değildir.

Soru 1: Ortalama blok gecikmesi. Bullshark'ta her çift turda bir sabit nokta vardır, her tek turun zirvesi ise oy verme olarak yorumlanır. Yaygın durumlarda, sabit noktaları sıralamak için iki tur DAG gereklidir, ancak sabit noktanın neden-sonuç geçmişindeki zirvelerin sıralanmasını beklemek için daha fazla tura ihtiyaç duyulmaktadır. Yaygın durumlarda, tek turdaki zirvelerin üç tura, çift turdaki sabit nokta olmayan zirvelerin ise dört tura ihtiyacı vardır.

Soru 2: Arıza durumu gecikmesi, yukarıdaki gecikme analizi arızasız durumlar için geçerlidir, diğer yandan, eğer bir tur lideri yeterince hızlı bir şekilde referans noktalarını yayınlayamazsa, referans noktaları sıralanamaz ( bu nedenle atlanır ), bu nedenle önceki turlardaki sıralanmamış tüm 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 düşürür, özellikle Bullshark zaman aşımının lideri beklemek için kullanılması nedeniyle.

Shoal çerçevesi

Shoal, bu iki gecikme süresi sorununu çözdü, Bullshark( veya herhangi başka bir Narwhal tabanlı BFT protokolünü ) güçlendiren bir pipeline aracılığıyla, her turda bir referans noktası olmasına izin vererek ve DAG'daki tüm referans noktası olmayan düğümlerin gecikmesini üç tura indirerek çalışır. Shoal ayrıca DAG'da sıfır maliyetli lider itibar mekanizması getirerek, hızlı liderlerin seçilmesini sağlıyor.

Zorluk

DAG protokolü bağlamında, boru hattı ve liderin itibarı zorlu sorunlar olarak kabul edilmektedir, nedenleri ise şunlardır:

1. Önceki akış şeması, temel Bullshark mantığını değiştirmeye çalıştı, ancak bu özünde imkansız gibi görünüyor.

2. Liderlerin itibarı DiemBFT'de tanıtılmış ve Carousel'de resmileştirilmiştir, bu, doğrulayıcıların geçmiş performansına dayanarak gelecekteki liderlerin dinamik olarak seçilmesi fikridir. Liderlik kimliğinde bir ayrımcılık olması bu protokollerin güvenliğini ihlal etmemekle birlikte, Bullshark'ta tamamen farklı bir sıralamaya yol açabilir, bu da sorunun özünü ortaya çıkarır; döngü çivisini dinamik ve belirleyici bir şekilde seçmek, konsensüsü çözmek için gereklidir ve doğrulayıcıların gelecekteki çivileri seçmek için sıralı geçmiş üzerinde uzlaşmaları gerekmektedir.

Sorunun zorluğuna dair bir kanıt olarak, Bullshark'ın uygulamasının, şu anda üretim ortamında olan uygulamanın, bu özellikleri desteklemediğini belirtiyoruz.

Protokol

Bu zorluklara rağmen, bir atasözünde denildiği gibi, çözümün basitliğin arkasında gizli olduğu kanıtlandı.

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ın temel içgörüsünü kabul etmesiyle, Shoal birden fazla Bullshark örneğini sıralı bir şekilde bir araya getirerek 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ış Hattı

V haritası vardır. Shoal, her bir örnek için ankrajın F haritası ile önceden belirlendiği şekilde Bullshark örneklerini birer birer çalıştırır. Her örnek bir ankraj talep eder, bu da bir sonraki örneğe geçişi tetikler.

Başlangıçta, Shoal DAG'ın ilk turunda Bullshark'ın ilk örneğini başlattı ve ilk sıralı referans noktasının belirlendiği zamana kadar bunu çalıştırdı, örneğin r. turda. Tüm doğrulayıcılar bu referans noktasında hemfikirdi. Böylece, tüm doğrulayıcılar r+1. turdan itibaren DAG'ı yeniden yorumlamayı kesin bir şekilde kabul edebilirler. Shoal, r+1. turda yeni bir Bullshark örneği başlattı.

En iyi durumda, bu, Shoal'ın her turda bir çapa sipariş etmesine izin verir. İlk turdaki çapa noktaları, ilk örneğe göre sıralanır. Ardından, Shoal ikinci turda yeni bir örnek başlatır, bunun kendine ait bir çapa noktası vardır, bu çapa bu örneğe göre sıralanır, sonra üçüncü turda başka bir yeni örnek çapa noktası sipariş eder ve bu süreç devam eder.

Liderlerin İtibarı

Bullshark sıralama sırasında bağlantı noktaları atlandığında, gecikme süresi artar. Bu durumda, boru hattı teknolojisi etkisizdir çünkü yeni bir örnek, önceki örneğin bağlantı noktalarını sipariş etmesinden önce başlatılamaz. Shoal, her doğrulama düğümünün son etkinlik tarihine dayalı olarak her bir doğrulama düğümüne bir puan vererek, gelecekte ilgili liderin kaybolan bağlantı noktalarını işleme ihtimalinin düşük olmasını sağlamak için bir itibar mekanizması kullanır. Protokole yanıt veren ve katılan doğrulayıcılar yüksek puan alacak, aksi takdirde doğrulama düğümleri düşük puan alacak, çünkü çökme, yavaşlama veya kötü davranış sergileme olasılıkları vardır.

Felsefesi, her puan güncellemesinde, yüksek puan alan liderleri tercih ederek, turlar ile liderler arasındaki önceden tanımlanmış F haritasını kesin olarak yeniden hesaplamaktır. Doğrulayıcıların yeni harita üzerinde uzlaşabilmesi için, puanlar üzerinde uzlaşmaları ve böylece puan türetiminde kullanılan geçmiş üzerinde uzlaşmaları gerekmektedir.

Shoal'da, akış ve liderlik itibarı doğal olarak bir araya gelebilir, çünkü her ikisi de ilk sıralı ankra noktası üzerinde anlaşmaya varıldıktan sonra DAG'ı yeniden yorumlamak için aynı temel teknolojiyi kullanır.

Aslında, tek fark, r. turda sabit noktaların sıralanmasından sonra, doğrulayıcıların sadece r. turda sıralı sabit noktaların nedensel geçmişine dayanarak r+1. turdan itibaren yeni bir haritalama F' hesaplaması gerektiğidir. Ardından, doğrulama düğümleri r+1. turdan itibaren güncellenmiş sabit nokta seçim fonksiyonu F' ile Bullshark'ın yeni örneğini gerçekleştirir.

Daha fazla zaman aşımı yok

Zaman aşımı, lider tabanlı belirleyici kısmi senkron BFT uygulamalarında kritik bir rol oynamaktadır. Ancak, bu uygulamaların getirdiği karmaşıklık, yönetilmesi ve izlenmesi 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ı, uygun şekilde yapılandırılmaları çok önemli olduğu için gecikmeyi önemli ölçüde artırabilir ve genellikle dinamik olarak ayarlanması gerekir, çünkü bu ortam ( ağına ) yüksek derecede bağımlıdır. Protokol, bir sonraki lidere geçmeden önce arızalı lider için tam zaman aşımı gecikme cezası ödeyecektir. Bu nedenle, zaman aşımı ayarları çok ihtiyatlı olmamalıdır, ancak zaman aşımı süresi çok kısa olursa, protokol iyi liderleri atlayabilir. Örneğin, biz gözlemliyoruz