Любой пользователь электронной почты сталкивается со спамом. Рекламные письма рассылаются миллионами экземпляров по всем подряд адресам в надежде, что хоть один из адресатов зайдет по указанной ссылке. И тогда вся эта многомиллионная рассылка окупится, ведь отправка одного электронного письма практически ничего не стоит.
Мусорные рассылки обычной почтой никогда не достигали таких масштабов. Потому что бумажный рекламный флайер нужно сначала напечатать, что стоит денег, а потом еще и заплатить за его доставку. Высокая себестоимость рассылки сдерживает спамеров. Вот если бы и на электронное письмо нужно было наклеивать марку… Но не существует электронного почтового ведомства, которое взимало бы плату.
А что если в качестве марки будет служить решение какой-нибудь сложной математической задачи? Пускай компьютеру для нахождения решения такой задачи понадобится одна секунда. Человек, отправляющий электронное письмо, даже не заметит этой дополнительной секунды, которую потратит его компьютер на “наклеивание марки”. Зато спамеру, чтобы разослать миллион писем, придется создать миллион марок и потратить 11,5 дней на непрерывные расчеты, не говоря уже о стоимости электроэнергии.
Решение задачи должно зависеть от содержимого письма (включая адреса отправителя и получателя) - чтобы одну и ту же марку нельзя было наклеить на разные письма. И должна быть возможность усложнять задачу при необходимости - чтобы и через много лет, когда появятся куда более мощные компьютеры, они по-прежнему тратили не меньше секунды на решение.
Но где такую задачу найти?
Представьте себе улицу большого города, по которой непрерывным потоком идут люди. И пусть ваша задача - найти человека, у которого номер паспорта четный. Среди людей, которые идут по улице, у половины четные номера паспортов, а у половины - нечетные, но у них на лице это не написано. Единственный способ найти нужного человека - это останавливать первых попавшихся людей и спрашивать, какой у них номер паспорта. Может быть, вам повезет и вы найдете нужного человека сразу. Может быть, вам сильно не повезет и придется опросить десяток человек. Но в среднем, по теории вероятностей, вам нужно будет опросить двоих. Если задача будет найти человека, номер паспорта которого заканчивается на ноль, то вам подойдет уже только один из десяти опрошенных. А если на два ноля - то один из ста. Как быстро вы справитесь с этим заданием, зависит только от того, как быстро вы умеете опрашивать людей. Несложно спрогнозировать в каждом случае, сколько времени в среднем вам понадобится, чтобы найти нужного человека.
А теперь представьте, что по улице идут не люди, а числа. И у каждого из них есть номер паспорта…
Какой у числа может быть номер паспорта? А вот какой. Возьмем число, покромсаем его хорошенько, перемешаем и пропустим через мясорубку. Полученный фарш называется хэшем (от английского to hash - рубить, измельчать, крошить). Хэш числа и будет его номером паспорта. Из хэша нельзя получить исходное число - фарш невозможно провернуть назад. Поэтому, если ваша задача - найти число, хэш которого заканчивается на ноль, у вас есть только один вариант - перебирать все числа подряд (или вразброс - не важно), спрашивать у каждого номер паспорта (то есть вычислять его хэш) и надеяться, что рано или поздно вы наткнетесь на нужное число.
Итак, наш алгоритм борьбы со спамом выглядит следующим образом. Мы берем текст письма (включая адреса отправителя и получателя) в виде одного длинного числа и прибавляем к нему еще одно небольшое (скажем, 10-значное) число, которое мы называем “маркой”. Результат пропускаем через мясорубку и получаем хэш. Наша задача - подобрать марку так, чтобы полученный хэш заканчивался на, скажем, пять нулей. Как только мы эту марку находим, мы отправляем письмо вместе с найденной маркой по электронной почте получателю.
Получатель делает то же самое: берет письмо, добавляет марку и вычисляет хэш. Если полученный хэш заканчивается на пять нулей, значит все в порядке. Если нет - письмо отправляется в мусорную корзину.
Этот алгоритм был предложен в 1997 году и получил название Hashcash. По своему прямому назначению - для защиты от спама - он использовался мало. Но десятилетие спустя, некий человек под псевдонимом Сатоши Накамото (его настоящего имени мы так и не знаем) предложил алгоритм работы системы электронных наличных денег, которые мы сейчас называем биткойнами. Система была основана на ведении бухгалтерской книги, копии которой находятся одновременно на множестве компьютеров по всему миру. Каждый из этих компьютеров (мы их будем называть участниками сети) может добавлять в бухгалтерскую книгу новые страницы, и делается это следующим образом:
- Каждый участник сети должен иметь самую свежую копию бухгалтерской книги.
- Каждый участник создает новую страницу книги и записывает на нее все транзакции, которые приходят к нему по сети.
- Одновременно с этим он пытается создать марку, чтобы наклеить ее на эту страницу. Марка зависит от всех транзакций на странице, а также от марки, наклеенной на предыдущую страницу.
- Как только кому-то из участников удалось наклеить марку, он рассылает страницу с наклеенной маркой всем остальным участникам, и эта страница становится частью бухгалтерской книги.
- Участник, наклеивший марку, может перевести себе комиссионные за все транзакции на странице. Это его награда за проделанную работу.
- Все повторяется опять с пункта 1.
- Раз в две недели сложность создания марки подстраивается таким образом, чтобы новая страница книги создавалась в среднем каждые десять минут.
Не слишком сложно, правда? Перечитайте этот пост еще раз и постарайтесь все уложить в голове. А подробности работы алгоритма мы рассмотрим в следующий раз.
