Биткоин. Доказательство выполнения работы

Доказательство произведенных вычислений — это способ, позволяющий проверить, что нужные вычисления были действительно проделаны. Часто этот протокол сводится к задаче. Эту задачу должно быть возможно решить, но потребуются многоэтапные вычисления. Упростить вычисления нельзя. С другой стороны, результат должен проверяться легко и за меньшее время, чем требуется на решение. Данный метод применяется, к примеру, в платежной системе Биткоин. В этой системе данный протокол применяется при формировании цепочки блоков. Помимо Биткоина, где протокол начал применяться сравнительно недавно, существуют и другие области применения. Например, принцип подтверждения выполнения вычислений используется для защиты от DoS атак. Смысл в том, что субъект, посылающий запрос, должен решить некую задачу, после чего он получает ответ на свой запрос или некую услугу. На выполнение задачи требуется определенное время. А отвечающая на запрос сторона может легко проверить, выполнил ли инициатор запроса поставленную задачу. Если да, его запрос выполняется. Но изначально этот принцип — доказательство проделанных вычислений — насколько я знаю, был предложен для защиты от спама. Надеюсь, все знают, что такое спам. Это электронные письма, которые вам абсолютно не нужны. В данном случае, этот протокол может быть привязан к сообщению. То есть, он работает как почтовая марка. Но вы платите не деньгами, как за марку, а вычислительной мощностью процессора. Если кто-то посылает небольшое количество сообщений, такая защита не слишком загрузит его компьютер. Это будет незначительная задержка, потому что число сообщений невелико. Некоторые затруднения в работе возникают, но весьма незначительные. А вот для спамера, который рассылает много сообщений, сотни тысяч, а может и миллионы, цена окажется чересчур высокой. На решение задач для всех сообщений уйдет слишком много времени. Надеюсь, мне удалось дать представление о сферах применения принципа протокола. Давайте посмотрим, как это работает на практике. Обычно, в качестве доказательства проделанных вычислений нужно подобрать ответ на некий запрос. Обозначим его буквой З. З — это запрос. И тот, кто пытается решить задачу, получить подтверждение выполнения вычислений, должен предъявить ответ, подходящий к запросу. Правильное решение и задача определенным образом математически связаны. Если говорить о спаме, то запрос может представлять собой электронное сообщение. То есть, задача должна быть непосредственно связана с областью применения. Итак, нам нужно ввести ответ, подтверждение, обозначим его как О. Нет, лучше обозначить буковой П. Это подтверждение или ответ. Смысл в том, что при предъявлении подтверждения, если соединить запрос и ответ, и применить к их сочетанию криптографическую хэш-функцию… Такую, например, как SHA-256 или нечто подобное. Итак, я беру запрос и подтверждение, соединяю и применяю хэш-функцию, которая представляет собой математическое преобразование. И мне нужно предъявить такое подтверждение, чтобы на выходе получился очень специфический код. Первые биты выходных данных должны представлять собой ноль. Скажем, первые 40 или первые 30 битов должны быть нулевыми. А остальные биты будут представлять собой оригинальное сообщение. Ясно, что нужно подобрать такой ответ, чтобы он вместе с запросом после применения хэш-функции давал именно такие выходные данные, которые должны получиться после соединения запроса и ответа. Если применяется хорошая хэш-функция, то единственный способ подобрать ответ — это перебрать множество вероятностей. То есть, применить грубую силу — просто подставлять ответы до тех пор, пока не найдется правильный. Например, если на выходе должно быть 40 нулевых битов, то вам потребуется 2 в 40-й степени попытки. 2 в степени 40 запуска хэш-функции. Нужно будет подставить 2 в 40-й степени варианта ответа и один из них должен сработать. 2 в 40-й степени — это приблизительно 1 триллион. То есть, есть триллион вариантов и каждый надо хэшировать. Вероятно, тогда вы подберете ответ, дающий 40 нулевых битов. Иногда нужно меньше, чем триллион попыток. А иногда — немного больше. Вам может повезти. Или наоборот — не повезти. Но в среднем, нужно около триллиона попыток, чтобы подобрать подходящий ответ. В общем, это непросто. Но в пределах возможного. Попробуем разобраться, почему сложно найти более эффективную схему, чем простой подбор вариантов. Надеюсь, вы помните, что хэш-код выглядит более-менее бессвязно. В некоторой степени, он напоминает результат подбрасывания монет. Как будто вы подкидывали монеты и, если выпадал орел, вы получали 0, а если решка — то 1. То есть, вы как будто пытаетесь посчитать, сколько раз нужно подбросить 40 монет, чтобы 40 раз подряд выпал орел. Ясно, что вероятность этого события невелика. Но это в пределах возможного. Если 40 монет подбрасывать около триллиона раз, то рано или поздно они все упадут орлом вверх. Кстати, подобные алгоритмы можно упрощать и усложнять. Скажем, вы хотите, чтобы для решения задачи потребовалось еще больше вычислений. Вам нужно увеличить объем работы по перебору вариантов. Для этого можно просто увеличить количество нулевых битов в начале. Каждый дополнительный 0 требует вдвое больше вычислительных ресурсов компьютера. То есть, увеличение количества монет, выпадающих орлом, всего на одну приведет к удвоению числа попыток. Если нужно подбросить 41 монету, чтобы 41 раз выпал орел, то потребуется в два раза больше попыток, чем с 40 монетами. Точно также, если число нулевых битов уменьшается на один, это в два раза сокращает объем вычислений, необходимых для решения. Например, если требуется, чтобы орел выпал только 39 раз, то количество подбрасывания монет сократиться вдвое, по сравнению с ситуацией, когда нужно 40 нулей. Интересно, что после того, как решение было найдено, скажем, кто-то сделал триллион попыток и ввел подтверждение, которое работает. Это решение очень легко проверить. Все, что для этого требуется — это соединить запрос и ответ и хэшировать их. Скажем, если кто-то предлагает такое решение, назовем его «П штрих», все, что нужно для проверки — это взять задачу и решение и хэшировать их. И выяснится, совпадает ли число нулевых битов. В общем, все, что требуется — это применить хэш-функцию к сочетанию «З» и «П штрих», и убедиться, что выходные данные действительно содержат нужное число нулевых битов. И если обнаружится, что нулей столько, сколько нужно, то можно посчитать, что работа была проделана, потому что ясно, что на получение ответа «П штрих», который, в сочетании с задачей, после применения хэш-функции дает нужное число нулей, потребовалось очень много времени, точнее — много попыток. Как вы могли убедиться, подобные схемы довольно просты, и, в то же время, эффективны. Они сводятся к тому, что нужно найти ответ, определенным образом математически связанный с запросом. Надеюсь, в этом видео мне удалось дать представление о принципе протокола доказательства произведенных вычислений. Subtitles by the Amara.org community