All streams
Search
Write a publication
Pull to refresh
2
0.1
Send message

Я не математик, я практик с небольшой подготовкой в криптографии (https://github.com/Dookoo2) потому могу задавать глуповатые вопросы для подготовленного человека. Но если это так как написано в статье, то, блин, это прорыв на самом деле. Я попробую алгоритмически описать ваши наблюдения и протестировать.

Ну-ка поясни, я как-то про это не думал. То есть даже при абсолютно рандомных K мы можем найти закономерности на графике, которые могут ограничить поиск закрытого ключа не всем порядком кривой, а только ее части?

Иногда не случайно, если например ГПСЧ тупит и кластеризует K из-за хреновой энтропии, например, или вообще переиспользует K для подписец. Тогда на подобном графике можно увидеть «облако» или явные точки на одной линии и уже бить более целенаправлено например через LLL алгоритм.

Но при текущей реализации ECDSA в нормальных библиотеках это крайне маловероятно. Статья просто как информация, практической ценности не несет.

Мне интересно! Выкладывай:)

Можешь рассказать по следубщим пунктам:

  1. Как синхронизировал батчи по варпам?

  2. При копировании данных с GPU с хоста, в какую памчть трамбовал данные? Shared/global?

  3. Была ли задействована constant память для каких-то данных?

  4. Сколько потоков запускал?

  5. Тестил ли на register pressure наборы данных, чтобы gpu не подтормаживала?

  6. Вижу вывод с винды, GPU немного недозагружена, но возможно это кривое отображение задействованных ресурсов GPU, так все-таки, пробовал ли на 100% ее загрузить?

  7. Считалось на CUDA или тензоры тоже подключались для каких-то действий?

  8. Не упирался в троттлинг по памяти/кристаллу?

Спасибо за ответы заранее:)

на самом деле не так сложно как кажется! Да, я не программист, за деньги в своей жизни ни строчки кода не написал, но в целом в IT человек не случайный.

Серию статей напишу, как только найду в себе силы, тут есть чем поделиться. Последние недели я писал свой распределенный пул для брутфорса головоломки сатоши на GPU. И он уже работает.

Вот ссылка, подключайтесь. По сути лотерейка, но с шансами на успех, цена победы 800.000 долларов: https://github.com/Dookoo2/Distibuted-CUDACyclone

А вообще история пула за свою трехнедельную историю почти как детектив с кибератаками, противодействием, переговорами с китами аппаратных мощностей, падение, запуски снова, скорость в пике до 24 Теркалючей в секунду (5090 до 8.5Gkeys/s дает).

Нормальный бы программист столько косяков не собрал, как я самоучка:)

Но вроде все в прошлом, работаем стабильно

Я немного знаю автора, вполне вменяемый и уважаемый в сообществе человек. Так что гайду можно верить, но делать строго как там написано. Написано отключить инет - отключай.

Господи, какой ужас… Курсы программирования в Видном, похожи на курсы программирования в Химках, только курсы программирования в Видном, ряжом с баром БарДак, пивнухой и общагой для гастеров. Наши курсы программирования в Видном, самые лучшие курсы программирования в Видном!

Есть 2 подхода для проектирования NGFW и обработки данных на нем, применительно к вычислительным мощностям:

CPU only - путь CheckPoint. За счет AVX/SSE/MBMI и прочих интринсиков батчить пакеты в регистрах CPU для параллельной обработки + низкоуровневые оптимизации драйверов и движков обработки данных с ASM внутри.

FPGA (ПЛИС)/ASIC - спец чипы для обработки той или иной операции.

Нигде в РФ я не видел хотя бы FPGA для какой-то из функций сетевой железки, все рубят в CPU и потому такая хреновая производительность.

А все почему, FPGA дороги? Нет! Просто нет вменяемых людей, кто может нормально спроектировать FPGA конвейер и отсинтезировать его работу. Формы на WebUI нашлепать - легко, взять opensource пакеты с перелицовкой якобы под бренд - еще проще. Затянуть к себе в "движки" SNORT/SURICATA/BRO - подержите мое пиво.

А лезть внутрь, нахер недо, в opensource этого ведь нет.

Короче начинание хорошее, еще один недоNGFW в России наравне с Континент, UserGate и прочим. Года 3-4 и может что и выйдет вменяемого.

P.S. Вру, видел я FPGA в РФ, в коммутаторах ELTEX.

Шалом, господа! Можно внесу пару корректив?

  1. На эллиптических кривых в конечном поле нет как такового деления точек, есть умножение на мультипликативное обратное, что эквивалентно делению. Так как кривая циклична, то деление произвольной точки на мультипликативное обратное 2 может дать как открытый ключ, чей скаляр в 2 раза меньше исходного, так и вынести получившуюся точку далеко от изначальной, если изначальный открытый ключ соответствовал нечетному скаляру.

  2. Алгоритм Shanks BSGS дает сложность Sqrt(b-a) только при условии сохранения память количества точек равную Sqrt(b-a), что для диапазонов типа 2^120 или не дай бог 2^256 обречено на провал. В случае сохранения в память произвольного количества точек Z, мы получим формулу O(N/Z), где N - порядок кривой или тот диапазон в котором осуществляется поиск. Для больших диапазонов лучше использовать Pollard Lambda/Pollard Rho.

Я уже пол-года как пилю брутфорсеры для BTC головоломки сатоши, перепробовал многое, в том числе и нечто похожее, что ты описал в статье, детская поделка. Коллектим миллиард точек в память и значения их скаляра. После чего открытый ключ, чей скаляр мы ищем, умножаем на производное мультипликативное обратное, если частное (точнее открытый ключ) получившийся в результате "деления" присутствует в массиве сохраненных точек, мы восстанавливаем значение скаляра от известного открытого ключа. Чтобы ненароком не пытаться делить искомый открытый ключ, чей скаляр - простое число или имеет мало делителей, каждый N кусок времени мы вычитаем из открытого ключа произвольное число равное 5% от диапазона поиска и накапливаем оффсет. После чего делим уже новый открытый ключ, получившийся в результате сужения диапазона. Но так можно делить до второго пришествия:)

Также недавно запилил брутфорсер на CUDA, вполне возможно, что с рекордной скоростью в 6.2 Gkeys/s на RTX4090 (результаты достигнуты, есть скрины), но столкнулся с проблемой с железом. После 1.5 часа работы горячая GDDR6X "начинает кипеть" и сбрасывать частоту памяти, что сносит скорость до 4.9 Gkeys/s. Я как GPU майнер, при холодном ядре кипящие и визжащие банки памяти.
Сейчас пытаюсь это победить.
Silicon lottery в чистом виде.
Вот ссылки на проекты: https://github.com/Dookoo2

Нет конечно, я свой софт вообще нигде не презентовал, только на Bitcointalk. Это ведь не index calculus для Secp256k1, не найденная изогения или какой-то необычный эндоморфизм, и не успешное решение полиномов Семаева для ECDLP.

Допустим 1 поток, в потоке 256 кенгуру, поток делает 5 миллионов прыжков в секунду, каждый кенгуру проскачет X прыжков. Сменим на 32 кенгуру, за тоже время каждый кенгуру проскачет 8x прыжков. Кажется, что разницы практически нет, но она есть и это факт. При бОльшем количестве прыжков в секунду на 1 кенгуру решение находится быстрее. Если поставить меньше кенгуру в потоке, то уже играет модульная инверсия, она жрет под 50% тактов для сложения точек и скорость резко падает. При 32 кенгурухах в потоке скорость стандартная, без падений.

Мой Mark1 работает не совсем как классический вариант. Я сначала стартую tame kang, точки старта выбираются как диапазон/количество потоков. В каждом поддиапазоне стартуют 32 кенгуру с известным смещением от точки старта. Если они допрыгивают до конца поддиапазона, срабатывает механизм wrap и кенгуруху возвращают обратно в поддиапазон, при этом накапливая оффсет сиещения от точки старта. При прыжках коллектятся DP, сохраняются только уникальные точки.

Далее стартуют wild кенгуру в поддиапазонах также по 32 в поддиапазоне, точно также прыгают и как только напрыгают размер диапазона wrap возвращает ее обратно в поддиапазон. Ни одного прыжка вне диапазона поиска не происходит. Работает детектор циклов Brent, ведь прыжки детерминированы и если одна кенгуруха уже была на какой-то точке, то другая кенгуруха посетив туже точку будет прыгать точно как предыдущая, тем самым снизив нам количество возможных траекторий.

Так что тут особой магии нет, почти классика, но именно что почти.

AI пользовался, как без этого, но честно сказать даже самые мощные модели типа o3, доступные на тот момент, просто жесть как тупили. Но если точечно попросить что-то добавить или подсказать, то норм. С нуля брутфорсер не напишут 100% или времени затратишь x5 от чисто самописного кода.

По CUDA все еще хуже, на самом деле, так что тут больше сам, благо мануалов и примеров много. Радует то, что множество операций типа point mult можно сделать на хосте и потом передать подготовленные данные на GPU, а сам GPU выполняет только point add, никаких point mult или hash160 делать не надо, просто вынести самый горячий цикл на cuda + закинуть bloom в vram.

Я взял в среднем по 32 кенгуру на поток при 32 потоках. брать больше - снижать количество прыжков каждого кенгуру на единицу времени и чаще попадать в циклы. Брать меньше - уже плохо работает батчевая инверсия и не достигается нужная скорость. Ч разбил алгоритм на 2 фазы - сначала все ручные коллектят DP, потом фаза 2 - дикие прыгают и ищут DP. При условии сохранения таблицы DP ч готов заплатить 1 раз много времени чтобы сколлектить DP, но потом их переиспользовать при возможных последующих запусках. Сами прыжки детерминированы, одинаковый Seed ГСЧ при всех запусках, как и таблицы прыжков. Так что у меня в параллель дикие и домашние не скачут. При параллельном запуске это просто баланс 1 к 1, например дает уполовинивание скорости GPU так как дикие кенгурушки не коллектят DP, 1 к 3 чуть получше, DP попадаются реже, но сами дикие кенгуру скачут быстрее. Так что я не стал морочиться и разбил просто на 2 фазы. При моих тестах сочетание 32 потока по 32 кенгуру дают лучшее время до нахождения коллизии. В коде Mark1.cpp это константы K и K_DP их можно поменять и поиграть с составом кенгурух.

На моей тестовой GPU реализации совсем по другому, чтобы загрузить все SM по 128 CUDA ядер в каждом(RTX 4060) мне надо много кенгурух запускать в параллель, много это около 140.000, по 64 где-то кенгурухи на поток, а тысячи потоков.

Может искать до 256 бит.

с иелефона, потому отвечу криво без цитирования.

  1. Именно так! Как ч не бился над SHA-NI intrinsic меньше 9 нс на хэш не получалось, хоть ты тресни и разбейся. Я много времени на это потратил, даже пробовал совместить SHA-NI и AVX. Получается худе, чем чистый AVX.

  2. А я и не писал, что она вводила тормоз. Наблюдая падение частоты при AVX я гуглил с чем это может быть связано, вот и нагуглил про AVX lag. А минипк на Ryzen 7945HX это Minisforum s795s7 в корпусе на 7 литров объема. Чтобы не гудел вертушками сменил на Noctua NF-A9 PWM на cpu и поставил на вдув еще одну нокту на 6 см вроде.

Cyclone - 3 месяца (Mark1 да, 1.5 месяца, может и быстрее немного), и уже на 90% готовой библиотекой SECP256k1 от JLP. Вот он - гений. Я только допилил ее немного, переписал часть функций арифметики (модульной и обычной), написал обе реализации хэширования и основной модуль ну мелочи типа Bloom и DP-таблицы Scalar256 + перевел это все на AVX интринсики где возможно вообще это сделать.

Нормальный сишник сделал бы быстрее, я ведь не программист даже, ни строчки кода за деньги в жизни не написал. Это хобби.

На одно физическое ядро около 10Mkey/s, на логический поток да, около 5Mkeys/s.

Почему работает быстро:

  1. ASM оптимизации библиотеки SECP256K1 от JLP с моими добавлениями и ускорениями в модульной арифметике.

  2. Убраны/переписаны constant time реализации функций (мы тут не безопасность обеспечиваем, а перебираем как можно быстрее)

  3. Групповая модульная инверсия через алгоритм DivStep62 (на основе whitepaper Thomas Pornin).

  4. Быстрейший алгоритм модульного умножения на основе 64 битных лимбов + Монтгомери.

  5. Батч сложение точек.

  6. AVX2 Bloom фильтр с проверкой пачки ключей за раз.

  7. Практически нигде не используется point multiplication.

  8. Применены все возможные флаги компиляции с MAVX2, BMI, ADX. Аггрессивная векторизация всего что только можно при компиляции.

  9. Крайне быстрый и простой алгоритм хэширования (splitmix).

  10. Быстрый псевдо ГСЧ xhoshiro.

Ну и в дополнение атомики для многопотока для превента race condition, что быстрее mutex и другие мелочи.

Что касается Cyclone там еще и ультраоптимизированные sha256 и ripemd160 с помощью AVX2 (8-way hash) или AVX512 (16-way hash). Sha256 на Ryzen 7 5800H считается за 4-5 наносекунд на хэш. Ripemd160 около 3 наносекунд.

Но при использовании векторных AVX интринсиков есть и минусы - CPU не выдает свою максимальную скорость из-за AVX boost lag. От максимальной частоты в 5.4 Ghz я наблюдаю максимум в 4.4 Ghz. Не хватает процу энергии для щелканья регистров AVX с такой скоростью. Но есть и плюсы - температура не выше 73 градусов при 100% загрузке всех 32 потоков.

И про координаты, да, афинные координаты, так повелось, что кто-то подкинул идею что проективные не катят, поверили:) Основная идея в том, что самая дорогостоящая операция - модульная инверсия, в проективных координатах откладывается только когда требуется проективные перевести в афинные, но с DivStep62 мы и так вычисляем модульную инверсию 1 раз сразу на батч точек (256 точек, например), что нивелирует преимущество проективных координат.

Блин сам себя с утра перемудрил, 12 байт, не бит:)

Итого мы имеем, допустим, глубину DP-бит в 16 бит (чтобы стать DP точка должна содержать последние 16 бит нулевых), такая точка встречается 1 к 65536 прыжков. Бит на запись в блум - 80 бит, вероятность false-positive около 6.5e-9. За секунду сейчас мой минипк делает 140 миллионов прыжков, соответственно DP будут признаны 2100-3000 точек, чтобы набрать на одну ложноположительную сработку надо десятки минут. Так что трафикообмен с SSD не просто минимальный, его почти нет.

Другое дело конда отрабатывает фаза 1, когда коллектятся DP. Тогда все найденые DP пишутся на SSD. Но чтобы не убить хард и не вызывать запись тысячами мелких данных за секунду, я собираю эти точки в батч и пишу сразу батчем. Так SSD живет дольше.

Блум дает ложноположительные сработки, но никогда ложноотрицательные. Доя этого есть вторая таблица DP на SSD. Все что Bloom дает как «возможно да» дополнительно проверяются по DP-таблице на SSD.

Да и к тому же сам фильтр тонко настраивается, можно задать больше бит на запись в блум чтобы снизить количество false-positive событий.

Для примера Блум фильтр на 12 бит весит 14.9 гигабайт при размере таблицы в 1.5 миллиарда DP. И этот массив легко помещается в память. DP таблица при том же обьеме точек весит 160 гигабайт на SSD, что тоже приемлемо.

Рассматривал дополнительно XOR и Cuckoo фильтры для работы, но блум проще и для моих целей подходит, тактов CPU на lookup в фильтре +/- одинаково, разве что XOR чуть шустрее.

Основная идея сообщества касательно DP в том, что нужен баланс между частотой проверок на DP и их количества, чтобы не было импакта на производительность. То есть заранее вычисляем нужное количество DP и стараемся его не перебрать при работе программы, балансируя DP битами (чем больше бит для DP точки, например последние 16 бит координаты X - ноли, тем реже они встречаются и реже надо проверять).

В своем Mark1 я эту идею отверг, мой Bloom проверяет DP за O(1) времени, будь их хоть 100 хоть миллиард, так что я могу их коллектить пока хватит RAM и SSD. Ну и это дает эффект конечно.

Времени написать Cyclone - 3 месяца, где-то так. В основе библиотека Secp256k1 от JeanLuckPons, хэширование с помощью AVX - моя реализация.

На Mark1 времени ушло меньше, месяца полтора или около того.

На счет навороченности я как-то не думал, но вообще да, они обе максимально близко к железу.

Сейчас разбираюсь с CUDA, переписываю ядро под GPU. Хобби такое:)

При текущем уровне сложности раскрытия кошельков, что ты получишь 10Gkeys/s на RTX5090, что 160Mkeys/s на Ryzen 9 7945HX - невелика разница, чистая удача. Я использую этот софт как лотерейку постоянную

Коэффициенты k не мерял, но при последовательном запуске Kangaroo от RetiredCoder и моей версии, он решил 80 бит на rtx4060 за 3:30 минуты, мои запуски на CPU Ryzen 9 7945HX:

  1. Первый тестовый - 38 минут

  2. Второй запуск - 3 секунды (500 миллионов DP)

RetiredCoder использует симметрию кривой, что на относительно малых диапазонах (120-140 бит) малополезна, только ест мощность GPU. А его SOTA метод детекции циклов на вскидку проигрывает обычному Brent Loop Detector в моей Mark1.

В общем нужна статья где опишу суть и сложность брутфорса кошельков сатоши.

1

Information

Rating
4,162-nd
Registered
Activity

Specialization

Specialist
Lead