Коллизия
Блоки в биткойне создаются каждые десять минут, при этом хеш SHA-256 от блока должен начинаться с D нулей, где D на данный момент — D0~70 и каждый год растет на 4. Оцените, в каком году будет впервые найден блок, хеш которого уже встречался в блокчейне биткойна.
Ответ
Каждый год в сети биткойн создается примерно N=216 блоков. Со временем t количество уникальных байтов в хеше каждого блока будет уменьшаться как U=256-D0-4t, то есть всего возможно M=2U различных хешей. Согласно парадоксу дней рождений, чтобы с вероятностью 50% среди N блоков была пара таких, у которых будет одинаковый хеш с U уникальных байтов, нужно, чтобы N22U, то есть U=32=256-D0-4t, t38. Следовательно, подобное произойдет приблизительно в 2055 году.
Свойства
Каким из этих свойств не обладает биткойн?
- Вероятность у разных участников иметь разные префиксы, отбросив последние k блоков, экспоненциально убывает с k
- Участник, обладающий x% голосующей мощности, создаст не больше ax% блоков
- Блокчейн растет со временем
- Только владелец приватного ключа может создать валидную подпись транзакции
Как этого планируют добиться в биткойне?
Ответ
Свойство 4, из-за signature malleability — имея (перехватив, например) подписанную транзакцию, можно рассчитать другую ее корректную подпись. Это не является критической проблемой протокола биткойна, однако может существенно повлиять на работу сторонних приложений, разработчики которых не знают о проблеме. Есть два предложения — SegWit и Canonical signatures.
Задача
Посчитать количество уникальных перестановок фигур на шахматной доске размером 6 на 9 клеток: двух королей, одного ферзя, одного слона, одной ладьи и одного коня — так, чтобы ни одна из них не била другую, цвет фигур не имеет значения. Решение должно работать до трех минут на среднестатистическом ноутбуке. В доказательство нужно предоставить код (он может быть написан на любом языке программирования).
Ответ
20 136 752
IT-компании, шлите нам свои задачки!
Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки на lozovsky@glc.ru — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.
4f4n4s
21.03.2017 at 11:57
Здрасьте, я тут впервые. Осознаю вопрос про «Коллизию». Либо я тупой, либо там напутано в байтами/битами.
«Со временем t количество уникальных байтов в хеше каждого блока будет уменьшаться как U=256-D0-4t», — конкретно тут. А может и еще где-то. Пожалуйста, ответьте мне, мне важно знать, тупой ли я)
4f4n4s
21.03.2017 at 12:00
Да и вообще какой-то там скомканный ответ. К чему там упоминается вероятность 50%, если потом приравнивается N^2 к 2^U… Это уже вроде как 100% вероятность.
pkrt
29.03.2017 at 10:31
В решении не учитывается вероятность коллизии с блоками, сгенерированными ранее. Даже если блок должен начинаться с D нулей, есть вероятность сгенерировать блок, начинающийся с D+4m нулей для некоторого m. По закону больших чисел считаем, что среди N блоков, которые должны начинаться с D = D0+4t нулей, найдутся 1/(2^4m) блоков, которые начинаются с (t + m) нулей. Т.о. в парадоксе о днях рождения будет участвовать не N хэшей, а сумма N + N/(2^4) + N/(2^8) + … + N/(2^16). Правда, при таком уточнии результат отличается незначительно, а именно вероятность коллизии будет около 50% через 36 лет, т.е. в 2053
pkrt
29.03.2017 at 10:37
Прошу прощения, опечатался. найдутся 1/(2^m) блоков, которые начинаются с (D0 + 4t + m) нулей. Далее рассуждения остаются теми же