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

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 depolamak için birçok alternatif yol 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 blok zinciri üzerinde veri depolamadan Merkle ispatları(opens in a new tab) kullanarak nasıl veri bütünlüğü sağlanacağını öğreneceksiniz.

Nasıl çalışır?

Teoride verileri şifrelenmiş bir şeklide blok zinciri üzerinde tutup, işlem için gerekli verileri gönderebilirdik. 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:

Sadece kök hash değerinin ağ üzerinde depolanmış olması gerekmektedir. 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ğlamak zorundasınız.

Uygulama

Örnek kod burada sağlanmıştır(opens in a new tab).

Zincir dışı kod

Bu makalede zincir dışı işlemler 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 hash fonksiyonunu kullanıyoruz(opens in a new tab).

1// The raw data whose integrity we have to verify. The first two bytes a
2// are a user identifier, and the last two bytes the amount of tokens the
3// user owns at present.
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 blok zinciri üzerinde okuyabilirsiniz(opens in a new tab) ancak bunu yapmak zorunda değilseniz kötü bir fikirdir.

1// The array of hash values, as BigInts
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// Convert between the string the hash function expects and the
2// BigInt we use everywhere else.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Ethers hash fonksiyonu, 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 onu onaltılık bir dizeye ve geri eski hâline dönüştürürüz.

1// Symmetrical hash of a pair so we won't care if the order is reversed.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Bu fonksiyon simetriktir (xor(opens in a new tab) b'nin hash değeri). 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. Merkel ispatı kontrolü zincir üstünde gerçekleşir, orada ne kadar az kod kullanırsak o kadar iyi.

Uyarı: Kriptografi göründüğünden daha zordur. Bu belgenin ilk versiyonu, hash(a^b) karma fonksiyonuna sahipti. Bu, a ve b'nin meşru değerlerini bilmeniz durumunda b' = a^b^a' denklemini kullanarak istediğiniz a' değerini kanıtlayabileceğiniz anlamına geldiği için kötü bir fikirdi. Bu fonksiyonla, hash(a') ^ hash(b') değeri, bilinen bir değere (köke giden yolda sonraki dal) eşit olacak şekilde b' değerini hesaplamanız gerekecekti ve bu çok daha zordur.

1// The value to denote that a certain branch is empty, doesn't
2// have a value
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// Calculate one level up the tree of a hash array by taking the hash of
2// each pair in sequence
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // To avoid over writing the input // Add an empty value if necessary (we need all the leaves to be // paired)
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ı unutmayın, girdiyi kopyalamaktan kaçınabilir ve uygun olduğunda döngüye hashEmpty ekleyebilirdik, ancak bu kod okunabilirlik için optimize edilmiştir.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Climb up the tree until there is only one value, that is the // root. // // If a layer has an odd number of entries the // code in oneLevelUp adds an empty value, so if we have, for example, // 10 leaves we'll have 5 branches in the second layer, 3 // branches in the third, 2 in the fourth and the root is the fifth
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.

Bir 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// A merkle proof consists of the value of the list of entries to
2// hash with. Simetrik bir karma işlevi kullandığımız için,
3// kanıtı doğrulamak için öğenin konumuna ihtiyacımız var, yalnızca onu oluşturmak için
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top
8    while (currentLayer.length > 1) {
9        // No odd length layers
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // If currentN is odd, add with the value before it to the proof
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it
17            : currentLayer[currentN+1])
18
Tümünü göster

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

1        // Move to the next layer up
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";
 Kopyala

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

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extremely insecure, in production code access to
10    // this function MUST BE strictly limited, probably to an
11    // owner
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Tümünü göster
 Kopyala

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 ö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    }
 Kopyala

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. Fonksiyon tanımına(opens in a new tab) dayanarak; bytes32(opens in a new tab) olarak veriyi depolamak ve dönüşümleri önlemek mümkün olabilir.

1    // Merkle kanıtı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
 Kopyala

Matematiksel gösterimde Merkle ispatı şö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 uyumlu değildir

Merkle ispatları, toplamalar ile 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 bakacak olursak: Katman 1 gaz yazmak ortalama 100 gwei, Katman 2 gaz yazmak ise 0,001 gwei'ye mal olmaktadır (bu, normal fiyattır ve tıkanıklık olursa 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 yazabiliriz (bir işlemde sağlanmak yerine zincir üzerinde hesaplayabileceklerini varsayarsak) ve hâlâ gaz maliyetinden tasarruf etme imkanımız 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ılabilirlikten ödün verdiğini 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.