2022 [11] Blockchain
Существует система хранения документов, построенная на основе связного списка блоков (блокчейн). Блоки состоят из транзакций и информации о предыдущем блоке цепочки. Структура блока описана в формате JSON и содержит следующую информацию:
– номер блока (_id),
– дата создания блока в формате “YYYY-MM-DD” (date),
– список транзакций, входящих в состав блока (storage),
– хеш-значение предыдущего блока (hash_prev),
– контрольная строка (nonce).
Для добавления блока в связный список необходимо вычислить значение контрольной строки (NONCE) такое, чтобы хеш-функция этого блока возвращала строку, начинающуюся с символов ‘00’. Хеш-функция блока вычисляется на основе значения хеш функции предыдущего блока, значения хеш-функции от списка идентификаторов транзакций блока и значения контрольной строки NONCE (см. листинги 1, 2 на языке C++).
Листинг 1 – Функция получения хеш-строки по массиву идентификаторов транзакций на языке программирования C++
// алфавит хеш-строки
const std::string ALPHABET = "0123456789@<=>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// получение символа из алфавита хеш-строки по его индексу (по модулю длины алфавита)
char getHashChar(unsigned long long index) {
return ALPHABET[index % ALPHABET.length()];
}
// Получение хеш-строки по массиву из ID транзакций
// STORAGE - массив (вектор) чисел-идентификаторов транзакций
// SIZE - длина получаемой хеш-строки
// RETURN
// вычисленную хеш-строку длины SIZE
std::string StorageHash(std::vector<int> storage, int size) {
// строка - результат (резервируем необходимое количество символов)
std::string res(size, 0);
// необходимые константы
unsigned long long intHash;
unsigned long long sum = 42;
unsigned long long mul = 37;
// основной цикл
for (int i = 0; i < size; i += 2) {
// вычисление суммы с предыдущим вычисленным значением hash
intHash = sum + i + (i > 0 ? res[i - 1] : 0);
// нормирование - получение символа хеш-строки
res[i] = getHashChar(intHash);
// вычисление произведения на основе суммы
intHash = (mul + i) * intHash;
// нормирование - получение символа хеш-строки
res[i + 1] = getHashChar(intHash);
}
// замешивание идентификаторов транзакций
for (int i = 0; i < storage.size(); i++) {
// сложение
intHash = res[i % size] + storage[i];
// нормирование - получение символа хеш-строки
res[i % size] = getHashChar(intHash);
// умножение
intHash = res[(i + 1) % size] * storage[i];
// нормирование - получение символа хеш-строки
res[(i + 1) % size] = getHashChar(intHash);
}
// возвращение результата
return res;
}
Листинг 2 – Функция получения хеш-строки по блоку в цепочке блокчейн на языке программирования C++
// алфавит хеш-строки
const std::string ALPHABET = "0123456789@<=>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// получение символа из алфавита хеш-строки по его индексу (по модулю длины алфавита)
char getHashChar(unsigned long long index) {
return ALPHABET[index % ALPHABET.length()];
}
// Получение хеш-строки на блок
// PREVHASH - хеш-строка предыдущего блока блокчейна
// STORAGEHASH - хеш-строка по массиву ID транзакций текущего блока
// NONCE - контрольная строка
// SIZE - длина получаемой хеш-строки
// RETURN
// вычисленную хеш-строку
std::string BlockHash(std::string prevHash, std::string storageHash, std::string nonce, int size) {
// строка - результат (резервируем необходимое количество символов)
std::string res(size, 0);
// необходимые константы
unsigned long long intHash;
unsigned long long hash = 2139062143;
unsigned long long sum = 42;
unsigned long long mul = 37;
// склеивание prevHash и storageHash
for (int i = 0; i < size; i += 2) {
res[i] = unsigned char(prevHash[i] + storageHash[i]);
res[i + 1] = unsigned char(prevHash[i + 1] * storageHash[i + 1]);
}
// основной цикл - склеивание с NONCE
for (int i = 0; i < size; i += 2) {
// сложение с очередным символом NONCE
intHash = sum + i + res[i] + nonce[i];
// нормирование - получение символа хеш-строки
res[i] = getHashChar(intHash);
// сложение и умножение с другим символом NONCE
intHash = (mul + i + 1) * hash + res[i + 1] + nonce[size/2 + i/2];
// нормирование - получение символа хеш-строки
res[i + 1] = getHashChar(intHash);
}
// возвращение результата
return res;
}
Один сотрудник решил добавить только что созданный документ (транзакция с идентификатором ID=33) в блок, сформированный в предыдущем месяце. Укажите, в какой блок необходимо добавить транзакцию и какое новое значение контрольной строки NONCE в этом блоке нужно задать, чтобы значение хеш-функции блока не изменилось, и модификация блока не была обнаружена в блокчейне?
К задаче прилагается:
Показать подсказку
Как зависит контрольная сумма блока от номеров транзакций, входящих в его состав?
Показать решение
Значение хеш-функции блока вычисляется на основе трех значений: хеш-значение предыдущего блока, хеш-значение транзакций блока и значение строки NONCE. Хеш-значение предыдущего блока поменять нельзя. Значение NONCE состоит из 14-ти символов, каждый из которых берется из алфавита, состоящем из 66-ти символов. Таким образом полный перебор значения нецелесообразен. Необходимо детально разобраться как формируется хеш-значение транзакций блока.
Рассмотрим тело функции StorageHash() и разобьем его на части :
std::string StorageHash(std::vector storage, int size) {
// ЧАСТЬ 1
std::string res(size, 0);
unsigned long long intHash;
unsigned long long sum = 42;
unsigned long long mul = 37;
// ЧАСТЬ 2
for (int i = 0; i < size; i += 2) {
intHash = sum + i + (i > 0 ? res[i - 1] : 0);
res[i] = getHashChar(intHash);
intHash = (mul + i) * intHash;
res[i + 1] = getHashChar(intHash);
}
// ЧАСТЬ 3 - замешивание идентификаторов транзакций
for (int i = 0; i < storage.size(); i++) {
intHash = res[i % size] + storage[i];
res[i % size] = getHashChar(intHash);
intHash = res[(i + 1) % size] * storage[i];
res[(i + 1) % size] = getHashChar(intHash);
}
// возвращение результата
return res;
}
Часть 1 тела функции содержит объявления переменных и константы. Эта часть всегда одинаковая для всех блоков.
Часть 2 содержит цикл, заполняющий строку-результат res. В этом цикле используются только константы, поэтому в результате выполнения этого цикла всегда будет одно и то же значение для любых блоков.
Часть 3 содержит цикл, в котором в значение строки-результата res из части 2 подмешиваются идентификаторы транзакций блока. Эта часть зависит от содержания блока и для каждого блока будет вычислено свое значение. Более того, при изменении транзакций блока именно в этой части функции проявятся изменения хеш-значения блока. В этой части осуществляется сложение и умножение символов строки res на идентификаторы транзакций, входящих в состав блока.
Рассмотрим цикл части 3 подробнее:
1 | for (int i = 0; i < storage.size(); i++) {
2 | intHash = res[i % size] + storage[i];
3 | res[i % size] = getHashChar(intHash);
4 | intHash = res[(i + 1) % size] * storage[i];
5 | res[(i + 1) % size] = getHashChar(intHash);
6 | }
Исходя из числа транзакций в блоке (storage.size()) будут заполнены соответствующие символы строки res. При этом, первый идентификатор транзакции из блока (storage[0]) повлияет на значение первого символа строки-результата (res[0]) и второго символа строки-результата (res[1]) (строки 3 и 5 листинга).
Второй идентификатор транзакции из блока (storage[1]) повлияет на значение второго (res[1]) и третьего символа строки-результата (res[2]). И так далее. Всего в строке-результате 14 символов.
Таким образом, при добавлении новой транзакции в блок необходимо понять, какие символы строки-результата изменятся. В файле с информацией о блоках в каждом блоке содержится по 5 транзакций. При добавлении 6-й транзакции изменятся только символы res[5] и res[6] строки-результата.
Теперь рассмотрим тело функции BlockHash() и разобьем его на части.
std::string BlockHash(std::string prevHash, std::string storageHash, std::string nonce, int size) {
// ЧАСТЬ 1
std::string res(size, 0);
unsigned long long intHash;
unsigned long long hash = 2139062143;
unsigned long long sum = 42;
unsigned long long mul = 37;
// ЧАСТЬ 2 - склеивание prevHash и storageHash
for (int i = 0; i < size; i += 2) {
res[i] = unsigned char(prevHash[i] + storageHash[i]);
res[i + 1] = unsigned char(prevHash[i + 1] * storageHash[i + 1]);
}
// ЧАСТЬ 3 - склеивание с NONCE
for (int i = 0; i < size; i += 2) {
intHash = sum + i + res[i] + nonce[i];
res[i] = getHashChar(intHash);
intHash = (mul + i + 1) * hash + res[i + 1] + nonce[size/2 + i/2];
res[i + 1] = getHashChar(intHash);
}
// возвращение результата
return res;
}
В качестве параметров функции BlockHash() передаются хеш-значение предыдущего блока (prevHash), хеш-строка (storageHash), вычисленная функцией StorageHash() и некоторая строка NONCE. Размер всех строк одинаковый и равен 14 символам.
Часть 1 тела функции содержит объявления переменных и константы. Эта часть всегда одинаковая для всех блоков.
Часть 2 содержит цикл, заполняющий строку-результат res на основе значений prevHash и storageHash.
Рассмотрим цикл из части 2 подробнее.
1 | for (int i = 0; i < size; i += 2) {
2 | res[i] = unsigned char(prevHash[i] + storageHash[i]);
3 | res[i + 1] = unsigned char(prevHash[i + 1] * storageHash[i + 1]);
4 | }
Первый символ строки-результата (res[0]) формируется на основе значений первых символов строк (prevHash[0]+storageHash[0]) (строка 2 листинга).
Второй символ строки-результата формируется на основе значений вторых символов строк (prevHash[1]*storageHash[1]) (строка 3 листинга). И так далее. Длины всех строк одинаковые, поэтому тут зацикливаний не будет.
Можно сделать вывод, что i-е символы строки-результата зависят только от i-х символов строк prevHash и storageHash.
Таким образом, при добавлении 6-й транзакции в блок, в строке storageHash изменятся символы storageHash[5] и storageHash[6], а значит и изменятся только символы res[5] и res[6] строки-результата. Остальные символы останутся прежними.
Рассмотрим цикл и части 3, в котором осуществляется формирование итогового хеш-значения блока на основании строки-результата из части 2 и строки NONCE:
1 | for (int i = 0; i < size; i += 2) {
2 | intHash = sum + i + res[i] + nonce[i];
3 | res[i] = getHashChar(intHash);
4 | intHash = (mul + i + 1) * hash + res[i + 1] + nonce[size/2 + i/2];
5 | res[i + 1] = getHashChar(intHash);
6 | }
К первому символу строки-результата (res[0]) добавляется первый символ строки NONCE (nonce[0]) (строки 2-3 листинга).
Ко второму символу строки-результата (res[1]) подмешивается символ с середины строки NONCE (nonce[7]) (строки 4-5 листинга).
К третьему символу строки-результата (res[2]) добавляется третий символ строки NONCE (nonce[2]).
К четвертому символу строки-результата (res[3]) подмешивается очередной символ после середины строки NONCE (nonce[8]).
И так далее:
res[4] – зависит от nonce[4], res[5] – зависит от nonce[9],
res[6] – зависит от nonce[6], res[7] – зависит от nonce[10],
res[8] – зависит от nonce[8], res[9] – зависит от nonce[11],
res[10] – зависит от nonce[10], res[11] – зависит от nonce[12],
res[12] – зависит от nonce[12], res[13] – зависит от nonce[13].
Таким образом, если в строке res в цикле из части 2 изменились символы res[5] и res[6], то для того, чтобы итоговое хеш-значение строки не изменилось необходимо поменять соответствующие символы строки NONCE: nonce[9] и nonce[6].
Можно написать цикл, который перебирает все символы алфавита в значении строки NONCE на месте символов nonce[9] и nonce[6] так, что итоговое хеш-значение блока не изменится при добавлении к нему новой транзакции.
В условии сказано, что транзакцию необходимо добавить в блок предыдущего месяца (февраль).
Для проверки решения возьмём февральский блок:
{
"_id": 5,
"date": "2023-02-18",
"hash_prev": "007Ctig2m87HRw",
"nonce": "pZ0uf@YZa0zR23",
"storage": [ 30, 27, 25, 7, 29 ]
}
В этот блок необходимо добавить транзакцию с ID 33.
Значение storageHash блока: xi@OLySqR9dbGq
Новое значение storageHash с добавленной транзакцией: xi@OLITqR9dbGq
Как видно, отличаются только символы storageHash[5] и storageHash[6].
Старое хеш-значение блока: 00>0E11mCe7a1O
Новое хеш-значение блока: 00>0EB2mCe7a1O
Для того, чтобы хеш-значение не изменилось, необходимо подобрать новые значения строки NONCE: nonce[9] и nonce[6].
Старое значение NONCE: pZ0uf@YZa0zR23
Новое значение NONCE: pZ0uf@XZadzR23
С новым значением NONCE хеш-значение блока не изменится после добавления в него транзакции с ID 33.
Показать ответ
Добавление транзакции в блок с _id=5.
Новый NONCE = pZ0uf@XZadzR23
Hash-строка блока = 00>0E11mCe7a1O
<< Назад в раздел (Все задания)
