Вот уже и наступила весна. Некоторые — самые торопливые — уже выкинули елки, в светодиодных гирляндах стали садиться батарейки, а наши читатели начали потихоньку выходить из спячки :). Сегодня мы узнаем ответы на прошлые задачи на собеседованиях и прославим читателя Алексея Астахова, который заработал на этом деле 1000 Waves — это примерно 292 доллара / 18 854 рубля на основе данных coinmarketcap.com (а на момент публикации было, как я посмотрю, 230 долларов / 15 000 рублей ;). — Прим. ред.).
 

Коллизия

Блоки в биткойне создаются каждые десять минут, при этом хеш 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 — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.

4 комментария

  1. 4f4n4s

    21.03.2017 at 11:57

    Здрасьте, я тут впервые. Осознаю вопрос про «Коллизию». Либо я тупой, либо там напутано в байтами/битами.
    «Со временем t количество уникальных байтов в хеше каждого блока будет уменьшаться как U=256-D0-4t», — конкретно тут. А может и еще где-то. Пожалуйста, ответьте мне, мне важно знать, тупой ли я)

  2. 4f4n4s

    21.03.2017 at 12:00

    Да и вообще какой-то там скомканный ответ. К чему там упоминается вероятность 50%, если потом приравнивается N^2 к 2^U… Это уже вроде как 100% вероятность.

  3. 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) нулей. Далее рассуждения остаются теми же

Оставить мнение

Check Also

Ugears. Новые модели подвижных конструкторов из дерева

Услышав слова «деревянный конструктор», ты, наверное, представляешь себе этакий Lego для с…