Çevrimdışı veri bütünlüğü için Merkle ispatları

depolama

Gelişmiş

Ori Pomerantz

30 Aralık 2021

9 dakikalık okuma

Giriş

İdeal olarak tüm verileri binlerce bilgisayarda depolanan ve son derece yüksek kullanılabilirlik (veri sansürlenemez) ve bütünlüğe (veri yetkisiz bir şekilde değiştirilemez) sahip olan Ethereum depolaması üzerinde saklamak isteriz ancak 32 bayt büyüklüğünde bir kelime depolamanın maliyeti yaklaşık olarak 20,000 gazdır. Bunu yazarken, bu maliyet $6,60'a eşittir. Bayt başına 21 sentlik ücret birçok kullanıcı için çok pahalıdır.

Bu sorunu çözmek için Ethereum ekosistemi, verileri merkeziyetsiz bir şekilde depolamanın birçok alternatif yolunu geliştirdi. Eğer ağ müsaitse maliyet daha az olacaktır ancak ağ eğer yoğunsa maliyet daha fazla olacaktır. Ancak ağın bütünlüğü hep aynı olacaktır.

Bu makalede, Merkle ispatlarını (opens in a new tab) kullanarak verileri blokzincirde depolamadan veri bütünlüğünün nasıl sağlanacağını öğreneceksiniz.

Nasıl çalışır?

Teorik olarak, verinin karmasını zincir üstünde depolayabilir ve tüm verileri gerektiren işlemlerde gönderebiliriz. Ancak bu hâlâ çok maliyetlidir. Bir işlem için bir bayt veri yaklaşık 16 gaz harcar. Bu, şu anda yaklaşık yarım sent veya kilobayt başına yaklaşık $5 değerindedir. Megabayt başına $5000, veriyi şifrelemenin maliyetini dahil etmesek bile bir çok kullanım alanı için çok pahalıdır.

Çözüm ise, verilerin farklı alt kümelerini art arda şifrelenmiş hâle getirmektir. Böylece göndermeniz gerekmeyen veriler için sadece bir hash değeri gönderebilirsiniz. Bunu, her düğümün altındaki düğümlerin hash değerlerinden oluştuğu bir ağaç veri yapısı olan bir Merkle ağacını kullanarak yapabilirsiniz:

Kök karma, zincir üstünde saklanması gereken tek kısımdır. Bir değeri kanıtlamak için, o değeri oluşturan tüm hash değerlerini sağlamanız gerekmektedir. Örneğin, C'yi kanıtlamak için D, H(A-B) ve H(E-H) sağlamanız gerekir.

Uygulama

Örnek koda buradan ulaşabilirsiniz (opens in a new tab).

Zincir dışı kod

Bu makalede, zincir dışı hesaplamalar için JavaScript kullanıyoruz. Çoğu merkeziyetsiz uygulama Javascript'te zincir dışı bileşenlere sahiptir.

Merkle kökünü oluşturma

Öncelikle ağa, Merkle kökünü sağlamamız gerekmektedir.

1const ethers = require("ethers")

Ethers paketindeki karma işlevini kullanıyoruz (opens in a new tab).

1// Bütünlüğünü doğrulamamız gereken ham veriler. İlk iki bayt
2// bir kullanıcı tanımlayıcısıdır ve son iki bayt kullanıcının
3// şu anda sahip olduğu jeton miktarıdır.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Örneğin her bir girişi 256-bit tam sayı değeri olacak şekilde kodlamak, bir JSON kullanmaktan daha az okunabilir olacaktır. Ancak bu, sözleşmedeki verilere erişmek için kayda değer ölçüde daha az işleme, dolayısıyla çok daha düşük gaz maliyetleri anlamına gelir. JSON'u zincir üstünde okuyabilirsiniz (opens in a new tab), ancak kaçınılabilecek bir durumsa bu kötü bir fikirdir.

1// BigInts olarak karma değerleri dizisi
2const hashArray = dataArray

Bu durumda veriler başlangıçta 256-bit değerindedir, bu yüzden herhangi bir işleme gerek yoktur. Eğer satır gibi daha karmaşık bir veri yapısı kullanıyor olsaydık, şifrelenmiş bir satır elde etmek için önce verileri şifrelediğimizden emin olmamız gerekirdi. Bunun ayrıca, kullanıcıların diğer kullanıcıların bilgilerini bilip bilmediklerini umursamamamızdan kaynaklandığını unutmayın. Aksi takdirde şifreleme yapmamız gerekecekti, böylece kullanıcı 1 kullanıcı 0'ın değerini; kullanıcı 2 kullanıcı 3'ün değerini bilmeyecekti vb.

1// Karma işlevinin beklediği dize ile
2// başka her yerde kullandığımız BigInt arasında dönüştürür.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Ethers karma işlevi, 0x60A7 gibi onaltılık bir sayıya sahip bir JavaScript dizesi almayı bekler ve aynı yapıya sahip başka bir dizeyle yanıt verir. Ancak kodun geri kalanı için BigInt kullanmak daha kolaydır, bu yüzden onaltılık bir dizeye dönüştürüp sonra tekrar geri çeviririz.

1// Bir çiftin simetrik karması, bu sayede sıranın tersine çevrilip çevrilmediğini önemsemeyiz.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Bu işlev simetriktir (a'nın xor (opens in a new tab) b'sinin karması). Bu, Merkle ispatını kontrol ettiğimizde, ispattaki değeri hesaplanan değerden önce mi sonra mı koyacağımız konusunda endişelenmemize gerek olmadığı anlamına gelir. Merkle ispatı kontrolü zincir üstünde yapılır, bu yüzden orada ne kadar az şey yapmamız gerekirse o kadar iyidir.

Uyarı: Kriptografi göründüğünden daha zordur. Bu makalenin ilk versiyonunda hash(a^b) karma işlevi vardı. Bu kötü bir fikirdi çünkü a ve b'nin meşru değerlerini biliyorsanız, istenen herhangi bir a' değerini kanıtlamak için b' = a^b^a' kullanabileceğiniz anlamına geliyordu. Bu işlevle, hash(a') ^ hash(b') değerinin bilinen bir değere (köke giden yoldaki bir sonraki dal) eşit olacak şekilde b' değerini hesaplamanız gerekir, ki bu çok daha zordur.

1// Belirli bir dalın boş olduğunu, bir değere sahip olmadığını
2// belirtmek için kullanılan değer
3const empty = 0n

Değerler ikinin katı tam sayılar olmadığında bunun yerine boş dalları işlememiz gerekir. Program bunu yapmak için boş dallara varsayılan değer olarak 0 atar.

1// Her bir çiftin karmasını sırayla alarak bir karma dizisi ağacında
2// bir seviye yukarı hesaplar
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // Girdinin üzerine yazmayı önlemek için // Gerekirse boş bir değer ekleyin (tüm yaprakların eşleştirilmesi gerekir)
6
7  if (inp.length % 2 === 1) inp.push(empty)
8
9  for (var i = 0; i < inp.length; i += 2)
10    result.push(pairHash(inp[i], inp[i + 1]))
11
12  return result
13} // oneLevelUp
Tümünü göster

Bu fonksiyon, güncel katmandaki değer çiftlerini karma hâle getirerek bir üst seviyeye "tırmanır". Bunun en verimli uygulama olmadığını, girdiyi kopyalamaktan kaçınıp döngüde uygun olduğunda hashEmpty ekleyebileceğimizi, ancak bu kodun okunabilirlik için optimize edildiğini unutmayın.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Ağaçta tek bir değer kalana kadar yukarı tırmanır, bu // köktür. // // Eğer bir katmanın tek sayıda girdisi varsa // oneLevelUp'daki kod boş bir değer ekler, yani örneğin // 10 yaprağımız varsa, ikinci katmanda 5 dal, // üçüncüde 3, dördüncüde 2 dal olur ve kök beşincidir
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Tümünü göster

Ana değere ulaşmak için ağaçta tek bir değer kalana kadar tırmanın.

Merkle ispatı oluşturma

Bir Merkle ispatı, Merkle kökünü geri almak için kanıtlanan değerle birlikte karma hale getirilecek değerlerdir. İspatlanacak olan değer sıklıkla diğer veride bulunabilir. Bu yüzden kodun bir parçası yerine ayrı olarak sağlamayı tercih ederim.

1// Bir merkle ispatı, birlikte karma alınacak giriş listesinin // değerinden oluşur. // Simetrik bir karma işlevi kullandığımız için, ispatı doğrulamak için öğenin konumuna ihtiyacımız // yoktur, yalnızca oluşturmak için gerekir
2const getMerkleProof = (inputArray, n) => {
3    var result = [], currentLayer = [...inputArray], currentN = n
4
5    // Zirveye ulaşana kadar
6    while (currentLayer.length > 1) {
7        // Tek uzunluklu katmanlar olamaz
8        if (currentLayer.length % 2)
9            currentLayer.push(empty)
10
11        result.push(currentN % 2
12               // Eğer currentN tekse, ispata ondan önceki değeri ekleyin
13            ? currentLayer[currentN-1]
14               // Çiftse, sonraki değeri ekleyin
15            : currentLayer[currentN+1])
16
Tümünü göster

(v[0],v[1]), (v[2],v[3]) vb. şeklinde karma alırız. Yani çift değerler için bir sonrakine, tek değerler için bir öncekine ihtiyacımız vardır.

1        // Bir üst katmana geç
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof

Zincir üstü kod

Nihayet, kanıtları kontrol eden koda ulaştık. Zincir üstü kod Solidity (opens in a new tab) ile yazılmıştır. Gaz maliyeti yüksek olduğundan burada optimizasyon çok daha önemlidir.

1//SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";

Bunu, geliştirme yaparken Solidity'den konsol çıktısı almamızı (opens in a new tab) sağlayan Hardhat geliştirme ortamını (opens in a new tab) kullanarak yazdım.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Son derece güvensiz, üretim kodunda bu işleve
10    // erişim MUTLAKA sıkı bir şekilde sınırlandırılmalı, muhtemelen bir
11    // sahip (owner) tarafından
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Tümünü göster

Merkle kökü için ayarlama ve getirme fonksiyonları. Bir üretim sisteminde herkesin Merkle kökünü güncellemesine izin vermek son derece kötü bir fikirdir. Örnek kodu basitleştirmek adına bunu burada yapıyorum. Veri bütünlüğünün gerçekten önemli olduğu bir sistemde bunu yapmayın.

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }

Bu fonksiyon bir eş karma değeri oluşturur. Bu sadece hash ve pairHash için JavaScript kodunun Solidity çevirisidir.

Not: Burada da okunabilirlik için optimizasyon yapılmıştır. İşlev tanımına (opens in a new tab) dayanarak, verileri bir bytes32 (opens in a new tab) değeri olarak depolamak ve dönüşümlerden kaçınmak mümkün olabilir.

1    // Bir Merkle ispatını doğrulayın
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof
Tümünü göster

Matematiksel gösterimde Merkle ispatı doğrulaması şöyle görünür: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...)))`. Bu kod onu uygular.

Merkle ispatları ve toplamalar birbiriyle uyuşmaz

Merkle ispatları toplamalarla iyi çalışmaz. Sebebi ise toplamalarda işlemlerin Katman 1 üzerinde yazılması ancak Katman 2 üzerinde işlenmesidir. Bir işlem ile Merkle ispatı göndermenin maliyeti katman başına ortalama 638 gazdır (güncel olarak çağrı verisinde gaz maliyeti, bayt sıfır değilse 16, sıfır ise 4'tür). Eğer 1024 kelimeden oluşan bir verimiz varsa, bir Merkle ispatı 10 katman veya 6380 gaz gerektirir.

Örneğin Optimism (opens in a new tab)'e bakıldığında, L1'e yazmanın gaz maliyeti yaklaşık 100 gwei, L2'nin gaz maliyeti ise 0,001 gwei'dir (bu normal fiyattır ve tıkanıklık durumunda artabilir). Yani bir Katman 1 gazının bedeli ile Katman 2 işlemeye yüz bin gaz harcayabiliriz. Depolamanın üzerine yazmadığımızı varsayarsak bu, bir Katman 1 gazı fiyatına Katman 2'deki depolamaya yaklaşık beş kelime yazabileceğimiz anlamına gelir. Tek bir Merkle ispatı için, 1024 kelimenin tamamını depolamaya yazabilir (başlangıçta bir işlemde sağlanmak yerine zincir üstünde hesaplanabildiklerini varsayarsak) ve yine de gazın çoğu artmış olur.

Sonuç

Gerçek hayatta, Merkle ağaçlarını hiçbir zaman kendi başınıza uygulamayacak olabilirsiniz. Denetlenmiş ve iyi bilinen kütüphaneler mevcuttur. Genel olarak kendi başınıza ilkel kriptografik yöntemleri uygulamamanız en iyi seçimdir. Fakat Merkle ispatlarını ve ne zaman kullanmaya değer olduklarını umarım daha iyi anlamışsınızdır.

Merkle ispatlarının bütünlüğü korurken kullanılabilirliği korumadığını unutmayın. Veri deposuna erişim yoksa ve onlara erişmek için bir Merkle ağacı oluşturamıyorsanız, varlıklarınızı başka kimsenin alamayacağını bilmek küçük bir teselli olur. Yani en iyisi Merkle ağaçlarının IPFS gibi bir merkeziyetsiz depolama ile kullanılmasıdır.

Çalışmalarımdan daha fazlası için buraya bakın (opens in a new tab).

Sayfanın son güncellenmesi: 18 Aralık 2025