Bitcoin Forum

Local => Кодеры => Topic started by: Wizard109 on September 06, 2011, 08:05:52 AM



Title: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 08:05:52 AM
Интересует собцтвенно сабж. Извиняюсь если где-то уже разжевано, не нашел :(

Из того что есть:
1) Высосанный из пальца (найденный в исходниках :) ) алгоритм. Звучит так: "Взять 80 байт из data, в конце 4 байта нулей заменить nOnce'ом, получить из этих 80 байт sha256 и потом sha256 из полученного хеша. В результате должны быть нули в конце/начале(пофиг, нет ни-там ни-там) этого хеша количество/маска которых определяется target'ом"
2) Проблема: "блин я их уже и переворачивал под разными углами менял dword'ы обращал байты и бегал с шаманским бубном а нулей нету нигде !"
3) То на чем тренируюсь, т.е. подставляю nOnce 0x3f83a747 (вроде - как подобранный хеш, поправьте если не так):
Quote
Server: nginx/1.0.4
Date: Tue, 30 Aug 2011 23:11:04 GMT
Content-Type: application/json; charset=utf-8
Connection: keep-alive
X-Host-List: [{"host":"f1.deepbit.net","port":8332,"ttr":0},{"host":"f2.deepbit.net","port":8332,"ttr":10}]
Expires: Tue, 30 Aug 2011 23:10:56 UTC
Content-Length: 593
Cache-Control: no-cache, private, no-store
Pragma: no-cache
X-Long-Polling: /listenChannel
X-Lift-Version: 2.3

{"result":{"midstate":"7598823b94e6048777a5f455d4fc04789fefb53fd3bf889b81b66235ef793ab6","data":"0000000195aceed772ae59178621bfd3079e20b50c9681a6c1fed72900000605000000007db50c1 ed21f3c24394105aa1a0e50a9352c7eee7e36423fc8d38be1e45383ea4e5d6ddb1a096fe3000000 0000000080000000000000000000000000000000000000000000000000000000000000000000000 0000000000080020000","hash1":"0000000000000000000000000000000000000000000000000000000000000000000000800000000 0000000000000000000000000000000000000000000010000","target":"ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000"},"error":null,"id":"1"}POST / HTTP/1.1
Connection: Keep-Alive
Content-Length: 302
Host: pit.deepbit.net:8332
Content-Type: application/json
Authorization: Basic Z29wb2NvZGVyQHlhbmRleC5ydV8wOmhndGg=
User-Agent: phoenix/v1.6.2

{"params": ["0000000195aceed772ae59178621bfd3079e20b50c9681a6c1fed7290000060500000000ccb1b4d 570c89f509d6196fad47dc91cd648bd2dbb08dac13d9860cf95ac8d584e5d6dd91a096fe33f83a7 4700000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000"], "method": "getwork", "id": 1}HTTP/1.1 200 OK
Server: nginx/1.0.4
Date: Tue, 30 Aug 2011 23:15:50 GMT
Content-Type: application/json; charset=utf-8
Connection: keep-alive
X-Host-List: [{"host":"f1.deepbit.net","port":8332,"ttr":0},{"host":"f2.deepbit.net","port":8332,"ttr":10}]
Expires: Tue, 30 Aug 2011 23:15:42 UTC
Content-Length: 37
Cache-Control: no-cache, private, no-store
Pragma: no-cache
X-Long-Polling: /listenChannel
X-Lift-Version: 2.3

{"result":true,"error":null,"id":"1"}


Title: Re: Алгоритм майнинга
Post by: ArsenShnurkov on September 06, 2011, 08:29:58 AM
Quote
подставляю nOnce 0x3f83a747

насколько я понимаю (https://en.bitcoin.it/wiki/FAQ#What_is_mining.3F), идея в том, чтобы подбирать (увеличивать на 1) nOnce так, чтобы нули в сумме суммы появились


Title: Re: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 08:33:09 AM
Тот что подставляю по идее подобранный. Потому и подставляю, чтоб проверить работоспособность и увидеть нули вживую :)


Title: Re: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 08:34:38 AM
За ссылку спасибо кстате. Сколько лазил - такого источника еще не находил


Title: Re: Алгоритм майнинга
Post by: Lis on September 06, 2011, 08:40:05 AM
# находим хеш заголовка блока
example http://blockexplorer.com/block/00000000000271de9d8b94afff543366e290e995f3e3e337bb86a0b7bf02e8d1

Code:
echo 010000008d42cab4b755d6e9f01ffe2d1ec8391325dfa2e1a8dc584ec0480100000000001d4575ddc877b25dd9b91284cedec424fbc7a583964f223ef8c4707410bcfe72614a574d5285021b0dd2aa13 | xxd -r -p | sha256sum -b | xxd -r -p | sha256sum -b
получим перевернутый результат хеша блока d1e802bfb7a086bb37e3e3f395e990e2663354ffaf948b9dde71020000000000
заголовок блока разбираем на запчасти
"ver revers" 01000000
"prev_block revers" 8d42cab4b755d6e9f01ffe2d1ec8391325dfa2e1a8dc584ec048010000000000
"mrkl_root revers" 1d4575ddc877b25dd9b91284cedec424fbc7a583964f223ef8c4707410bcfe72
"time revers" 614a574d
"bits(~target) revers" 5285021b
"nonce revers" 0dd2aa13

revers значит перевернут побайтно "nonce revers" 0dd2aa13 => 13aad20d


Title: Re: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 09:12:03 AM
Эээээ.... ммммм.... может я как-то поподробнее...

От сервера получаю:

Quote
midstate
data
hash1
target
Насколько я понимаю midstate какбэ... не особо нужен, hash1 тоже (ну тоесть они может и нужны но необязательны).
Основные поля: data и target.

Что я делаю с data:
Отрезаю первые 80 байт и заменяю nOnce'ом. nOnce подбирается, но для проверки юзаю подобранный.
Получаю первый хеш из 80 байт поля data, а из него второй, из #длина_хеша получившегося хеша, короче:

Quote
char Hash[HASH_SIZE];
Sha256.GetHash(sha2::enuSHA256, (sha_byte*)&Data, sizeof(Data));
const char *RawHash = Sha256.RawHash(dwHashLen);
memcpy(&Hash, RawHash, dwHashLen);
Sha256.GetHash(sha2::enuSHA256, (sha_byte*)&Hash, dwHashLen)

Тест провален. Мои результаты:
1) Прямой порядок байт в Data:
Quote
Hash1: 428b17dba1e66bc6396657fb251d210e392c46fa733b56a113e0b275eeda5ffa
Hash2: 1c06b25d3ec4c14a7cccb1b46df152261894fb1e741dd7be09cf3dd939ba92b8
2) Обратный порядок байт в Data:
Quote
Hash1: 86a122e771252b18f0a7c587305b171fe733eb5dcd848aadc42606c519bff7b4
Hash2: 59febd6e8cf7318509fc3c38887b7e8341905338c2766b6eab7aa9c0307bfe58


Title: Re: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 11:17:00 AM
Хм. Почти два дня угробил на глупость.
Тот тест что я постил выше... ээээ... наверное не работает или тут как-то замешан midstate и иже с ним

Я много наслушался размышлений в стиле "чего - как попробовать попереворачивать", но...
Вобщем странникам идущим путем дзена предлагается решение:

Действительно нужно взять первые 80 байт от data. Потом нужно в цикле брать dword и "переворачивать". Нпример строка 0102030405060708 становится 0403020108070605. В конце должно быть какое-то количество нулей, их и нужно подбирать (так называемый nOnce). Собственно алгоритм простейший. Берешь data, нули которые есть в конце заменяешь своими значениями (0x00..0xffffffff) и делаешь два хеша: хеш из данных и хеш из хеша. Себе я добавил данные типа firstnonce и lastnonce чтобы перебирать в определенном диапазоне. В текущих тестовых данных firstnonce сразу же дает профит:

Quote
MyHASH1: 8d621e9e0ae4b0e4b1124ffde910a264bf97ecae507616b6a3b2d367cc676b60
MyHASH: ad488916f30ea7f25f8ef9659af7904c71dc58be13db5bb4a4feba5300000000


Тестовые данные (midstate, hash1 и пр. отбалды ибо я их не юзаю пока. Нужны только data и target):
Quote
#define BITCOIN_TEST_DATA "{\"id\": \"26fffdfe-3890-11e0-8d10-fefd6d4ac335\", \"result\": {\"hash1\":\"0000000000000000000000000000000000000000000000000000000000000000000000800000000 0000000000000000000000000000000000000000000010000\", ""\"data\": \"00000001e5b5979c98525e7bdde6bc8a4ba5d64ac0acbd7f501f474500000a0b00000000391393c 3c94aacbb837347074f6e4fd62aa861536b1db5404f4a8441e214c29e4e051fdb1a0c2a12000000 0000000080000000000000000000000000000000000000000000000000000000000000000000000 0000000000080020000\", ""\"midstate\": \"7598823b94e6048777a5f455d4fc04789fefb53fd3bf889b81b66235ef793ab6\", ""\"target\": \"ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000\", \"firstnonce\":\"1734B7F4\", \"lastnonce\":\"1734B837\"}, \"error\": null}"


Title: Re: Алгоритм майнинга
Post by: Lis on September 06, 2011, 12:25:47 PM
UPDATE

сделал дамп решения вот что вышло:

я получил задание на поиск блока 144209
Code:
{u'hash1': u'00000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000010000', u'data': u'0000000159239d7d15fac20cd745a8216f73f3b3202522f1b73e49f0000009150000000073bb4e72c484cc9572356f0fe3fefd084d52e1f62c8b2cbf1ac1d40c49c054124e661e491a096fe300000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000', u'midstate': u'1bc7b4a768a626fbe999a4ff3959026384860d624123bb03e1156c521378c717', u'target': u'ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000'}

на что мой майнер ответил
Code:
0000000159239d7d15fac20cd745a8216f73f3b3202522f1b73e49f0000009150000000073bb4e72c484cc9572356f0fe3fefd084d52e1f62c8b2cbf1ac1d40c49c054124e661e491a096fe32e6b0a1d000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

как ты и сказал самое главное это "data"
парсим:
Code:
полученное задание
00000001 версия блока
из частичек 59239d7d 15fac20c d745a821 6f73f3b3 202522f1 b73e49f0 00000915 00000000 собираем 0000000000000915b73e49f0202522f16f73f3b3d745a82115fac20c59239d7d что есть хеш блока 144208
73bb4e72 c484cc95 72356f0f e3fefd08 4d52e1f6 2c8b2cbf 1ac1d40c 49c05412 Merkle root пересоберем так же в 49c054121ac1d40c2c8b2cbf4d52e1f6e3fefd0872356f0fc484cc9573bb4e72
4e661e49 date (hex unix format)
1a096fe3 Difficulty он же Bits
00000000 Nonce
000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

отправленное решение
00000001 версия блока
59239d7d15fac20cd745a8216f73f3b3202522f1b73e49f00000091500000000
73bb4e72c484cc9572356f0fe3fefd084d52e1f62c8b2cbf1ac1d40c49c05412
4e661e49 date (hex unix format)
1a096fe3 Difficulty он же Bits
2e6b0a1d Nonce
000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000

из полученных данных собираем строку которую будем дабхешить
Code:
01000000 версия блока (revers)
7d9d23590cc2fa1521a845d7b3f3736ff1222520f0493eb71509000000000000 хеш предыдущего блока (revers)
724ebb7395cc84c40f6f357208fdfee3f6e1524dbf2c8b2c0cd4c11a1254c049 Merkle root (revers)
491e664e date (hex unix format) (revers)
e36f091a Difficulty он же Bits (revers)
1d0a6b2e Nonce (revers)

полученное дабхешим
Code:
echo 010000007d9d23590cc2fa1521a845d7b3f3736ff1222520f0493eb71509000000000000724ebb7395cc84c40f6f357208fdfee3f6e1524dbf2c8b2c0cd4c11a1254c049491e664ee36f091a1d0a6b2e | xxd -r -p | sha256sum -b | xxd -r -p | sha256sum -b

получаем
Code:
74d934fa48604f6f8132e790e3f6886002141d14a1d5993768987ae400000000
и если это число перевернуть оно меньше перевернутого заданного target
Code:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000

т.е. 00000000e47a98683799d5a1141d14026088f6e390e732816f4f6048fa34d974 < 00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff


Title: Re: Алгоритм майнинга
Post by: Lis on September 06, 2011, 02:48:05 PM
перенесите тему плз к кодерам


Title: Re: Алгоритм майнинга
Post by: Wizard109 on September 06, 2011, 05:43:38 PM
Ок. Идем дальше, кто знает что есть hash1 и midstate ?
Я просто ближе к кернел-девелопменту чем к математике и.т.п.

Готовые кодесы есть конечно... первая стадия - прикрутить такой кодес (поэтому интересно, их тоже нужно по'dword'но приводить к юзабельному виду ?) но вообще-то хотелось бы разобраться.


Title: Re: Алгоритм майнинга
Post by: Lis on September 06, 2011, 06:30:16 PM
Ок. Идем дальше, кто знает что есть hash1 и midstate ?
Я просто ближе к кернел-девелопменту чем к математике и.т.п.

Готовые кодесы есть конечно... первая стадия - прикрутить такой кодес (поэтому интересно, их тоже нужно по'dword'но приводить к юзабельному виду ?) но вообще-то хотелось бы разобраться.
увы я пока далее не продвинулся =(


Title: Re: Алгоритм майнинга
Post by: yo-blin on January 17, 2012, 11:41:35 AM
Вот чего я не понял
Пулл сразу уже знает какой № блока он майнит ?


Title: Re: Алгоритм майнинга
Post by: LZ on January 17, 2012, 01:29:42 PM
В каждом блоке есть хеш предыдущего блока. Это цепочка.


Title: Re: Алгоритм майнинга
Post by: yo-blin on January 17, 2012, 01:35:47 PM
созданного тем же самым пуллом ?


Title: Re: Алгоритм майнинга
Post by: LZ on January 17, 2012, 03:13:30 PM
Любым пулом или соломайнером. Если будет создано два блока с одинаковым
хешем предыдущего блока, то в цепочке сохранится только тот блок, с хешем
которого будет создан следующий, то есть эта цепочка будет сильнее другой.
Трансакции же из мертвой цепочки не пропадут, а будут занесены в сильную
цепочку, по крайней мере - если сплит сети не длился дольше 100 блоков. :)

Если нужны технические подробности, то рекомендую изучить код PyMiner (https://github.com/jgarzik/pyminer). :)


Title: Re: Алгоритм майнинга
Post by: btcsec on January 25, 2012, 04:55:10 PM
http://bitcoinmedia.com/proof-of-work-exposed/ кто что думает?


Title: Re: Алгоритм майнинга
Post by: Ninazu on February 23, 2012, 03:33:34 PM
Что-то прояснилось по поводу midstate и hash1?

Code:
this.tryHash = function(midstate, half, data, hash1, target, nonce){  
    data[3] = nonce;
    this.sha.reset();

    var h0 = this.sha.update(midstate, data).state;   // compute first hash
    for (var i = 0; i < 8; i++) hash1[i] = h0[i];   // place it in the h1 holder
    this.sha.reset();                 // reset to initial state
    var h = this.sha.update(hash1).state;       // compute final hash
    if (h[7] == 0) {
      var ret = [];
      for (var i = 0; i < half.length; i++)
        ret.push(half[i]);
      for (var i = 0; i < data.length; i++)
        ret.push(data[i]);
      return ret;
    } else return null;
  };

Вот такую штуку нарыл. Может она сможет разъяснить


Вопрос номер 2.
Если допустим считать хеш отнимая Nonce. От FFFFFFFF ->0. Мы найдём решение которое удовлетворит маску. Примет ли его система? Ведь по сути оно будет больше чем решение которое найдёт другой майнер, который будет считать от нуля


Title: Re: Алгоритм майнинга
Post by: Lis on February 24, 2012, 06:52:54 AM
Вопрос номер 2.
Если допустим считать хеш отнимая Nonce. От FFFFFFFF ->0. Мы найдём решение которое удовлетворит маску. Примет ли его система? Ведь по сути оно будет больше чем решение которое найдёт другой майнер, который будет считать от нуля
сравнивается не nonce а хеш если твой хеш найден быстрее или он сильнее (значительно меньше target) то сеть примет твой блок. Nonce можно перебирать хоть методом random()


Title: Re: Алгоритм майнинга
Post by: SHawk on March 15, 2012, 08:54:42 PM
Что-то прояснилось по поводу midstate и hash1?



Алгоритм хэширования работает с блоками по 512 бит. Результат хеширования - 256 бит. Алгоритм спроектирован так, что каждый блок он обрабатывает последовательно, модифицируя при этом хэш, накопившийся от обработки предыдущих блоков.
Поскольку перебираемый нонс находится в последнем блоке, то нет смысла для каждого нонса хешировать все с самого начала. Хэшируется только последний блок (data), в который вставляется каждый раз новый нонс. А вот результат хэширования всех предыдущих блоков передается майнеру в поле midstate. Именно это значение используется для инициализации хэш-функции на первой итерации перебора, что эквивалентно повторению процедуры хеширования от начала данных...


Title: Re: Алгоритм майнинга
Post by: Balthazar on April 07, 2012, 08:49:49 AM
midstate и hash1 это deprecated параметры и сегодня они не используются, передаются для совместимости.


Title: Re: Алгоритм майнинга
Post by: DeepBit on April 08, 2012, 08:32:45 AM
midstate и hash1 это deprecated параметры и сегодня они не используются, передаются для совместимости.
Они не необходимы, но всё же иногда используются.
Могут быть полезными для FPGA-майнинга, например. Хотя их можно и на клиентской стороне получить.


Title: Re: Алгоритм майнинга
Post by: MadF on January 21, 2014, 01:51:33 PM
Добрый день, Господа.

Пробовал по вашим исследованиям создать/повторить алгоритм расчета litecoin - не удалось (много вопросов).
Удалось до конца отработать алгоритм?

зы: без влезание в JSON.
зы2: мне это нужно для понятия сколько ресурсов требуется, чтобы потом (возможно) сделать всё это аппаратно.


Title: Re: Алгоритм майнинга
Post by: hazarun on January 21, 2014, 08:35:05 PM
Удалось до конца отработать алгоритм?

Присоединяюсь к вопросу. Тема, довольно интересна.


Title: Re: Алгоритм майнинга
Post by: strelok369 on January 22, 2014, 08:42:35 AM
hash1 и midstate. Для лайта не знаю (точнее там в начале scrypt'а тоже SHA256), в чистом sha256:
"Первые 80 байт"(а надо их из сетевого порядка в человеческий перевернуть) это 640 бит, в sha256 можно затолкать
512 (с учетом правила дополнения сообщений в конце последнего куска по 512бит должна быть длина, то есть если
имеем 512 бит сообщения, то полный "конвеер"(да я делал конвеером, им понятнее, но пришлось делать классикой
по 3раунда последовательно, тк ни в одну FPGA не влезло)) надо прогонять 2 раза: первый 512бит сообщения, второй 1 в начале и длина (512) в конце.
Обратно на землю. 640 бит это 512 + 128, причем мы меняем только последние 32 из тех 128, дальше 1 и "640длина" в конце.
Таким образом hash1 это результат sha256 после первого прогона(первые 512бит), чтобы получить хэш сообщения
надо допрогнать еще один проход(128бит_"1"0000....0000"640"). То есть hash1 не нужен, тк есть midstate.
Ну и собственно вопрос а что нам мешает считать второй прогон только с места где мы меняем nounce, а не с начала?
А ничего. Вот midstate и будет являться тем самым состоянием в конце постоянной части.
То есть если мы используем midstate, то нам надо прогнать sha256 1,8125 раза вместо 3 раз, когда мы меняем nounce.
К сожалению формат midstate не знаю, всегда считал его отдельно.

На своем игрушечном майнере на спартане 3 никогда не майнил, но блоки он "находил" уже найденные,
я кормил его найденными блоками с blockchain.info и проверял, найдет ли он нужный nounce, было 1-2Мх/с с 30МГЦ.
Делал летом, со злости распаял взапчасти.

тьфу все зря написал, уже было, всеравно запощу.


Title: Re: Алгоритм майнинга
Post by: MadF on January 24, 2014, 06:28:53 AM
Спасибо.

Но как-то всё сумбурно/эмоционально написано, что ничего не понятно. Я ожидал четко, по полочкам разложенного ответа (мы же тут не стихи пишем). Видимо тема не актуальна.


Title: Re: Алгоритм майнинга
Post by: strelok369 on January 27, 2014, 12:21:29 PM
Ну преподавание для меня никогда не было особо приоритетным навыком.
Без эмоций можно разобраться вот с этим:
http://ru.wikipedia.org/wiki/SHA-2 (http://ru.wikipedia.org/wiki/SHA-2) про SHA256, я разбирался с Биткоинами,
поэтому SHA256, он не лишний, scrypt им "пропитан". Советую нарисовать схему
полного SHA256, если хочется "понять" его до оптимизации, моя склеена из листов А4 - 5 метров.

/**************************OFF************************************/
Пошел против SHA256 "алгеброй" вместо статистики(уже как месяца 3). Вчера получил
уравнение для самого длинного "пути" в раунде(a=t1+t2), искал решение "запакованным" т.е. со
скобками и минимальной длинной в модифицированной (для слов вместо битов, паршиво
модифицированной) алгебре Жегалкина. Весит гадость 300МБ текста и не в какую не
решается, хочу для двух раундов построить и поискать межраундную характеристику
по Wi, кажись ничего не получится, надо софтину заново переписывать чтоб диск загадить
вместо оперативы - выделение из свопа ужасно, оптимизировать (32ГБ как слону дробина),
все равно не решится, в лом.
К проблемме майнинга на калькуляторе и как успеть найти блок без асика,
чтобы все думали, что асик был.
/**************************OFF************************************/

Про то, что плюет тебе GETWORK и как перевернуть порядок байт написано тут:
https://en.bitcoin.it/wiki/Getwork (https://en.bitcoin.it/wiki/Getwork) , про stratum не знаю, не интересовался.

Если умеешь читать C#, почитай тут:
https://github.com/lithander/Minimal-Bitcoin-Miner (https://github.com/lithander/Minimal-Bitcoin-Miner) 316 строк
Майнить на нем бестолку, но понять, что там и как, можно.