Блокчейн? Это структура данных

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

• Tехнология блокчейн в целом
• Протокол, или правила конкретного блокчейна
• Валюта, которая работает на базе этой блокчейн - если она существует.

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

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

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

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

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

Блокчейн — это тип структуры данных

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

Термин blockchain происходит от структуры, в которой хранятся ваши данные. Все данные разделяются на блоки. Каждый блок указывает, какой блок был до него, создавая "цепочку" блоков. Указание того, какой блок был предыдущим, обычно называют ссылкой.

Сравнение таблицы как структуры данных для хранения записей и блокчейна. На деле ничего сложно, что блокчейн, что таблица имеют внутренние поля (строки), однако блокчейн хранит информацию о предыдущей строке.

База данных: эффективная, но централизованная

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

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

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

Блокчейн: менее эффективный, но децентрализованный

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

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

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

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

Транзакция транслируется в сеть, и каждый участник (или узел, или пир) хранит ее копию. Узлом может управлять человек, магазин, принимающий криптовалюту, или банк; нет разницы, кто вы. Количество копий делает блокчейн медленнее, чем базу данных, но делает его более безопасным.

Наглядное сравнение, что такое централизованная система (слева, например банк) и децентрализованная система (справа), например p2p торрент-система или блокчейн, о котором ведём речь.

Откуда взялся термин "блокчейн"?

Блокчейн не хранит данные в одном огромном цифровом реестре, а разделяет их на блоки. Затем эти блоки соединяются, как отдельные страницы в книге. Так и появился термин "блокчейн". Представьте себе букмекера, который записывает записи, используя отдельные страницы книги вместо одного большого свитка. Каждые несколько минут он начинает использовать новую страницу и добавляет ссылку на последнюю страницу - "эта страница следует за страницей x". Ссылка, которую он включает, "скрепляет" страницы вместе. Он может легко упорядочить страницы, если вдруг уронит их, потому что каждая страница ссылается на свою предшественницу.

Иллюстрации наше всё. Блокчейн - он же реестр записей, он же на сленге "лэджер" в привычном смысле можно представить такую тетрадку с готовыми полями для заполнения, кто, куда, кому и по каком адресу перевёл активы (пока будем называть их активами). Справа же наглядное представление блоков и той даты (даты в смысле данные - data), которая хранит в hexadecimal системе исчисления данные, зашифрованные!

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

Теперь ясно, что блокчейн — это структура данных

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

Основные структуры данных

Массивы (Arrays)

Массив (array) — это несколько перечисляемых элементов. Этими элементами могут быть цифры, буквы, слова или даже целые файлы. Индексы позволяют обращаться к любому элементу по отдельности, поэтому если вы хотите изменить запись в массиве и знаете ее местоположение, у вас будет мгновенный доступ.

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

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

Массивы полезны своей простотой и свойством мгновенного доступа.

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

Связанные списки (Linked Lists)

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

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

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

Главное отличие списка от массива заключается в том, что в списке нет индексов и добираться до 100-ого элемента в списке придётся с самого первого. В этом смысле листы работают медленее, чем массивы. При это добавление элемента в конец списка приисходит без перевыделения памяти. Кому интересно, рекоммендуем выполнить реализацию листа через ООП на С++ или C# например.

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

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

Первый элемент связного списка называется головой, а последний - хвостом.

Графическое представление, что есть начало листа (head-голова), указатель (pointer) и последний элемент листа (tail). Английский мы используем для баланса, чтобы Вы, как читатель, могли уловить и мировую терминологию.

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

Как было сказано ранее, под массив мы выделяем последовательно байт за байтом памят в ОЗУ. Для листа, его узлы могут находиться в абсолютно разных местах памяти даже на разных "плашках".

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

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

Хеш-таблица (Hash-table)

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

Ключи сопоставляются с ячейками по их хеш-значению, например, если хеш-значение "Alice" равно 152, оно хранится в этой ячейке. Ячейки могут храниться в массиве, поскольку выходное пространство хеш-функции известно. К каждой ячейке можно мгновенно получить доступ через его индекс.

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

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

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

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

Простыми словами мы используем массив для ускорения доступа к листу из произвольных элементов. В массиве лежит указатель на ячейку памяти, где хранится сущность под значением ключа например Bob. Поэтому, 1) берём ключ, переводим его в хэш (число), идёт в ячейку массива по индексу (это быстро), достаём оттуда значение ссылки на память (это тоже быстро) и бежим по указателю в блок ОЗУ, где лежит объект, читаем объект (тоже быстро). Хэш-таблицы - это сила!

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

Выводы

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

Команда EasyHex.