Блокчейн (blockchain) переводится как «цепочка блоков». Это способ хранения данных, защищённый от подделки, используемый, в частности, криптовалютой биткоин.
Блокчейн действительно представляет собой последовательность блоков. Каждый блок представляет собой некоторую полезную информацию (в частности, в случае биткоина это список транзакций за определённый период времени — кто кому когда сколько денег передал), снабжённую случайным числом и некоторыми служебными данными, в том числе хэшем — числом, которое по определённой формуле зависит от остальной части блока и хэша предыдущего блока.
Хэш должен быть меньше определённого числа. При этом формула, по которой вычисляется хэш, устроена так, что невозможно получить достаточно маленький хэш иначе, чем перебирая различные значения случайного числа. Поэтому если злоумышленник решит подделать блокчейн (и, допустим, вставить в его середину блок с записью о том, что все люди передают ему все свои деньги), то ему придётся подобрать новое случайное число в новое поддельном блоке и всех последующих (ведь хэш каждого следующего блока зависит от хэша предыдущего), что потребует невозможно больших вычислительных мощностей.
Поэтому блокчейн в целом защищён от подобных атак.
Напишите программу, которая проводит проверку правильности хэшей в модельном блокчейне с простой хэш-функцией.
Блок bn с номером n включает полезную информацию mn, представленную натуральным числом, rn — случайное число от 0 до 255 и hn — хеш (целое число от 0 до 255). У каждого блока хэш вычисляется по формуле hn = 37×(mn+rn+hn-1) (по модулю 256), при вычислении хэша начального блока h0 вместо хэша предыдущего блока берётся ноль.
При этом каждый блок представлен одним числом bn = hn + rn×256 + mn×2562. При этом требуется, чтобы хэш hn был меньше 100.
Формат ввода
На первой строке вводится натуральное число N — количество блоков.
Далее следуют N чисел bn, каждое на отдельной строке.
Формат вывода
Следует вывести номер первого блока, у которого неправильный хэш (не меньше 100 или не совпадает с вычисленным по указанной в условии формуле), или -1, если все хэши в блокчейне правильные. Нумерация блоков идёт с нуля, т. е. они имеют номера от 0 до N-1.
напиши код на python
Информатика 10 класс Алгоритмы и структуры данных ключевые слова: блокчейн хэш проверка хэша криптовалюта биткоин Новый
Давайте разберем, как можно решить эту задачу шаг за шагом.
Для начала, нам нужно понять, как извлечь из числа bn все необходимые компоненты: mn, rn и hn.
Теперь, когда мы знаем, как извлечь все компоненты, давайте перейдем к проверке корректности хэшей.
Теперь давайте напишем код, который реализует описанный алгоритм:
def check_blockchain(N, blocks):
previous_hash = 0
for i in range(N):
bn = blocks[i]
mn = bn // (256 ** 2)
rn = (bn // 256) % 256
hn = bn % 256
expected_hash = (37 * (mn + rn + previous_hash)) % 256
if hn != expected_hash or hn >= 100:
return i
previous_hash = hn
return -1
# Пример использования:
N = int(input())
blocks = [int(input()) for _ in range(N)]
result = check_blockchain(N, blocks)
print(result)
Этот код читает количество блоков и сами блоки, затем проверяет каждый блок на корректность хэша и выводит номер первого блока с ошибкой или -1, если все блоки корректны.