hash tree

hash tree (tsz. hash trees)

1. (informatika) A hash tree, más néven Merkle tree, egy speciális adatstruktúra, amely egy fa-szerkezetben tárolt adatok hash értékein alapszik. Célja, hogy gyorsan és hatékonyan lehessen ellenőrizni adatok integritását és hitelességét, különösen elosztott rendszerekben.

A hash tree-ben:

✅ A levélcsomópontok az adatok hash értékei, ✅ A belső csomópontok pedig gyerekeik hash értékeinek kombinációjából származó hash-ek, ✅ A gyökér (root hash) egyetlen rövid ujjlenyomat, amely az egész adatstruktúrát képviseli.

Tegyük fel, 4 adatblokk van: D1, D2, D3, D4.

1. Levél hash-ek:

   H1 = hash(D1)
   H2 = hash(D2)
   H3 = hash(D3)
   H4 = hash(D4)

2. Belső szintek:

   H12 = hash(H1 || H2)
   H34 = hash(H3 || H4)

3. Gyökér:

   H1234 = hash(H12 || H34)

👉 H1234 az egész fa “összegzése” — ha bármelyik adat vagy hash megváltozik, a gyökérérték is megváltozik.

• A hash fa lehetővé teszi, hogy csak néhány hash értékkel igazoljuk egy adatblokk hitelességét.
• Ezért használják blokkláncokban, verziókezelésben, tanúsítványláncokban.

       H1234
       /    \
    H12      H34
   /  \     /   \
 H1  H2   H3   H4

• Ha pl. D3 változik, akkor H3, H34, és H1234 is változik.
• A gyökér változása alapján egyből észrevehető a módosítás.

#include <string>
#include <vector>
#include <openssl/sha.h>

std::string hash(const std::string& data) {
    unsigned char hash;
    SHA256((const unsigned char*)data.c_str(), data.size(), hash);
    return std::string((char*)hash, SHA256_DIGEST_LENGTH);
}

std::string merkleRoot(const std::vector<std::string>& leaves) {
    std::vector<std::string> level = leaves;
    while (level.size() > 1) {
        std::vector<std::string> next;
        for (size_t i = 0; i < level.size(); i += 2) {
            std::string left = level;
            std::string right = (i + 1 < level.size()) ? level : left;
            next.push_back(hash(left + right));
        }
        level = next;
    }
    return level;
}

• hash tree - Szótár.net (en-hu)
• hash tree - Sztaki (en-hu)
• hash tree - Merriam–Webster
• hash tree - Cambridge
• hash tree - WordNet
• hash tree - Яндекс (en-ru)
• hash tree - Google (en-hu)
• hash tree - Wikidata
• hash tree - Wikipédia (angol)