Вот уже и наступила весна. Некоторые — самые торопливые — уже выкинули елки, в светодиодных гирляндах стали садиться батарейки, а наши читатели начали потихоньку выходить из спячки :). Сегодня мы узнаем ответы на прошлые задачи на собеседованиях и прославим читателя Алексея Астахова, который заработал на этом деле 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 комментария

Подпишитесь на ][, чтобы участвовать в обсуждении

Обсуждение этой статьи доступно только нашим подписчикам. Вы можете войти в свой аккаунт или зарегистрироваться и оплатить подписку, чтобы свободно участвовать в обсуждении.

Check Also

Скрытая сила пробела. Эксплуатируем критическую уязвимость в Apache Tomcat

В этой статье мы поговорим о баге в Apache Tomcat, популярнейшем веб-сервере для сайтов на…