Как работает AsicBoost?

Документ AsicBoost Тимо Хэнке и Серхио Демьяном Лернером описывает способ увеличивая производительность ASIC на 20%. Тем не менее, он немного редок. Что они оптимизируют?

20 голосов | спросил Nick ODell 2 AMpSat, 02 Apr 2016 03:42:32 +030042Saturday 2016, 03:42:32

2 ответа


17

Введение

AsicBoost ускоряет разработку Bitcoin в целом (для ASIC и процессоров), уменьшая частоту вычисления одной части расчета SHA-256.

Заголовок блока биткойнов имеет длину 80 байтов. Он помещается в 2 блока для хеширования SHA-256. Он получает хеширование в 32-байтовое значение, затем снова хэширует (1 блок), чтобы получить окончательное значение, сравниваемое с порогом.

псевдокод

Традиционный способ добычи биткойнов выглядит следующим образом:

while True:
    blockHeader = ...  # based on Merkle root and other fields
    sha256Block0 = sha256Expand(blockHeader[0 : 64])
    midState = sh256Compress(sha256InitVector, sha256Block0)

    for i in range(2**32):  # Try nonces
        blockHeader.nonce = i
        sha256Block1 = padAndExpand(blockHeader[64 : 80])
        singleSha = sh256Compress(midState, sha256Block1)

        sha256Block2 = padAndExpand(singleSha)
        doubleSha = sh256Compress(sha256InitVector, sha256Block2)
        if doubleSha < target:
            miningSuccessful(blockHeader)  # Jackpot!

Обратите внимание, что внутренний цикл имеет 2 вычисления расширения блока и 2 вычисления сжатия блоков.

Теперь то, что предлагает AsicBoost, заключается в том, что мы как-то находим кучу значений blockHeader, где sha256Block0 отличается, но sha256Block1 - это то же самое. Поскольку поле корня Merkle охватывает оба блока хэширования, это означает, что нам нужно сгруппировать кандидатов по последним 4 байтам хеши Merkle. Теперь алгоритм интеллектуального анализа выглядит следующим образом:

while True:
    blockHeader = ...  # based on various fields
    candidates = dict()  # 4 bytes -> sets of blocks
    for i in range(...):  # Generate the more the merrier
        tempBh = blockHeader.randomizeMerkle()
        sha256Block0 = sha256Expand(tempBh[0 : 64])
        tempBh.midState = sh256Compress(sha256InitVector, sha256Block0)
        candidates[tempBh.merkleRoot[28 : 32]].add(tempBh)

    for i in range(2**32):  # Try nonces
        for key in candidates:
            tempBh = candidates[key][0]
            tempBh.nonce = i
            sha256Block1 = padAndExpand([64 : 80])

            for tempBh in candidates[key]:
                singleSha = sh256Compress(tempBh.midState, sha256Block1)
                sha256Block2 = padAndExpand(singleSha)
                doubleSha = sh256Compress(sha256InitVector, sha256Block2)
                if doubleSha < target:
                    miningSuccessful(blockHeader)  # Jackpot!

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

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

ответил Nayuki 5 AMpTue, 05 Apr 2016 06:22:24 +030022Tuesday 2016, 06:22:24
5

Я воспроизвожу цифры 2 и 3 из приведенной ниже статьи, чтобы предоставить альтернативную интерпретацию.

Рис. 2:

 Организация заголовка блока биткойнов

Рисунок 3:

 введите описание изображения здесь>> </a> </p>

<p> Исторически, майнинг состоит из внутреннего цикла (красного) и внешнего цикла (зеленый). Каждый из них проходит через внутренний цикл, а nonce увеличивается. Это затрагивает только Chunk 2 и вызывает повторное вычисление всех красных блоков. Вы можете сделать это только 4 миллиарда раз (2 ^ 32), прежде чем приступать к созданию дублированных результатов. В этот момент внешний контур настраивает компоновку данных блока для получения нового корневого поля случайных меркелей, и вы повторяете. </p>

<p> В этой реализации вам нужно выполнить 4 больших операции для каждого внутреннего цикла. При изменении корня merkle как части внешнего цикла вам нужно сделать еще 2 больших операции (зеленым) поверх нормального 4. Однако автор AsicBoost заметил, что при изменении значения корня merkle существует 1 : 2 ^ 32 вероятность того, что содержимое Chunk 2 не изменится, и в этом случае выход расширителя Chunk 2 тоже не изменится, поэтому мы можем пропустить повторное вычисление этого вычисления. </p>

<p> Ключ на этом этапе - <a href= проблема с днем ​​рождения . Прежде чем мы начнем добывать блок, мы можем вычислить несколько случайных корней merkle и найти коллизии (т. Е. Множественные корни merkle, у которых есть те же последние 4 байта или «хвост»), без необходимости оценивать где-нибудь около 2 ^ 32 корней merkle. Кроме того, предкоммутируйте значение, обозначенное «среднее состояние», связанное с каждым из этих разных корней merkle.

Наконец, это позволяет нам альтернативный способ генерировать новый дайджест без , увеличивающий значение nonce: повторное использование текущего значения Chunk 2, выбор нового корня merkle, который сталкивается с используемым в данный момент хвостом и обновлением «среднее состояние» со значением, связанным с этим корнем merkle (который мы вычислили ранее). Затем переоцените все красные блоки, за исключением Expander, прикрепленного к Chunk 2, так как мы не изменили значение Chunk 2 - это только три большие операции вместо обычных четырех.

Пример

Предположим, мы нашли 3 корня merkle, все они имеют один и тот же хвост и предварительно вычислили связанные с ними средние состояния (A, B, C). Наш цикл разработки выглядит примерно так:

  1. Установить nonce = 0, midstate = A (4 операции).
  2. Установите действия midstate = B ( 3 ).
  3. Установить midstate = C ( 3 ).
  4. Установить nonce = 1, midstate = A (4 операции).
  5. Установите действия midstate = B ( 3 ).
  6. ... И так далее.

Каждое столкновение с кластером merkle, которое вы прекомпопуете, экономит вас 2 ^ 32. Разверните операции, так как вы можете повторно использовать его во всех 2 ^ 32 nonces. Из-за проблемы с днем ​​рождения затраты на прекомпопуляцию этих столкновений составляют менее 2 ^ 32 за столкновение, поэтому это может быть чистая прибыль.

На практике вы получите несколько непересекающихся множеств встречных корней merkle, а не только 1 набор, показанный здесь. Таким образом, вы можете переходить через {A, B, C}, затем {D, E, F}, а переключение с C на D будет стоить нормальные 4 операции, потому что хвост изменился. Или вы можете подавать каждый непересекающийся набор на другое ядро ​​/чип шахтера.

ответил Ponkadoodle 28 AM00000030000004931 2017, 03:02:49

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132