Comments 17
Постановка проблемы выглядит вполне хорошей, правда я уж понадеялся что будет решение, но итог «Именно поэтому мы пока не видим в блокчейнах доказанно стойкого PVRB» не сильно обнадёживает, хотя продолженние стоит делать.
Здесь очень много технических нюансов, и сплетается одновременно и криптография, и архитектура систем, плюс — крайне мало готового кода, гораздо чаще — proof-of-concept или вообще голая статья. Также, ограничения блокчейна все таки крайне серьезные, и все это делает задачу еще сложнее. Статью по конкретным решениям конечно хочется хорошо написать, а инфы крайне мало, и можно легко ошибиться или пропустить что то реально важное. Поэтому я так расплывчато написал когда и про что напишем. Да нам и самим надо понять, стоит ли нам раскрывать сейчас как мы хотим эту задачу решать в ближайшее время, или продолжать мониторить криптографов, пока они не разродятся еще каким нибудь решением, которое «на этот раз уже точно». За похвалу спасибо, будем стараться писать интересно
конечно стоит, может коллективный разум подскажет что полезное
ведь лучше узнать о возможных проблемах как можно раньше
А давайте вместе подумаем — здесь и сейчас.
Для того чтобы N сторонам договориться о случайном числе, есть такой алгоритм:
1) Каждый из них придумывает случайное число, считает хеш от него и говорит его
2) После этого каждый говорит свое случайное число, а все участники проверяют его с ранее сказанным хешем
3)Общее случайное число получается как сумма (например по модулю 2) всех случайных чисел.
Главное условие это выполнение алгоритма по шагам, не делать следующий шаг, если не сделан предыдущий. По сути это и есть PVRB.
Теперь про применение и возможные атаки:
Если мы хотим получить доказуемое случайное число внутри уже существующего блокчейна, например для игры в кости, то достаточно обеспечить необратимость действий на каждом шаге выбрав разумное число подтверждений блоков.
Но справедливости надо сказать — ничего нового я не написал, это все давно известно и были даже статьи на Хабре.
Главный посыл статьи, что изобретения PVRB позволит не ограничено масштабироваться сети за счет шардинга, путем по истине случайного распределения честных блок-продюсеров (которых по определению минимум 51%).
Шардинг — это одна из самых амбициозных и серьезных задач в области блокчейн, ее решение позволит строить децентрализованные сети фантастической производительности и объема. PVRB — это лишь один из важных блоков, для ее решения
У меня вопрос: если уже существует PVRB на блокчейне с протоколом POW, что мешает применять его результат для назначения блок-продюсеров в подчиненных цепочках? Т.е. схема будет такая, каждая нода валидирует главную цепочку + другую случайно назначенную великим и могущим PVRB.
ну у этой схемы (называется commit-reveal) проблемы с контролем бита. Если я на последнем шаге «говорю свое число», то перед тем как «говорить» я могу решить, стоит мне это делать или нет и тем самым контролирую результат. Прикидываю что получится и в том и в другом варианте (к примеру я играю на «красное-черное» в рулетку и выбираю тот рандом, который приводит именно к «черному»).
Я уже готовлю следующую статью, там как раз и разберу почему схема на хешах применима, но очень ограничено. Если про «вскрытие-невскрытие», то обычно это решают депозитом на этапе commit, который отнимут, если не будет reveal. Но это ограничивает цену игры и для консенсусов и других важных вещей не годится
Я уже готовлю следующую статью, там как раз и разберу почему схема на хешах применима, но очень ограничено. Если про «вскрытие-невскрытие», то обычно это решают депозитом на этапе commit, который отнимут, если не будет reveal. Но это ограничивает цену игры и для консенсусов и других важных вещей не годится
Наиболее яркий представитель таких алгоритмов: Ouroboros от команды Cardano, который, как объявлено, обладает математически доказуемой стойкостью к наличию сговора среди BP.
Он действительно обладает математически доказуемой стойкостью или это только объявлено?
Если действительно обладает стойкостью, то в чем основная идея? Мне вот интуитивно представляется что невозможно создать такой алгоритм, но я надеюсь что ошибаюсь…
имеется в виду доказуемой стойкостью равной стойкости используемого PVRB. Типа «если используемый рандом идеально стойкий, то Ouroboros доказуемо имеет ту же степень стойкости». Это частая история в криптографии — например когда используют хеширование, допускают что оно «идеально стойкое», чтобы оценивать остаток алгоритма. В случае Ouroboros более-менее понятно почему доказуемо стойкое — если «идеально рандомно» выбирать BP, то чаще будут выбираться честные BP если их тупо больше чем нечестных. Но каждый раз когда вы добавляете очередное усложнение в протокол, возможна порча этой доказуемости…
Погодите, а применяемый в Ouroboros PVRB математически строго доказан?
Имелась в виду доказуемая надежность консенсуса, а не PVRB. Это означает, что если PVRB стойкий, то консенсус доказуемо такой же стойкий, как PVRB. «Доказуемо стойкий» никогда не означает «защищен навсегда от всего», а обычно означает что «при заданных допущениях — взломать ту часть, которая доказуемо стойкая не получится». Ключевое здесь «при заданных допущениях».
Например есть «доказуемо стойкий» шифр Шеннона, который является в первую очередь моделью, для доказательства стойкости других шифров, а не реальным алгоритмом. В чистом виде он неюзабелен
Например есть «доказуемо стойкий» шифр Шеннона, который является в первую очередь моделью, для доказательства стойкости других шифров, а не реальным алгоритмом. В чистом виде он неюзабелен
Спасибо, это я понял. Поэтому спросил конкретно про PVRB. Т.е. если у них нет доказанного PVRB, то они фактически занимаются передергиванием, нет?
Тут некоторое недопонимание — в криптографии вообще нет «доказанно стойких» (кроме XOR :)). Имеется в виду доказанно стойки при некоторых условиях. В реальности эти условия не соблюдаются, либо не имеют смысла. Поэтому приходится стараться максимально приближаться к «доказанно стойким» схемам. Например, когда мы гененрируем одноразовый ключ для симметричного шифрования, мы полагаемся на то, что наш генератор — стойкий. Это, возможно не так, но анализируя алгоритм, криптографы говорят, что «он стойкий, при условии что гененратор непредсказуем, и открытый текст непредсказуем, и т.д. и т.п.» Cardano занимается как раз реализацией различных практических вариантов PVRB, выбирая наиболее надежный. Учитывая опыт их команды, желающие могут просто подождать пока они это сделают и тупо забирать хороший рандом прямо из из блокчейна. Сначала они использовали одну схему, использующую Fiat-Shamir secret sharing, сейчас вроде стали другую, не смотрел пока, но буду писать следующую статью — постараюсь описать
Смотрите, вы пишите, что PVRB решает проблему масштабируемости внутри одной цепочки, т.к.
Поэтому предлагаете использовать кванты-времени на основе PVRB
Это хорошо, но так как в статье сохранилась интрига — а есть ли вообще в природе PVRB, то у меня вопрос. Почему бы не использовать для определения так называемого “BP schedule” — алгоритм на основе PoW?
Т.е. истинная причина попытки найти PVRB — это проблема большого трафика. Когда мы составляем расписание блок-продюсеров мы по факту составляем список адресов нод, куда нужно слать новые транзакции при создании очередного блока. Таким образом радикально сокращается трафик. Почему бы нам не выбирать в качестве текущего блок-продюсера ноду, которая только что нашла максимальный PoW? Такая нода создает блок, определяет очередного победителя pow и передает ему бразды правления по созданию следующего блока…
При росте числа BP, количество необходимых сообщений в сети экспоненциально растет, поэтому, алгоритмы консенсуса, требующие финальность, используемые например в pBFT-консенсусе Hyperledger, не работают с нужной скоростью, начиная уже с нескольких десятков BP, требуя огромного числа соединений
Поэтому предлагаете использовать кванты-времени на основе PVRB
Этот принцип выделения равных квантов времени каждому BP впервые был применен в Graphene (предшественнике EOS), и позволяет большинство блоков закрывать одной подписью, что очень сильно снижает сетевую нагрузку и позволяет этому консенсусу работать крайне быстро и устойчиво.
Это хорошо, но так как в статье сохранилась интрига — а есть ли вообще в природе PVRB, то у меня вопрос. Почему бы не использовать для определения так называемого “BP schedule” — алгоритм на основе PoW?
Т.е. истинная причина попытки найти PVRB — это проблема большого трафика. Когда мы составляем расписание блок-продюсеров мы по факту составляем список адресов нод, куда нужно слать новые транзакции при создании очередного блока. Таким образом радикально сокращается трафик. Почему бы нам не выбирать в качестве текущего блок-продюсера ноду, которая только что нашла максимальный PoW? Такая нода создает блок, определяет очередного победителя pow и передает ему бразды правления по созданию следующего блока…
действительно, PoW — один из способов реализации PVRB — если затраты на подбор хеша огромны, то «перемайнивать» блок, ради нового значения рандома будет слишком дорого. Но все равно, если на кону возможность с гарантированной вероятностью больше 50% удваивать ставку, просто удвоив майнинговые мощности (выбирая между хотя-бы двумя рандомами), такой PVRB можно атаковать. Поэтому в таких PVRB все равно приходится делать протокол коллективной генерации — все должны потрудиться, отдать свои PoW хеши (или использовать иную Verifiable Delay Function), и из них сконструировать результат. Причем важно, что результат должен быть unbiasable — один и только один, вне зависисмости от действий сговорившейся группы участников.
что касается причины попыток найти PVRB, то как я сказал, PVRB в блокчейнах — то же самое что генераторы псеводслучайных последовательностей для симметричной криптографии на отдельных компьютерах. Эти генераторы — техническая основа огромного числа протоколов, поточных шифров, протоколов расширения ключа, даже хеширования.
И в блокчейнах происходит развитие этих концепций, по сути блокчейн-технологии — это про создание распределенных компьютеров, в которых недоверенные узлы объединяются для решения одной задачи. Поэтому merkle tree в них — аналог хеширования, PVRB — аналог ГПСП, транзакции — вызовы функций, и т.п. К сожалению, нюансов и атак очень много, поэтому нельзя взять и быстро на коленке запилить что угодно на блокчейне.
И в блокчейнах происходит развитие этих концепций, по сути блокчейн-технологии — это про создание распределенных компьютеров, в которых недоверенные узлы объединяются для решения одной задачи. Поэтому merkle tree в них — аналог хеширования, PVRB — аналог ГПСП, транзакции — вызовы функций, и т.п. К сожалению, нюансов и атак очень много, поэтому нельзя взять и быстро на коленке запилить что угодно на блокчейне.
Кажется, что наиболее важное применение для PVRB, это различные игры, лотереи, и вообще любые виду gambling-а на блокчейне
Любые виды
ну можно сравнить атаку на PVRB в каком нибудь онлайн казино, и атаку на PVRB, работающего в алгоритме консенсуса какого нибудь блокчейна типа EOS. Вторая позволяет сделать double spend и потенциально организовать кидок на десятки миллионов (в зависимости от тоо, сколько в атаку может вложить атакующий). В первом случае — придется обманывать казино, а оно обычно ограничивает размеры ставок, да и с KYC может прижучить. Поэтому игры — это важно, и, наверное, какая нибудь огромная лотерея и может являться вкусной целью, но у блокчейна к PVRB есть и более серьезные запросы. Кстати про арбираж сделок и RandPay там тоже неспроста — эти задачи важны также и с инженерной точки зрения — чтобы поддержать масштабирование блокчейнов и убрать ненужные взаимодействия.
Sign up to leave a comment.
Случайные числа и децентрализованные сети: практическое применение