thesis-report/chapters/2.theoretical-background/2.3.merkle-trees.tex

\section{Δένδρα Merkle} \label{section:2-3-merkle-trees}

Ένα δένδρο Merkle (Merkle tree ή hash tree) είναι μία δενδρική δομή δεδομένων, η οποία απαρτίζεται α) από φύλλα (leaf nodes) που περιέχουν hash από block δεδομένων και β) από άλλους κόμβους (non-leaf nodes) που περιέχουν τα hash των συνενώσεων των hash των θυγατρικών τους. Στην κορυφή του δένδρου βρίσκεται ο ριζικός κόμβος με το λεγόμενο root hash.

Η πιο συνηθισμένη υλοποίηση είναι το δυαδικό (binary) δένδρο Merkle, το οποίο περιλαμβάνει δύο θυγατρικούς κόμβους (child nodes) κάτω από κάθε γονικό (non-leaf) κόμβο, και είναι αυτό που αναλύεται στη συνέχεια.

\begin{figure}[H]
	\centering
	\includegraphics[width=.85\textwidth]{assets/figures/chapter-2/2.3.merkle-tree}
	\caption{Παράδειγμα δυαδικού δένδρου Merkle}
\end{figure}

Τα Merkle tree επιτρέπουν την αποδοτική και ασφαλή επαλήθευση των περιεχομένων που ανήκουν σε σετ δεδομένων μεγάλου μεγέθους. Η βασική ιδιότητα είναι ότι για κάθε σετ δεδομένων υπάρχει ακριβώς ένα πιθανό δένδρο, το οποίο δε γίνεται να τροποποιηθεί χωρίς να αλλάξει ταυτόχρονα και το root hash. 

Έτσι, μέσω των λεγόμενων Merkle proof, μπορούμε:
\begin{itemize}
	\item Να αποφανθούμε εάν κάποια δεδομένα ανήκουν στο δένδρο, υπολογίζοντας (για το εκάστοτε leaf node) hash πλήθους ανάλογου του λογαρίθμου του συνολικού αριθμού των φύλλων.
	\item Να αποδείξουμε συνοπτικά την εγκυρότητα ενός τμήματος κάποιου σετ δεδομένων, χωρίς να χρειαστεί να αποθηκεύσουμε ολόκληρο το σύνολο δεδομένων.
	\item Να διασφαλίσουμε την εγκυρότητα ενός συγκεκριμένου συνόλου δεδομένων εντός ενός μεγαλύτερου σύνολου, χωρίς να χρειαστεί να αποκαλυφθεί το περιεχόμενο οποιουδήποτε εκ των δύο.\cite{2.3-merkle-proofs-explained} 
\end{itemize}