Her blok zincirinin kendisiyle ilişkilendirilmiş bir durumu vardır. Bu durum, anahtar/değer çiftlerinin bir koleksiyonu olarak düşünülebilir . Bu durum, her hesabın sahip olduğu jeton sayısı gibi basit bir şeyi temsil edebilir. Durum, bir akıllı sözleşmenin kodu gibi daha karmaşık bir şeyi temsil edebilir. Bu durum neyi temsil ediyor olursa olsun, blok zincirindeki herkesin anlaşmaya varması gerekiyor. Ben on jetonunuz olduğunu düşünseydim, ama siz bir milyon jetonunuz olduğunu düşünseydiniz, hangimizin haklı olduğunu anlayana kadar pek bir şey başaramazdık.

Ne yazık ki devlet konusunda anlaşmaya varmak oldukça büyük bir sorun. Bir sorun, kötü katılımcıların asla güvenilir katılımcıları kötü bir durumu kabul etmeleri için kandıramayacakları şekilde nasıl ayarlanacağıdır. Diğer konu ise devletin çok büyük olmasıdır. Durumu iletmek bile uzun zaman alıyorsa, katılımcılar nasıl hızlı bir şekilde anlaşmaya varabilir? Bu yazıda, ikinci soruna olası bir çözüm olan Merkle trie hakkında konuşacağız.

Merkle Trie nedir?

Bir Merkle trie, diğer iki veri yapısının özelliklerini birleştiren bir veri yapısıdır . İlki bir Merkle ağacı ve ikincisi bir sayı tabanı trie .

Merkle Ağacı nedir?

Merkle ağacı özel bir ağaç türüdür . Merkle ağaçlarının özelliği, ağacın tamamı için olduğu gibi, ağacın her bir parçası için “parmak izleri” oluşturmalarıdır. Tıpkı gerçek bir parmak izi gibi, ağaç tarafından üretilenler oldukça benzersizdir. Ağaçtaki herhangi bir veriyi değiştirdiğinizde, parmak izi de değişir.

Bu bize, her bir katılımcının mevcut durumda ne düşündüğünü iletme sorununa bir çözüm sağlar. Ağacın tamamını temsil eden parmak izini alıp diğer blockchain katılımcılarına gönderebilirsiniz. Durum verileri için herkes aynı parmak izini oluşturduysa, aynı duruma sahip olmaları gerekir. Parmak izleri farklıysa, durum farklı olmalıdır.

Radix Trie nedir?

Radix trie , anahtar/değer çiftlerini saklamayı ve almayı kolaylaştıran özel bir trie türüdür (trie özel bir ağaç türüdür). Bir Merkle ağacı, bazı verilerin ağacın bir parçası olduğunu kanıtlamanıza izin vermede gerçekten iyidir, ancak anahtarlarla ilişkili değerleri aramayı kolaylaştırmaz, bu nedenle, bir şey elde etmek için sayı tabanı trie ve Merkle ağacını birleştiriyoruz. ikisini de yapabilir

Her şey nasıl çalışıyor?

Benzer işlevleri uygulamanın birçok farklı yolu olduğundan, bir Merkle trie’nin nasıl çalıştığına ilişkin kesin ayrıntılar değişebilir. Tüm bu farklı yolları açıklamaya çalışmak bu makalenin kapsamı dışındadır, bu nedenle bu makalenin geri kalanında yalnızca belirli bir uygulama açıklanacaktır.

Tüm yol boyunca düğümler var

Merkle trie, yalnızca bir nesneden, düğümlerden oluşur. Her düğüm, trie içinde depolanan küçük bir veri yığınıdır. Her düğümün içerdiği veriler, anahtar bilgisi, değer bilgisi (eğer düğümün anahtarı için varsa) ve alt düğümlerin parmak izleridir.

Doğrudan bir düğümün “altındaki” düğümlere alt düğümler denir. Bir düğümün “üzerindeki” düğüm, ana düğüm olarak adlandırılır. Her düğümün yalnızca bir ebeveyni vardır, ancak birçok çocuğu olabilir. Trie’de ebeveyni olmayan özel bir düğüm var. Bu, trie’nin “en üstündeki” düğümdür ve buna kök düğüm denir.

• Bir Merkle trie’nin görsel bir temsili. En üstteki düğüm kök düğümdür. Bu örnekte, Düğüm A ve Düğüm B olarak işaretlenmiş iki çocuğu vardır. Düğüm A’nın iki çocuğu , B Düğümünün ise üç çocuğu vardır . Düğüm C’nin ebeveyni , Düğüm B’dir. B Düğümünün ebeveyni , kök düğümdür. [Not: Bu tartışmada, şemaları daha basit hale getirmek için maksimum çocuk sayısı 4 olacaktır. Gerçekte çoğu uygulama daha fazla sayıda çocuğu seçer .]

Parmak izi oluşturma

Her düğümün parmak izini oluşturmak için bir Merkle trie’yi nasıl kullanırsınız? En yaygın yol, bir kriptografik hash işlevi kullanmaktır . Pek çok farklı kriptografik hash işlevi mevcuttur, ancak bunların tümü, Merkle denemeleri için önemli olan iki özelliği paylaşır.

Bir hash fonksiyonunun ilk özelliği, verileri girdi olarak alması ve bu verileri temsil eden bir dizi sabit boyutta çıktı vermesidir. Genellikle çıktı alınan sayı, boyut olarak girdi verilerinden önemli ölçüde daha küçüktür. Örneğin, popüler bir hash işlevi olan SHA-256 , herhangi bir boyuttaki girdileri alır ve 256 bit uzunluğunda bir çıktı numarası üretir. İşlev çok hassastır, bu nedenle girdideki küçük değişiklikler çıktıda büyük farklılıklara yol açacaktır.

Hash fonksiyonunun çıkardığı sayı, istediğimiz parmak izidir. Her düğüm için, düğümdeki verilere hash işlevini uyguluyoruz ve oluşturulan sayıyı düğümün parmak izi olarak kullanıyoruz. Düğümün alt öğelerinin parmak izleri, düğümün verilerinin bir parçasıdır, dolayısıyla bir düğümün parmak izi aynı zamanda düğümün altındaki trie’deki tüm verileri kapsar. Artık trie’deki tüm verileri kök düğümün parmak izi ile temsil edebiliriz.

Hash fonksiyonlarının ikinci özelliği, fonksiyonu “tersine çevirmenin” çok zor olması gerektiğidir, yani verilen bir çıktı numarası verildiğinde, bu sayıyı üretecek herhangi bir girdi bulmak. Karma işlevinin tersine çevrilmesi kolay olsaydı, birisi aynı sayıyı üreten farklı durum verileri bulabilirdi. Bunu diğer katılımcıları kandırmak ve sorunlara neden olmak için kullanabilirler. Şans eseri, bunu yapmak kolay değil, bu da blockchain katılımcılarının diğer katılımcılarla aynı parmak izini ürettiklerinde aynı verilere sahip olduklarına güvenmelerini sağlıyor.

Kriptografik hash işlevleriyle ilgili bir sorun, hesaplamalarının biraz yavaş olma eğiliminde olmalarıdır. Bu yavaşlık bir yandan bir güvenlik özelliğidir. Aynı hash işlevi çıktısına sahip sahte bir durum oluşturmak istiyorsanız, işe yarayan bir şey bulana kadar farklı girdileri tekrar tekrar deneyebilirsiniz. Karma işlevini yürütmek ne kadar yavaşsa, arama o kadar uzun sürer. Öte yandan, yavaş hesaplama hızı, normal kullanımda hash işlevine çok fazla çağrı yaptığı için Merkle trie kullanımını yavaşlatabilir.

Anahtar/değer çifti bulma

Bu Merkle trie’deki verilerin mevcut blockchain durumu olduğunu ve durumun anahtar/değer çiftlerinden oluştuğunu hatırlayın. Yapmanız gereken yaygın işlemlerden biri, bir anahtarla ilişkili değeri aramaktır. Bu, anahtarı trie boyunca bir yola çevirerek yapılır. Kök düğümden başlayarak ve ardından bu anahtar yolu izleyerek, istediğiniz değeri depolayan düğüme ulaşacaksınız.

Anahtarı bir yola çevirmek

Her nasılsa, trie’yi geçmek için bir anahtardan bir dizi adıma geçmemiz gerekiyor. Bu yüzden anahtarı daha küçük parçalara ayırmamız gerekiyor ve her parça bir sonraki adımımızı belirleyecek. Bu işlemi kolaylaştırmak için, anahtarları ikili veri (yalnızca 0 ve 1’den oluşan bir sayı) olarak gösterelim . Bu, anahtarı daha küçük parçalara ayırmayı ve ardından parçaları sayılara dönüştürmeyi kolaylaştırır. Bu sayılar bize bundan sonra hangi düğümü ziyaret edeceğimizi söyler.

Bu uygulamada her düğümü en fazla 4 çocuğa sahip olacak şekilde sınırlayalım. Anahtarı bit çiftlerine ayırırsak, her bir çift bize 4 çocuktan hangisini ziyaret edeceğimizi söyleyecektir. Bitler ve çocuk düğümler arasındaki bu yazışma mümkündür çünkü her ikisinden de aynı sayıda vardır. 4 farklı olası bit çifti [00, 01, 10, 11], 4 farklı alt düğüme [0, 1, 2, 3] karşılık gelir.

Örneğin, aşağıdaki şemada, 110110 anahtarınız var. İlk önce onu 11|01|10 çiftlerine ayıracaksınız. Bunları alt sayılara çevirmek 3|1|2 olur. Tüm yollar kök düğümde başlar, bu nedenle 110110 anahtarına sahip düğüme giden yolu takip etmek için kök düğümde başlarız. O zaman kökün 3. çocuğuna gidersiniz. O zaman o düğümün 1. çocuğuna geçersiniz. Sonunda o düğümün 2. çocuğuna geçersiniz. Daha sonra 110110 anahtarının değerini içerecek olan son düğüm.

Yolu sıkıştırmak

Anahtar yolunu tam olarak yukarıda açıklandığı gibi oluşturursanız, birçok boş düğüm oluşturursunuz. Bu boş düğümler, her bit çifti bir düğüme karşılık geldiği için oluşturulur. Anahtarın 1000 bit çifti varsa, yolun içinde 1000 düğüm olacaktır. Bu, istediğimiz değere sahip düğümü bulmadan önce 1000 düğümün her biri ziyaret edileceğinden aramayı yavaşlatır.

Aramaların yavaş olmasını önlemek için fazla düğümleri tek bir düğüme sıkıştırabiliriz. Sıkıştırılan her düğüm için hangi çocuk numarası olduğunu kaydederiz. Sonra bu sayı listesini birleştirilmiş düğüme koyarız. Bir anahtar yolu boyunca seyahat ederken, mevcut düğümün mevcut anahtarla eşleşen sıkıştırılmış bir yolu varsa ileri atlayabilirsiniz.

• Yol sıkıştırmanın görselleştirilmesi. Yeşil düğümlerin anahtar yolu [alt 2 -> alt 1 -> alt 3]’e sahiptir. Bu 3 düğüm, mavi düğümde birleştirilebilir. Birleştirilen yol [child 2 -> child 1 -> child 3] olduğundan, bu mavi düğümde 2->1->3 olarak kaydedilir.

Karışımdaki sıkıştırılmış yollarla arama biraz değişir. Bir arama sırasında sıkıştırılmış yolu olan bir düğümle karşılaşırsanız, anahtar yolunda kalan her adım için sıkıştırılmış yoldan sonraki adımla eşleşip eşleşmediğini kontrol edin. Eşleşirlerse, anahtar yolunda ve sıkıştırılmış yolda bir sonraki adıma geçin. Eğer yapmazlarsa, aradığınız anahtar trie’de değildir.

Örneğin, bir anahtar yol boyunca seyahat ettiğinizi ve ulaştığımız düğümün [3->2] sıkıştırılmış bir yola sahip olduğunu ve anahtar yolun kalan adımlarının [child 3 -> child 2 -> child 0 olduğunu varsayalım. ]. Bu senaryoda, anahtar yolunun sonraki adımı [child 3] ve sıkıştırılmış yolun sonraki adımı [child 3]’tür. Bunlar eşleşiyor, bu yüzden bir sonraki adıma geçiyoruz. Anahtar yolundan bir sonraki adım [child 2] ve sıkıştırılmış yolun bir sonraki adımı [child 2], bunlar eşleşiyor, böylece tekrar bir sonraki adıma geçiyoruz. Anahtar yolunun bir sonraki adımı [child 0] ve sıkıştırılmış yolun başka adımı yok, bu nedenle mevcut düğümün alt 0’ına gidiyoruz ve işimiz bitiyor.

• Yol sıkıştırma olduğunda aramanın görselleştirilmesi. Mavi düğüm, 1110011101 anahtarının değerine sahiptir. Bu anahtarın yolu [kök -> çocuk 3 -> çocuk 2 -> çocuk 1 -> çocuk 3 -> çocuk 1]. Kökten kökün 3. çocuğuna, turuncu düğüme giderek bu anahtar yolu izlemeye başlıyoruz. Turuncu düğümün [2->1->3] şeklinde sıkıştırılmış bir yolu vardır, bu da [child 2 -> child 1 -> child 3] yolunun ona sıkıştırıldığı anlamına gelir. Anahtar yolunun sonraki üç adımı, düğümün sıkıştırılmış yolunun üç adımıyla eşleşir. Eşleşen üç adım “iptal” ve [çocuk 1]’in son adımıyla baş başa kalıyoruz. Turuncu düğümden -> çocuk 1’e gitmek, bizi aradığımız değeri tutan düğüm olan mavi düğüme götürür.

Anahtar/değer çifti ekleme

Trie’ye bir anahtar/değer çifti eklemek, mevcut bir anahtarı aramaya çok benzer. Temel fark, aradığınız anahtar trie’de olmayabilir. Anahtar yolu takip ederken, çeşitli durumlardan biri gerçekleşecektir. Ya o anahtara karşılık gelen düğümü bulacaksınız, aranacak düğümleriniz tükenecek ya da anahtar yolu ile eşleşmeyen sıkıştırılmış bir yolu olan bir düğüme ulaşacaksınız.

• Senaryo 1: Anahtara karşılık gelen bir düğüm bulun
  Trie’de anahtara sahip bir düğüm varsa, o zaman anahtar yolunun sonunda olacaktır. Bu düğümü bulduktan sonra, ona yeni değeri eklemeniz yeterlidir.
• Senaryo 2 : Anahtar yolunu takip ederken düğümler tükendi
  Anahtara karşılık gelen bir düğüm olmadığında, anahtar yolunda hiçbir düğüm olmadığı için atamayacağımız bir adıma geleceğiz. Bu durumda, basitçe yeni bir düğüm oluşturur ve onu, anahtar yol boyunca var olan son düğümün alt öğesi olarak ekleriz.

• Senaryo 3: Çakışan Sıkıştırılmış Yol Bulundu
  Anahtar yolundan geçerken, girilen anahtarla eşleşmeyen sıkıştırılmış yola sahip bir düğüme çarpabilirsiniz. Bu, yeni anahtar/değer çifti düğümüyle birlikte “dallanma” yoluna izin verebilecek yeni bir düğümün eklenmesi gerektiği anlamına gelir. Tüm süreç şu adımları takip eder:

1. Yeni bir “Şube” düğümü oluşturun. Sıkıştırılmış yolu şuna eşit olacaktır ​ ​ ​ ​ ​ ​​​ ​ ​ ​ ​ ​ ​ ​​ ​ ​ ​ ​ ​ herhangi bir ortak yol Yeni anahtar yolu ile mevcut düğümün sıkıştırılmış yolu arasındaki adımlar.

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ 2. Mevcut düğümü “Dal” düğümünün alt öğesi olacak şekilde taşıyın

​ ​ ​ ​ ​ ​​​ ​ ​ ​ ​ ​​​ 3. Anahtar/değer çifti için yeni bir düğüm oluşturun ve bunu ​ ​ ​ ​ ​ ​​​ ​ ​ ​ ​ ​ ​ ​ ​​​ ​ ​ ​ ​ ​ ​ ​​​​ ​​ “Şube” düğümü

Devleti paylaşmak

Birisi blok zincirine ilk kez katıldığında, blok zincirinin durumundan hiçbirine sahip değildir. Bu durum olmadan, gerçekleşen işlemleri yorumlayamaz ve doğrulayamazlar. Duruma ulaşmanın bir yolu, blok zincirinin en başından başlamak ve ardından gerçekleşen her işlemi baştan sona oynamaktır. Blockchain bir süredir mevcutsa, bu çok uzun zaman alabilir.

Bir alternatif, durumu diğer blockchain katılımcılarından talep etmektir. Ne yazık ki bir blok zincirinde diğer katılımcılara güvenemezsiniz. Merkle trie, bu güven sorununun çözülmesine de yardımcı olur. Merkle trie, içinde bir anahtar/değer çiftinin olduğunu “kanıtlamak” için kullanılabilir. Anahtar/değer için bir kanıt göndererek, verilerin doğru ve güvenilir olduğundan emin olmak mümkündür.

Tek Anahtarın değerini kanıtlamak

Bir Merkle Trie verildiğinde, belirli bir anahtar/değer çiftinin trie’de olduğunun kanıtı, anahtar yolu boyunca düğümlerdeki tüm verileri sağlayarak oluşturulabilir.

Bu düğümlerden gelen veriler, mavi düğümün değerinin bir kanıtı görevi görür. Kanıtı doğrulamak için, tüm bu verileri boş bir denemeye eklersiniz. Bu trie’nin kökünde biraz parmak izi olacak. Bu parmak izi, tüm blockchain katılımcılarının üzerinde anlaştığı parmak iziyle eşleşirse, kanıtın doğrulanmış olduğu kabul edilir. Aynı parmak izini üretecek sahte veriler oluşturmak çok zordur, dolayısıyla bu kanıt, gönderilen anahtar/değer çiftinin gerçekten blok zincirinin durumunun bir parçası olduğundan emin olmamızı sağlar.

Bir Anahtar Aralığı için değerleri kanıtlama

Tüm durum verilerini almamız gerekiyor, ancak her çift için bir kanıt oluşturup göndermek zorunda olmak verimsiz olacaktır. Bunun yerine, ispat konseptini bir dizi anahtar/değer çiftini ispatlamaya genişletebiliriz.

Bu aralık kanıtı üç bölümden oluşur. İlki bir başlangıç ​​anahtarının kanıtı, ikincisi ise bitiş anahtarının kanıtıdır. Bunlar, yoldaki tüm düğümleri başlangıç ​​ve bitiş anahtarlarını bulmaya göndererek yukarıda açıklandığı gibi çalışır. Üçüncü ve son kısım, başlangıç ​​ve bitiş arasında kalan tüm anahtar/değer çiftleridir. Durum ve bitiş arasındaki düğümler için yalnızca anahtar/değer çiftleri gönderildiğinden, bu ispat, her bir anahtar/değer çifti için ayrı ayrı ispatlar oluşturmaktan çok daha küçüktür. Bu azaltılmış boyut, verilerin trie içinde daha verimli bir şekilde iletilmesine izin verir.

• Bu şemada, yeşil düğümler başlangıç ​​anahtarının kanıt yolunu, kırmızı düğümler bitiş anahtarının kanıt yolunu ve turuncu düğümler, anahtar/değer çiftleri kanıta dahil edilecek tüm düğümleri temsil eder. Yeşil ve kırmızı düğümlerdeki tüm veriler gönderilir, ancak yalnızca turuncu düğümlerin anahtarı ve değeri gönderilir.

Tek anahtar/değer çifti kanıtının doğrulanmasına benzer şekilde, başlangıç ​​kanıt düğümlerinden, son kanıt düğümlerinden ve tüm anahtar/değer çiftlerinden gelen veriler boş bir trie’ye eklenebilir. Bu trie’nin kök düğümünün parmak izi, üzerinde anlaşmaya varılan parmak iziyle eşleşirse, kanıtta gönderilen tüm anahtar/değer çiftleri geçerli durum verileri olarak kabul edilir.

Çözüm

Bir Merkle trie ile anahtar/değer çiftleri ekleyebilir/alabilir, blok zincirinin durumu hakkında anlaşmaya varabilir ve durumun kanıtlarını diğer katılımcılarla paylaşabilirsiniz. Bu özellikler, güvenilir olmayan bir blok zinciri çalıştırmak için gereken işlevselliğin büyük bir bölümünü kapsar. Yine de bu hala aktif bir araştırma alanı, bu yüzden belki daha da iyi bir şey bulabilirsin!

Buradan nereye gidilir?

Hala merak ediyorsanız, daha fazla okumak için birçok seçenek var. Kod eğilimliyseniz, yukarıda açıklanana benzer bir Merkle Trie uygulaması burada görüntülenebilir . Merkle denemelerinin diğer uygulamalarını merak ediyorsanız, Ethereum’un Merkle uygulamasıyla ilgili bu wiki girişine göz atın . Akademik olarak daha yatkınsanız, polinom taahhütleri hakkındaki bu makale , blok zinciri durumunun düğüm parmak izlerini ve kanıtlarını oluşturmak için ilginç bir alternatif sunar.