درخت مرکل چیست؟ Merkle Tree در بلاکچین چه کاربردی دارد؟

فناوری بلاکچین در ظاهر عجیب و پرماجرا است. شاید بپرسید حجم بالای تراکنش‌ها چطور دسته‌بندی و پردازش می‌شوند؟ چطور در بین این همه داده، صحت یک تراکنش ‌خاص مجددا ارزیابی می‌شود؟ چطور می‌توانیم مطمئن باشیم که داده‌های هر بلاک بدون دستکاری به بلاک بعدی متصل می‌شوند؟ اگر با درخت مرکل (Merkle Tree) آشنا شویم، می‌توانیم پاسخ این سوالات را پیدا کنیم. درخت مرکل یک ساختار داده ریاضی مبتنی بر هش است که کمک می‌کند در سیستم‌های توزیع‌شده با استفاده از قدرت محاسباتی محدود و زمان کمتر اطلاعات را ذخیره و ارزیابی کنیم. با میهن بلاکچین همراه باشید تا با مرکل تری یا درخت هش باینری بیشتر آشنا شویم و عملکرد آن در بلاکچین، مزایا و کاربردهای غیربلاکچینی آن را بررسی کنیم.

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

درخت مرکل چیست؟

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

برای درک عملکرد درخت مرکل ابتدا باید با تابع هش (Hash Function) و مفهوم هش که بخشی از علم رمزنگاری است، آشنا شویم. درواقع می‌خواهیم بدانیم چرا برای مجموعه داده‌های بزرگی مانند تراکنش‌ها در بلاکچین به هشینگ نیاز داریم.

تابع هش چیست؟

تابع هش، یک تابع ریاضی است که داده‌های ورودی با هر حجم و اندازه‌ای را می‌گیرد و دنباله‌ای ثابت، منحصر‌به‌فرد و تغییرناپذیر از اعداد و حروف بزرگ و کوچک را خروجی می‌دهد. این دنباله “Hash” نام دارد و برای ورودی یکسان، همیشه خروجی ثابتی دارد. به‌علاوه حدس زدن عبارت ورودی با استفاده از خروجی، بسیار دشوار و تقریبا غیرممکن است. با یک مثال، موضوع را ساده‌تر کنیم؛ اگر شما کلمه “Fox” را وارد تابع هش کنید، همیشه دنباله ثابتی را دریافت می‌کنید. اما اگر هر تغییری در ورودی ایجاد شود، مثلا حرف “x” بزرگ نوشته شود یا عددی به آن اضافه شود، هش خروجی تغییر می‌کند.

طول خروجی (مجموع کاراکترهای دنباله) تابع هش، همیشه همان مقداری است که توسط الگوریتم هش تعیین شده است. به‌طور مثال خروجی تابع SHA1 یک مقدار ۱۶۰ بیتی و هش تابع SHA2 همیشه ۲۵۶ بیت است. اس‌اچ‌ای (SHA) مخفف عبارت “Secure Hashing Algorithm” و به معنای «الگوریتم هش امن» است. تصور کنید قرار است فایلی را دریافت کنید و می‌خواهید مطمئن باشید که تغییری در داده‌های فایل ایجاد نشده است. می‌توانید از فرستنده بخواهید هش فایل ارسالی را محاسبه کند و خودتان هم یک بار هش را حساب کنید. در‌صورتی که هش‌ها یکسان باشند، فایل اصلی به‌دست شما رسیده است. در سیستم‌هایی که حاوی مقادیر زیادی داده هستند، شناسایی و ذخیره داده با استفاده از این الگوریتم به قدرت محاسباتی و فضای ذخیره کمتری نیاز دارد.

تاریخچه درخت مرکل

درخت مرکل در سال ۱۹۸۸ میلادی (۱۳۶۶) توسط رالف مرکل (Ralph Merkle) و با هدف بهبود ساختار امضای دیجیتال ایجاد شد. رالف، یک دانشمند علوم کامپیوتر و ریاضیدان آمریکایی است و اختراع رمزنگاری کلید عمومی و هش رمزنگاری را در کارنامه حرفه‌ای خود دارد.

آشنایی با مفهوم درخت مرکل

بلاکچین یک شبکه غیرمتمرکز و همتا به همتا است که تمام داده‌ها (تراکنش‌ها) و هر نوع تغییر در داده‌ها را ثبت می‌کند. زمانی که یک تراکنش در شبکه انجام می‌شود، این تغییر باید توسط تمام شرکت‌کننده‌های شبکه (نود) تایید شود تا یکپارچگی اطلاعات حفظ شود. اگر بلاکچین از تابع هش استفاده نکند، شبکه باید دائما در حال تایید کوچکترین تغییرات باشد که باعث ناکارآمدی سیستم می‌شود. این‌جا است که درخت مرکل مورد استفاده قرار می‌گیرد.

مجددا سراغ یک مثال ساده برویم. فرض کنید یک فروشگاه فست‌فود دارید و می‌خواهید دخل و خرج ماه گذشته را حساب کنید. در حین حساب و کتاب هزینه‌ها (مثل حقوق و دستمزد و … ) و درآمد‌ها (پرداخت‌های مشتری) با قلم و کاغذ، متوجه می‌شوید که مبلغی را که در روز پنجم ماه برای خرید نان ثبت کرده‌اید، اشتباه بوده است. با این تغییر کوچک، باید تمام محاسبات تا پایان ماه را تغییر دهید. استفاده از چنین سیستمی حتی در مقیاس کوچک هم آزاردهنده و ناکارآمد است. حالا اگر به جای این سیستم سنتی از یک نرم‌افزار حسابداری استفاده کنید، بدون نیاز به تغییر تمام دفتر سیاهه می‌توانید حساب خود را آپدیت کنید.

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

در سمت چپ تصویر زیر رویکرد ساده هش داده و در سمت راست نمای کلی هش در درخت مرکل را مشاهده می‌کنید. همان‌طور که مشخص است در رویکرد ساده هش‌ها به‌صورت زنجیروار کنار هم قرار می‌گیرند و هش هر بلاک فقط با هش بلاک بعدی جمع می‌شود؛ اما درخت مرکل از یک ساختار درخت‌گونه و سلسله‌مراتبی استفاده می‌کند.

بررسی ساختار درخت مرکل

درخت مرکل همان‌طور که از نامش پیدا است، ساختاری شبیه به درخت دارد؛ اما ریشه آن به سمت بالا است. بررسی این ساختار شاید کمی سخت به‌نظر برسد؛ اما با توجه به تصویر زیر درک مسئله روشن‌تر می‌شود.

تراکنش‌های A ،B ،C و D در اولین سطح قرار دارند. هش هر یک از این تراکنش‌‌ها به‌طور جداگانه محاسبه می‌شود و در سطح بعدی قرار می‌گیرند. بنابراین Hash A ،Hash B ،Hash C و Hash D به‌دست می‌آید که به آن‌ها نود برگ (Leaf Nodes) گفته می‌شود. هش هر نود برگ هم با نود برگ کناری محاسبه می‌شود و Hash AB و Hash CD به‌دست می‌آيد که نود غیربرگ نامیده می‌شوند. در نهایت با محاسبه ۲ به ۲ هش نودهای غیربرگ به Hash ABCD می‌رسیم که به آن هش ریشه یا هش مرکل گفته می‌شود. همان‌طور که می‌بینید با استفاده از این ساختار سلسله مراتبی، نتیجه نهایی زودتر حاصل می‌شود. خلاصه‌ای از این اطلاعات به شرح زیر است:

•  نود برگ (Leaf Node): هر تراکنش در یک بلاک به‌ داده‌ هش‌شده تبدیل می‌شود که ما آن را با نام شناسه تراکنش (TXID) می‌شناسیم. نودهای برگ، هش حاصل از هر دو هش تراکنش‌ هستند.
• نودغیربرگ (Non-Leaf Node): نودهای غیربرگ، حاصل هش جفت نودهای برگ هستند.
• ریشه مرکل (Merkle Root): ریشه مرکل یا هش ریشه خلاصه‌ای از همه هش‌ها است که در بخش هدر بلاک ذخیره می‌شود.

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

مثال: عملکرد درخت مرکل در تراکنش آلیس به باب

T_A بیانگر یک تراکنش معمولی است که در مثال فوق قابل مشاهده است. این تراکنش‌ها به طور مجزا هش می‌شوند تا مقدار هش هر کدام مشخص شود. برای مثال T_D از تابع هش عبور می‌کند تا مقدار هش H_D متناظر با آن مشخص شود. در مورد بیت کوین، تابع هشی که استفاده می‌شود، SHA256 است.

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

برای مثال، مقادیر هش H_C و H_D ترکیب و هش می‌شوند تا هش H_CD تولید شود. در مثال فوق، ۸ تراکنش با مقادیر هش مختص به خود وجود دارد. هرچند اگر تعداد تراکنش‌ها فرد باشد، برای مثال ۷ تراکنش وجود داشته باشد، هش هفتم با خود جفت می‌شود تا مقدار هش جدید تولید شود و در این صورت، H_H با H_H ترکیب می‌شود تا H_HH ایجاد شود.

این فرآیند تا زمانی تکرار می‌شود که آخرین مقدار هش به دست آید. به این مقدار، ریشه مرکل می‌گویند. در مثال فوق، ریشه مرکل H_ABCDEFGH است. اندازه ریشه مرکل ۳۲ بایت است و در هدر بلاک قرار می‌گیرد که بیانگر خلاصه ای از اطلاعات تمام تراکنش‌هاست.

کاربرد درخت مرکل در بلاکچین‌ها

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

درخت مرکل در بلاکچین بیت کوین

بیت کوین با استفاده از تابع هش رمزنگاری SHA256 هر تراکنش را هش می‌کند و این یعنی همه تراکنش‌ها بعد از هشینگ، طول ثابتی برابر با ۲۵۶ بیت دارند. به‌علاوه هش همه تراکنش‌ها محاسبه می‌شود و خلاصه‌ای از آن‌ها در هدر بلاک قرار می‌گیرد. این مکانیزم چند مزیت برای بلاکچین بیت کوین دارد:

• اولا نودهای تایید ساده پرداخت (SPV) یا کلاینت‌های کم‌حجم (lightweight clients) مجبور به دانلود کل بلاکچین نیستند و می‌توانند فقط هدر بلاک طولانی‌ترین زنجیره را دانلود کنند. در حقیقت نود SPV می‌تواند با استفاده از نگاشت تراکنش در یک درخت مرکل خاص و ارتباط آن با هش ریشه مرکل در هدر بلاکی که متعلق به طولانی‌ترین زنجیره است، وضعیت یک تراکنش را مشخص کند. به این روند، اثبات مرکل (Merkle proof) گفته می‌شود.
• ثانیا از آنجایی که فقط هش ریشه در هدر بلاک ذخیره می‌شود، می‌توان شاخه‌های غیرضروری درخت مرکل و بلاک‌های قدیمی را حذف کرد و فقط بلاک‌های مورد نیاز برای اثبات مرکل را نگه داشت.

استفاده از درخت مرکل در سایر بلاکچین‌ها

بیت کوین اولین بلاکچینی بود که از درخت مرکل استفاده کرد؛ اما بسیاری از بلاکچین‌های دیگر هم ساختارهای درخت مرکل یا حتی نسخه‌های پیچیده‌تر را اجرا کردند. به‌طور مثال، اتریوم که یک تورینگ کامل و پلتفرمی برای ساخت برنامه‌های غیرمتمرکز بسیار پیچیده است، از نسخه پیچیده‌تری به نام درخت مرکل پاتریشا (Merkle Patricia Tree) استفاده می‌کند. پاتریشا از سه درخت مرکل جداگانه تشکیل شده است و از سازوکار جفت‌‌ «کلید و ارزش» برای پیوند داده‌ها استفاده می‌کند.

کاربردهای غیربلاکچینی درخت مرکل

از درخت مرکل، به غیر از بلاکچین در موارد دیگری هم استفاده می‌شود که می‌توانیم به نمونه‌های زیر اشاره کنیم:

• گیت (Git) یکی از رایج‌ترین سیستم‌های کنترل نسخه توزیع‌شده است که ردیابی تغییرات در مجموعه فایل‌های رایانه‌ای را امکان‌پذیر می‌کند. معمولا برنامه‌نویسانی که به‌طور مشترک روی توسعه کد منبع یک نر‌م‌افزار کار می‌کنند از گیت برای نظارت و مدیریت پروژه‌ها بهره می‌گیرند.
• سیستم فایل بین‌سیاره‌ای (IPFS) یک پروتکل توزیع‌شده همتا به همتا برای ذخیره، نگهداری و دسترسی به انواع داده (فایل، برنامه و وبسایت) است.
• دیتابیس‌های غیررابطه‌ای (No-SQL)، رویکردی برای مدیریت پایگاه داده است و طیف گسترده‌ای از مدل‌های داده را در قالب گراف، ستونی گسترده و سندی در خود جای می‌دهد. دیتابیس Amazon DynamoDB نمونه‌ای از این مدل است.
• سیستم شفافیت گواهینامه (Certificate Transparency log) یک ابزار متن باز برای نظارت و شناسایی گواهی‌نامه‌های شخصی و جعلی SSL است. از درخت مرکل در بخشی از این فرایند استفاده می‌شود.

مزایای درخت مرکل

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

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

برای مثال اگر کاربر بخواهد بررسی کند که آیا تراکنش H_D در بلاک حضور دارد، به جای دانلود کل بلاک چین و بررسی آن، فقط به ریشه مرکل، HAH_{EFGH ،}H_AB و H_C نیاز دارد. اگرچه در این روند هم دسترسی به یک‌ سری اطلاعات لازم است، اما به‌طور چشمگیری بهتر از دانلود کل بلاک چین است.

• تغییرناپذیر بودن داده: یکی از مزایای ساماندهی تراکنش‌ها در ساختار درخت مرکل این است که می‌توانیم به‌راحتی تایید کنیم در هیچ کدام از تراکنش‌های داخل بلاک، مداخله‌ای صورت نگرفته است.

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

• انتقال داده بدون تاخیر: با استفاده از درخت مرکل، داده‌ها بدون تاخیر در شبکه منتقل می‌شوند.
• نیاز به فضای حافظه کمتر: ساماندهی تراکنش‌ها با استفاده از ساختار سلسله مراتب مرکل تری در مقایسه با سایر ساختارهای اطلاعاتی به فضای کمتری نیاز دارد.
• اطمینان از عدم دستکاری داده: وجود ریشه مرکل در هر هدر بلاک، نشانه‌ای برای اطمینان از کامل بودن و دستکاری نشدن تراکنش‌ها است.

جمع‌بندی 

درخت مرکل روش قدرتمندی برای ساماندهی تراکنش‌ها و امکان پذیر ساختن ارزهای دیجیتالی نظیر بیت کوین و اتریوم است. پردازش حجم بالای اطلاعات بلاکچین قطعا به قدرت محاسباتی و فضای حافظه عظیمی نیاز دارد. به لطف درخت مرکل (Merkel Tree) نیاز نیست هر نود بلاکچین نسخه کاملی از هر تراکنش را ذخیره کند. به‌علاوه با توجه به نوع رمزنگاری (هشینگ) و ساختار درختی، شناسایی یک داده خاص بسیار آسان‌تر است. مسئله دیگر دشوار شدن دستکاری داده است، زیرا هر بلاک شامل هش ریشه همان بلاک و هش بلاک قبلی است و کوچکترین تغییری در داده منجر به تغییر هش‌ ریشه می‌شود.

سوالات متداول (FAQ)