Mengapa menggunakan pohon hash daripada menggunakan satu nilai hash?

Question

Jika seseorang memiliki file $x_1, x_2, .., x_n$. Apa manfaat menggunakan pohon hashing$-$ juga dikenal sebagai pohon Merkle $-$ (misalnya di git) daripada menghitung satu nilai hash $h(x_1,x_2,..,x_n)$ ?

Answer 1

Pohon Merkle digunakan untuk mengambil atau mengirim data secara efektif di jaringan sehingga Anda dapat mengirim / mengambil data pada pesanan apa pun dan memverifikasi data saat ini dengan tambahan$O(\log n)$-data mengirimkan dan masuk $O(\log n)$-waktu. Sebenarnya, hanya hash root yang disimpan$O(1)$. Sambil menyimpan hash root, semua data yang diambil / kirim diverifikasi.

\ begin {array} {lcr} & \ text {With Merkle Tree} & \\ \ hline \ text {receiver} & \ text {data transmit} & \ text {Databank} \\ \ hline \ text {pertahankan hash root } & & \ text {simpan file} \\ O (1) \ text {-space} & & \\ & \ xrightarrow {\ text {minta file ke-it}} & \\ & \ xleftarrow {\ text {kirim file ith dengan} O (\ log n) \ text {saudara ke hash root}} \\ \ text {Verifikasi} & & \\ O (\ log n) \ text {- waktu} & & \ end { Himpunan}

Diagram di atas bahwa Anda adalah pemilik data dan mengalihdayakannya . Jika klien ingin mengunggah data , pertama-tama mereka dapat mengirimkan hash root yang ditandatangani secara digital ke server tempat diagram berlanjut.

Jika Anda menggunakan satu hash, maka untuk memverifikasi Anda perlu mengirim / menerima semua data dan menghitung hash di atasnya $O(n)$-data mengirimkan dan masuk $O(n)$-waktu. Ada juga hashing paralel seperti ParallelHash dari SHA3 atau Blake3. Ini dapat mengurangi waktu pencirian$h(x_1,x_2,..,x_n)$jika Anda memiliki lebih dari satu inti / utas. Secara teori, ini$O(\log n)$Namun, dalam praktiknya, mungkin tidak. Namun, untuk memverifikasi, seseorang perlu mentransfer semuanya sekaligus, yaitu$O(n)$-data mengirimkan.

\ begin {array} {lcr} & \ text {With Single Hash} & \\ \ hline \ text {receiver} & \ text {data transmit} & \ text {Databank} \\ \ hline \ text {pertahankan hash} & & \ text {simpan file} \\ O (1) \ text {-space} & & \\ & \ xrightarrow {\ text {minta file ke-i}} & \\ & \ xleftarrow {\ text {kirim semua file } O (n) \ text {-data transmit}} \\ \ text {Verifikasi} & & \\ O (n) \ teks {- waktu} & & \ end {larik}

Oleh karena itu , manfaatnya adalah mengurangi waktu hash dan mengurangi transmisi data.