Thread by @_professorc

Verkle ağaçları ,temelde Merkle ağaçlarıyla aynı işi yaparlar. Verkle ağacında kriptografik hash fonksiyonlarının yerine vektör taahhütleri kullanılır. Ancak Verkle ağaçlarının sağladığı temel özellik, kanıt boyutunda çok daha verimli olmalarıdır.

Verkle ağaçlarının ve Merkle Patricia ağaçlarının yapısındaki tek gerçek fark verkle ağacının pratikte daha kısa ve şişman olmasıdır. Verkle ağaçlarında genişlik arttıkça ağacın boyu kısalır.

Ağacın boyuna değil yanlara doğru büyüdüğünü düşünün aynı veri sayısında verkle ağaçları daha kısa ve şişman olurken merkle ağaçları ise daha çok derinliğe sahip olur. Bant genişliği azalma, ağacın derinliğinden bağımsızdır sadece dallanma faktörüne bağlıdır.

Verkle ağaçları(VERy short merKLe), Ethereum'un stateless-client olma yolunda duran kilit sorunu olan kanıt boyutu sorununu çözer.

Vitalik’in makalesine göre bir ağaç bir milyar veri parçası içeriyorsa, geleneksel bir ikili Merkle ağacında bir ispat yapmak yaklaşık 1 kilobayt gerektirir, ancak bir Verkle ağacında ispat 150 bayttan az olur.Bu stateless-clientleri uygulayabilmek için nihayet yeterli bir azalma

Kaydedilen bu bant genişliği, verkle ağacını oluşturmak ve yaprak düğümlerinin kanıtlarını doğrulamak için gereken bazı ekstra hesaplamaları yanında getirir. Verkle ağaçları, ortalama durumda kanıt boyutlarının kabul edilebilir derecede küçük olmasına izin veriyor.

Verkle Ağaçları, bant genişliğini azaltma potansiyeline sahiptir. Bu potansiyel için bir şeyden fedakârlık verir. Taviz verebileceğimiz bir özellikten taviz verirken çok ciddi bir kazanım sağlarız.

Hesaplama gücü ile bant genişiliği arasında bir takas yaparız. Daha çok hesaplama gücüne ihtiyacımız olurken daha az bant genişliğine ihtiyaç duyarız. Merkle ağaçlarına göre daha az bant genişliği gerektirir. Bu kanıtın boyutu küçültülerek sağlanır.

Dallanma faktörü k = 3 olduğu bir verkle ağacı böyle gözükür. Gördüğünüz gibi dallanma faktörünü arttırdıkça ağacın node sayısı azalır. Dallanma faktörü, bu yüzden bant genişliğini azaltır. Merkle ağaçlarında çok fazla node vardır bu ağacın boyutunun artmasına neden olur.

Verkle Treeyi hesaplamadan önce ağacın dallanma faktörü olan k ya karar vermemiz gerekir. Daha sonra verilerimizi k ya göre gruplandırırız. Her grup için vektör taahhütü hesaplanır.

Sonra her veri(Fi) için C ye göre altküme olan bir kanıtı( πi) hesaplanır. Köke ulaşana kadar bu adım tekrarlanır. Sağladığımız her düğüm için, aslında onun üstündeki düğümün çocuğu olduğunu (ve doğru konumda olduğunu) kanıtlamamız gerekir.

9 verilik bir verkle ağacı k yani dallanma faktörü 3 alınırsa 3erli altkümelere bölünür. Her altküme üzerinde kanıtlarla ile bir vektör taahhüdü hesaplanır ve C1,C2,C3 taahhütlerini verir. Bu köke kadar devam eder.

C1, C2 ve C3 taahhütleri için π9, π10 ve π11 kanıtları ile birlikte bu üç taahhüt üzerinden Vektör Taahhüdü C4'ü hesaplıyoruz. Verkle Ağacının özeti, bu durumda C4 olan kök taahhüttür.

Merkle ağaçları çok fazla küçük dosyalarda büyük kanıtlar veriyor. Büyük boyutlu kanıtlar bant genişliği açısından verimli değildir. Vektör taahhütlerinde kaç veri bulunduğuna bakılmaksızın her kanıt sabit boyuta sahiptir

Merkle ağaçları çok hızlı hesaplanıyordu ancak bant genişliği açısından oldukça maliyetli olabiliyordu. Vektör Taahhüdünü oluşturmak için ihtiyaç duyduğumuz hesaplama ise maliyetli ancak bu bize sabit bir kanıt boyutu vadediyor.

Bu kabul edilebilir ve dikkate değer, çünkü hesaplama gücünde makul bir artış pahasına bant genişliğini azaltmamıza izin veriyor.Ayrıca kanıt boyutu yalnızca O(logkn) bu merkle ağaç kanıtlarından O(log2 k) kere daha küçük. Bunun tatmin edici bir takas olduğuna inanıyoruz

k = 1024 olarak ayarlarsak, kanıt boyutunda ve dolayısıyla bant genişliğinde Merkle ağaçlarına göre 10 kat azalma elde ederiz.(O(log2 k) 1024=2^10) Hesaplama gücünde ise 1024 kat bir maliyet artışı görürüz. Daha az hesaplama gücü isteniyorsa k düşürülebilir.

k'nin tam değeri, uygulamadan uygulamaya değişebilir. Hesaplama ve bant genişliği arasındaki ilişki için bir değer optimizasyonu sağlanmalı.

Ethereum için önerilen Verkle ağacının genişliği 256 ve hatta bazıları 1024'e yükseltmeyi tercih ediyor. Bu genişlik ağacın boyunu kısalttığı için hesaplamayı zorlaştırır ancak kanıt boyutunu da kısaltır.

Stateless-Clientler için tanık sağlamak kolay olacak

Tanık oluşturma şu anda yaklaşık 3 saniye sürüyor ancak daha fazla optimizasyon üzerinde çalışılıyor.

Tanık doğrulama ise birkaç yüz milisaniye içinde yapılabilir

Verkle Ağaçları için bir kaynak:

math.mit.edu/research/highs…

Basit görselli anlatım:
math.mit.edu/research/highs…

Vitalik'in verkle ağaçlarını açıkladığı yazı:
vitalik.ca/general/2021/0…