گراف غیر چرخشی جهت‌دار (Directed Acyclic Graph (DAG))

مفهوم:

والد:

بعد:

فرزند:

---

لید

سیستم های بلاک چین براساس «مثلث غیرممکن» مشهور شامل امنیت، تمرکز زدایی، و مقیاس پذیری طراحی می شوند و به منظور دستیابی به هدف تمرکززدایی، تمامی گره های کل شبکه، به طور مشترک داده ها را نگهداری کرده و به صورت مشترک تراکنش ها را بازبینی می کنند. مکانیزم اجماع اثبات کار (poW) به گره هایی نیازمند است تا محاسبات بی ارزشی را برای رقابت بر سر دستیابی به حقوق حسابداری انجام داده که منجر به ذخیره و محاسبه مازاد بر نیاز می شود اما این اقدامات برای تامین امنیت شبکه ضروری هستند. بنابراین، نحوه بهبود عملکرد سیستم های بلاک چین به عنوان یک مساله مهم مطرح شده است. روش های جریان اصلی در حال حاضر برای بهبود اجرا و مقیاس پذیری سیستم بلاک چین از نوع تقسیم-پذیری بر حسب قالب (شاردینگ)، ساختار غیرچرخشی مستقیم، اجماع مقیاس پذیر، زنجیره فرعی، بهینه سازی بر روی زنجیره و بهینه سازی سیستم می باشند. تعدادی از پروتکل ها مانند کانفلاکس (Conflux)، هدرا هش گراف (Hedera Hashgraph)، آیوتا (IOTA) و نانو (Nano) همراه با پروژه های استارتاپی شبیه به زنجیره اینترنت اشیاء و اوبایت(Obyte) از ساختارهای مبتنی بر گراف غیرچرخشی جهت دار (DAG) استفاده می کنند.

تعریف به حد

گراف غیرچرخشی جهت دار (DAG) مثل درختی است که تراکنش ها از یک تراکنش به تراکنش دیگر منشعب می شود. این شبکه مانند گرافی است که در یک مسیر بدون سیکل های مرتبط با سایر ضلع ها حرکت می کند. روش ساده تر برای توجه به گراف غیرچرخشی جهت دار (DAG) «رشته ای از گره های شبکه» بوده که هر گره شبکه با یکدیگر مرتبط است اما در حال راه اندازی ارتیاطات یک طرفه به گره های دیگر شبکه می باشد. یکی از منافع اصلی گراف غیرچرخشی جهت دار (DAG)، این است که این شبکه ها به خاطر نحوه سنجش اعتبار تراکنش ها، سریع تر حرکت کرده و سپس با روشی موازی پردازش می شوند.

وجوه افتراق یا شقوق مختلف

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

فهرست مطالب

مقدمه

سیستم های بلاک چین براساس «مثلث غیرممکن» مشهور شامل امنیت، تمرکز زدایی، و مقیاس پذیری طراحی می شوند و به منظور دستیابی به هدف تمرکززدایی، تمامی گره های کل شبکه، به طور مشترک داده ها را نگهداری کرده و به صورت مشترک تراکنش ها را بازبینی می کنند. مکانیزم اجماع اثبات کار (poW) به گره هایی نیازمند است تا محاسبات بی ارزشی را برای رقابت بر سر دستیابی به حقوق حسابداری انجام داده که منجر به ذخیره و محاسبه مازاد بر نیاز می شود اما این اقدامات برای تامین امنیت شبکه ضروری هستند. بنابراین، نحوه بهبود عملکرد سیستم های بلاک چین به عنوان یک مساله مهم مطرح شده است. روش های جریان اصلی در حال حاضر برای بهبود اجرا و مقیاس پذیری سیستم بلاک چین از نوع تقسیم-پذیری بر حسب قالب (شاردینگ)، ساختار غیرچرخشی مستقیم، اجماع مقیاس پذیر، زنجیره فرعی، بهینه سازی بر روی زنجیره و بهینه سازی سیستم می باشند.

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

اصطلاحات زیر برای گراف غیرچرخشی جهت دار (DAG) یکتا هستند:

-وب، شبکه ای است که شامل گره های متصل به یکدیگر یا ضلع هاست.

-ضلع، محل اتصال یک طرفه بین یک یا چند گره شبکه است.

--غیرچرخشی، به این معناست که تراکنش نمی تواند با گره مشابه برای بار دوم مواجه شود زمانی که حرکت از یک گره به گره دیگر با دنبال کردن ضلع های شبکه انجام می شود.

تعدادی از پروتکل ها مانند کانفلاکس (Conflux)، هدرا هش گراف (Hedera Hashgraph)، آیوتا (IOTA) و نانو (Nano) همراه با پروژه های استارتاپی شبیه به زنجیره اینترنت اشیاء و اوبایت(Obyte) از ساختارهای مبتنی بر گراف غیرچرخشی جهت دار (DAG) استفاده می کنند.

ساختارهای داده های دفتر کل توزیع شده

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

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

بلاک چین فهرستی از بلوک های متصل به یکدیگر است اما گراف غیرچرخشی جهت دار (DAG) مثل درختی است که تراکنش ها از یک تراکنش به تراکنش دیگر منشعب می شود. این شبکه مانند گرافی است که در یک مسیر بدون سیکل های مرتبط با سایر ضلع ها حرکت می کند. روش ساده تر برای توجه به گراف غیرچرخشی جهت دار (DAG) «رشته ای از گره های شبکه» بوده که هر گره شبکه با یکدیگر مرتبط است اما در حال راه اندازی ارتیاطات یک طرفه به گره های دیگر شبکه می باشد.

نمودار 1 به صورت تصویری ساختار معمولی بلاک چین را با ساختار گراف غیرچرخشی جهت دار (DAG) در هش گراف هدورا (Hedora Hashgraph) مقایسه می کند. ساختار بلاک-چین نیز خطی تر و به صورت هرمی می باشد. یکی از منافع اصلی گراف غیرچرخشی جهت دار (DAG)، این است که این شبکه ها به خاطر نحوه سنجش اعتبار تراکنش ها، سریع تر حرکت کرده و سپس با روشی موازی پردازش می شوند. این در حالی است که تراکنش ها در هر بلاک چین، به صورت سریالی پردازش می شوند.

نمودار 1. بلاک چین در مقابل ساختار گراف غیرچرخشی جهت دار (DAG) در هدورا هش گراف (Hedora Hashgraph)

منبع: هالبروک (2020)

اجماع

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

نیازی به انتخاب رهبر در نانو  (که مبتنی بر گراف غیرچرخشی جهت دار (DAG) می باشد) وجود ندارد زیرا کاربران مجبور به سفارش تراکنش های خود بوده و الگوریتم اثبات کار(PoW) هنوز هم مورد استفاده قرار می گیرد هر چند که این کار به خاطر انتخاب رهبر نیست(چون رهبری وجود ندارد). الگوریتم اثبات کار(PoW) در چارچوب نانو، به عنوان سنجه حفظ اسپم (spam) مورد استفاده قرار می گیرد تا مشابه هشکش ، از تولید بیش از حد تراکنش ها توسط کاربر نامرتبط ممانعت کند. اما روشی متفاوت برای حل تعارض ها یعنی سیستم نمایندگان معرفی شده است. هنگامی که حسابی ایجاد می شود، باید نماینده ای را انتخاب کند که در طول زمان بتواند تغییر کند. نمایندگان گراف غیرچرخشی جهت دار (DAG) به منظور حل تناقض ها، رای می دهند و رای های آنها موزون هستند: رای یک نماینده در مجموع همه مانده حساب هایی است که این نماینده را انتخاب می کند. تراکنش برنده در وضعیت تناقض، کسی است که بیشترین رای را با توجه به وزن رای دهندگان گراف غیرچرخشی جهت دار (DAG)کسب کند و نیاز به هیچ سرباری برای تراکنش های بدون مساله نیست.

اطمینان از تایید تراکنش

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

اندازه دفتر کل توزیع شده

نانو، بین نوع گره ها تمایز قائل می شود: از نظر زمانی یا تاریخی، رکوردی از همه تراکنش ها را حفظ می کند، از نظر جاری بودن که تنها در پیشران زنجیره های حساب قرار می گیرد و از نظر سبک بودن که هیچ داده دفتر کل توزیع شده ای را نگه نداشته و تنها تراکنش های جدید را مشاهده یا خلق می کند (همه گره ها در پیاده سازی جاری، جزء گره های زمانی یا تاریخی هستند). نانو، برای کاهش اندازه دفتر کل توزیع شده، برای پیاده سازی هرس برنامه ریزی می کند. از آنجایی که حساب ها، رکوردی از مانده حساب ها را به جای داده های ورودی تراکنش (خرج نشده) نگهداری می کنند، همه داده های مالی دیگر می توانند برای کاهش اندازه دفتر کل توزیع شده کنار گذاشته شوند.

مقیاس پذیری

برخلاف تکنولوژی بلاک چین که درآن باید معتبرساز اختصاصی وجود داشته باشد تا ایجاد و ثبت سفارش بلوک ها را انجام دهند، کاربر در نانو باید تراکنش های خود را دسته بندی کند. این رویکرد به طور گسترده متفاوت از روشی است که تراکنش ها به وسیله آنها بر روی سیستم های بلاک چین انجام می شوند. به جای در اختیار داشتن گره هایی که با سفارش گذاری تراکنش-ها شارژ می شود، سفارش گذاری تراکنش به صورت ناهماهنگ توسط حسابی انجام می شود که دارنده آن حساب، عهده دار سفارش گذاری تراکنش می باشد. این رویکرد تا حد زیادی بر مقیاس پذیری اثرگذار است و نتیجه این تصمیم برای طراحی، چیزی است که در آن هیچ پوشش ذاتی در تراکنش در ظرفیت پذیرش پروتکل مربوطه وجود ندارد. اما، بالاترین ظرفیت پذیرش بر روی تستی که در شبکه قابل دستیابی می شود، 306 تراکنش در ثانیه (TPS)  با سرعت متوسط 105.75 تراکنش بر ثانیه می باشد و حد و اندازه مذکور در حال حاضر به وسیله کیفیت سخت افزاری رتبه مصرف کننده و شرایط شبکه تعیین می شود.

انواع

بلاک چین های کلاسیک نظیر بیت کوین ساختار زنجیره مستقل را می پذیرند و مانع از هر انشعابی می شوند که تضمین دوبار خرج کردن را از نظر ساختار داده ها ارائه کند. هدف از گراف غیرچرخشی جهت دار (DAG) تبدیل بلاک چین ها به بلاک چین های مقیاس پذیرتر برای بالا بردن سرعت تراکنش ها به مفهوم موازی سازی یا انشعاب می باشد. دو پیاده سازی متمایز در این جا وجود دارد.

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

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

جستارهای وابسته

پانویس/ پاورقی

منابع

• Joshi, J., Nepal, S., Zhang, Q., & Zhang, L. J. (2019). Blockchain–ICBC 2019. Springer International Publishing.

• Holbrook, Joseph(2020) - Architecting enterprise blockchain solutions-Sybex .

• Benčić, F. M., & Žarko, I. P. (2018, July). Distributed ledger technology: Blockchain compared to directed acyclic graph. In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS) (pp. 1569-1570). IEEE.

پیوند به بیرون

الگوهای ناوبری

رده