درخت مرکل (Merkle tree) چیست و چه کاربردی در بیتکوین دارد؟

درخت مرکل (Merkle tree) چیست؟

مفهوم Merkle tree اوایل دهه ۱۹۸۰ میلادی توسط Ralph Merkle که یک دانشمند علوم رایانه بود و بواسطه کارهایش بر روی کلید عمومی و رمزنگاری شناخته شده بود مطرح شد.

درخت مرکل یا همان Merkle tree ساختاری است که از آن برای صحت‌سنجی بهینه‌ی درستی داده‌ها در یک مجموعه استفاده می‌شود. درخت مرکل در شبکه‌های نظیر به نظیر (P2P) اهمیت ویژه‌ای دارند که در آنها شرکت کنندگان می‌بایست داده‌ها را با هم به اشتراک بگذارند و به صورت مستقل اقدام به اعتبار‌سنجی آنها کنند. تابع‌های هش هسته اصلی درخت مرکل را تشکیل می‌دهند.

درخت مرکل ( Merkle tree ) چگونه عمل می‌کند؟

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

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

شاید با خودتان فکر کنید که کاش راه ساده‌تری برای این موضوع وجود داشت. خوشبختانه وجود دارد و این راه حل درخت مرکل Merkle tree است. با استفاده از یکی از این درخت‌های مرکل، فایلتان را به قطعات کوچکتری تقسیم می‌کنید مثلا اگر فایلتان ۵۰ گیگابایت باشد، آن را به ۱۰۰ قطعه نیم گیگابایتی تقسیم می‌کنید بعد می‌توانید این قطعات را یکی بعد از دیگری دانلود کنید. وقتی فایل‌ها را از طریق تورنت(Torrent) اشتراک‌گذاری می‌کنید هم عملا همین کار را می‌کنید.

در این صورت، منبع دانلود فایلتان به شما هشی به نام ریشه مرکل (Merkle root) می‌دهد. این هشِ واحد، نماینده‌ای از قطعه داده‌هایی است که مجموعا فایل شما را تشکیل می‌دهند. اما ریشه مرکل (Merkle root) صحت‌سنجی فایل را خیلی ساده‌تر می‌کند.

برای اینکه درکش برایتان ساده‌تر شود مثالی می‌زنم که در آن یک فایل ۸ گیگابایتی را به ۸ قطعه تقسیم می‌کنیم. هر کدام از این ۸ قطعه را با حروف A تا H نامگذاری کنید. حالا هر کدام از این ۸ قطعه را از تابع هشی عبور می‌دهیم که در نتیجه به ما ۸ هش مختلف می‌دهد.

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

نه، به جای این کار، هر جفت هش را بر می‌داریم با هم ترکیبشان می‌کنیم بعد آنها را با هم هش‌گذاری می‌کنیم. در نتیجه hA + hB، hC + hD، hE + hF و hG + hH را هش‌گذاری می‌کنیم. در نتیجه این کار ۴ هش بدست می‌آوریم. سپس فرایند هش‌گذاری را با این ۴ هش یک دور دیگر انجام می‌دهیم تا به ۲ هش برسیم و نهایتا این دو هش را هش‌گذاری می‌کنیم تا به هش اصلی یا همان ریشه مرکل (Merkle root) یا ریشه هش برسیم.

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

خوشبختانه یک راه کاربردی وجود دارد که بررسی کنیم ببینیم کدام قطعه از داده‌ها هش اشتباهی داشته. در مثال ما، فرض کنید که قطعه hE بوده. کار را با بررسی دو هشی که هش مرکل یا هش ریشه را ایجاد کرده‌اند (یعنی hABCD و hEFGH ) شروع می‌کنید. مقدار hABCD باید با هش منبع تطابق داشته باشد چرا که در این شاخه از درخت مرکل خطایی وجود ندارد اما مقدار hEFGH تطابق ندارد، در نتیجه متوجه می‌شوید که باید این شاخه از درخت مرکل را بررسی کنید. سپس hEF و hGH را بررسی می‌کنید و آنها را با هش منبع خودتان مقایسه می‌کنید. hGH خوب به نظر می‌رسد در نتیجه متوجه می‌شوید که hEF قطعه مشکل دار ماست. دست آخر، هش‌های hE و hF را مقایسه می‌کنید و حالا می‌فهمید که هش hE مشکل دارد و اشتباه است. بنابراین حالا می‌توانید این قطعه را مجددا دانلود کنید.

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

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

درخت‌های مرکل در بیتکوین و بسیاری از رمزارزهای دیگر ضروری هستند. آنها جزئی لاینفک از هر بلاک هستند و می‌توان آنها را در هدر بلاک‌ها پیدا کرد. برای اینکه برای درختمان برگ هم داشته باشیم از هش تراکنش استفاده می‌کنیم یعنی TXID هر تراکنش در بلاک قرار داده می‌شود.

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

استخراج

هر بلاک بیتکوین از دو جز تشکیل شده است. جزء اول هدر بلاک (Block Header) است که اندازه ثابتی دارد و حاوی متادیتای بلاک است. جزء دوم فهرستی از تراکنش‌ها است که اندازه این بخش از بلاک متغیر است اما معمولا از اندازه هدر بلاک بیشتر است.

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

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

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

صحت سنجی

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

فرض کنید که می‌خواهیم اطلاعاتی درباره تراکنشی بدست بیاوریم که TXID آن hD است. اگر hC به ما داده شود می‌توانیم hCD را محاسبه کنیم. سپس برای محاسبه hABCD نیاز به hAB داریم و سرانجام با hEFGH می‌توانیم ببینیم که ریشه مرکل حاصله با ریشه مرکلی که در هدر بلاک آمده مطابقت دارد یا خیر. اگر مطابقت داشت که اثبات‌کننده این است که آن تراکنش در آن بلاک قرار داشته چرا که ایجاد همان هش با استفاده از داده‌های دیگر تقریبا محال است.

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

در پایان

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

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

دوستان لطفا اگه از این مطلب خوشتون اومد حتما برای حمایت پست رو لایک کنید و برای دوستانتون هم فوروارد کنید و صفحه من در توییتر و کانال تلگرام رو هم حتما فالو کنید و عضو بشید. ممنون

صفحه توییتر:

http://twitter.com/BitcoinBreads

کانال تلگرام:

https://t.me/BitcoinBreads