اعداد تصادفی و شبکه های غیرمتمرکز: کاربردهای عملی

معرفی

"تولید اعداد تصادفی آنقدر مهم است که به شانس سپرده شود."
رابرت کاوو، 1970

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

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

تولید اعداد تصادفی

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

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

اگر یک دوره ابتدایی رمزنگاری را گذرانده اید، باید همه اینها را بدانید، پس بیایید در مورد شبکه های غیرمتمرکز ادامه دهیم.

تصادفی در بلاک چین

اول از همه، من در مورد بلاک چین هایی با پشتیبانی از قراردادهای هوشمند صحبت خواهم کرد؛ آنها کسانی هستند که می توانند به طور کامل از فرصت های ارائه شده توسط تصادفی با کیفیت بالا و غیرقابل انکار استفاده کنند. علاوه بر این، برای اختصار، من این فناوری را " می ناممچراغ‌های تصادفی قابل تأیید عمومی” یا PVRB. از آنجایی که بلاک چین ها شبکه هایی هستند که در آن اطلاعات می تواند توسط هر شرکت کننده تأیید شود، بخش کلیدی نام «قابل تأیید عمومی» است. هرکسی می‌تواند از محاسبات برای به دست آوردن مدرکی استفاده کند که نشان دهد عدد به دست آمده در بلاک چین دارای ویژگی‌های زیر است:

• نتیجه باید دارای توزیع یکنواخت قابل اثبات باشد، یعنی مبتنی بر رمزنگاری قابل اثبات قوی باشد.
• کنترل هیچ یک از بیت های نتیجه ممکن نیست. در نتیجه، نمی توان نتیجه را از قبل پیش بینی کرد.
• شما نمی توانید با شرکت نکردن در پروتکل یا با بارگذاری بیش از حد شبکه با پیام های حمله، پروتکل تولید را خراب کنید.
• همه موارد فوق باید در برابر تبانی تعداد مجاز از شرکت کنندگان پروتکل غیر صادق (مثلاً 1/3 شرکت کنندگان) مقاوم باشد.

هر گونه امکان تبانی یک گروه کوچک از شرکت کنندگان برای تولید تصادفی حتی کنترل شده زوج/فرد یک حفره امنیتی است. هر گونه توانایی گروه برای جلوگیری از صدور تصادفی یک حفره امنیتی است. به طور کلی مشکلات زیادی وجود دارد و این کار ساده ای نیست ...

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

الگوریتم های اجماع

PVRB نقش بزرگی در سازماندهی اجماع شبکه ایفا می کند. تراکنش‌ها در زنجیره‌های بلوکی توسط یک امضای الکترونیکی محافظت می‌شوند، بنابراین «حمله به یک تراکنش» همیشه شامل یا حذف یک تراکنش در یک بلوک (یا چندین بلوک) است. و وظیفه اصلی الگوریتم اجماع توافق بر سر ترتیب این تراکنش ها و ترتیب بلوک هایی است که شامل این تراکنش ها می شود. همچنین، یکی از ویژگی‌های ضروری برای بلاک چین‌های واقعی، نهایی‌بودن است - توانایی شبکه برای توافق بر این که زنجیره تا بلوک نهایی نهایی است و هرگز به دلیل ظهور فورک جدید حذف نمی‌شود. معمولاً برای توافق در مورد معتبر بودن یک بلوک و مهمتر از همه نهایی بودن، جمع آوری امضا از اکثریت تولیدکنندگان بلوک (از این پس BP - تولیدکنندگان بلوک نامیده می شود) لازم است که حداقل مستلزم تحویل زنجیره بلوک است. به همه BPها، و توزیع امضا بین همه BPها. با افزایش تعداد BP ها، تعداد پیام های ضروری در شبکه به طور تصاعدی افزایش می یابد، بنابراین، الگوریتم های اجماع که نیاز به نهایی شدن دارند، به عنوان مثال در اجماع Hyperledger pBFT، با سرعت مورد نیاز کار نمی کنند، از چندین ده BP شروع می شود و نیاز به نهایی دارند. تعداد زیادی اتصال

اگر یک PVRB غیرقابل انکار و صادقانه در شبکه وجود داشته باشد، حتی در ساده ترین تقریب، می توان بر اساس آن یکی از تولیدکنندگان بلوک را انتخاب کرد و در طول یک دور پروتکل، او را به عنوان "رهبر" منصوب کرد. اگر داریم N تولیدکنندگان بلوک، که از آن جمله است M: M > 1/2 N صادق باشید، تراکنش ها را سانسور نکنید و زنجیره را برای انجام یک حمله «دوباره خرج کردن» منقبض نکنید، سپس با استفاده از یک PVRB بدون چالش توزیع شده یکنواخت، امکان انتخاب یک رهبر صادق با احتمال را فراهم می کند. M / N (M / N > 1/2). اگر به هر یک از رهبران بازه زمانی اختصاص داده شود که در طی آن بتواند یک بلوک تولید کند و زنجیره را تأیید کند و این فواصل زمانی برابر باشند، در این صورت زنجیره بلوکی BP های صادق طولانی تر از زنجیره ای خواهد بود که توسط BP های مخرب تشکیل شده است و اتفاق نظر وجود دارد. الگوریتم به طول زنجیره متکی است و به سادگی "بد" را کنار می گذارد. این اصل تخصیص برش‌های زمان مساوی به هر BP برای اولین بار در گرافن (سلف EOS) اعمال شد و به اکثر بلوک‌ها اجازه می‌دهد با یک امضا بسته شوند، که بار شبکه را تا حد زیادی کاهش می‌دهد و اجازه می‌دهد این اتفاق نظر بسیار سریع کار کند. به طور پیوسته با این حال، شبکه EOS اکنون باید از بلوک های ویژه (آخرین بلوک غیر قابل برگشت) استفاده کند که با امضای 2/3 BP تأیید می شود. این بلوک ها برای اطمینان از نهایی بودن (عدم امکان شروع یک چنگال زنجیره ای قبل از آخرین بلوک غیرقابل برگشت) خدمت می کنند.

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

برجسته ترین نماینده چنین الگوریتم هایی: اوروبروس از تیم کاردانو که گفته می شود در برابر تبانی BP از نظر ریاضی قابل اثبات است.

در Ouroboros، PVRB برای تعریف به اصطلاح "برنامه BP" استفاده می شود - برنامه ای که بر اساس آن هر BP زمان خود را برای انتشار یک بلوک اختصاص می دهد. مزیت بزرگ استفاده از PVRB "برابری" کامل BPها (با توجه به اندازه ترازنامه آنها) است. یکپارچگی PVRB تضمین می کند که BP های مخرب نمی توانند زمان بندی شکاف های زمانی را کنترل کنند و بنابراین نمی توانند با تهیه و تجزیه و تحلیل فورک های زنجیره از قبل، زنجیره را دستکاری کنند و برای انتخاب یک چنگال کافی است به سادگی به طول زمان تکیه کنیم. زنجیره ای، بدون استفاده از روش های پیچیده برای محاسبه "مطلوب" BP و "وزن" بلوک های آن.

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

مقیاس بندی و تعادل بار

PVRB همچنین می تواند در کارهایی مانند کاهش بار و مقیاس پرداخت سود زیادی داشته باشد. برای شروع، منطقی است که خود را با آن آشنا کنید مقاله Rivesta "بلیت های قرعه کشی الکترونیکی به عنوان پرداخت خرد". ایده کلی این است که به جای پرداخت 100 1c از پرداخت کننده به گیرنده، می توانید یک قرعه کشی صادقانه با جایزه 1$ = 100c انجام دهید، که در آن پرداخت کننده یکی از 1 "بلیت لاتاری" خود را برای هر یک به بانک می دهد. پرداخت 100c. یکی از این بلیت‌ها برنده یک شیشه 1 دلاری است و این بلیط است که گیرنده می‌تواند در بلاک چین ثبت کند. مهم ترین نکته این است که 99 بلیط باقی مانده بدون مشارکت خارجی، از طریق کانال خصوصی و با هر سرعت دلخواه بین گیرنده و پرداخت کننده منتقل می شود. شرح خوبی از پروتکل مبتنی بر این طرح در شبکه Emercoin قابل خواندن است اینجا.

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

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

بازی ها، پروتکل های اقتصادی، داوری

نقش اعداد تصادفی در صنعت بازی به سختی قابل برآورد است. استفاده صریح در کازینوهای آنلاین، و استفاده ضمنی هنگام محاسبه اثرات عملکرد بازیکن، همگی مشکلات بسیار دشواری برای شبکه‌های غیرمتمرکز هستند، جایی که هیچ راهی برای تکیه بر منبع مرکزی تصادفی وجود ندارد. اما انتخاب تصادفی می تواند بسیاری از مشکلات اقتصادی را نیز حل کند و به ساخت پروتکل های ساده تر و کارآمدتر کمک کند. فرض کنید در پروتکل ما اختلافاتی در مورد پرداخت برخی از خدمات ارزان قیمت وجود دارد و این اختلافات به ندرت رخ می دهد. در این حالت، در صورت وجود PVRB غیرقابل انکار، مشتریان و فروشندگان می توانند توافق کنند که اختلافات را به صورت تصادفی، اما با احتمال معین حل کنند. به عنوان مثال، با احتمال 60٪ مشتری برنده می شود و با احتمال 40٪ فروشنده برنده می شود. این رویکرد که از دیدگاه اول پوچ است، به شما امکان می‌دهد تا به طور خودکار اختلافات را با سهمی دقیقاً قابل پیش‌بینی از برد/باخت حل کنید، که برای هر دو طرف بدون مشارکت شخص ثالث و اتلاف وقت غیرضروری مناسب است. علاوه بر این، نسبت احتمال می تواند پویا باشد و به برخی از متغیرهای جهانی بستگی دارد. به عنوان مثال، اگر شرکتی خوب کار می کند، تعداد اختلافات کم و سودآوری بالایی دارد، شرکت می تواند به طور خودکار احتمال حل یک اختلاف را به سمت مشتری محوری سوق دهد، به عنوان مثال 70/30 یا 80/20، و بالعکس. اگر اختلافات پول زیادی می گیرند و تقلبی یا ناکافی هستند، می توانید احتمال را به سمت دیگری تغییر دهید.

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

از کجا می توان تصادفی مناسب را پیدا کرد؟

در تئوری، انتخاب تصادفی منصفانه در شبکه‌های غیرمتمرکز تقریباً هر پروتکل را در برابر تبانی ایمن می‌سازد. منطق کاملاً ساده است - اگر شبکه بر روی یک بیت 0 یا 1 توافق کند و کمتر از نیمی از شرکت‌کنندگان صادق نباشند، با توجه به تکرارهای کافی، شبکه تضمین می‌شود که در مورد آن بیت با یک احتمال ثابت به اجماع برسد. صرفاً به این دلیل که یک تصادفی صادق 51 نفر از 100 شرکت کننده را در 51٪ مواقع انتخاب می کند. اما این در تئوری است، زیرا ... در شبکه‌های واقعی، برای اطمینان از چنین سطح امنیتی مانند مقالات، پیام‌های زیادی بین میزبان‌ها، رمزنگاری پیچیده چند گذری مورد نیاز است و هر گونه پیچیدگی پروتکل بلافاصله بردارهای حمله جدیدی را اضافه می‌کند.
به همین دلیل است که ما هنوز یک PVRB مقاوم اثبات شده را در بلاک چین نمی بینیم، که برای مدت زمان کافی برای آزمایش توسط برنامه های کاربردی واقعی، ممیزی های متعدد، بارگذاری ها و البته حملات واقعی مورد استفاده قرار می گرفت، که بدون آنها دشوار است که محصول واقعا ایمن

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

منبع: www.habr.com