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

merklebütünlükdepolama

Gelişmiş

Ori Pomerantz

30 Aralık 2021

8 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 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:

(opens in a new tab)

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.

(opens in a new tab)

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")
2

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]
8

Ö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
3

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.

1const pairHash = (a, b) =>
2  BigInt(ethers.utils.keccak256("0x" + (a ^ b).toString(16).padStart(64, 0)))
3

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.

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.

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n
4

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

(opens in a new tab)

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
6
7  // Add an empty value if necessary (we need all the leaves to be
8  // paired)
9  if (inp.length % 2 === 1) inp.push(empty)
10
11  for (var i = 0; i < inp.length; i += 2)
12    result.push(pairHash(inp[i], inp[i + 1]))
13
14  return result
15} // oneLevelUp
16
Tümünü göster

Bu fonksiyon güncel katmandaki verileri hash hâline 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]
5
6  // Climb up the tree until there is only one value, that is the
7  // root.
8  //
9  // If a layer has an odd number of entries the
10  // code in oneLevelUp adds an empty value, so if we have, for example,
11  // 10 leaves we'll have 5 branches in the second layer, 3
12  // branches in the third, 2 in the fourth and the root is the fifth
13  while (result.length > 1) result = oneLevelUp(result)
14
15  return result[0]
16}
17
Tümünü göster

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

Bir Merkle ispatı oluşturma

Bir Merkle ispatı, Merkle kökünü geri almak için kanıtlanan değerle birlikte hash edilecek 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. Because we use a symmetrical hash function, we don't
3// need the item's location to verify the proof, only to create it
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
19
Tümünü göster

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

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
8

Zincir üstü kod

Nihayet ispatları 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";
5
 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
15
Tümünü göster
 Kopyala

Merkle kökünü ayarlamak ve getirmek için 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 pairHash(uint _a, uint _b) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a ^ _b)));
3    }
4
 Kopyala

Bu fonksiyon bir eş hash değeri oluşturur. Bu yalnızca JavaScript'teki pairHash kodunun Solidity'e uyarlamasıdır.

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    // Verify a Merkle proof
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
15
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 düzgün ç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ı asla 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. Ama umarım Merkle ispatlarını ve ne zaman kullanmaya değer olduğunu 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.