مرکل تری (Merkle tree) یا درخت مرکل یک ساختار پلهکانی و سلسهمراتبی است که برای اعتبارسنجی و بررسی صحت دادههای یک پایگاه استفاده میشود. در بلاک چین، درخت، ریشه، برگ و اثباتهای مرکل کاربردهای مختلفی دارند که در این مطلب، به معرفی مزایا و نحوه کار آنها میپردازیم.
درخت مرکل (Merkle Tree) یا مرکل تری چیست؟
درخت مرکل نوعی ساختار است که برای اعتبارسنجی سریع صحت داده در یک مجموعه استفاده میشود. این ساختار عمدتا شامل توابع هش است که بهصورت گسترده در تکنولوژی بلاک چین کاربرد دارد. در واقع مرکل تری یک معماری سلسهمراتبی از هشهای تراکنشهاست:
- ریشه مرکل (مرکل روت – Merkle Root) یا هش ریشه (روت هش – Root Hash): بالاترین نود درخت
- نودهای غیر برگ (Non-leaf Nodes): نودهای هش فرزند تراکنشهای میانی
- نودهای برگ (Leaf Nodes): نودهای فرزند یا نودهای تراکنشها
تاریخچه درخت مرکل
مفهوم مرکل تری اولین بار توسط یک دانشمند علوم کامپیوتر بهنام رالف مرکل (Ralph Merkle) معرفی شد. وی سالهای متمادی از زندگی حرفهای خود را روی رمزنگاری کلید عمومی کار کرده است. با وجودی که اکثر تحقیقات پیرامون این موضوع در دهه 80 میلادی صورت گرفته است، اما این مفهوم اولین بار در سال 1979 توسط آقای مرکل مطرح شد.
ریشه مرکل (Merkle Root) یا مرکل روت چیست؟
از مهمترین اجزای ساختار مرکل تری، روت یا ریشه مرکل است که در بالاترین سطح معماری آن قرار دارد. ریشه مرکل یک تکنیک ریاضیاتی است که دادهها و واقعیات پیرامون مرکل تری را تایید میکند.
ریشه درخت مرکل در بلاک چین و رمز ارزها قسمتی از هدر و عنوان بلاک است که باعث عدم قابلیت تغییر و دستکاری دادههای آن میشود. در ادامه، بیشتر به نقش مرکل روت در تشکیل بلاک خواهیم پرداخت.
هدر یا عنوان بلاک (Block Header) چیست؟
پیش از پرداختن به نحوه کار مرکل تری، باید با اجزای تشکیلدهنده یک بلوک در بلاک چین آشنا شوید. یک بلاک از یک عنوان (Header) و یک بدنه (Body) ساخته میشود. این هدر خودش شامل مرکل روت، تایم استمپ یا مهر زمان (Timestamp)، شماره نسخه بلاک (تعیینکننده مجموعه قوانین اعتبارسنجی بلاک)، هدف سختی ماینینگ، نانس و هش بلاک قبلی است. در طرف مقابل، بدنه بلاک تمام تراکنشهای تاییدشده درون آن را شامل میشود.
درخت مرکل چگونه کار میکند؟
برای درک بهتر مرکل تری، با یک مثال ساده کار را آغاز میکنیم. فرض کنید 4 تراکنش (A و B و C و D) در یک بلاک (بلاک 2 تصویر زیر) وجود دارد و هر کدام از آنها دارای یک هش بلاک منحصربهفرد (HashA و HashB و HashC و HashD) هستند.
حالا هر جفت از این تراکنشهای هششده برای ساخت یک هش جدید با یکدیگر ترکیب میشوند. در این مثال، هش A با B ترکیب و هش AB را میسازد. در طرف دیگر، تراکنش هششده C و D نیز با یکدیگر ترکیب و هش CD را میسازند. حالا مجددا هش AB و CD توسط تابع هش ترکیب شده و ABCD را میسازد که در واقع همان ریشه مرکل یا هش ریشه برای درخت ماست. نهایتا مرکل روت در هدر و عنوان بلاک ذخیره میشود.
نمونه یک مرکل تری نامتوازن با تعداد تراکنشهای فرد
در مثال قبل، برای ساخت جفتها، در هر سطح تعداد برگهای مرکل زوج و با یکدیگر برابر بود. اما اگر تعداد تراکنشها در بلاک چین فرد باشد و به یک درخت مرکل با تعداد برگهای فرد ختم شود چه اتفاقی میافتد؟
فرض کنید 5 تراکنش در یک بلاک داریم. هر کدام از این 5 تراکنش (A و B و C و D و E) هم هش منحصربهفرد خود (HashA و HashB و HashC و HashD و HashE) را دارند. حالا جفت تراکنشهای هششده A و B هش AB و جفت C و D، هش CD را میسازند. در اینجا تراکنش هششده E برای ساخت یک شاخه جدید، بدون جفت باقی مانده است.
بهخاطر ذات دودویی و باینری مرکل تری، تعداد برگها باید زوج باشد. به همین خاطر، در صورت وجود یک هش جفتنشده، آن هش کپی و با خودش جفت میشود. در این مثال، HashE دوپلیکیت شده و با جفت شدن با خودش، HashEE را میسازد.
پس از این مرحله، HashAB و HashCD جفت شده و HashABCD را میسازد. در طرف دیگر، HashEE دوباره دوپلیکیت و با خودش جفت شده و HashEEEE را میسازد. نهایتا، هشهای ABCD و EEEE جفت شده و هش نهایی یعنی ریشه مرکل HashABCDEEEE را تشکیل میدهند.
نهایتا از این مرکل روت برای یافتن هش معتبر و منحصربهفرد بلاک به همراه 0های آغازگر استفاده میشود. مثلا، فرض کنید ریشه مرکل بلاک شماره 72608# برابر مقدار زیر است:
a1c6d67c992a70fca66188e178d9ca7c20d5c775393948f19955be7f0952c0f
حالا این هش ریشه با اطلاعات دیگری شامل شماره بلاک، هش بلاک قبلی، تایماستمپ، هدف سختی و نانس درون یک تابع هش ترکیب و هش معتبر و منحصربهفرد آن بههمراه 0های آغازکننده ساخته میشود. شکل نهایی هش بهصورت زیر خواهد بود:
00001a03b7328189f5f7154681c5827a1b2fce2fcb5301a8e412e22ea9a7859
پس از تایید، هش بلوک به بخشی از بلاک چین تبدیل و بلاکهای جدید بهدنبال آن اضافه خواهند شد.
اثبات مرکل (Merkle Proof) چیست؟
اثباتهای مرکل برای اعتبارسنجی یک تراکنش یا محتوای خاص در یک حجم وسیع از داده بهکار میروند. در سیستمهای بلاک چینی دو نوع نود یا گره شبکه داریم:
- نودهایی معروف به فول نود (Full Node) که تاریخچه کامل بلاک چین را نگهداری میکنند.
- گرههایی بهنام نودهای سبک یا لایت ویت (Lightweght Node) که بهجای کل تاریخچه تراکنش، حاوی تنها بخشی از بلاک چین، عموما هم فقط هدر بلاک (شامل ریشه مرکل)، هستند. نودهای سبک بدون نیاز به دانلود کل بلاکچین، فقط تراکنشهای داخل یک بلوک را میتوانند اعتبارسنجی کنند.
نودهای لایت ویت برای اعتبارسنجی یک بلاک خاص، از یک تابع هش برای پیدا کردن مقدار هش تراکنش مورد نظر استفاده میکنند. حال یکی از فول نودها بر اساس ساختار درخت مرکل، تمام مقادیر هش را به گره سبک مسئول اعتبارسنجی میفرستند. در مرحله بعد، گره لایت ویت برای محاسبه مقدار هش ریشه عملیات هشینگ را تکرار میکند و در صورت پیدا شدن آن، با مقدار هش ریشه ارسالی به فول نود مقایسه میشود.
فرض کنید یک گره سبک درصدد تایید گم شدن یا دستکاری تراکنش D است. برای این کار، یک فول نود مقادیر HashC و HashAB و HashEFGH و ریشه مرکل را برای وی میفرستد. اول از همه، نود لایت ویت Hash تراکنش D را با استفاده از تابع هش پیدا میکند. سپس HashD به همراه HashC و HashAB و HashEFGH برای تولید مرکل روت یا هش ریشه مجددا محاسبه میشوند. حالا اگر ریشه مرکل محاسبهشده و مرکل روت اصلی با یکدیگر تطابق داشته باشند، درست بودن HashD در رخت مرکل تایید و تراکنش D بخشی از مرکل تری خواهد بود. در صورت عدم تطابق، دستکاری و نادرستی تراکنش D مشخص خواهد شد.
مزایای درخت مرکل
درختهای مرکل بهخاطر تسهیل اعتبارسنجیهای سریع و آسان بهگونهای که در دیگر روشها ممکن نیست، برای فناوری بلاک چین اهمیت ویژهای دارند. مرکل تریها با حذف تمام دادههای غیر ضروری و تبدیل دادههای باقیمانده به هش، توانایی فشردهسازی مجموعه بزرگی از دادهها را برای توسعهدهندگان فراهم میکنند. به همین خاطر، استفاده از مرکل تری برای اعتبارسنجی تراکنشها در فناری بلاک چین و پلتفرمهای رمز ارزی مزایای زیادی از جمله جلوگیری از تاخیر، دستکاری و افزایش کارایی پردازشها دارد:
- فرآیند کارآمد اعتبارسنجی داده: اعتبارسنجی صحت تراکنشها عملا در کسری از زمان قابل انجام بوده و بهخاطر نحوه ساختاربندی داده، طی فرآیند اعتبارسنجی به حافظه بسیار کمی نیاز است.
- تشخیص هرگونه دستکاری: ساختار هش، شناسایی دستکاری تراکنشها را برای ماینرها ساده میسازد و از دابل اسپندینگ جلوگیری میکند. همه تراکنشها بهصورت هش درون یک مرکل تری ذخیره میشوند. بنابراین با تغییر حتی یک تراکنش، تغییرات انجامشده پیش از رسیدن به ریشه مرکل، به سطوح بالاتر درخت میرسد. سپس امکان مقایسه ریشه مرکل که در هدر بلاک نمایش داده میشود با ریشه موجود در داده وجود دارد. بنابراین دستکاریها سریعا شناسایی میشوند.
- عدم تاخیر: انتقال داده در شبکه با استفاده از مرکل تری بدون هیچگونه تاخیر قابل انجام است.
- کاهش حافظه ذخیرهسازی: بلاک چینها از صدها هزار بلوک ساخته میشوند که هر بلاک هم حاوی چندین هزار تراکنش است. بنابراین، فضای ذخیرهسازی و قدرت محاسباتی دو مشکل بزرگ برای اعتبارسنجی داده خواهند بود. اما با استفاده از مفهوم مرکل تری، هر نود یا گره شبکه دیگر ملزم به نگهداری یک کپی از تمام تراکنشها نیست. درخت مرکل با هش کردن تمام سوابق در دفتر کل، اثبات داده را از خود داده جدا میسازند، در نتیجه کاربران به تایید بلاکها پرداخته و با استفاده از این هشها تراکنشها را بررسی میکنند.
اهمیت درخت مرکل برای شبکه بیت کوین
بیت کوین اولین رمز ارزی بود که ساختار مرکل تری را بهکار گرفت. این شبکه برای تضمین حفاظت و عدم بازگشتپذیری ساده مقادیر هش، از الگوریتم هشینگ امن شناختهشده SHA-256 استفاده میکند. در این قالب، خروجی مقادیر هش 256 بیت طول دارد. در دل این الگوریتم، درختهای مرکل برای ذخیرهسازی داده و همچنین هرس تراکنشها استفاده میشوند.
همانطور که گفتیم، بلاکهای یک بلاک چین با استفاده از مقادیر هش به یکدیگر متصل هستند و در یک بلاک، هدرها اطلاعات مهمی را در خود جای دادهاند از جمله:
- هش مرکل روت
- شماره نسخه بلاک
- تایم استمپ
- نانس
- هدف سختی استخراج
- هش بلاک قبلی
از جمله مزایای استفاده از درخت مرکل برای شبکه بیت کوین روشی بهنام Simple Peyment Verification یا بهطور خلاصه SPV است که در اثبات مرکل هم به آن اشاره کردیم. این SVPها همان نودهای لایت ویت هستند که صرفا بلندترین زنجیره هدرهای بلوک را دانلود کرده و نیازی به دانلود کل بلاک چین ندارند. برای این کار، این نودها فقط ملزم به تایید هدرهای ذخیرهشده در بلندترین زنجیره هستند.
کاربرد درخت و ریشههای مرکل در بلاک چین
امروزه، ساختار درخت و ریشه مرکل در بسیاری از بلاک چین ها و پلتفرمهای رمز ارزی استفاده میشوند. در این قسمت، به بررسی کاربردهای این مفاهیم میپردازیم.
ماینینگ و استخراج
بلاکهای شبکههایی نظیر بیت کوین شامل هدرهایی هستند که در آنها متادیتا و همچنین فهرست بلندبالایی از تراکنشها وجود دارد. این لیست غالبا بزرگتر از خود هدر بلاک است، بنابراین ماینرها با هش کردن دادهها، خروجیهای متناسب با شرایط خاص میسازند که برای اعتبارسنجی یک بلوک ضروری است. همچنین ممکن است ماینرها برای یافتن یک بلاک معتبر چندین هزار بار تلاش کنند. حالا هر تلاش این افراد، نیازمند تغییر یک شماره در هدر بلاک است. از طرفی با وجود حضور هزاران تراکنش مجزا در یک بلاک، هر کدام از آنها باید هش شوند.
ریشههای مرکل این فرآیند را برای ماینرها کارآمدتر میکنند. مثلا با آغاز پروسه استخراج بیت کوین، تنها کافی است تراکنشها به یک ساختار درخت مرکل تبدیل شده و سپس هش ریشه درون هدر بلاک قرار بگیرد. در این مرحله، ماینر بهجای هش کردن کل بلوک، تنها نیازمند هش کردن هدر آن است.
اعتبارسنجی
جنبه دیگر کاربرد ریشه مرکل، تمرکز بر کلاینتهای سبک است. زمانی که نودی با استفاده از یک دستگاه نسبتا ضعیف با منابع محدود فعالیت میکند، کاربران دیگر قادر به دانلود و هش کردن تمام تراکنشها در یک بلاک واحد نیستند. در عوض، درخواست اثبات مرکل (Merkle Proof) صادر میشود که در واقع تاییدی بر حضور یک تراکنش در یک بلوک است. با کاهش تعداد هشینگهای لازم طی فرآیند اعتبارسنجی، این عملیات میتواند بدون منابع محاسباتی بالا نیز انجام شود.
مرکل تری در اتریوم
اتریوم بر اساس نسخه اصلاحشده درخت مرکل بهنام Merkle Patricia Tree کار میکند. در این بلاک چین، برخلاف ساختار باینری درخت بیت کوین، هر بلوک حاوی 3 مرکل تری است و هر کدام از 3 ریشه نیز هدف خاص خود را دارد.
ریشه اول ریشه تمام تراکنشهاست. ریشه دوم وضعیت تراکنش را نشان میدهد و ریشه آخر، گیرنده تراکنش است. کاربران نیز میتوانند با بررسی مرکل روت وجود یا عدم وجود یک تراکنش در یک بلوک خاص و همچنین موجودی حساب آن را تعیین کنند.
کاربردهای غیر بلاک چینی درخت مرکل
علاوه بر بلاک چین، درخت مرکل در دیگر حوزهها نیز کاربرد دارد از جمله:
- Git: یک نرم افزار کنترل پروژه که برای ساختار مخزن خود برای برنامهنویسان سراسر جهان از مرکل تری استفاده میکند.
- گواهینامههای قابل تایید: مراجع گواهیدهنده برای ساخت و صدور گواهینامههای قابل تایید از این معماری بهره میبرند.
- سیستم IPFS: این سیستم یک پروتکل توزیعشده متن باز همتابههمتاست که برای ساختار فایلهای خود از درخت مرکل بهره میگیرد.
- تکثیر داده: از مرکل تری برای تکثیر داده در پایگاههای داده توزیعشده غیر SQL نظیر آمازون و DynamoDB استفاده میشود.
سخن پایانی
درختهای مرکل برای پلتفرمهایی که بهدنبال سادهسازی و افزایش کارایی فرآیند اعتبارسنجی تراکنشهای خود هستند، بسیار سودمندند. بدون وجود ساختار مرکل تری، بهخاطر نیاز به ارسال داده در کل شبکه، اعتبارسنجی به پروسهای بسیار وقتگیر تبدیل خواهد شد. پلتفرمهای بلاک چینی استفادهکننده از معماری ریشه های درخت مرکل، به قدرت محاسباتی و پنهای باند کمتری نیاز دارند.
تهیه شده در بیت 24