Задачи на собеседованиях. Награждение победителей от Waves Platform

Коллизия

Блоки в биткойне создаются каждые десять минут, при этом хеш SHA-256 от блока должен начинаться с D нулей, где D на данный момент — D₀~70 и каждый год растет на 4. Оцените, в каком году будет впервые найден блок, хеш которого уже встречался в блокчейне биткойна.

Ответ

Каждый год в сети биткойн создается примерно N=2¹⁶ блоков. Со временем t количество уникальных байтов в хеше каждого блока будет уменьшаться как U=256-D₀-4t, то есть всего возможно M=2^U различных хешей. Согласно парадоксу дней рождений, чтобы с вероятностью 50% среди N блоков была пара таких, у которых будет одинаковый хеш с U уникальных байтов, нужно, чтобы N²2^U, то есть U=32=256-D₀-4t, t38. Следовательно, подобное произойдет приблизительно в 2055 году.

Свойства

Каким из этих свойств не обладает биткойн?

• Вероятность у разных участников иметь разные префиксы, отбросив последние k блоков, экспоненциально убывает с k
• Участник, обладающий x% голосующей мощности, создаст не больше ax% блоков
• Блокчейн растет со временем
• Только владелец приватного ключа может создать валидную подпись транзакции

Как этого планируют добиться в биткойне?

Ответ

Свойство 4, из-за signature malleability — имея (перехватив, например) подписанную транзакцию, можно рассчитать другую ее корректную подпись. Это не является критической проблемой протокола биткойна, однако может существенно повлиять на работу сторонних приложений, разработчики которых не знают о проблеме. Есть два предложения — SegWit и Canonical signatures.

Задача

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

Ответ

20 136 752