سارینا حیدری
سارینا حیدری
خواندن ۹ دقیقه·۵ سال پیش

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

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

توابع هش کریپتوگرافیک

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

هش به دست آمده از ورودی دلخواه نه تنها طول ثابتی دارد بلکه کاملا یکتا و منحصر به ورودی است. خود تابع نیز قطعی است، یعنی هر چند بار هم که تابع را روی یک ورودی اجرا کنید خروجی همیشه یک چیز خواهد بود. برای نمونه اگر دیتاست‌های (مجموعه دیتا) زیر را ورودی بگیریم، خروجی‌ به دست آمده از هر کدام از ورودی‌ها منحصر به فرد و یکتا خواهد بود. توجه کنید که در نمونه‌های دوم و سوم، با اینکه تفاوت فقط در حد یک واژه است، خروجی‌های به دست آمده کاملا با هم فرق دارند. این ویژگی تابع هشینگ بسیار مهم است، زیرا به ما امکان می‌دهد از دیتا «اثر انگشت» بگیریم.


یک تابع هش کریپتوگرافیک. عکس از ویکی پدیا

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

در زمینه بلاک چین، از الگوریتم‌های هشینگ برای تعیین حالت بلاک چین استفاده می‌شود. بلاک چین ها در حقیقت لیست‌های پیوسته‌ای هستند که در آن‌ها دیتا و اشاره‌گر هش وجود دارد. اشاره‌گر هش (hash pointer) در هر بلاک به بلاک پیشین اشاره دارد و مشخص می‌کند بلاک قبلی چیست. به این ترتیب یک زنجیره از بلاک‌ها به وجود می‌آید که یکی پس از دیگری به هم متصل هستند؛ به همین خاطر به این مجموعه «بلاک چین» یا زنجیره بلاکی گفته می‌شود. به این ترتیب آنچه یک بلاک را به بلاک کنار خود وصل می‌کند یک اشاره‌گر هش است. هر اشاره‌گر هش دارای دو بخش است. یکی آدرس بلاک قبلی و دیگری هش برگرفته از دیتای موجود در بلاک قبلی. در این روش هر هش که خروجی دیتای بلاک قبلی است، بیانگر حالت کل بلاک چین نیز می‌باشد زیرا این هش نتیجه‌‌ تمام دیتاهای هش شده‌ بلاک‌های پیشین است. این هش خروجی (اگر الگوریتم SHA-256 باشد) شبیه چنین چیزی است:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

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

با این وجود همان‌طور که در ادامه خواهید دید، درختان مرکل خطر ناچیزی برای تمامیت دیتا ایجاد می‌کنند و به کمک اثبات مرکل (Merkle proof) می‌توان دیتا را در سرتاسر درخت نگاشت کرد (نقشه آن را تهیه کرد).

درخت مرکل و اثبات مرکل

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


نمونه‌ای از یک درخت مرکل باینری، عکس از ویکیپدیا

در شکل بالا مهم است توجه کنید که گره‌های غیر برگ یا همان شاخه‌های سمت چپ (Hash 0-0 و Hash 0-1) هش‌های زیرشاخه خود یعنی L1 و L2 هستند. یک ردیف بالاتر، شاخه Hash 0‌، هش دو زیرشاخه خود یعنی شاخه‌های Hash 0-0 و Hash 0-1 است.

نمونه بالا یک درخت مرکل ساده است. این رایج‌ترین نمونه به نام درخت مرکل باینری (binary) شناخته می‌شود. همان‌طور که می‌بینید یک هش راس وجود دارد که هش همه‌ی درخت است. این هش را با نام روت هش یا هش ریشه می‌شناسند. درخت‌ مرکل یک ساختار دیتا است که می‌تواند n شاخه داشته باشد و همه‌ی آن را با یک هش بیان کند.

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

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

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

می‌توان از روت هش به عنوان اثرانگشت کل یک دیتاست استفاده کرد. برای نمونه می‌توان با آن کل یک دیتابیس یا حالت کلی یک بلاک چین را نشان داد. در ادامه می‌بینیم که سیستم‌هایی همچون بیت کوین چگونه از درخت مرکل بهره گرفته‌اند.

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

تابع هش کریپتوگرافیک به کار رفته در بیت کوین را «الگوریتم SHA-256 » می‌نامند. این نام مخفف عبارت «الگوریتم هشینگ امن» (Secure Hashing Algorithm) است که خروجی آن طول ثابتی به اندازه 256 بیت دارد. تابع اصلی درخت مرکل در بیت کوین ابتدا تراکنش‌ها را در بلاک ذخیره کرده و در پایان آن‌ها را از بلاک بیرون می‌کشد.

همان‌طور که پیش‌تر گفتیم، در بلاک چین بلاک‌ها به وسیله‌‌ی هش‌ها به هم متصل هستند و این هش‌ها برگرفته از بلاک قبلی هستند. در بیت کوین، هر بلاک دارای تعدادی تراکنش و یک سربلاک یا بلاک هِدِر (block header) است. سربلاک دارای بخش‌های زیر است:

  • شماره ورژن بلاک
  • هش بلاک پیشین
  • تایم‌استمپ یا برچسب زمانی
  • سختی استخراج مورد نظر
  • نانس
  • روت هش مرکل

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


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

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

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

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

اتریوم که در کنار بیت کوین شناخته‌ شده‌ترین رمز ارز جهان است، بزرگ‌ترین نمونه استفاده از درخت مرکل پس از بیت کوین است. ساختار درخت مرکلی که اتریوم اجرا کرده با نسخه بیت کوین تفاوت دارد. دلیل آن این است که اتریوم یک سیستم تورینگ کامل (turing-complete) است و پلتفرمی برای طراحی کارکردها و اپلیکیشن‌های پیچیده‌تر است. به همین خاطر نسخه درخت مرکل به کار رفته در اتریوم پیچیده‌تر است. این نسخه، درخت مرکل پاتریشیا (Merkle Patricia Tree) نام دارد و در حقیقت 3 درخت مرکل جداگانه است که برای سه کار متفاوت استفاده می‌شوند.

درخت مرکل یکی از اجزای اساسی سیستم‌های کنترل نسخه‌ توزیع شده است و سیستم‌هایی مانندGit و IPFS از آن بهره برده‌اند. توانایی درخت مرکل در تایید بی‌دردسر تمامیت دیتا‌ی مشترک میان کامپیوترها با فرمت P2P آن را به یک ابزار غیرقابل ارزش‌گذاری برای چنین‌ سیستم‌هایی تبدیل کرده است.

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

منبع

تلگرام-فینمگ

درخت مرکلدرخت مرکل چیست
من اینجا هستم تا شما رو با دنیای بلاک چین و رمزارزها آشنا کنم.جدیدترین مطالب رو در سایت ما finmag.ir بخونید.
شاید از این پست‌ها خوشتان بیاید