Хэширование

Бердинских Марина, Елизарова Елена_МПМ-16

Blockchain

Хэширование — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения». Например, мы можем подать на вход 128-битной хеш-функции роман Льва Толстого в шестнадцатиричном виде и число 1. В результате на выходе мы в обоих случаях получим набор псевдослучайных шестнадцатиричных цифр вида: "c4ca4238a0b923820dcc509a6f75849b". При изменении исходного текста даже на один знак, полностью меняется результат хеш-функции.

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

Хэш-функции – это функции, предназначенные для «сжатия» произвольного сообщения или набора данных, записанных, как правило, в двоичном алфавите, в некоторую битовую комбинацию фиксированной длины, называемую сверткой. Хэш-функции имеют разнообразные применения при проведении статистических экспериментов, при тестировании логических устройств, при построении алгоритмов быстрого поиска и проверки целостности записей в базах данных. Основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента.

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

Для того, чтобы хеш-функция H считалась криптографически стойкой, она должна удовлетворять трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии:

• Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m не должен быть вычислен блок данных Х, для которого H(X)=m
• Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого 
• Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений имеющих одинаковый хеш.

Почему нужна blockchain?

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

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

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

Blockchain как раз и решает все эти проблемы.

Слайд 1

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

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

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

Что такое blockchain?

Blockchain – это технология надежного  распределенного хранения достоверных записей в цепочку блоков или другими словами связный список. В таком списке каждая следующая запись ссылается на одну предыдущую и так по цепочке до самой первой. Например, в blockchain можно хранить записи о денежных переводах. И в криптовалютах blockchain как раз используется для фиксирования информации о том, кто, кому и сколько виртуальных денег перевел. Но в blockchain можно хранить и данные о выданных кредитах, правах на собственность, нарушении правил дорожного движения, бракосочетаниях. В общем, все, что можно записать на бумаге, можно записать и в blockchain с одним лишь отличием – в blockchain просто нереально подменить или подделать записи.

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

 

 

Разберем на примере.

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

Теперь Олег всегда может подойти к доске и убедиться, что Макс всё вернул, а вот Ваня не отдает уже 700 рублей. Однажды Олег приглашает Ваню выпить к себе домой. Пока Олег отходит в другую комнату, Ваня стирает запись «Занял Ване 200 рублей» и вписывает вместо неё «Ваня отдал 500 рублей».

Доверявший своему списку Олег забывает про долг и теряет 700 рублей. Он решает как-то с этим бороться.

В прошлом году Олег ходил на курсы по программированию, где ему рассказали про хеширование. Он помнит, что любую строку можно превратить в однозначный набор символов (буквы и цифры) — хеш, и изменение любого символа строки полностью изменит его.

Добавление точки в конце изменит итоговый хеш до неузнаваемости — этим можно воспользоваться.

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

Но ИВАН тоже умеет в SHA-256 и легко может изменить запись вместе с её хешем. Особенно, если хеш написан прямо рядом на доске.

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

Но однажды Иван прокрадывается ночью, изменяет нужную ему запись и обновляет хеши для всего списка до конца. У него это занимает несколько часов, но Олег всё равно крепко спит и не слышит. На утро Олег обнаруживает абсолютно верный список — все хеши совпадают. Но Иван всё равно его обманул, хоть и потратил на это бессонную ночь. Как еще можно защититься от Ночного Ивана?

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

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

Зато проверить список всё так же просто: сначала нужно как раньше сравнить хеши, а потом проверить решения уравнений простой подстановкой. Если всё сходится — список не изменен.

В реальности же с уравнениями не всё так хорошо: компьютеры слишком хорошо их решают, да и где хранить столько уникальных уравнений. Потому авторы блокчейна придумали более красивую задачу: нужно найти такое число (nonce), чтобы итоговый хеш всей записи начинался на 10 нулей. Такой nonce сложно найти, зато результат всегда можно проверить просто глазами.

Теперь Олег сверяет все хеши и дополнительно убеждаются, чтобы каждый начинался на оговоренное количество нулей. Хитрый Иван, даже вооружившись мощным ноутбуком, не успеет за ночь пересчитать все хеши так, чтобы они удовлетворяли условию — не хватит времени.

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

ЦЕНТРАЛИЗАЦИЯ ДОВЕРИЯ

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

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

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

Децентрализация: никто не доверяет никому

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

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

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

Транзакции

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

Наши записи типа «Занял Ване 500 рублей» — тоже транзакции. Но у нас нет банка, авторизующего автора транзакций. Как нам проверить, что Иван втихую не добавил запись «Макс должен Олегу 1000 рублей»?

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

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

Этим достигается открытость и безопасность сети. Если раньше за это отвечали банки, то в блокчейне за это отвечает математика.

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

Отсутствие понятия «баланса»

Блокчейн по сути состоит только из истории транзакций. Он не хранит баланс каждого кошелька, иначе бы нам пришлось изобретать дополнительные способы защиты. 
 
Владение кошельком подтверждает только приватный ключ. Но как другие участники сети убедятся, что у меня есть достаточно денег для покупки? 
Раз у нас нет баланса — это должны доказывать вы. Потому в транзакцию блокчейна входит не только ваша подпись и сколько вы хотите потратить, но и ссылки на предыдущие транзакции, в которых вы получили нужное количество денег. То есть если вы хотите потратить 400 рублей вы пробегаете по всей своей истории доходов и расходов, и прикрепляете к своей транзакции те доходы, где вам дали 100 + 250 + 50 рублей, тем самым доказывая, что у вас есть эти 400 рублей. 

Каждый участник сети еще раз обязательно проверит, что вы не прикрепляли доходы дважды. Что те 300 рублей, что дал Макс на прошлой неделе, вы действительно еще не потратили. 
Такие прикрепленные к транзакции доходы в блокчейне называются инпутами (input), а все получатели денег — аутпутами (output). Сумма всех инпутов редко бывает ровно такой, сколько вы хотите перевести за раз — потому один из аутпутов чаще всего будете вы сами. Другими словами транзакция в блокчейне выглядит как «мне дали 3 и 2 BTC, я хочу из них перевести 4 BTC и оставшийся 1 BTC вернуть себе обратно».