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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 27, 2019, 04:07:27 AM

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

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

Quote from: amaclin1 on February 27, 2019, 04:07:27 AM

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

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

Code:

len(bin(10**27))

получил 2⁹²

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 27, 2019, 03:24:49 AM

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

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

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

Quote

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

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: A-Bolt on February 26, 2019, 03:56:13 PM

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

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

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

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

Quote from: A-Bolt on February 26, 2019, 03:56:13 PM

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

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

A-Bolt

legendary

Activity: 2317

Merit: 2318

Quote from: n00by on February 26, 2019, 03:06:44 PM

Гипотеза 2: Алгоритмы формирования публичного ключа "не теряют информацию", а следовательно, должны существовать алгоритмы восстановления приватного ключа. Прямой перебор наиболее уебищный из алгоритмов. Я бы вот этих вообще загнобил, увидев их на улице https://bitcointalksearch.org/topic/bitcoin-puzzle-transaction-32-btc-prize-to-who-solves-it-1306983

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 02:15:59 PM

Quote from: n00by on February 26, 2019, 01:49:19 PM

Интересно вот что. Откинув всю математику (которая только в 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://bitcointalksearch.org/topic/bitcoin-puzzle-transaction-32-btc-prize-to-who-solves-it-1306983

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 01:49:19 PM

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

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 01:41:27 PM

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 01:32:47 PM

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

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 01:26:43 PM

Quote from: n00by on February 26, 2019, 01:20:05 PM

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

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

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

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

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 01:20:05 PM

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

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

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 01:14:41 PM

Quote from: n00by on February 26, 2019, 01:12:55 PM

При генерации все числа берутся по модулю 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

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 01:12:55 PM

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

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

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 01:05:58 PM

Quote from: n00by on February 26, 2019, 01:01:24 PM

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

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

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

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

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

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 01:01:24 PM

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

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

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

Quote from: n00by on February 26, 2019, 01:01:24 PM

берется только при подписи, но не при генерации привкея
при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

Да генерировать мы можем хоть 100500-битное число и считать его приватным ключом!
Все равно никто не узнает что у нас на бумажке в сейфе записано!
Публичный ключ и подпись строятся при взятии приватного ключа по модулю
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141

https://en.bitcoin.it/wiki/Private_key

То есть настрогать таких пар (и троек, и пятерняшек) я могу не глядя миллион.
Берем приватный ключ и добавляем к нему число
0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141
Вуаля!

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 12:56:24 PM

остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141?

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

при генерации мы в группе p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

n00by

member

Activity: 172

Merit: 11

Quote from: amaclin1 on February 26, 2019, 12:56:24 PM

Quote from: n00by on February 26, 2019, 12:36:01 PM

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая)

Оба ключа записаны в hex. Ключи разные. Числа в инт'е
115792089237316195423570985008687907853053774472357734211582463631972694901057
и
216210193282829828977300490454533406720

(подсказка: циклическая группа)

amaclin1

sr. member

Activity: 770

Merit: 305

Quote from: n00by on February 26, 2019, 12:36:01 PM

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Навскидку, потому что это не два ключа, а две разные записи одного и того же ключа (правильная запись вторая)
Что будет если взять остаток от деления первого числа на 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 ?
(можно просто вычесть столбиком - даже без калькулятора)
Лень считать, уверен на 100% что получится 0x00000000000000000000000000000000a2a8918ca85bb0000000000000000000

n00by

member

Activity: 172

Merit: 11

Да и еще немного накину матана вам в мозг.

Вот здесь https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=2ahUKEwiyjIvc-tngAhVpxIsKHf2EC9EQFjABegQICBAB&url=https%3A%2F%2Fistina.msu.ru%2Fdownload%2F18836198%2F1gCJiV%3A9tP1ODSVO_-fEn5MoWaXrXJJl8E%2F&usg=AOvVaw17vEKPcPZScYZ4jWRHDgJM диссертация к.м.н по криптографии, в которой есть сравнение сложности алгоритмов "зашифровать" для эллиптических кривых.

Так вот, по первым оценкам алгоритм "захешировать" гораздо сложнее.

n00by

member

Activity: 172

Merit: 11

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

Вот эти приватные ключи дают один и тот же публичный:

ffffffffffffffffffffffffffffffff5d576e7357a4503bbfd25e8cd0364141
и
00000000000000000000000000000000a2a8918ca85bb0000000000000000000

Почему так происходит оставлю вам в качестве домашнего задания (secp256k1).

Но могу привести кое-какие количественные оценки данного действа:
В подгруппе эллиптической кривой порядка биткоина может быть сгенерировано 2^131 степени таких ключей.
Сразу оговорюсь, что клиент их не генерирует, а вот сторонний софт вполне себе.

Ну и собственно их генерирует сеть (половина нулей слева дает хороший шанс попробовать найти привкей)

fxpc

sr. member

Activity: 1316

Merit: 420

KTO EC/\U HUKTO?

Quote from: A-Bolt on February 17, 2019, 06:31:20 PM

Quote from: fxpc on February 17, 2019, 02:30:41 PM

Что значит прокручивать версию блока в цикле? Придётся же заново пересчитывать первую часть для каждого потока.

Имеется в виду, что дешевле перебирать версию блока вместо ExtraNonce, потому как в случае перебора ExtraNonce нужно каждый раз вычислять ещё и корень дерева Меркла, а в случае перебора версии, корень дерева Меркла вычислять не требуется.

Перебор версии называют оvert AsicBoost, перетасовку транзакций с целью сохранения последних 4-х байт корня дерева Меркла называют соvert AsicBoost.

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

Topic: Математика и алгоритмы биткоина. - page 2. (Read 17585 times)