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

[amaclin1]

Это не уравнение. к - это точка на эл.кривой.

Да ну прям.
Это ж скаляр, а не вектор. Так что ну никак это не точка на кривой.
По смыслу - это то же самое, что приватный ключ.

Обратная ей точка это координата y с противоположным знаком.

Не. Ну откуда же это обратная по игрек? Это в минус первой степени. То есть k * k^-1 = 1
Вот вам код на скорую руку:

Code:

static void test ( )
{
  const MyKey32 k ( MyKey32::brain ( "correct horse battery staple" ) );
  qDebug ( ) << "k=" << k.toStringRev ( );
  const MyKey32 k1 ( MyKey32::inv ( k ) );
  qDebug ( ) << "k1=" << k1.toStringRev ( );
  const MyKey32 m ( MyKey32::mul ( k, k1 ) );
  qDebug ( ) << "m=" << m.toStringRev ( );
}

вот такой результат дает исполнение этого кода:

Code:

k= "c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a"
k1= "29e775d4509f0844eb5ee81fd21bc408c2e1f791edb1436fe0e2ad4b3285ee2c"
m= "0000000000000000000000000000000000000000000000000000000000000001"

[kzv]

А как работает функция MyKey32::inv ( k ) ?

k это не точка, но ее можно рассматривать как одну из координат точки (x или y). По сути да, k это второй приватный ключ. Когда k умножаем на G то получаем точку, которая по сути то же самое что второй публичный ключ.

Я вот тут еще поизучал либы и понял, что многие статьи безбожно пиздят про то, как публичный ключ связан с адресом.
Тут https://bits.media/bitcoin-address-theory/ и еще в паре мест видел, что
адрес = "1" + ripemd160(sha256("04" + x + y)) + чексумма

На самом деле правильная формула
адрес = "1" + ripemd160(sha256(("02" || "03") + x)) + чексумма

То есть хэшируется не полный публичный ключ, а только его первые 32 байта плюс 2 или 3, то есть публичный ключ в compressed-формате.

Проверка. Берем первую попавшуюся транзакцию из блокчейна
http://chainquery.com/bitcoin-api/getrawtransaction/25e442d4413ed5d013af38b5c9538fda3a9a38ab9c85dfb7d1778d282da26a34/1

            "scriptSig": {
               "asm": "3045022100ceb27a63c2d831c4db72be3b6447cb844aa2d891c05fb1fbe871d82335b0c2cc02204 020c58ea9c84149d59aa3451c6436d226f806a1f92496859f123593a64ebe04[ALL] 039ba9494f5ec12628aec689ea46ce4cb14e2d828e1c317640612aec0f748c4d1e",
               "hex": "483045022100ceb27a63c2d831c4db72be3b6447cb844aa2d891c05fb1fbe871d82335b0c2cc022 04020c58ea9c84149d59aa3451c6436d226f806a1f92496859f123593a64ebe040121039ba9494f 5ec12628aec689ea46ce4cb14e2d828e1c317640612aec0f748c4d1e"
            },

[amaclin1]

А как работает функция MyKey32::inv ( k ) ?

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

Code:

//  static const MyKey32 inv ( const MyKey32& s );

const MyKey32 MyKey32::inv ( const MyKey32& s )
{
  BIGNUM* _r = BN_new ( );
  BIGNUM* _s = BN_bin2bn ( s.constPtr ( ), 32, BN_new ( ) );
  BN_CTX* _c = BN_CTX_new ( );
  BN_mod_inverse ( _r, _s, bn_order, _c );      // обратная величина
  MyKey32 r;
  BN_bn2bin ( _r, r.ptr ( ) + ( 32 - BN_num_bytes ( _r ) ) );
  BN_CTX_free ( _c );
  BN_free ( _s );
  BN_free ( _r );
  return r;
}

[amaclin1]

То есть хэшируется не полный публичный ключ, а только его первые 32 байта
плюс 2 или 3, то есть публичный ключ в compressed-формате.

Есть приватный ключ.
Можно сделать публичный ключ (вектор).
Этот публичный ключ можно записать в стандартизированном представлении [как минимум] двумя способами.
Можно записать обычным способом 04 + x + y
Moжно записать компрессированным способом 02/03 + x

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

Поэтому сейчас [почти] все юзают именно компрессированные публичные ключи.
В вики написано все верно.

[kzv]

В вашем коде надо дальше копать функцию BN_mod_inverse ( _r, _s, bn_order, _c )
Я вобщем сам нарыл уже, что мультипликативная инверсия по модулю может быть найдена двумя способами:
1. Полный перебор
2. Расширенный алгоритм Евклида.

Про перебор понятно, что не наш случай. На досуге почитаю про Евклида. )

ЗЫ про compressed ключи понял. Спасибо.

[amaclin1]

В вашем коде надо дальше копать функцию BN_mod_inverse ( _r, _s, bn_order, _c )

Ну это из модуля BigNumber библиотеки OpenSSL
https://man.openbsd.org/BN_mod_inverse.3

В такие базовые функции я уже не вдавался - сделал себе класс-обёртку MyKey32
напихал туда всё что использую и забыл. Как она считает там внутре k^-1
- это я не знаю. Видимо, не самая сложная операция. Про алгоритм Евклида я краем
уха слышал, но экзамен по этому вопросу завалю.

То есть переехать на lib_secp256k1 я не против, изменения коснутся только "потрохов".
Но как-то не сложилось. Под вендой не хочет нормально компилироваться, а к линуксам
я не очень привычный.

[kzv]

Да мне чисто академический интерес.
Для дела я на node.js насобачился кодить. Там 100500 либ готовых есть и компилировать не надо париться )

[lolobit2]

Доброго . можно немного оффтопа в академические тёрки.
https://bitcointalk.org/index.php?topic=963373.0
этот эксперимент кто смог повторить?
буду рад любым мыслям

[kzv]

Доброго . можно немного оффтопа в академические тёрки.
https://bitcointalk.org/index.php?topic=963373.0
этот эксперимент кто смог повторить?
буду рад любым мыслям

Что-то сомнительный эксперимент имхо. Ибо

сообщения и транзакции клиент биткоина тоже подписывает по разному...
Перед тем как хэшировать сообщение, к сообщению добавляется "магическая фраза" типа "Bitcoin signed message\n". А перед тем как хэшировать транзакцию никаких магических фраз не добавляется. Думаю это такая защита для дурака: чтобы никто не мог с помощью кошелька вместо сообщения подписать транзакцию ))

[amaclin1]

Интересно искать вещи в интернете.
Главное - правильно вопрос сформулировать ( это 75% успеха )
Я вот задал в поиске "compressed public keys site:bitcointalk.org" - так вообще кладезь знаний.

Например, компрессированные ключи появились в версии 0.6.0
https://bitcointalk.org/index.php?topic=74737.0

Про префиксы публичных ключей тут:
https://bitcointalk.org/index.php?topic=42384.0
Там главная фраза "Correct. The public key format is managed by OpenSSL, bitcoin treats it as a black box."
Потом уже решили что зависеть от OpenSSL нельзя.

Кто впервые увидел, что публичный ключ в имплементации от Сатоши можно заменить на компрессированный -
пока найти не могу. Точно видел этот топик несколько лет назад. Но тогда проще по форуму было искать.

[amaclin1]

сообщения и транзакции клиент биткоина тоже подписывает по разному...
Перед тем как хэшировать сообщение, к сообщению добавляется "магическая фраза" типа "Bitcoin signed message\n". А перед тем как хэшировать транзакцию никаких магических фраз не добавляется. Думаю это такая защита для дурака: чтобы никто не мог с помощью кошелька вместо сообщения подписать транзакцию ))

Да, да и еще раз да.

Code:

const std::string strMessageMagic = "Bitcoin Signed Message:\n";

Иначе говоря, для абы-какой технологии тут возможна утечка. Но в биткойне эту дырку заштопали намертво.

[fxpc]

Я тут почитал про цифровую подпись еще. Подписывание сообщение у большинства нормальных людей проходит следующим образом...

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков. На js подписывание с использованием ECC в ~2.3 раза быстрее верификации.
https://github.com/indutny/elliptic
Хотелось бы узнать производительность на кодовой базе биткоина.

Доброго . можно немного оффтопа в академические тёрки.
https://bitcointalk.org/index.php?topic=963373.0
этот эксперимент кто смог повторить?
буду рад любым мыслям

Что-то сомнительный эксперимент имхо. Ибо

сообщения и транзакции клиент биткоина тоже подписывает по разному...
Перед тем как хэшировать сообщение, к сообщению добавляется "магическая фраза" типа "Bitcoin signed message\n". А перед тем как хэшировать транзакцию никаких магических фраз не добавляется. Думаю это такая защита для дурака: чтобы никто не мог с помощью кошелька вместо сообщения подписать транзакцию ))

Про клиент биткоина в топике речи не идёт. Скорее всего в онлайн кошельках дыра не заштопана или была не заштопана и доверчивый хомяк подписывал транзакцию по переводу некой суммы на адрес злоумышленника.

[amaclin1]

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков.

Зависит от имплементации.
Тут некий trade-off между потреблением памяти, временем старта и скоростью присутствует.
Если говорить про либу secp256k1 - ну попробуй собрать https://github.com/bitcoin-core/secp256k1
Там есть вроде бенчмарки. И даже с OpenSSL можно сравнить

[kzv]

Про клиент биткоина в топике речи не идёт. Скорее всего в онлайн кошельках дыра не заштопана или была не заштопана и доверчивый хомяк подписывал транзакцию по переводу некой суммы на адрес злоумышленника.

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

[fxpc]

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков.

Зависит от имплементации.
Тут некий trade-off между потреблением памяти, временем старта и скоростью присутствует.
Если говорить про либу secp256k1 - ну попробуй собрать https://github.com/bitcoin-core/secp256k1
Там есть вроде бенчмарки. И даже с OpenSSL можно сравнить

Было бы интересно узнать какой прирост производительности подписывания при увеличении потребления памяти и времени старта, но к сожалению, не осилю. Как думаешь, оптимизирован ли вообще алгоритм подписывания в либе битка? Bottleneck в скорости верификации и могли остановиться на её оптимизации, вроде ни у кого нет необходимости в подписывании 100500 транзакций в секунду.

Про клиент биткоина в топике речи не идёт. Скорее всего в онлайн кошельках дыра не заштопана или была не заштопана и доверчивый хомяк подписывал транзакцию по переводу некой суммы на адрес злоумышленника.

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

Вероятность есть, там ещё те рукожопы. Возможно атакующему нужен был публичный ключ жертвы для вычисления из него и неслучайного значения R приватного ключа. Онлайн кошельки регулярно факапятся с RNG. Имхо, помогло бы даже подмешивание к кривому RNG каких-то пользовательских хешей от хешей, но это не точно. Удивляет что рукожопы не додумались даже до этого, полностью положившись на RNG.
https://www.coindesk.com/hacker-returns-225-btc-taken-blockchain-wallets
https://99bitcoins.com/blockchain-info-wallet-users-get-stolen-service-patched-the-bug-and-assures-it-will-refund-everyone/

[n00by]

Это не уравнение. к - это точка на эл.кривой.

Да ну прям.
Это ж скаляр, а не вектор. Так что ну никак это не точка на кривой.
По смыслу - это то же самое, что приватный ключ.

Да, сорри. Пьяный был)

[vitvert]

Насколько подписывание быстрее или медленнее алгоритма проверки подписи? Нигде не могу найти бенчмарков.

Зависит от имплементации.
Тут некий trade-off между потреблением памяти, временем старта и скоростью присутствует.
Если говорить про либу secp256k1 - ну попробуй собрать https://github.com/bitcoin-core/secp256k1
Там есть вроде бенчмарки. И даже с OpenSSL можно сравнить

Про клиент биткоина в топике речи не идёт. Скорее всего в онлайн кошельках дыра не заштопана или была не заштопана и доверчивый хомяк подписывал транзакцию по переводу некой суммы на адрес злоумышленника.

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

Ребят, человеку с уровнем знаний математики на уровне 8 класса сколько лет осталось изучать сей предмет, чтобы понимать все, что вы тут пишите? При условии, что в день есть только 1 час на это дело

[kzv]

Я тут на досуге поэкспериментировал с нахождением sha256 от чисел. Получил интересные результаты
Если посчитать все хэши чисел от 1 до 1 000 000, то среди них будут:

62326 хэшей у которых один или больше нулей в начале, среднее число переборов = 16, при этом в 64.3% случаев, требуемое число переборов меньше среднего

3855 хэшей у которых два или больше нулей в начале, среднее число переборов = 259, при этом в 62.4 % случаев, требуемое число переборов меньше среднего

248 хэшей у которых три или больше нулей в начале, среднее число переборов = 3993, при этом в 59.3 % случаев, требуемое число переборов меньше среднего

23 хэша у которых четыре нуля в начале, среднее число переборов = 42065, при этом в 69.6 % случаев, требуемое число переборов меньше среднего


Таким образом оказалось, что решения с заданной сложностью распределены неравномерно. Значит sha256 не дает нормального распределения? Можно ли эту особенность использовать как преимущество в майнинге?
Сейчас на слуху какой-то супер секретный алгоритм асик буст. Кто что про него знает? Я ничего толкового нагуглить не могу.

[investgroup]

Я тут на досуге поэкспериментировал с нахождением sha256 от чисел. Получил интересные результаты
Если посчитать все хэши чисел от 1 до 1 000 000, то среди них будут:

это на одинарной или двойной SHA?

В майнинге двойная(то есть SHA(SHA(x)) ) - если не трудно, то проверьте то-же самое на двойной?..

[amaclin1]

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

Равномерно они будут распределены на значительно больших выборках, чем 1м
То, что у тебя получилось не 256, а 259 - это в порядке вещей, потому что выборка была маленькая
Флуктации рандома, так сказать