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

درخت مرکل، ساختار داده‌ای است که در آن هر گره، هشی از داده‌های زیرگره‌ها است؛ درخت مرکل در بلاک چین، برای اثبات وجود ترتیب تراکنش‌ها و تایید تاریخچه‌ کاربرد دارد.

درخت مرکل (Merkle Tree)‌ یا درخت هش، درختی است ساختار رشدی، برعکس رشد درخت‌های عادی دارد؛ رشد این درخت به جای ریشه از برگ‌ها‌یش آغاز می‌شود! در درخت مرکل، هر برگ (گره برگ یا Leaf Node) با هش رمزنگاری یک بلوک داده، هر زیرشاخه (گره غیربرگی یا Non-Leaf Node)، با هش رمزنگاری دو برگ و هر شاخه هم با هش رمز‌نگاری زیرشاخه فرزند خود برچسب‌گذاری می‌شود و این ماجرا تا رسیدن به ریشه ادامه دارد.

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

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

برای راحتی شما عزیزان، فایل پادکست این مقاله برای شما آماده شده است.

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

درخت مرکل، که به آن درخت هش باینری هم می‌گویند، نوعی ساختار داده رایج در علوم کامپیوتر است. این درخت، در علوم کامپیوتر و رمزنگاری، درختی است که در آن هر برگ (گره) با هش رمزنگاری یک بلوک داده و هر گره‌ای که برگ نیست (شاخه یا گره داخلی) با هش رمزنگاری گره‌های فرزند خود برچسب‌گذاری می‌شود. مفهوم درخت هش باینری را دانشمند و ریاضی‌دانی به نام رالف مرکل در سال ۱۹۷۹ به ثبت رساند و به افتخار او، این درخت را درخت مرکل می‌نامند.

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

دانلود هفتمین ماهنامه دامیننس

سواد اقتصادی و ذهنیت برنده در دنیای کریپتوکارنسی

Please leave this field empty.

Δ

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

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

فرض کنید ۴ مجموعه داده (A، B، C، D) داریم؛ برای ساخت درخت مرکل با این داده‌ها به صورت زیر عمل می‌کنیم: ابتدا هر داده را با تابع هش، به رشته‌ای ثابت تبدیل می‌کنیم. برای سادگی، فرض می‌کنیم که تابع هش برای هر مجموعه داده، یک حرف برمی‌گرداند.

A -> H1
B -> H2
C -> H3
D -> H4

سپس دو داده هش شده را با هم ترکیب کرده و دوباره با تابع هش تبدیل می‌کنیم. H1 و H2 با هم ترکیب شده و با تابع هش به H12 تبدیل می‌‌شوند. به همین ترتیب، H3 و H4 نیز با هم ترکیب شده و با تابع هش به H34 تبدیل می‌شوند. در نهایت، دو داده جدید (H12 و H34) را با هم ترکیب و با تابع هش به H1234 تبدیل می‌شوند؛ این داده نهایی را ریشه درخت مرکل می‌نامند:

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

• روشی ساده و سریعی برای تأیید صحت داده‌ها است. برای مثال، اگر بخواهید بدانید که آیا A جزئی از درخت است یا خیر، تنها کافی است H1، H2 و H34 را بدانید. با این اطلاعات، می‌توانید با ترکیب و هش کردن آن‌ها، به ریشه درخت برسید. اگر ریشه درخت همان ترکیب قبلی باشد، پس A جزئي از درخت است.
• روشی قابل اطمینان برای همگام‌سازی داده‌ها است. برای مثال، اگر دو نفر درخت مرکل چند داده را نگهداری كنند و بخواهند آن‌ها را به‌روزرسانی كنند، تنها كافی است كه ريشه دو درخت را با هم مقايسه كنند؛ اگر ریشه‌ها یکسان نباشند، پس داده‌های ابتدایی با هم تفاوت داشته و باید همگام‌سازی شوند.
• ریشه‌های درخت مرکل در تراکنش‌های ارزهای دیجیتال، کاربرد مشابهی داشته و برای اطمینان از کامل، سالم و بدون تغییر بودن بلوک‌های داده ارسال شده از طریق شبکه‌ای همتا‌به‌همتا، استفاده می‌شوند. درواقع، ریشه‌های درخت مرکل نقش بسیار مهمی در محاسبات مورد نیاز برای حفظ ارزهای دیجیتال مانند بیت کوین و اتر دارند.

توابع هش رمزنگاری

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

برای مثال، تابع هش MD5، الگوریتمی است که داده‌های ورودی را به ۱۲۸ بیت (۳۲ کاراکتر) هش (درهم‌سازی یا ترکیب) می‌کند؛ این الگوریتم برای بررسی صحت فایل‌های دانلود شده و رمزنگاری پسوردها به‌ کار می‌رود. برخی از الگوریتم‌های هش دیگر عبارتند از SHA-1, SHA-256, SHA-512, WHIRLPOOL و CRC32.

اگر از الگوریتم هش SHA-256 استفاده کرده و عبارت 101Blockchains را به عنوان ورودی به آن ارسال کنید، خروجی زیر را دریافت خواهید کرد.

fbffd63a60374a31aa9811cbc80b577e23925a5874e86a17f712bab874f33ac9

حال اگر حرف s را در همین عبارت حذف کنیم، خروجی الگوریتم هش SHA-256 به صورت زیر خواهد بود:

c4d67db72f3d18eaca2e8e8498271de353d25874e4448be4887f2563576c6fe8

پس تابع هش باید دارای ویژگی‌های زیر باشد:

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

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

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

همان‌طور که گفتیم، ساختار درخت مرکل با هش کردن مکرر جفت گره‌ها، ایجاد شده و این فرایند تا زمانی که تنها یک هش باقی بماند، ادامه پیدا می‌کند. هش نهایی با نام ریشه مرکل (Merkle Root) یا ریشه هش (Root Hash) شناخته می‌شود. این ریشه از شناسه تراکنش‌ها ساخته شده‌ و هرکدام، هشِ مجموعه‌ای مجزا از تراکنش‌ها هستند. هر گره غیربرگی، هشِ هشِ قبلی خود است و هر گره برگی هم، هشِ داده‌های تراکنش است.

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

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

درختان مرکل برای فناوری بلاک چین، چهار مزیت قابل‌توجه به ارمغان می آورند:

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

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

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

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

چرا هش‌ها به تنهایی برای تراکنش‌ها کافی نیستند؟

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

اینجا است که درختان مرکل وارد می شوند؛ درختان مرکل بدون نیاز به دانلود کل بلوک، تایید می‌کنند که آیا تراکنشی در یک بلوک وجود دارد یا خیر! درواقع، با استفاده از درختان مرکل، می‌توانیم تایید جزئی یک بلوک را بدون نیاز به دانلود و بررسی هر تراکنش در آن، انجام دهیم. تنها به مسیری نیاز داریم که از یکی از گره‌های برگ (هش تراکنش) شروع شود و تا ریشه پیدا کند. این مسیر، اثبات دربرگیری (Proof of Inclusion) نامیده می‌شود و با هش کردن یک تراکنش با سایر گره‌های موجود در مسیر و مقایسه نتیجه با ریشه مرکل، می‌تواند ثابت کند که آن تراکنش متعلق به یک بلوک است یا خیر.

دیگر موارد استفاده درخت مرکل

درخت هش باینری در موارد دیگری هم پیاده‌سازی می‌شود:

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

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

دینامو دی‌بی (Amazon DynamoDB) و آپاچی کاساندرا (Apache Cassandra) هم دو سیستم مدیریت پایگاه داده NoSQL هستند که در طول فرایند تکثیر داده‌ها، برای کنترل تغییرات از درختان مرکل استفاده می‌کنند.

درخت ورکل (Verkle Tree) چیست؟ چه مزایایی ارائه می‌دهد؟

درختان ورکل یا Verkle Tree بسیار شبیه به درخت مرکل است و امکان سازماندهی حجم زیادی از داده‌ها را فراهم می‌کند. این نوع درخت، شاهدی برای هر بلوک بلاک چین ایجاد می‌کند که می‌تواند برای تأیید توسط هر کاربری با دسترسی ریشه مورد استفاده قرار گیرد. درخت ورکل، نقشی حیاتی در مقیاس‌بندی بلاک چین‌هایی مانند اتریوم ایفا می‌کند و به کمتر از ۱۵۰ بایت برای اثبات درخت نیاز دارند. مزایای درخت ورکل عبارت‌اند از:

• قابلیت تأیید داده‌ها: داده‌های درخت ورکل را می‌توان به‌راحتی توسط هر کاربری با دسترسی ریشه تأیید کرد.
• ذخیره‌سازی کمتر: درخت ورکل می‌تواند اندازه‌های اثبات را تا ۳۰ برابر کمتر از درختان مرکل کاهش دهد.
• ضروری برای مقیاس‌پذیری: درخت ورکل برای مقیاس‌پذیری بلاک چین‌های لایه 1 و تطبیق با نیازهای روزافزون کاربر، حیاتی است.

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

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

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

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

گفتار پایانی

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

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

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

سوالات متداول

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

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

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

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

• چرا درخت مرکل برای بلاک‌ چین ضروری است؟

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