Глава 3: Proof of Work

Глава 3: Proof of Work

June 17, 2019

Система лотереи, разработанная нами на данный момент, имеет две основные проблемы:

  1. Кто будет продавать лотерейные билеты и выбирать выигрышные номера, если мы уже определили, что у нас не может быть какого-либо центрального доверенного органа?

  2. Как мы можем убедиться, что победитель лотереи действительно будет записывать в реестр  валидные транзакции, а не пытаться обмануть остальных участников?

Если нам нужна не требующая разрешения система, к которой может присоединиться каждый, то мы должны отказаться от необходимости в доверии. Наша система должна обладать следующими свойствами:

  1. Каждый должен иметь возможность создать свой собственный лотерейный билет, поскольку мы не можем доверять центральному органу. Стандартные централизованные системы лотереи, такие как Powerball, управляются кем-то, кто генерирует определенное количество билетов со случайными числами на них. Поскольку мы не можем полагаться на центральную власть, мы должны разрешить всем генерировать собственные билеты.

  2. У нас должен быть какой-то способ сделать участие в лотерее платным. Таким образом мы сможем помешать кому-либо монополизировать лотерею, бесплатно генерируя огромное количество билетов. Как сделать так, чтобы вам приходилось тратить деньги на покупку билетов, когда нет никого, у кого их можно купить? Мы заставим участников покупать их у Вселенной путем сжигания дорогостоящего ресурса — электрической энергии.

  3. Всем остальным участникам должно быть несложно проверить билет победителя. В Powerball операторы лотереи генерируют выигрышную комбинацию. Поскольку нашей децентрализованной системе такой вариант не подходит, мы заставим всех заранее договориться о диапазоне выигрышных номеров. Таким образом, если ваш лотерейный номер попадает в диапазон, вы выигрываете в лотерею. Для этого мы будем использовать криптографический прием, называемый хеш-функцией.

Proof of Work: энергоемкая асимметричная головоломка #

Элегантное решение всех этих трех проблем называется Proof of Work (доказательство проделанной работы). На самом деле оно было изобретено еще до Биткоина в 1993 году. Полное объяснение того, как работает эта лотерея является, вероятно**,** самой сложной составляющей процесса понимания Биткоина. Поэтому мы посвятим следующие несколько глав подробному рассмотрению данного решения.

Для начала нужно сделать “покупку лотерейных билетов” недешевой, иначе участники смогут генерировать неограниченное количество билетов. Что может быть дорогостоящим, но не зависеть при этом от какого-либо центрального органа управления?

Именно здесь важную роль в работе Биткоина начинает играть физика: первый закон термодинамики гласит, что энергия не может быть ни создана, ни разрушена. Другими словами, нет такого понятия, как бесплатный обед, когда разговор заходит об энергии. Электричество не бывает бесплатным, потому что вы должны покупать его у производителей или иметь в распоряжении собственную электростанцию. В любом случае получение электроэнергии обходится дорого.

Концепция Proof of Work заключается в том, что вы участвуете в процессе, в котором, как и при броске игрального кубика, большая роль предоставлена случайности. Но вместо шести граней, у него примерно столько же сторон, сколько атомов во Вселенной. Чтобы бросить кубик и сгенерировать лотерейный билет с номером, ваш компьютер должен выполнить соответствующее количество операций, которые требуют затрат электричества.

Фактически, номер на билете – это сумма хешей всех транзакций, выбранных вами для записи в реестр, и количества очков, выпавших на кубике. Чтобы получить выигрышное число, вам, возможно, придется бросить кубик миллиарды, триллионы или квадриллионы раз, расходуя электричество на тысячи долларов. Поскольку основной характеристикой процесса является случайность, а все остальные параметры общеизвестны и соблюдаются благодаря действию протокола, любой может создавать свои собственные лотерейные билеты без участия центрального органа. Все, что вам понадобится — это генерирующий случайные числа компьютер и список транзакций, которые вы хотели бы записать в реестр.

Несмотря на то, что вам потребовалось потратить тысячи долларов, чтобы заполучить достаточно энергии для нахождения случайного выигрышного числа, всем остальным пользователям для подтверждения вашего выигрыша нужно выполнить лишь несколько основных проверок:

  1. Находится ли число, которое вы указали, в диапазоне целевых чисел, о котором все заранее договорились?

  2. Действительно ли это число получено путем математической обработки валидного набора транзакций?

  3. Валидны ли предлагаемые вами транзакции относительно правил протокола Биткоин: нет двойного расходования, новые биткоины не генерируются вне пределов допустимого графика и т. д.

Proof of Work — это процесс, в основе которого лежит случайность. Он требует большого количества вычислений для подбора выигрышного числа. Однако для проверки решения требуется всего одна подобная операция. Это как в кроссворде или судоку: решение может занять много времени, но любой, кто получит ответ или подсказку, может с легкостью подтвердить правильность решения. Это делает процесс Proof of Work асимметричным: он сложный для игроков, но легкий для проверяющих.

Поскольку вы потратили значительное количество энергии и, следовательно, денег, играя в эту лотерею, вы хотите, чтобы все приняли ваш выигрышный лотерейный билет. Таким образом, вы заинтересованы вести себя хорошо, записывая в реестр только валидные транзакции.

Например, если вы попытаетесь потратить деньги, которые уже были потрачены, то ваш, на первый взгляд, выигрышный лотерейный билет будет отклонен всеми остальными. Следовательно, вы потеряете все деньги, потраченные на электроэнергию, сожженную ради получения этого билета. С другой стороны, если вы записываете в реестр валидные транзакции, сеть вознаградит вас биткоинами, чтобы вы могли оплатить счета за электроэнергию и получить некоторую прибыль.

Система Proof of Work имеет важное свойство: она формирует связь электронной системы с ресурсами из реального мира. Таким образом, если вы хотите атаковать сеть, угрожая некоторым ее участникам, вам придется не только прийти к ним домой и получить контроль над их компьютером, но и оплатить их счета за электричество.

Как участники доказывают, что они сожгли эту энергию? Нам понадобится учебник для начинающих по информатике, освещающий два понятия: хеширование и биты.

Хеширование #

Асимметричная головоломка Proof of Work Биткоина включает использование хеш-функции. Из базовой алгебры мы знаем, что функция — это математическая формула, в которую вы вводите входное (input) значение x и получаете выходное (output) значение f (x). Например, функция f(x)=2x принимает любое значение и умножает его на два. Таким образом, ввод x=2 дает нам вывод f (x)=4.

Хеш-функция — это специальная функция, в которую вы вводите любую строку букв, цифр или других данных, например, “Привет, Мир”, и получаете гигантское случайное число:

11118117132582192426613293577574904584554890446643616001126584346633541502095

Конкретная хеш-функция, которую я использовал для хеширования “Привет, Мир” называется sha256. Именно ею и пользуется Биткоин.

Данные вводятся с одной стороны, гигантские непредсказуемые числа выходят с другой.

Хеш-функция sha256 имеет следующие полезные свойства:

  1. Результат детерминирован: для одного и того же ввода вы всегда будете получать один и тот же результат.

  2. Результат непредсказуем: изменение лишь одной буквы или добавление пробела в исходную строку радикально изменит результат настолько, что вы не сможете найти никакой корреляции с исходными данными.

  3. Скорость вычисления хеша для любого размера введенных данных высока.

  4. Найти два разных набора входных данных, хеширование которых приведет к одному выходу, невозможно.

  5. Имея лишь результат хеширования sha256, невозможно воспроизвести введенную строку данных. Эта функция называется односторонней.

  6. Выходные данные всегда имеют определенный размер (256 бит для sha256).

Быстрое руководство по битам #

Система исчисления, которую вы знаете и любите, состоящая из чисел от 0 до 9, называется десятичной, потому что она имеет десять цифр. Компьютеры, с другой стороны, предпочитают иную систему исчисления, состоящую только из единиц и нулей, которые указывают на наличие либо отсутствие электрического сигнала. Эта система исчисления называется двоичной или бинарной.

Десятичная система состоит из цифр от 0 до 9. Если вы будете использовать только одну цифру, вы сможете создать десять различных чисел от 0 до 9. Если вы используете две цифры, вы можете представить 10 x 10 = 100 различных чисел: 00, 01, … до 99. При использовании трех цифр  у вас может быть 10 x 10 x 10 = 1000 чисел: 000, 001, … до 999.

Надеюсь, вы уловили связь. Чтобы выяснить, сколько разных чисел мы можем представить с помощью N-количества цифр, мы умножаем десять на само себя N раз, другими словами, 10N или 10 в степени N.

Бинарный код работает так же. Единственное, что меняется, это количество доступных нам цифр. В то время как мы привыкли к десятичной системе с десятью цифрами, бинарное число или бит может иметь только два значения: ноль или один.

Если 1 бит может представлять два значения, то два бита могут представлять 4 значения: 00, 01, 10, 11. Вы можете рассчитать это, умножив 2 x 2, поскольку каждая цифра может иметь два значения.

Три бита могут представлять 2x2x2=23=8 значений: 000, 001, 010, 011, 100, 101, 110, 111.

Бинарное число длиной в N бит может представлять 2N различных значений.

Поэтому число уникальных значений, которые вы можете представить с помощью 256 бит (размер выхода хеш-функции sha256) равен 2^256. Это гигантское, почти невероятное число. Представленное с использованием десятичной системы, это число будет длиной в 78 цифр. По своему значению оно приблизительно равно предполагаемому количеству атомов в Наблюдаемой Вселенной.

2^256=115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936

Это количество возможных вариантов выходных данных при использовании хеш-функции sha256. Таким образом, фактически невозможно предсказать, как будет выглядеть число, преобразованное с помощью этой функции. Это все равно, что предсказать результат 256 бросков монеты подряд или угадать местоположение конкретного атома, который я выбрал где-то во Вселенной.

Это число слишком длинное, чтобы каждый раз записывать его полностью, поэтому далее мы просто будем представлять его как 2^256. И я надеюсь, что это заставит вас каждый раз задумываться о целой Вселенной возможностей.

Давайте обработаем некоторые строки при помощи хеш-функции #

Вот несколько примеров строк и их хеши sha256. Я показал их вывод с использованием шестнадцатеричной системы, хотя внутри компьютера они будут отображаться в виде двоичной строки из нулей и единиц.

Суть здесь в том, чтобы продемонстрировать, насколько кардинально меняется результат от незначительного изменения входной строки. Вы не можете предсказать результат, полученный с помощью хеш-функции, основываясь на входных данных:

“Привет, мир!”
9A0AF011605A6AB9022F248FB797064A42782210AC91E834348B3EF089313E5F
“Привет, мир!!”
90B12CFD373CC519013169EF6088F986FC799998598C846AB77E3CAABDB7023E

Никто, даже компьютер, не может воссоздать исходную информацию, основываясь лишь на полученном случайном числе. Если вы хотите поиграть с sha256, вы можете попробовать сделать это на сайте https://passwordsgenerator.net/sha256-hash-generator/.

Хеширование с целью выиграть лотерею Proof of Work #

Теперь мы готовы поговорить о ключевой составляющей Биткоин-магии. Мы сказали, что существует 2^256 возможных значений вывода sha256. Чтобы было легче понять, давайте представим, что всего существует 1000 возможных хешей-выводов.

Система лотереи работает так:

  1. Элис объявляет, что хочет отправить Бобу 2 доллара.
  2. Каждый, кто играет в лотерею, берет эту транзакцию “Элис дает 2 доллара Бобу”, добавляя в конце случайный параметр, называемый нонс (однократно используемое число). Это делается для того, чтобы убедиться, что строка, которую они хешируют, отличается от входных данных других игроков, помогая им найти выигрышный билет лотереи.
  3. Если подобранное число позволяет получить хеш меньше целевого числа (об этом мы поговорим в следующей главе), игроки выигрывают в лотерею.
  4. Если полученное число больше целевого числа, то они снова хешируют те же данные, добавляя другие случайные одноразовые числа: “Элис дает 2 доллара Бобу, нонс=12345”, затем “Элис дает 2 доллара Бобу, нонс=92435”, затем “Элис дает 2 доллара Бобу, нонс=132849012348092134” и т. д., пока итоговое хеш-число не окажется меньше целевого числа.

Может потребоваться очень много попыток найти хеш, который окажется меньше целевого числа. При этом, мы можем контролировать, как часто кто-то будет выигрывать в лотерею, контролируя вероятность того, что найденное число попадет в целевой интервал. Если существует 1000 возможных хешей и мы устанавливаем целевое число равное 100, то какой процент хешей находится в рамках этой цели?

Это базовая математика: нам подходят 100 из 1000 возможных чисел или 100/1000 = 10% хешей, которые меньше целевого числа. Поэтому, если вы хешируете какую-либо строку и ваша хеш-функция может выдать 1000 различных выходов, вы ожидаете получить хеш, который находится ниже целевого значения 100, примерно в 10% случаев.

Вот как работает майнинг: мы согласовываем целевое число, затем берем транзакции, о которых мы знаем и хешируем их, добавляя случайное однократно используемое число в конце. Как только хеш, меньший целевого числа, найден, мы объявляем об этом всем в сети:

Привет всем!

• Я взял транзакции: “Элис отправляет 2 доллара Бобу, Шарлотта отправляет 5 долларов Элис”.

• Я добавил однократно используемое число “32895”.

• Итоговый хеш получился равным 42, что меньше целевого числа 100.

• Вот мое доказательство выполненной работы: данные транзакции, нонс, который я подобрал, и хеш, который был создан на основе этих вводных данных.

Возможно, чтобы получить это число, мне потребовались миллиарды попыток хеширования, я сжег при этом энергии на тысячи долларов, но все остальные могут немедленно подтвердить тот факт, что я корректно выполнил эту работу.

Поскольку я дал им как входные данные (транзакции и нонс), так и ожидаемый вывод (хеш-число). Теперь они могут сразу получить итоговый хеш, используя предоставленные данные, и тем самым подтвердить, что я предоставил правильные данные.

В случае с Биткоином мы можем представить себе хеширование, как бросок гигантской игральной кости, который генерирует числа от нуля до числа, равного количеству атомов во Вселенной, используя транзакции в качестве основы для входных данных. Но чтобы выиграть в лотерею PoW-майнинга, вы должны подобрать хеш меньше целевого числа и предоставить данные, которые вы использовали для создания этого хеша.

Как это связано со сжиганием энергии? Мы уже говорили, что число всех возможных в нашем случае хешей приблизительно равно количеству атомов во Вселенной. Теперь мы можем установить целевое число на достаточно низкое значение, чтобы подходила лишь небольшая часть хешей. Это означает, что любому, кто хочет найти подходящий хеш, придется потратить на вычисления огромное количество времени и, следовательно, электричества, чтобы найти хеш-число, которое было бы меньше установленной цели.

Чем меньше цель, тем больше попыток потребуется, чтобы найти подходящее число. Чем больше цель, тем быстрее мы сможем найти выигрышный хеш. Если наши шансы поразить цель составляют миллион к 1, то факт достижения цели является доказательством выполнения приблизительно миллиона вычислений.


Connect to our relay to leave a comment. Details.
Подключитесь к нашему релею, чтобы оставить комментарий. Подробнее.