Skip to main content

Не все полиномы одинаково полезны или почему CRC32 давно не тот

Терминология

Часто под CRC подразумевают две разные вещи:

  • Cyclic Redundancy Code — применяется в помехоустойчивом кодировании для обнаружения и исправления ошибок

  • Cyclic Redundancy Check — использование циклических кодов в качестве хэш-функции для проверки целостности принимаемых даных

Поскольку большинство современных проводных каналов связи обладают достаточными характеристиками для поддержания хорошего BER, то зачастую достаточно убедиться в том, что сообщение не искажено во время прохождения по внешнему каналу, а для этого достаточно использования циклических кодов в качестве контрольных сумм (перезапрос «бракованного» кадра как правило  в большинстве интерфейсов происходит на более высоком протокольном уровне). 

Критерии качества

Качественным критерием оценки контрольной суммы является вероятность возникновения коллизии — т.е. необнаружения искажения данных: подразумевается искажение данных таким образом, что подсчитанный CRC (от искаженных данных) совпадет с референсным CRC (либо одновременно исказятся и CRC и данные в канале передачи). Причём, чем длиннее сообщение, тем больше вероятность появления коллизии — больше возможностей для того чтобы «звёзды совпали», поэтому часто выбор длины полинома для подсчёта CRC соотносят с размером пакета, к которому этот CRC применяют. 

Для этого ввели такой термин как Расстояние Хэмминга (Hamming Distance, HD) или Метрика Минковского — она служит некоей метрикой различности двух объектов (в нашем случае — двух пакетов: переданного и принятого). В терминах CRC, HD — это минимально возможное число бит сообщения, инверсия которых может привести к коллизии (необнаружению повреждения сообщения). Так, например в стандарте CAN (от Bosch GmbH) используемый полином вкупе с длиной сообщений обеспечивает HD=6, что означает, что не существует никаких комбинаций 1-, 2-, 3-, 4- и 5-битных ошибок (здесь ошибка — инверсия передаваемого бита в сообщении), которые не были бы необнаруживаемыми, но существует как минимум одна комбинация 6-ти битной ошибки, которую невозможно обнаружить с помощью используемого полинома CRC.

Также необходимо отметить, что на правильность выбора полинома для того или иного протокола (и получения конкретного значения HD) зависит и скорость передачи информации — характер ошибок и их динамика может сильно меняться (например, за счет увеличения скорости передачи — появляться пачки ошибок), вот для примера какие цифры фигурируют в знакомых мне протоколах:

Связь скорости передачи, длины сообщения и выбора степени полинома CRC

Дань традициям 

В большинстве стандартизированных протоколов используются контрольные суммы CRC, однако часто используемые в них стандартизованные полиномы не являются самыми эффективными в терминах эффективного расстояния Хэмминга (HD), в [1] затрагивается вопрос на всю глубину: большинство стандартов в плане обнаружения ошибок не столь эффективны, как могли бы быть, из-за того, что используется полином для контрольной суммы, однажды выбранный на этапе утверждения стандарта. 

Наиболее яркий пример — стандарт на Ethernet-пакеты IEEE 802.3, который использует самый популярный 32-разрядный полином, но в то же время, использование иных 32-разрядных полиномов (CRC32C, CRC32K, etc) позволило бы достичь лучших показателей (в терминах HD) в различных диапазонах длин передаваемых сообщений, посмотрим на таблицу:

CRC32 hamming distance comparison

Видно, что стандартный полином CRC32 на пакетах свыше 372 байт имеет  HD=4, в то время как CRC32K на пакетах до 2045 байт имеет HD=6, А если оперировать Jumbo-фреймами, то CRC32C на пакетах до 16 КБайт обеспечивает HD=4 (в то время как стандартный CRC32 обеспечивает HD=4 при длине пакета до 11,5 КБайт). Т.о. видно, что если есть возможность отойти от стандарта (например, создание своего полностью кастомного оборудования для стандартных протоколов, которое работает только во внутренней собственной инфраструктуре) следует воспользоваться этой возможностью — в случае стандартного Ethernet можно сделать модификацию под какой-нибудь Industrial Ethernet с CRC32C/CRC32K, снизив вероятность необнаружения ошибки или увеличив размер пакета по отношению к стандартному, не снижая при этом имеющегося HD.

Мораль

Не только при конструировании новых протоколов обмена, но и при реализации стандартных полезно сверяться прежде всего не со стандартами, а с работами, подобными Best CRC Polynomials, особенно если специфике вашей работы свойственно выжимать максимум из возможного и где цена необнаружения ошибки высока  (Aerospace/Aircraft, Industrial, Automotive). 

Следующим призывом будет там где это возможно писать на верилоге модули CRC, конфигурируемые не параметрами, а в процессе работы (on-the-fly). Это легко реализуется (в первую очередь — с минимальными аппаратными затратами), если вычислять CRC через последовательную реализацию (LFSR), а не по 4/8/N-бит за такт.

Тест на внимательность

В заголовке статьи использована картинка с LFSR, реализующим 24-битный CRC на verilog (из BLE), а не CRC32 из IEEE 802.3 как могло показаться.

Литература

  1. Philip Koopman, Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks

  2. Блейхут Ричард. Теория и практика кодов, контролирующих ошибки [Theory and Practice of Error Control Codes] — М.: Мир, 1986.

  3. Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950. 

Читать далее

Эффективное оборудование для майнинга коинов или не так страшен ASIC: особенности реализации

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

Классифицируем особенности реализации ASIC для майнинга биткоина либо аналогичных криптовалют на несколько категорий (заранее отмечу, что особенности реализации призваны в том или ином виде оптимизировать себестоимость майнинг-чипов и по максимуму поднять удельную (на чип) производительность):

Архитектура

Поскольку современные фермы должны быть масштабируемы, то всегда предусмотрена возможность каскадирования в daisy chain  нескольких сотен/тысяч чипов (наиболее распространенный интерфейс для внешних коммуникаций — SPI).

RTL-кодирование

При разработке ASIC-майнеров часто отказываются от верилог-кодирования, отдают предпочтение новомодным метросексуальным JS-фреймворкам, поэтому этот раздел под NDA пустой.

Физический дизайн и топология

Чтобы не облажаться по полной как описано в заметке не стоит отдавать весь физдизайн на аутсорс в дизайн-центр при фабрике, нужен разумный компромисс между рисками разной природы.

Список используемых ухищрений:

  • Использование современного техпроцесса, обеспечивающего баланс требований по предельному быстродействию ячеек и их динамическому потреблению (TSMC HPP/HPM/HPC+)  — утечки в статике на числодробилке работающей 24/7 мало кого волнуют
  • Активное использование технологии DVS (Dynamic Voltage Scaling) для того чтобы у одного и того же ASIC было два профиля тепловыделения: режим максимальной производительности (т.н. турбо) для использования с активным охлаждением и стандартный режим производительности для пассивного охлаждения. Так или иначе это маркетинговые названия не отражающие физическую суть, а суть в том, что turbo — это может быть работа на пониженном Vcore (например, 0.85В вместо стандартных 0.9В для TSMC 28nm), а standart — работа на сверхнизком Vcore (0.78В для  TSMC 28нм). Сделано это с целью уложиться в TDP используемых корпусов
  • В каких-то экзотических реализациях отказываются от тактовых деревьев и синхронного дизайна в целях уменьшения тепловыделения/потребления
  • Из аналоговых блоков используют разве что ФАПЧ для получения высокой частоты тактирования внутри кристалла. Чипы майнера, выполненные по современным технологиям 40..16нм работают на частотах от 1 ГГц и выше, из-за проблем с целостностью цифрового сигнала такую частоту сложно завести на чип снаружи. Пожалуй, в рамках оптимизации стоимости это чуть ли не единственный аналоговый блок, необходимый для дизайна ASIC-майнера.

Корпусирование

Тут две основные тенденции: максимальное удешевление корпусирования и эффективный отвод мощности от кристалла, каким образом этого достигают?

WireBond

Небольшое число ног и отсутствие высокоскоростных интерфейсов позволяют использовать доступную и недорогую разварку кристалла по технологии WireBond.

WireBond-кристалл, разваренный на массивные lane для ввода питания ядра и отвода тепла

Эффективный отвод мощности

Минимальное число ног и тут играет на руку, также как и использование последовательных интерфейсов для коммуникации с фабрикой хеш-блоков. Активно использующиеся массивные lane для ввода питания ядра и земли (для подвода к чипу большого тока с низким падением напряжения) служат и для второй функции: большой пятак земли выполняет еще и важную функцию отвода тепла от кристалла (эти решения очень напомнили мне ноу-хау последного десятилетия от InternationalRectifier  в их SMD-корпусостроении MOSFET-ов).

 Большой пятак земли и питания ядра должет быть запаян на соответствующие специально спроектированные полигоны для отвода тепла от кристалла

 

Проектирование на уровне системы и иные ухищрения

 Поскольку чип представляет собой достаточно регулярную структуру фабрики блоков по расчету хешсум, то часто разработчики вносят в схему возможность байпаса произвольных блоков и механизм BIST (самотестирования). Это преследует сразу две DFT-цели:

  • Экономия на производственном тестировании (поскольку почти всю площадь кристалла занимают блоки расчета хешсумм)
  • Увеличение выхода годных (бракованные по результатам самотеста блоки расчета хешсум не используются в работе — в принципе это практически та же самая техника, что используется при тестировании и отбраковке больших массивов накристальной SRAM, только тут еще и на eFuse съэкономили)

Выводы

Как видим, особенностей реализации не так уж и много, однако (экономический) эффект от внедрения не следует недооценивать: специализированные ASIC-чипы для майнинга пережили уже не одно поколение и передовыми компаниями был накоплен некоторый опыт, который и учтён в последнем поколении чипов.

Читать далее

Как сделать ферму майнинга коинов на ASICах и не обанкротиться

Первый вариант заголовка: Bitmine & InnoSilicon: История об одном неудавшемся чипмейкерстве; но порывшись в сети и найдя ответное открытое письмо InnoSilicon, нельзя утверждать, что всё так однозначно в этой истории.

Жил-был такой зарегистрированный в Швейцарии стартап, звался он BITMINE AG, занимался разработкой СБИС для майнинга биткоинов и производством майнеров на базе собственной же СБИС, но что-то не задалось у этого стартапа с бизнесом и в 2015г он объявил себя банкротом (после чего против компании были поданы многочисленные иски), опубликовав на своём сайте  https://bitmine.ch/ открытое письмо и указав на основные причины этого, которые заслуживают рассмотрения на мой взгляд. Итак что же или кого же винит BITMINE в собственных неудачах?

Причины банкротства

Заранее отмечу, что нижеперечисленные причины так или иначе являются следствием задержки выхода на рынок в силу различных обстоятельств.

Изменение стоимости биткоина и увеличение сложности добычи

 Из-за быстрого увеличения стоимости майнинга и падения стоимости BTC (2014-2015гг) более половины клиентов отменили свои заказы. Компания осознавала эти риски, но слепо верила в силу биткоина и оправдывает свой провал тем, что многие конкуренты так же обанкротились идя на поводу у общей истерии первой криптовалюты.

InnoSilicon

 Это основной пункт «оправдательного» письма. InnoSilicon — китайский дизайн-центр; подрядчик и впоследствии партнёр, который отлично подошёл на роль главного козла отпущения. Утверждается, что InnoSilicon на условиях подрядчика занималась разработкой ASIC «под ключ» по технологии 28нм (включая создание топологии, масок, изготовление чипов и корпусирование), используя ноу-хау, предоставленные BITMINE AG. Контракт подряда предусматривал эксклюзивное право Bitmine на продажу чипов А1 сроком на 1 год. Однако, со слов Bitmine, InnoSilicon начала продавать их А1 с самого начала производства на сторону, притом по отпускной цене, ниже, чем они доставались самой Bitmine, которой партии чипов были отгружены с различными задержками, вопреки контракту. Также утверждается, что поскольку большиснтво отгруженных чипов было бракованными, это заставило Bitmine заказывать дополнительные партии чтобы выполнить обязательства перед клиентами, и в итоге InnoSilicon сумело выкачать подобным образом из Bitmine в общей сумме около 8ми миллионов франков (!). Также утверждается, что китайские законы таковы, что Bitmine никогда не смог бы выиграть суд против InnoSilicon.

«Непредвиденные» инженерные сложности

 При разработке источников питания для СБИС был допущен просчёт из-за чего возникла необходимость нанять более квалифицированных инженеров и запуска дополнительных (незапланированных) итераций дизайна. Утверждается, что даже новые, более квалифицированные инженеры слишком поздно решили проблему. Вторая часть проблемы — острый дефицит и задержка поставки ключевых компонентов системы питания майнера: контроллеры DC/DC-преобразовтелей, танталовые конденсаторы, MOSFETы, из-за чего серийные изделия не вышли в срок или не вышли вовсе.

 

Взгляд глазами InnoSilicon

Innosilicon Inc в ответном открытом письме утверждает, что она является действующим и единственным обладателем прав на A1 BTC ASIC и A2 LTC ASIC. Единственными причинами неудачам Bitmine является инженерная некомпетентность и безрассудный бизнес-риск.

1. A1 ASIC вышел вовремя и работоспособным, с типовым для техпроцесса 28нм выходом годных. На момент получения Bitmine чипов А1, рынок ВТС был весьма горячим, но Bitmine не смогли в приемлемые сроки выпустить майнеры на базе чипа А1. Причиной, по которой Bitmine не смогли в срок выпустить майнеры на базе А1, является инженерная некомпетентность и ошибки в проектировании системы питания чипов и многочисленные ошибки в дизайне печатных плат,  которые требовали новых итераций и перевыпуска PCB.

2. Начиная с октября 2013 г проект А1 был продолжен на партнерских условиях, из-за неспособности Bitmine в дальнейшем финансировать проект. Тогда же были внесены поправки в контракт, позволяющие Innosilicon продавать чипы А1 на правах, равных с правами Bitmine.

3. Innosilicon единолично разработал и владеет 100% интеллектуальной собственности, использованной в чипе А1. Innosilicon — известный и уважаемый во всём мире дизайн-центр с хорошей репутацией среди заказчиков и превосходным портфолио выполненных проектов. После успеха А1 BTC, Innosilicon разработал и вывел на рынок А2 LTC, а в последствии и А4 LTC, которые быстро стали номер 1 на рынке майнинга. Bitmine — компания, состоящая из двух человек с нулевым опытом в области микроэлектроники и цифрового дизайна. Согласно контракта, любой проектный взнос компании принадлежит компании, сделавшей его. Фактический взнос Bitmine — это файлы тестовых векторов для валидации СБИС.

4. Bitmine использовал деньги своих клиентов из предзаказов, чтобы приобрести себе сторонние фермы майнинга и проводил рискованные операции с биткоинами, на чём и погорел. Реальной проблемой Bitmine являлся посредственный риск-менеджмент и отсутствующая компетенция в технических вопросах на высококонкурентном рынке. У Bitmine было достаточное окно возможности, чтобы разработать дизайн майнера на базе А1, до прихода чипа с фабрики, но они эпично профакапили эту возможность. Даже после выхода майнера на А1 от Bitmine, у него наблюдались проблемы со стабильностью работы, что подтвержлают многочисленные жалобы немногочисленных клиентов. 

Выводы для начинающих чипмейкеров

Если правдивы заявления Bitmine

1. IP: Необходимо принимать меры по защите своей интеллектуальной собственности, и я говорю не об юридических гарантиях защиты: требуется предотвратить риск и максимально снизить привлекательность использования вашего продукта без вашего ведома — на сегодня чип без документации по программированию, даташитов с режимами работы и характеристиками, информационных протоколов обмена малопривлекателен для производства в третью смену и отгрузку на сторону (а конечному пользователю, обычно, эти данные не нужны).  Концентрируйте на своей стороне контроль за работой чипа, вплоть до параноидальной встройки блока с UID (e-Fuse), который по процедуре инициализации рабочего режима аутентифицируется  вашим сервером в интернете (главное не перестараться и соблюсти tradeoff между удобством для клиента и защитой реализованных в кремнии ноу-хау).

2. Аналогичен пп.2 ниже.

Если правдивы заявления Innosilicon

1. Время — деньги: на эти грабли не наступали лишь единицы. собственными глазами был очевидцем нескольких схожих ситуаций. Типичная: торопливость в желании скорого TapeOut оборачивается тем, что сама работа начинается только по приходу чипа (тут был место правда СнК — программисты без малого 2 года возились оживляя кристалл, работая на пополнении Silicon Errata и написании драйверов), хотя идеологически и методологически должна была быть выполнена до отдачи проекта на фабрику. Или другой пример: чип пришёл раньше запланированного срока (есть такая профессия — глотатели чипов), а с ним нельзя начать работы — не готовы PCB, либо ошибки в дизайне и необходима еще одна итерация (перевыпуск) дизайна — а ведь большинство ошибок дизайна можно найти без установки чипа (нам очень повезло что мы живем в эпоху экстремальной доступности измерительного и диагностического оборудования): необходимо только изготовить и смонтировать PCB, чтобы начать отлаживать дизайн в железе (типично, самые частые ошибки как раз в системе питания СБИС). 

2. Не продешевите: войско «студентов-ардуинщиков» врядли в принципе в адекватное время и затраты материальных ресурсов решит подводные камни, которые всплывут при процедуре bring-up первых пришедших с фабрики чипов. Необходимо сразу закладывать бюджет на матерого разработчика, лучше по рекомендациям знакомых/коллег по цеху. Да и в целом в руководстве компании стояли гуманитарии менеджеры, рассудочность технических решений которых под большим вопросом, в таких глобальных по финансам проектах как чипмейкерство среди лиц принимающих решение (и/или соучредитель) должен быть как минимум один сильный технический лидер, который понимает технические риски проекта и знает что с ними делать: как на этапах планирования проекта, когда происходит разделение ролей — что оставить у себя, а что можно отдать на подряд, так и на более поздних этапах, при срабатывании триггеров рисков.

3. Риск-менеджмент: как было сказано выше, докучи необходимо учитывать еще и технические риски. Помимо этого стоит отдавать себе отчет в насколько высококонкурентной сфере вы решаете испытать удачу: промедление в выходе на рынок эквивалентно банкротству предприятия (время — деньги) и при задержке в каких-то 2 месяца ваш продукт уже может быть никому не интересен. Также стоит упомянуть, что необходимо отдавать себе отчёт в том, насколько дорогостоящее само по себе занятие чипмейкерством. Bitmine молодцы, что полностью переложили риски по разработке и изготовлению чипа на Innosilicon, а Innosilicon молодцы, что профессионалы своего дела и не облажались. Однако при желании защитить свою интеллектуальную собственность и взять на себя часть технических рисков — будьте готовы иметь соразмерную отрасли подушку безопасности чтобы изыскать возможность перевыпустить маски в случае если первый блин чип будет комом.

 

Читать далее

[opensource]: Аппаратный криптодвижок ГОСТ 28147-89

Что такое движок по ГОСТ 28147-89?

Реализация на верилоге советсткого стандарта симметричного шифрования, который был рассекречен в 1989г. В стандарте применяется шифрование с 256-битным ключом над 64-битным блоком данных за 32 раунда.

Текущая реализация являет собой некий компромисс между используемыми ресурсами и производительностью с целью демонстрации возможности размещения криптодвижка в низкобюджетных ПЛИС (оставаясь при этом относительно быстрым), как видно из отчета по использованию ресурсов — цель была достигнута.

Возможности

  • RTL и тесты написаны на верилоге
  • Реализация шифровщика/дешифровщика как единого блока
  • Поддержка режима EBC
  • Реализация алгоритма ГОСТ 28147-89 оптимизированная по использованию минимума ресурсов
  • Реализация криптования/декриптования 1 блока за 32 такта
  • Поддержка следующих типов S-box (имена даны в соответствии с RFC4357):
    • id-GostR3411-94-TestParamSet
    • id-Gost28147-89-CryptoPro-A-ParamSet
    • id-Gost28147-89-CryptoPro-B-ParamSet
    • id-Gost28147-89-CryptoPro-C-ParamSet
    • id-Gost28147-89-CryptoPro-D-ParamSet
    • id-tc26-gost-28147-param-Z
    • также поддерживается S-box из ГОСТ Р34.11-94 из CryptoPro

(далее…)

Читать далее

[WiP][opensource]: Аппаратный криптодвижок ГОСТ P34.12-2015 aka «Кузнечик»

Что такое аппаратный Кузнечик (ГОСТ P34.12-2015)?

Реализация на верилоге свежего российского крипто-стандарта, который (почему-то?) получил второе имя «Кузнечик». О чём стандарт: симметричное шифрование, 256-битный ключ, 128-битный блок данных, 10 раундов.

 

Текущий статус

Написана и проверена поведенческая верилог-модель стадий S и R.

Особенности

  • Verilog HDL для RTL и тестовых стимулов
  • Реализация шифровщика/дешифровщика как единого блока
  • Поддержка режима EBC

Планируемые доработки

  • Поддержка следующих режимов поточного шифрования: CBC, CFB, OFB (возможно CTR)
  • Добавление AXI4-Stream для потокового шифрования
  • Добавление параллельной шины для конфигурации/статуса (АМВА АРВ-like?) в составе СнК
  • Возможность предзагрузки рассчитанного для всех раундов ключа
  • Параллельная сверка работы с моделью на Си (механизм DPI)
  • Различные реализации: критерии «минимальная площадь» и «максимальная производительность»

(далее…)

Читать далее

ГОСТ 34.12-2015 «Кузнечик». Производительность в железе.

Входные данные

  • 9 [честных] раундов
  • 128 бит [16 байт] блок данных
  • 100 МГц частота ПЛИС [при реализации криптоалгоритма]

 

Оценки

В некоторых докладах [ Рудской В. Российские криптографические стандарты: функции хэширования, блочные шифры и режимы их работы ] слышны цифры что на Си под 64битный линукс удаётся достичь скорости шифрования до 130 МБайт/с. (далее…)

Читать далее