Ripple Konsensus Algoritması

Ön söz

Merhabalar, Ripple’ın Konsensus Algoritması üzerine yapılmış dokümantasyonu okurken çıkarmış olduğum notları sizlerle paylaşmaktan mutluluk duyuyorum. Dokümantasyondaki başlıklarla paralel olacak şekilde başlıklandırma yaptım bu sayede merak ettiğiniz yerleri dokümantasyona gidip inceleyebilirsiniz. Keyifli okumalar!

1. Giriş

Ripple dağıtık sistmelerdeki teknik sorunları 3’e ayırıyor

1.1 Doğruluk Problemi

Doğruluktan kasıt geçerli bir işlem ile geçersiz bir işlemin ayırt edilmesine atıfta bulunulmasıdır. Gündelik dünyada bu kurumlar arası güvene ve kriptografik imzalara dayanıyor. Dağıtık sistemlerde herhangi bir güvene ihtiyaç duyulmadığı gibi kimlik doğrulamaya dahi gerek kalmıyor.

1.2 Uzlaşma Problemi

Uzlaşma problemi bir işlemin ağdaki herkes tarafından kabul edilmemesi ve sonraki işlemlerin bu işlemden haberdar olacak şekilde gerçekleştirilmemesi sorunudur. Zararlı bir kullanıcı aynı anda 2 doğru işlemi ağa yollayarak zararlı bir sonuç çıkmasına sebep olabilir. Kullanıcı, hesabında sadece 1 işleme yetecek miktarla 2 tane doğru işlem yollayarak bu işlemleri kabul ettirirse Çifte Harcama Problemine sebep olmaktadır. Bu yüzden herkes tarafından üzerinde uzlaşılmış işlemlerin olduğu bir ağa ihtiyacımız vardır.

1.3 Kullanılabilirlik Problemi

Bu terim genel olarak sistem çalışmasının kolaylaştırılması problemini ele almaktadır. Bu kolaylaştırmanın alt başlıklarına ise ağın hızlandırılması ve sisteme katılmak için gerekli hesaplama gücünün düşürülmesi örnek verilebilir.

2. Tanım, Formalizasyon ve Önceki Konsensuslar

2.1 Ripple Protokolünün Bileşenleri

Sunucu ( Server ) : Ripple yazılımını çalıştıran herkese denir. Tek görevi para transferidir.

Cüzdan : Her kullanıcının hesabındaki miktarı tutan bileşendir. Her işlemde güncellenir.

Kapalı Cüzdan : Kapalı Cüzdan, konsensus süreci tarafından onaylanan en son cüzdandır ve bu nedenle ağın mevcut durumunu temsil eder.

Açık Cüzdan : Bu cüzdan her sunucunun; işlemleri, üzerinde uzlaşılıp Kapalı Cüzdana dönüşene kadar beklettiği yerdir.

Benzersiz Düğüm Listesi (BDL) : Her sunucu bir BDL’ye sahiptir. Sunucular, bu BDL’lere sadece güvendikleri diğer sunucuları eklerler ve konsensusa varırken BDL’deki sunucuların oylarına göre karar verirler. Bir BDL’de ağdaki her sunucunun bulunması zorunlu değildir.

Önergeci : Her sunucu konsensus süreci için işlem listesi önerebilir ve önerir ancak bu süreçte herhangi bir sunucu (s1 diyelim mesela) sadece kendi BDL’sindeki sunucuların işlemlerini dikkate alır. Yani s1 sunucusu için önemli olan kendi BDL’sindeki sunucuların önerdikleri işlemlerdir.

2.2 Formalizasyon

Bilgi bozulması sorunları, adaptasyon sorunları veya Bizans hatalarıyla karşılaşılan sunuculara hatalı sunucu deniyor. Bizans hatalarıyla karşılaşmayan sunuculara ise hatasız sunucu deniyor.

Ripple Protokolü işlem onayını ikili seçim problemine indirgiyor. Yani her düğüm kendilerine 1 veya 0 şeklinde verilen seçenekelerden birini seçerek uzlaşıya varıyor.

Consensus aşağıdaki 3 aksiyoma göre tasarlanmış :

C1 : dürüst olan her sunucu belirli bir zaman içerisinde karara varmalıdır.

C2 : her dürüst sunucu aynı karara varmalıdır.

C3 : 0 veya 1 dürüst sunucuların karar verebilmesi için tek uygun seçeneklerdir. Yani bir sunucu ya 0 ya 1, ya evet ya hayır şeklinde kararlarla karşılaşır.

2.3 Halihazırda Var Olan Consensus Algoritmaları

İlk konsensus algoritmalarında düğümler asenkron olarak çalışıyorlardı bu yüzden de en ufak bir hata konsensus için yıkıcı olabiliyordu. Bu, senkronizasyona ihtiyaç olduğunu anlamamızı sağladı.

Bir konsensus algoritmasının güçlülüğü hatalarla karşı baş gösterebilme yetkinliği ile ilişkilidir. Örneğin Bizanslı General Probleminde algoritma en fazla %33’lük bir hataya toleranslıdır. Tabii ki bazı mesajların doğruluğunun garanti edilmesi şartıyla bu oran yükselebilmektedir.

3. Ripple’ın Konsensus Algoritması (RKA)

RKA her node tarafından birkaç saniyede bir uygulanır. Bu sıklıkta uygulanmasının sebebi doğruluk ve uzlaşı problemini çözmektir. Konsensusa varıldıktan sonra mevcut defter Kapalı Defter’e dönüşür. Bu, konsensusun sorunsuz çalıştığının ve ağda bir çatallanma olmadığının kanıtı olmuş olur.

3.1 Tanım

RKA birkaç aşamadan oluşur. Her aşamada:

- Bütün onaylanmamış işlemler bir listeye alınır. (candidate set)

- Kendi listesinde olmayan ama BDL’lerin listesinde olan tüm işlemleri de bu listeye ekler. Ve evet & hayır şeklinde oylamaya başlar.

- Belirli sayıdaki evetler geçerken geçemeyenler ya tamamen etkisiz hale gelir ya da bir sonraki konsensusa kalır.

- Bir sunucu BDL listesinden en az %80 geçer oy almalıdır. Alan işlemler geçerli alamayanlar ise geçersizdir.

3.2 Doğruluk

Sahtekarlık içeren bir işlemin onaylanması, tolerans oranından fazla sayıda sahtekar düğüm olmadığı sürece mümkün değildir. Kanıtı ise şuna dayanmaktadır: Bir işlemin onaylanması için %80 lik bir uzlaşı gerekiyor; buna dayanarak ağın %80’i güvenilir olduğu sürece ağda sahtekarlık mümkün değildir. Aynı zamanda %80 sahtekar olmadığı sürece de sahtekarlık içeren bir işlem onaylanmayacaktır.

Eğer bir sahtekar Çifte Harcama yapmaya çalışarak 2 işlem gönderirse ve ikisi de onaylanırsa bu işlemlerin onaylanması deterministik bir şekilde yapıldığından birinci işlemden sonra ikinci işlem için yeterli miktar kalmadığı için işlem geçersiz olacaktır. Konsensus; ağdaki tüm düğümlerin aynı işlem setine deterministik kuralları uyguladığından emin olacak şekilde tasarlanmıştır.

3.3 Uzlaşı

Uzlaşıyı sağlamak için her sunucunun ortak bir işlem kümesi üzerinde uzlaşmaya varması gerektiğini unutmamak gerekiyor. Uzlaşıda önemli olan nokta her sunucunun BDL’sinin bir kesişim kümesi olması gerektiğidir. Aksi takdirde her sunucu farklı işlem kümeleri üzerinde uzlaşıp çatallanmalara sebep olabilirler.

3.4 Kullanılabilirlik

3.4.1 Yakınsama

Yakınsamayı güçlü bir şekilde varılmış uzlaşıya olan yaklaşma olarak tanımlayabiliriz. %80 sahtekar olmadığı sürece güçlü uzlaşı sağlanılabilirdir.

Doğruluk için %80 lik sınır ve Uzlaşı için ise bir kesişim kümesi gerekliliğinden bahsettik. Kullanılabilirlik için bir gereklilikten bahsedecek olursak bu gerekliliğe hız diyebiliriz. Yani konsensusun belirli bir zaman içinde tamamlanması gerekiyor. Bu zamana t diyelim. t süresi içerisinde oylamayı tamamlayamayan düğümler bütün BDL’lerden kaldırılırlar ve konsensus bu yeni listelerle yeniden başlar.

3.4.2 Sezgisel Yöntemler ve Prosedürler

Yukarıda da bahsettiğimiz gibi bir t sınırının koyulması Ripple Konsensusunun yakınsamasına sebep olacaktır. Bunlara ek olarak Ripple Konsensusuna kullanılabilirlik sağlayan birkaç sezgisel yöntem ve prosedürler var:

- Her düğüme aday işlem listesini sunması için 2 saniye verilir.

- Her oylamada hayır oyu vermek gibi davranışlar gösteren düğümler işaretlenir ve atılır.

- Her düğüme sahtekarlığın önlenmesi için bir BDL ripple tarafından atanır. Kullanıcılar isterlerse bu BDL’yi değiştirebilirler. İsterlerse de atanmış BDL’yi kullanabilirler.

- Bölünmeleri yani çatallanmaları tespit eden bir algoritma da bulunmaktadır. Eğer ki bir sunucu BDL’sindeki aktiflikte bir düşüş gözlemlerse bu bir bölünme olduğu anlamına geliyor olabilir. Ancak BDL’nin büyük kısmının gecikme yaşadığı durumlarda sunucunun sanki bir bölünme olmuş gibi davranmaması için sunucuya zaman tanınır ve geçici bir onay vermesi istenir. Daha sonradan ağı yakalaması beklenir.

- Bu consensus algoritmasını tek round ile sınırlı tutmak bir seçenek fakat çoklu round yapmak ekstra bir fayda sağlıyor. %80 kabul alındığı an bir sonraki rounda geçiliyor. Böylece hem ağ beklememiş oluyor hem de geç kalan düğümler arkadan rahatlıkla yetişme fırsatı buluyor.

4. Simülasyon Kodu

Simülasyon kodu Ripple konsensus algoritmasının bir aşamasıdır. Bu simülasyon düğümlerin yarısının evet yarısının hayır dediği bir durumdan başlar ve her düğüm BDL’sine bakarak kararını tekrar tekrar günceller. Herhangi bir taraf %80’e ulaşınca konsensusa ulaşılmış olur.

5. Tartışma

Ripple protokolü saniyeler içerisinde doğruluk, uzlaşılabilirlik ve kullanılabilirlik gibi özellikleriyle güvenli ve güvenilir işlemler gerçekleştirebilmektedir. Tüm özellikleri göz önünde bulundurulduğunda bahsettiğimiz konsensus algoritması Ripple’ın bütün dünyada geçerli olabilecek kadar düşük maliyetli ve güvenli bir ödeme altyapısı olmasına elverişli hale getiriyor.

Son…

Okuduğunuz için teşekkürler! Bu algoritmanın Bizanslı generaller üzerinden özetlenmiş halini twitterda paylaştım. Okumak için linke tıklayabilirsiniz.

Yazılarımdan haberdar olmak için beni medium ve twitterdan takip edebilirsiniz.

Twitter hesabım : https://twitter.com/yarkinaltinel

Kaynakça

https://ripple.com/files/ripple_consensus_whitepaper.pdf

(Feragatname: Yazmış olduğum yazı yalnızca bilgilendirme amaçlıdır ve yatırım tavsiyesi içermemektedir.)