آیا در صورت عدم اعتماد به یکدیگر امکان تولید اعداد تصادفی وجود دارد؟ قسمت 1

هی هابر!

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

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

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

1. او باید بی طرف باشد. به عبارت دیگر، هیچ شرکت کننده ای نباید به هیچ وجه بر نتیجه مولد اعداد تصادفی تأثیر بگذارد.

2. او باید غیرقابل پیش بینی باشد. به عبارت دیگر، هیچ شرکت‌کننده‌ای نباید بتواند پیش‌بینی کند که چه عددی تولید می‌شود (یا هر یک از ویژگی‌های آن را استنباط کند) قبل از تولید.

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

در این مقاله به دو رویکرد خواهیم پرداخت: RANDAO + VDF و رویکرد کدهای پاک کردن. در قسمت بعدی رویکرد مبتنی بر امضاهای آستانه را به تفصیل بررسی خواهیم کرد.

اما ابتدا، بیایید به یک الگوریتم ساده و پرکاربرد نگاه کنیم که قابل اجرا، غیرقابل پیش‌بینی، اما مغرضانه است.

RANDAO

RANDAO یک رویکرد بسیار ساده و در نتیجه بسیار رایج برای ایجاد تصادفی است. همه شرکت کنندگان شبکه ابتدا به صورت محلی یک شماره شبه تصادفی را انتخاب می کنند، سپس هر شرکت کننده یک هش از شماره انتخاب شده را ارسال می کند. در مرحله بعد، شرکت کنندگان به نوبت اعداد انتخابی خود را فاش می کنند و عملیات XOR را روی اعداد فاش شده انجام می دهند و نتیجه این عملیات به نتیجه پروتکل تبدیل می شود.

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

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

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

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

RANDAO+VDF

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

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

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

توسعه VDF های خوب بسیار دشوار است. اخیراً پیشرفت های متعددی صورت گرفته است، به عنوان مثال. این и این، که VDF را در عمل کاربردی تر کرد و اتریوم 2.0 قصد دارد از RANDAO با VDF به عنوان منبع اعداد تصادفی در دراز مدت استفاده کند. جدا از این واقعیت که این رویکرد غیرقابل پیش‌بینی و بی‌طرفانه است، در صورتی که حداقل دو شرکت‌کننده در شبکه در دسترس باشند، این مزیت را نیز دارد (با فرض اینکه پروتکل اجماع مورد استفاده در هنگام برخورد با تعداد کمی از شرکت‌کنندگان قابل اجرا باشد).

بزرگترین چالش این رویکرد راه اندازی VDF به گونه ای است که حتی شرکت کننده ای با سخت افزار تخصصی بسیار گران قیمت نمی تواند VDF را قبل از پایان مرحله کشف محاسبه کند. در حالت ایده‌آل، الگوریتم حتی باید حاشیه ایمنی قابل توجهی داشته باشد، مثلاً 10x. شکل زیر حمله بازیگری را نشان می‌دهد که دارای ASIC تخصصی است که به او اجازه می‌دهد یک VDF را سریع‌تر از زمان اختصاص داده شده برای فاش کردن تایید RANDAO اجرا کند. چنین شرکت کننده ای همچنان می تواند با استفاده از شماره خود یا عدم استفاده از آن، نتیجه نهایی را محاسبه کند و سپس بر اساس محاسبه، انتخاب کند که آن را نشان دهد یا نه.

برای خانواده VDF که در بالا ذکر شد، عملکرد یک ASIC اختصاصی می تواند 100+ برابر بیشتر از سخت افزار معمولی باشد. بنابراین اگر مرحله استقرار 10 ثانیه طول بکشد، VDF محاسبه شده در چنین ASIC باید بیش از 100 ثانیه طول بکشد تا حاشیه ایمنی 10 برابر داشته باشد، و بنابراین همان VDF محاسبه شده روی سخت افزار کالا باید 100 x 100 ثانیه = ~ 3 ساعت طول بکشد.

بنیاد اتریوم قصد دارد این مشکل را با ایجاد ASIC های رایگان و در دسترس عمومی خود حل کند. هنگامی که این اتفاق می افتد، همه پروتکل های دیگر نیز می توانند از این فناوری بهره ببرند، اما تا آن زمان، رویکرد RANDAO+VDF برای پروتکل هایی که نمی توانند روی توسعه ASIC های خود سرمایه گذاری کنند، قابل اجرا نخواهد بود.

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

ما از کدهای پاک کردن استفاده می کنیم

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

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

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

2. شرکت کنندگان از نوعی اجماع برای رسیدن به توافق بر روی مجموعه های کدگذاری شده از 67 شرکت کننده خاص استفاده می کنند.

3. پس از رسیدن به اجماع، هر شرکت کننده سهام رمزگذاری شده در هر یک از 67 مجموعه رمزگذاری شده با کلید عمومی خود را می گیرد، همه این سهام را رمزگشایی می کند و همه این سهام رمزگشایی شده را منتشر می کند.

4. هنگامی که 67 شرکت کننده مرحله (3) را کامل کردند، تمام مجموعه های توافق شده را می توان به طور کامل رمزگشایی و به دلیل ویژگی های کدهای پاکسازی بازسازی کرد، و عدد نهایی را می توان به عنوان XOR از ردیف های اولیه که شرکت کنندگان با آن در (1) شروع کردند به دست آورد. .

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

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

هنگامی که در مرحله (4) شرکت کننده 67 بیت را برای یک رشته خاص رمزگشایی می کند و سعی می کند رشته اصلی را از آنها بازسازی کند، یکی از گزینه ها ممکن است:

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

2. ردیف بازیابی می‌شود، اما ریشه محاسبه‌شده محلی با ردیفی که در آن به اجماع رسیده است مطابقت ندارد.

3. ردیف بازیابی نشده است.

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

امضاهای آستانه

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

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

یک برنامه رایج برای امضاهای BLS در پروتکل های بلاک چین، علاوه بر تولید اعداد تصادفی، امضای بلوک در پروتکل های BFT است. فرض کنید 100 شرکت کننده بلوک ایجاد می کنند و اگر 67 نفر آن را امضا کنند، یک بلوک نهایی در نظر گرفته می شود. همه آنها می توانند قسمت های خود را از امضای BLS ارسال کنند و از برخی الگوریتم های اجماع برای توافق بر روی 67 مورد از آنها استفاده کنند و سپس آنها را در یک امضای BLS ادغام کنند. هر 67 (یا بیشتر) قسمت را می توان برای ایجاد امضای نهایی استفاده کرد، که بستگی به ترکیب 67 امضا دارد و بنابراین ممکن است متفاوت باشد، اگرچه انتخاب های مختلف توسط 67 شرکت کننده، امضای متفاوتی ایجاد می کند، هر گونه امضایی معتبر خواهد بود. امضای بلوک شرکت‌کنندگان باقی‌مانده تنها به دریافت و تأیید فقط یک امضا در هر بلوک، به‌جای 67 امضا، از طریق شبکه نیاز دارند که به‌طور قابل‌توجهی بار روی شبکه را کاهش می‌دهد.

معلوم می شود که اگر کلیدهای خصوصی که شرکت کنندگان استفاده می کنند به روش خاصی تولید شوند، مهم نیست که کدام 67 امضا (یا بیشتر، اما نه کمتر) جمع آوری شود، امضای حاصل یکسان خواهد بود. این می تواند به عنوان منبع تصادفی استفاده شود: شرکت کنندگان ابتدا روی برخی از پیام هایی که امضا می کنند توافق می کنند (این می تواند خروجی RANDAO یا فقط هش آخرین بلوک باشد، تا زمانی که هر بار تغییر کند، واقعاً مهم نیست. و سازگار است) و یک امضای BLS برای آن ایجاد کنید. نتیجه تولید تا زمانی که 67 شرکت کننده قطعات خود را ارائه ندهند غیرقابل پیش بینی خواهد بود و پس از آن خروجی از قبل تعیین شده است و نمی تواند به اقدامات هیچ شرکت کننده ای وابسته باشد.

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

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

در نتیجه

این مقاله اولین مقاله از سری مقالات فنی وبلاگ است نزدیک. NEAR یک پروتکل و پلت فرم بلاک چین برای توسعه برنامه های غیرمتمرکز با تاکید بر سهولت توسعه و سهولت استفاده برای کاربران نهایی است.

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

می توانید ببینید که توسعه NEAR چگونه است و در IDE آنلاین آزمایش کنید اینجا.

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

به زودی میبینمت!

منبع: www.habr.com