Математика и алгоритмы биткоина.

[n00by]

берется только при подписи, но не при генерации привкея

Генерация привкея по определению число из диапазона от 1 до
0хFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Твоё 256-битное число не удовлетворяет этому условию. То, что некоторые программы
могут гипотетически генерировать такие приватные ключи ничего ровным счетом не
добавляет и ничего не меняет, так как при вычислении и публичного ключа, и подписи
сначала все берется по модулю

При генерации все числа берутся по модулю 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f.
То есть тебе никто не запрещает взять в качестве ключа 512-байтовое число. Однако модуль в расчетах будет взят по числу выше.

А вот генерация подписи ограничена именно тем числом, которое ты указал. Там модуль 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

[amaclin1]

При генерации все числа берутся по модулю 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f.

Где ты это взял? Ну бред же!

[n00by]

При генерации все числа берутся по модулю 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f.

Где ты это взял? Ну бред же!

Нифига, нифига.. Не бред.
Во первых в определении эллиптической кривой. Там есть параметры:

Code:

curve = EllipticCurve(
    'secp256k1',
    # Field characteristic.
    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
    # Curve coefficients.
    a=0,
    b=7,
    # Base point.
    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
    # Subgroup order.
    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
    # Subgroup cofactor.
    h=1,
)

Так вот мы работаем в поле чисел р. То есть публичный ключ считается по модулю р. Однако подписать мы можем только ключом из n (Subgroup order). То есть 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

[amaclin1]

Однако подписать мы можем только ключом из n (Subgroup order). То есть 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Ну а я что сказал?
Первым делом вычисляем остаток от деления числа на n (Subgroup order)
Потом делаем все остальное.
Те два числа которые ты дал на этом первом шаге станут одним числом

Можешь сам проверить чему будут равны публичные ключи от пар:

0x1 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142
0x2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364143
0x3 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364144

[n00by]

Однако подписать мы можем только ключом из n (Subgroup order). То есть 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Ну а я что сказал?
Первым делом вычисляем остаток от деления числа на n (Subgroup order)
Потом делаем все остальное.
Те два числа которые ты дал на этом первом шаге станут одним числом

Можешь сам проверить чему будут равны публичные ключи от пар:

0x1 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142
0x2 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364143
0x3 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364144

Тут больше интересно следующее. Я в свое время сканировал этот форум и гитхаб на ключи (оставленные в любой записи) на предмет забывчивости разрабов/дилетантов.
Понаходил всякого и, в том числе, hex'ы ключей в диапазоне 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f


Ну и, сначал интуитивно, а потом с помощью диссертации на прошлой странице нашел, что искать траты на скрипт hash160(sha256d(priv)) гораздо затратнее, чем искать траты на pubkey.

[amaclin1]

Тут больше интересно следующее. Я в свое время сканировал этот форум и гитхаб на ключи (оставленные в любой записи) на предмет забывчивости разрабов/дилетантов.
Понаходил всякого и, в том числе, hex'ы ключей в диапазоне 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Непонятно что тут интересного.
Я повторю мысль.
Приватный ключ - он только у тебя. Как ты его запишешь - в хексе, октале или на языке сомалийских пиратов -
это твоя личная половая драма.
Кода ты вычисляешь публичный ключ и сигнатуру - ты должен брать число из интервала [1..n-1]
Многие программы (в том числе OpenSSL) не парятся, а берут по модулю от того, что ты им дал в параметре
Некоторые (например https://www.bitaddress.org ) проверяют входящее значение на попадание в интервал.

От того, что ты нашел 256-битные числа за пределами диапазона ровным счетом никаких бенефитов нет.

[n00by]

Непонятно что тут интересного.

Интересно вот что. Откинув всю математику (которая только в 2-3 формулах существует) для эллиптической кривой, возможно ли зная точку на этой кривой и максимальную битовую длину числа "родителя" найти это число "родитель"?
Мне кажется это возможным. Математических доказательств обратного до сих пор ни у кого не появилось.
Сейчас вот и исследую это поле, ну и циклические группы вдобавок.

[amaclin1]

Интересно вот что. Откинув всю математику (которая только в 2-3 формулах существует) для эллиптической кривой, возможно ли зная точку на этой кривой и максимальную битовую длину числа "родителя" найти это число "родитель"?
Мне кажется это возможным. Математических доказательств обратного до сих пор ни у кого не появилось.
Сейчас вот и исследую это поле, ну и циклические группы вдобавок.

Я тут уже немного не понимаю. Точка на эллиптической кривой - это [x,y] - то есть публичный ключ.
Мы уже выяснили, что он делается умножением приватного ключа p на число G
По публичному ключу определить приватный - в настоящий момент мы не знаем как решать эту задачу, кроме
как перебором, который вряд ли закончится до угасания солнца.

Твой вопрос звучит так: если мы определенно знаем, что приватный ключ из диапазона [a..b] -
может ли это упростить нашу задачу? Для определенности, a=1
По-моему, нет.
Разумеется, с учетом того, что диапазон меньше - то и перебор у нас меньше и быстрее получится.
То есть при b=1000 нам надо перебрать только 1000 значений, а не 2²⁵⁶

[n00by]

Интересно вот что. Откинув всю математику (которая только в 2-3 формулах существует) для эллиптической кривой, возможно ли зная точку на этой кривой и максимальную битовую длину числа "родителя" найти это число "родитель"?
Мне кажется это возможным. Математических доказательств обратного до сих пор ни у кого не появилось.
Сейчас вот и исследую это поле, ну и циклические группы вдобавок.

Я тут уже немного не понимаю. Точка на эллиптической кривой - это [x,y] - то есть публичный ключ.
Мы уже выяснили, что он делается умножением приватного ключа p на число G
По публичному ключу определить приватный - в настоящий момент мы не знаем как решать эту задачу, кроме
как перебором, который вряд ли закончится до угасания солнца.

Твой вопрос звучит так: если мы определенно знаем, что приватный ключ из диапазона [a..b] -
может ли это упростить нашу задачу? Для определенности, a=1
По-моему, нет.
Разумеется, с учетом того, что диапазон меньше - то и перебор у нас меньше и быстрее получится.
То есть при b=1000 нам надо перебрать только 1000 значений, а не 2²⁵⁶

Я просто выдвигаю гипотезы, которые сам же потом и стараюсь опровергнуть или принять на вооружение.

Гипотеза 1: В настоящее время существует ненулевое количество непотраченных выходов с приватных ключей в диапазоне чисел от 2^0 до 2^131+-1 (которые являются разницей характеристикой поля Р и порядком циклической группы n).

Примерами таких выходов могут служить вот эти: https://www.blockchain.com/btc/tx/5d45587cfd1d5b0fb826805541da7d94c61fe432259e68ee26f4a04544384164, а также многие другие из моего списка, но которые уже были использованы.

Гипотеза 2: Алгоритмы формирования публичного ключа "не теряют информацию", а следовательно, должны существовать алгоритмы восстановления приватного ключа. Прямой перебор наиболее уебищный из алгоритмов. Я бы вот этих вообще загнобил, увидев их на улице https://bitcointalk.org/index.php?topic=1306983.msg49486901#msg49486901

Ну и Гипотеза 3: Алгоритм взятия дискретного логарифма функции эллиптической кривой "легче" алгоритма нахождения коллизии sha256, либо старших алгоритмов хэширования.

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

[A-Bolt]

Гипотеза 2: Алгоритмы формирования публичного ключа "не теряют информацию", а следовательно, должны существовать алгоритмы восстановления приватного ключа. Прямой перебор наиболее уебищный из алгоритмов. Я бы вот этих вообще загнобил, увидев их на улице https://bitcointalk.org/index.php?topic=1306983.msg49486901#msg49486901

В случае с ECDSA действительно известны более эффективные алгоритмы нахождения приватного ключа, чем простой перебор. В теме, на которую вы сослались, arulbero демонстрирует виртуозное владение алгоритмом "baby-step, giant-step" для нахождения частично известного приватного ключа из публичного ключа.

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

[n00by]

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

Перечитайте еще раз гипотезу №1. Упоминание транзакции-пазла очень хорошо ложится на нее. Выходы с ключами от 2^61 до 2^131 можно считать попутной нагрузкой (в случае если они будут найдены).
Полный перебор - это адово вычислительно сложная задача.
Таким образом мы переходим к гипотезе 2.

Где асики для ECC? Нет их. А почему их нет? Потому что профит не предсказуем?

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

В теме, на которую вы сослались...

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

[amaclin1]

Где асики для ECC? Нет их. А почему их нет? Потому что профит не предсказуем?

Давайте посчитаем вероятность нахождения адреса с непустым балансом.
Адресов всего у нас 2¹⁶⁰
непустых из них, допустим, 16 миллионов, то есть 2¹⁰ * 2¹⁰ * 2⁴ = 2²⁴
То есть вероятность найти непустой адрес перебирая хеши 2^-136

Сравните с вероятностью найти подходящий хэш для блока - это что-то порядка 2^-80
Вы понимаете разницу в этих цифрах?
Без учета того, что для вычисления публичного ключа, адреса и сравнения с базой непустых адресов
потребуется колоссальное количество дополнительных операций. И асик, который перебирает sha256d
хэши со скоростью 14 Th/s просто в тысячи раз замедлится, если его еще нагрузить этой работой

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

Давайте без "кажется", а?
Вот здесь есть графики: http://bitcoin.sipa.be/
Перебрали что-то в районе 10²⁷ хэшей
Сравните какое это количество от 2¹⁶⁰

[Здесь надо картинку с солнцем запостить для тех, кто еще не видел её]

[n00by]

непустых из них, допустим, 16 миллионов, то есть 2¹⁰ * 2¹⁰ * 2⁴ = 2²⁴

непустых сейчас 50 с хвостиком миллионов. Никто не говорит, что нужно перебирать все. Ну и да, половину диапазона можно убрать по причине распределения 0 и 1 в битовой записи.
В общем не убедил.

Перебрали что-то в районе 10²⁷ хэшей
Сравните какое это количество от 2¹⁶⁰

в консоли питона выполнил

Code:

len(bin(10**27))

получил 2⁹²

[Coin-1]

Ну и Гипотеза 3: Алгоритм взятия дискретного логарифма функции эллиптической кривой "легче" алгоритма нахождения коллизии sha256, либо старших алгоритмов хэширования.

При использовании ECDSA secp256k1 длина приватного ключа равна 256 битам, но стойкость этой эллиптической кривой равна 128 битам. Атакующему для решения проблемы дискретного логарифмирования требуется выполнить работу по перебору 2¹²⁸ вариантов (методом Полларда, и т.п.) при условии, что с целевого BTC-адреса была совершена хотя бы одна исходящая транзакция, то есть известен публичный ключ, являющийся координатами [X, Y] точки на эллиптической кривой secp256k1.

По-моему, в Bitcoin нет никакого смысла нахождения коллизии SHA256. Возможно, Вы имели в виду коллизии RIPEMD160, которым хешируются BTC-адреса на конечной стадии генерации.

В любом случае, да, решение проблемы логарифмирования на эллиптической кривой является менее ресурсоёмкой задачей по сравнению с перебором хешей.

[amaclin1]

В любом случае, да, решение проблемы логарифмирования на эллиптической кривой является менее ресурсоёмкой задачей по сравнению с перебором хешей.

Более ресурсоемкой. (Да, вот такой я зануда)

Возможно, Вы имели в виду коллизии RIPEMD160, которым хешируются BTC-адреса на конечной стадии генерации.

Ну да. Можно перебирать биткойн-скрипты вида PUSH_20_байт_мусора OP_DROP OP_TRUE
И ждать пока hash160 ( ) от скрипта станет 385cR5DM96n1HvBDMzLHPYcw89fZAXULJP
Ну или другому P2SH-адресу - список непустых адресов можно составить

[n00by]

В любом случае, да, решение проблемы логарифмирования на эллиптической кривой является менее ресурсоёмкой задачей по сравнению с перебором хешей.

Да, про половинный интервал я умолчал специально. Вы все правильно поняли.

Более ресурсоемкой. (Да, вот такой я зануда)

Как-то прям голословно выглядит.

[amaclin1]

Как-то прям голословно выглядит.

А, я не понял. Вы нашли что-то эффективнее брутфорса? Тогда вы правы, а я нет.

[MrFreeRoMan]

Итак, чтобы получить пару биткоин ключей (приватный + публичный), алгоритм будет следующий:
1. Придумываем любое 256-битное число. Это и будет приватный ключ.
2. Умножаем приватный ключ на магическую константу G которая на самом деле вектор с координатами
x= 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
y= 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8


G*приватный_ключ = публичный ключ.

Теперь остается вопрос: как это умножение устроено?
Понятно, что
G*приватный_ключ = G+G+G+... (сложить столько раз, скольки равен приватный_ключ)

G*1 = G (по определению единицы)

Осталось понять: как вычислить хотя бы
G*2 = G+G

Эти функции являются односторонней функцией, которая означает, что если a = function (b), то нет практического способа найти b, если вы знаете a.
и нет практического способа получить private_key из public_key.

[n00by]

нет практического способа получить private_key из public_key.

Способы есть, их много, все они на переборе. Самые современные алгориты выполняются за (0.97+О(1))sqrt(N), где N - порядок подгруппы.
Это теоретические оценки, которые на кривых малых порядков бьются с практическими показателями.
Но дождаться результата для secp256k1 вы, к сожалению, пока не сможете.

[kzv]

В смысле: "сумели разложить"?
Что конкретно китайцы сделали с этим числом?