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


ماهان سرجوقیان 26 شهریور 1401 13 دقیقه مطالعه
درخت مرکل چیست؟

فهرست محتوا

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

درخت مرکل ساختاری است که برای تایید کارآمد یکپارچگی داده ها در یک مجموعه استفاده می شود.

آنها به ویژه در زمینه شبکه های همتا به همتا، که در آن شرکت کنندگان نیاز به اشتراک گذاری و تایید مستقل اطلاعات دارند، جالب هستند.

توابع هش در هسته ساختارهای درختی مرکل قرار دارند، بنابراین توصیه می کنیم هشینگ چیست؟ قبل از ادامه مطالعه کنید .

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

فرض کنید که می خواهید یک فایل بزرگ دانلود کنید.

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

اگر این کار را کرد، می دانید که فایلی که در رایانه خود دارید دقیقاً مشابه فایل آنهاست.
اگر هش ها مطابقت ندارند، مشکل دارید.

شما یا یک فایل مخرب را دانلود کرده اید که به عنوان نرم افزار ظاهر شده است یا به درستی دانلود نشده است و بنابراین کار نمی کند.

اگر مورد دوم باشد، اگر مجبور شده باشید مدتی صبر کنید تا فایل دانلود شود، احتمالا خیلی خوشحال نخواهید شد.

اکنون، باید فرآیند را دوباره راه اندازی کنید و امیدوار باشید که دوباره خراب نشود.

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

اگر یک فایل 50 گیگابایتی بود، می توانید آن را به 100 قطعه تقسیم کنید، به طوری که اندازه هر کدام 0.5 گیگابایت باشد.

سپس تکه تکه دانلود می شود. این اساساً کاری است که هنگام تورنت کردن فایل ها انجام می دهید.

در این صورت منبع شما یک هش به نام ریشه Merkle در اختیار شما قرار می دهد. این هش واحد نمایشی از هر تکه داده ای است که فایل شما را تشکیل می دهد. اما ریشه Merkle تأیید داده ها را بسیار آسان تر می کند.

برای ساده نگه داشتن آن، بیایید مثالی بزنیم که در آن از یک فایل 8 گیگابایتی استفاده می کنیم که به هشت قسمت تقسیم شده است.

ادامه مطلب
معروف ترین رمز ارزهای 2022

قطعات مختلف را از A تا H فراخوانی کنید. سپس هر قطعه از یک تابع درهم عبور داده می شود و به ما هشت هش مختلف می دهد.

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

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

اگر فایل شما هزاران قطعه دارد، آیا واقعاً همه آنها را هش می کنید و نتایج را با دقت مقایسه می کنید؟

نه. در عوض، ما هر جفت هش را می گیریم، آنها را ترکیب می کنیم، سپس آنها را با هم هش می کنیم. بنابراین ما hA + hB، hC + hD، hE + hF و hG + hH را هش می کنیم.

در نهایت با چهار هش مواجه می شویم. سپس یک دور دیگر هش کردن را با اینها انجام می دهیم تا در نهایت به دو عدد برسید.

در نهایت، دو مورد باقی مانده را هش می کنیم تا به هش اصلی خود – ریشه Merkle (یا هش ریشه) برسیم.

ساختار شبیه یک درخت وارونه است. در ردیف پایین، برگ ها را داریم که برای تولید گره ها و در نهایت ریشه ترکیب می شوند.
 
ما اکنون ریشه Merkle را داریم که نشان دهنده فایلی است که دانلود کرده ایم.

ما می توانیم این هش ریشه را با هش ارائه شده توسط منبع مقایسه کنیم. اگر مطابقت داشته باشد، عالی است! اما اگر هش ها متفاوت باشد، می توان مطمئن بود که داده ها اصلاح شده اند.

به عبارت دیگر، یک یا چند قطعه هش متفاوتی تولید کرده اند. بنابراین هر گونه تغییر جزئی در داده ها ریشه Merkle کاملاً متفاوتی را به ما می دهد.

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

شما می توانید با درخواست از یک همتا برای دو هش که ریشه Merkle (hABCD و hEFGH) را تولید می کنند، شروع کنید.

مقدار hABCD شما باید با ارزش آنها مطابقت داشته باشد زیرا هیچ اشتباهی در آن زیردرخت وجود ندارد.

ادامه مطلب
الگوریتم اجماع اثبات اعتبار (PoA) چیست ؟

اما hEFGH این کار را نمی‌کند، بنابراین می‌دانید که آنجا را بررسی کنید. سپس hEF و hGH را درخواست کنید و آنها را با خودتان مقایسه کنید.

hGH خوب به نظر می رسد، بنابراین می دانید که hEF مقصر ماست. در نهایت، شما هش های hE و hF را مقایسه می کنید.

اکنون می دانید که hE نادرست است، بنابراین می توانید آن قطعه را دوباره دانلود کنید.

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

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

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

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

درختان مرکل در بیت کوین و بسیاری دیگر از ارزهای دیجیتال ضروری هستند. آنها جزء جدایی ناپذیر هر بلوک هستند، جایی که می توان آنها را در هدرهای بلوک یافت.

برای بدست آوردن برگ درخت خود، از هش تراکنش (TXID) هر تراکنش موجود در بلوک استفاده می کنیم.

ریشه Merkle در این مورد به چند هدف عمل می کند. بیایید نگاهی به کاربردهای آنها در استخراج ارز دیجیتال و تأیید تراکنش بیندازیم.

معدن

یک بلوک بیتکوین از دو قطعه تشکیل شده است. بخش اول هدر بلوک است، یک بخش با اندازه ثابت که حاوی ابرداده برای بلوک است.

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

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

آنها می توانند قبل از یافتن یک تریلیون ها تلاش کنند. با هر تلاش، آنها یک عدد تصادفی را در هدر بلوک (nonce) تغییر می دهند تا خروجی متفاوتی تولید کنند.

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

ادامه مطلب
امضای دیجیتال چیست؟

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

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

این کار می کند زیرا ضد دستکاری است. شما به طور موثر همه تراکنش های بلوک را در قالب فشرده خلاصه می کنید.

شما نمی توانید یک هدر بلوک معتبر پیدا کنید و بعداً لیست تراکنش ها را تغییر دهید، زیرا این امر ریشه Merkle را تغییر می دهد.

هنگامی که بلوک به گره های دیگر ارسال می شود، آنها ریشه را از لیست تراکنش محاسبه می کنند. اگر با هدر مطابقت نداشته باشد، بلوک را رد می کنند.

ویژگی جالب دیگری از ریشه های مرکل وجود دارد که می توانیم از آن استفاده کنیم. این یکی به مشتریان سبک (گره هایی که یک کپی کامل از بلاک چین را در خود ندارند) مربوط می شود.

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

کاری که می توانید به جای آن انجام دهید این است که به سادگی درخواست اثبات Merkle کنید – شواهد ارائه شده توسط گره کامل که ثابت می کند تراکنش شما در یک بلوک خاص است.

این بیشتر به عنوان تأیید پرداخت ساده یا SPV نامیده می شود و توسط ساتوشی ناکاموتو در وایت پیپر بیت کوین توضیح داده شده است.

برای بررسی hD، فقط به هش هایی نیاز داریم که با رنگ قرمز نشان داده شده اند.

سناریویی را در نظر بگیرید که در آن می خواهیم اطلاعاتی درباره تراکنشی که TXID آن hD است بدانیم. اگر hC به ما ارائه شود، می توانیم hCD را کار کنیم.

سپس برای محاسبه hABCD به hAB نیاز داریم. در نهایت، با hEFGH، می‌توانیم بررسی کنیم که ریشه Merkle به دست آمده با هدر بلوک مطابقت دارد.

اگر این کار را انجام دهد، دلیلی بر این است که تراکنش در بلوک گنجانده شده است – ایجاد هش یکسان با داده‌های مختلف تقریباً غیرممکن است.

ادامه مطلب
الگوریتم اثبات فعالیت (PoA) چیست؟

در مثال بالا، ما فقط سه بار مجبور شدیم هش کنیم. بدون اثبات مرکل، ما باید این کار را هفت بار انجام می‌دادیم.

از آنجایی که امروزه بلوک ها حاوی هزاران تراکنش هستند، استفاده از اثبات های Merkle باعث صرفه جویی زیادی در زمان و منابع محاسباتی ما می شود.

بستن افکار

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

در سیستم‌های توزیع‌شده، درختان مرکل امکان تأیید آسان اطلاعات را بدون سیل کردن شبکه با داده‌های غیرضروری فراهم می‌کنند.

بدون درختان مرکل (و ریشه های مرکل)، بلوک های بیتکوین و سایر ارزهای دیجیتال به اندازه امروز فشرده نمی شدند.

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

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

با هر تلاش، آنها یک عدد تصادفی را در هدر بلوک (nonce) تغییر می دهند تا خروجی متفاوتی تولید کنند.

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

یک ریشه Merkle روند را به طور قابل توجهی ساده می کند.

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

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

این کار می کند زیرا ضد دستکاری است. شما به طور موثر همه تراکنش های بلوک را در قالب فشرده خلاصه می کنید.

شما نمی توانید یک هدر بلوک معتبر پیدا کنید و بعداً لیست تراکنش ها را تغییر دهید، زیرا این امر ریشه Merkle را تغییر می دهد.

هنگامی که بلوک به گره های دیگر ارسال می شود، آنها ریشه را از لیست تراکنش محاسبه می کنند.

اگر با هدر مطابقت نداشته باشد، بلوک را رد می کنند.

ادامه مطلب
 چرا وای فای (WiFi) عمومی ناامن است و حملات MitM چیست؟
Share this...
Tweet about this on Twitter
Twitter
Share on LinkedIn
Linkedin
برچسب‌ها :

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.

Rating*