If you're seeing this message, it means we're having trouble loading external resources on our website.

Если вы используете веб-фильтр, пожалуйста, убедитесь, что домены *.kastatic.org и *.kasandbox.org разблокированы.

Основное содержание
Текущее время:0:00Общая продолжительность:10:32

Транскрипция к видео

тельства произведенных вычислений это способ позволяющий проверить что нужно и вычисления были действительно проделаны часто этот протокол сводится к задаче эту задачу должно быть возможно решить но потребуются многоэтапные вычисления упростить вычисления нельзя с другой стороны результат должен проверяться легко и за меньшее время чем требуется на решение данный метод применяется к примеру в платежной системе bitcoin и данный протокол применяется при формировании цепочки блоков помимо биткоина где про так со сравнительно недавно существуют и другие области применения например принцип подтверждения выполнения вычислений используется для защиты от dos-атак экд посылающий запрос должен решить некую задачу после чего он получает ответ на свой запрос или некую услугу на выпал требуется определенное время качающие на запрос сторона может легко проверить выполнил ли инициатор запроса поставленную задачу если до его запрос выполняется но изначально этот принцип доказательство проделанных вычислений насколько я знаю был предложен для защиты от спама надеюсь все знают что такое спам это электронные письма которые вам абсолютно не нужны в данном случае этот протокол может быть привязан к сообщению то есть он работает как почтовая марка но вы платите деньгами как за марку а вычислительной мощностью процессора если кто-то посылает небольшое количество сообщений такая защита не слишком загрузит его компьютер будет незначительная задержка число сообщений невелико некоторые затруднения в работе возникают но весьма незначительные а вот для спамера который рассылает много сообщений сотни тысяч а может и миллионы цена окажется чересчур высокой на решение задач для всех сообщений уйдет слишком много времени надеюсь мне удалось дать представление о сферах применения принципа протокола давайте посмотрим как это работает на практике точно в качестве доказательства проделанных вычислений нужно подобрать ответ на некий запрос обозначим его буквой з з это запрос это решить задачу получить подтверждение выполнении вычислений должен предъявить ответ подходящие к запросу правильное решение и задача определенным образом математически связаны если говорить о спаме то запрос может представлять собой электронное сообщение то есть задача должна быть непосредственно связана с областью применения к нам нужно ввести ответ подтверждение обозначим его как о нет лучше вас буквой p не или ответ смысл в том что и предъявлении подтверждения если соединить запрос и ответ и применить к их сочетанию криптографическую хэш-функцию такой например как sha-256 или нечто подобное итак я беру запросы подтверждения соединяю и применяю хэш-функцию которая представляет собой математическое преобразование и мне нужно предъявить такое подтверждение чтобы на выходе получился очень специфический код первые биты выходных данных должны представлять собой 0 скажем первые 40 или первые 30 битов должны быть нулевыми а остальные биты будут представлять собой оригинальное сообщение ясно что нужно подобрать такой ответ чтобы он вместе с запросом после применения хэш-функции давал именно такие выходные данные которые должны получиться после соединения запроса и ответа если применяется хорошие это единственный способ подобрать ответ это перебрать множество вероятностей то есть применить грубую силу просто подставлять ответы до тех пор пока не найдется правильной если на выходе должно быть 40 нулевых битов то вам потребуется 2 в сороковой степени попытки 2 в степени 40 запуска хэш-функции нужно будет подставить 2 в сороковой степени варианта ответа и один из них должен сработать два в сороковой степени это приблизительно 1 триллион то есть есть триллион вариантов и каждый надо хэшировать вероятно тогда вы подберете ответ дающие 40 нулевых битов иногда нужно меньше чем триллион попыток а иногда немного больше вам может повезти или наоборот не повезти одним нужно около триллиона попыток чтобы подобрать подходящий ответ в общем это не просто но в пределах возможного почему сложно найти более эффективную схему чем простой подбор вариантов надеюсь вы помните что хэш-код выглядит более-менее бессвязно которой степени он напоминает результат подбрасывания монет то вы подкидывали монеты и если выпадал орел вы получали 0 а если решка то 1 то есть вы как будто пытаетесь посчитать сколько раз нужно подбросить сорок монет чтобы 40 раз подряд выпал орел ясно что вероятность этого события невелика но это в пределах возможного если сорок монет подбрасывать около триллиона раз то рано или поздно они все упадут орлом вверх кстати подобные алгоритмы что упрощать и усложнять скажем вы хотите чтобы для решения еще потребовалось еще больше вычислений вам нужно увеличить объем работы по перебору вариантов для этого можно просто увеличить количество нулевых битов вначале каждый дополнительный 0 требует вдвое больше вычислительных ресурсов компьютера то есть увеличение количества монет выпадающих орлом всего на одну приведет к удвоению числа попыток если нужно подбросить 40 одну монету чтобы 41 раз выпал орел то потребуется в два раза больше попыток чем с 40 монетами точно так же если число нулевых битов уменьшается на 1 это в 2 раза сокращает объем вычислений необходимых для решения например если требуется чтобы орел выпал только тридцать девять раз то количество подбрасывания монет сократиться вдвое по сравнению с ситуации когда нужно 40 нулей интересно что после того как решение было найдено скажем кто-то сделал триллион попыток и ввёл подтверждение которые работают это решение очень легко проверить все что для этого требуется это соединить запрос и ответ и хэшировать их скажем если кто-то предлагает такое решение назовём его p штрих все что нужно для проверки это взять задачу и решение и хэшировать их и выяснится совпадает ли число нулевых битов в общем все что требуется это применить хэш-функцию к сочетанию цып штрих и убедиться что выходные данные действительно содержат нужное число нулевых битов если обнаружится что нулей столько сколько нужно то можно посчитать что работа была проделана потому что ясно что на получение ответа b-штрих которые в сочетании с задачей после применения хэш-функции дает нужное число нулей потребовалось очень много времени точнее много попыток подобные схемы довольно просты и в то же время эффективны они сводятся к тому что нужно найти ответ определенным образом математически связаны с запросом надеюсь в этом видео мне удалось дать представление о принципе протокола доказательства произведенных вычислений