Merkle Tree یا Hash Tree

درخت‌های درهم سازی (Hash Tree) شاخه‌ای از فهرست‌های درهم‌سازی هستند. به این درخت‌ها درخت‌های مرکل (Merkle Tree) نیز می‌گویند.

در رمزنگاری و علوم کامپیوتری، درخت درهم‌سازی نوعی از داده ساختارها هستند که شامل یک درخت که خلاصهٔ اطلاعات یک دادهٔ بزرگتر را در خود جای داده‌است و برای تشخیص محتویات آن داده به کار می‌رود.

 

 

مداخله ناپذیر

یکی از مزایای ساماندهی کردن تراکنش ها در ساختار درخت مرکل این است که بسیار راحت و آسان می توان تایید کرد در هیچ کدام از تراکنش های داخل بلاک، مداخله ای صورت نگرفته باشد. برای مثال اگر تراکنش T_H به تراکنش T_XYZ تغییر کرده باشد، مقدار هش آن نیز متفاوت خواهد بود. بنابراین، هنگامی که هش به دست آمده با هش مجاور خود ترکیب شود، هش نهایی نیز متفاوت خواهد شد. این امر منجر به ریشه مرکل کاملا متفاوتی می‌شود، بنابراین می‌توان نتیجه گرفت که هرگاه ریشه مرکل تغییر کند، در یک یا بیش از یک تراکنش مداخله و تغییر ایجاد شده است.

استفاده از منابع کمتر

ساماندهی تراکنش ها در ساختار درخت مرکل در مقایسه با هش کردن مجموعه تراکنش ها و وارد کردن آن ها به هدر بلاک، از منابع کمتری استفاده می‌کند. اگرچه از نظر فنی، اگر تمام تراکنش ها به صورت روش دوم یا همان هش تراکنش ها و وارد کردن آنها به هدر بلاک ساماندهی شوند، هم چنان عملکرد خواهد داشت اما از منابع بسیار زیادی استفاده خواهد کرد. این روش مدیریت تراکنش ها به دلیل هزینه بسیار زیاد مدیریت منابع بیشتر، می‌تواند منجر به کاهش نودها در شبکه بیت کوین شود. در نتیجه، غیرمتمرکز شدن شبکه بیت کوین کاهش می‌یابد.

تایید یک تراکنش

درخت مرکل به کاربران امکان می‌دهد تا بدون دانلود کردن کل بلاک چین، بتوانند بررسی کنند یک تراکنش مشخص در بلاک حضور دارد یا خیر. اگرچه با استفاده از کلاینت های سبک تر نظیر پروتکل SPV، کاربران می‌توانند بررسی کنند که تراکنش مورد نظرشان در بلاک چین حضور دارد یا خیر.

برای مثال اگر کاربر بخواهد بررسی کند که آیا تراکنش H_D در بلاک حضور دارد، به جای دانلود کل بلاک چین و بررسی آن، تنها چیزی که وی نیاز دارد ریشه مرکل، HAH_EFGH، H_AB و H_C می باشد. اگرچه هم چنان برای تایید حضور تراکنش در بلاک به اطلاعات مربوطه نیاز است، اما به طور چشمگیری بهتر از دانلود کل بلاک چین است.

 

کاربردها

درخت‌های درهم‌سازی می‌توانند برای محافظت از هر نوع داده‌ای که ذخیره شده‌است یا مورد استفاده قرار می‌گیرد یا در بین رایانه‌ها منتقل می‌شود؛ استفاده شود. در حال حاضر بیشترین و مهم‌ترین کاربرد درخت‌های درهم‌سازی در شبکه‌های نظیر به نظیر است. در این شبکه‌ها برای حصول اطمینان از اینکه اولاً بسته‌های دریافت شده، بدون عیب و بدون تغییر هستند و ثانیاً اینکه بسته‌ها جعلی نیستند؛ از این درخت‌ها استفاده می‌شود. البته پیشنهادهایی برای استفاده از این درخت‌ها در سیستم‌های محاسباتی معتبر شده‌است. شرکت سان میکرو سیستمز از درخت‌های مرکل در پرونده‌های سیستم‌های ZFS استفاده کرده‌است.

درخت درهم‌سازی در سال ۱۹۷۹ و توسط رالف مرکل، اختراع شد. کاربرد اصلی این درخت‌ها در شیوه‌ای به نام امضای لمپورت است که در رمزنگاری کاربرد دارد. ترکیب این روش با درخت درهم‌سازی باعث شد تا این روش رمزنگاری برای پیام‌های زیادی مورد استفاده قرار بگیرد و به روشی نسبتاً کارآمد برای امضاهای دیجیتالی تبدیل شود.

چگونگی عملکرد درخت درهم‌سازی

یک درخت درهم‌سازی درختی است که برگ‌های آن درهم‌سازی شدهٔ بلوک‌های داده (مثلاً یک فایل یا مجموعه‌ای از فایل‌ها) است. هر گره پدر، در هم‌سازی شدهٔ گره‌های فرزند خودش است. این روش بر خلاف دیگر روش‌های معمول درخت‌ها، از پایین به بالا کار می‌کند؛ یعنی ورودی آن برگ‌ها هستند و نه ریشه. به عنوان مثل، در شکل روبرو، ۰ حاصل در هم‌سازی ۰–۰ و ۱–۰ است؛ که با الحاق ۰–۰ و ۱–۰ به دست می‌آید. اکثر پیاده‌سازی‌های انجام شده برای درخت‌های درهم سازی، دودویی هستند. اما می‌توان، با توجه به روش مورد استفاده و همچنین نیاز، فرزندان بیشتری را نیز متصور بود. معمولاً یک تابع درهم‌سازی رمزی مثل: SHA-1، Whirpool, Tiger و… برای درهم‌سازی مورد استفاده قرار می‌گیرد. اگر قرار باشد که درخت‌های درهم‌سازی فقط در برابر صدمات غیرعمدی محافظت شوند؛ می‌توان از روش‌هایی که امنیت کمتری دارند ولی در عوض ساده‌تر هستند مثل CRC استفاده کرد. در بالای درخت درهم سازی؛ Top Hash قرار دارد. پیش از دانلود کردن یک فایل از شبکه‌های نظیر به نظیر، در اکثر موارد، Top Hash از یک منبع مورد اطمینان مثل رایانهٔ یک دوست یا حتی سایت‌هایی که در این زمینه شهرت دارند، دریافت می‌شود. اگر توانستیم بدین وسیله Top Hash را به دست آوریم، ما بقی درخت درهم‌سازی را می‌توان از هر منبع دیگری دریافت کرد. در نهایت، درخت درهم سازیِ دریافت شده را می‌توان به وسیلهٔ Top Hash مطمئنی که قبلاً دریافت کرده‌ایم، بررسی کرد. اگر قسمتی از درخت درهم سازی، صدمه دیده یا جعلی باشد، آن قسمت از درخت از منبع دیگری امتحان می‌شود تا در نهایت، برنامه Top Hash درست و مطابق با Top Hash اولیه را بیابد. تفاوت عمده‌ای که بین درخت‌های درهم‌سازی و فهرست‌های درهم‌سازی وجود دارد این است که در درخت‌های درهم سازی، یک شاخه از درخت را می‌توان یکجا دانلود کرد و یکپارچگی آن را بلافاصله بررسی کرد؛ حتی اگر تمام درخت به‌طور کامل در دسترس نباشد. این یک ویژگی خوب برای درخت‌های درهم‌سازی است چرا که تکه کردن فابل‌ها به بلوک‌های کوچکتر، به صرفه است؛ زیرا اگر آن‌ها صدمه ببینند، فقط قطعه‌ای از داده‌ها باید دوباره دانلود شود و نیازی به دانلود تمام فایل نیست.