Как мы можем доказать, что биткойн-блок всегда разрешим?

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

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

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

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

теперь предположим, что блок действительно всегда разрешим, могу ли я предположить, что для его решения достаточно использования 64-битного случайного целого числа? как насчет 32бит? или я должен использовать бесконечное целое число?

например, в проекте basiccoin:

код для подтверждения работы следующий:

    def POW(block, hashes):
    halfHash = tools.det_hash(block)
    block[u'nonce'] = random.randint(0, 10000000000000000000000000000000000000000)
    count = 0
    while tools.det_hash({u'nonce': block['nonce'],
                          u'halfHash': halfHash}) > block['target']:
        count += 1
        block[u'nonce'] += 1
        if count > hashes:
            return {'error': False}
        if restart_signal.is_set():
            restart_signal.clear()
            return {'solution_found': True}
        ''' for testing sudden loss in hashpower from miners.
        if block[u'length']>150:
        else: time.sleep(0.01)
        '''
    return block

этот код рандомизирует число между [0, 1000000000000000000000000000000000000000000] в качестве начальной точки, а затем просто увеличивает значение одно за другим:

block[u'nonce'] += 1

Я не программист на Python, я не знаю, как Python обрабатывает тип целого числа. нет обработки целочисленного переполнения.

Я пытаюсь реализовать аналогичную вещь с С++, я не знаю, какое целое число может гарантировать решение.


bitcoin sha256 hash
person Bill Yan    schedule 21.10.2014    source источник
comment
Я не уверен, что понимаю ваш вопрос, но погрешность в выводе криптографических хэшей настолько мала, что не имеет значения для практических целей. Таким образом, вы можете считать, что существует 50% вероятность того, что любой бит криптографического хэша равен 0. Существует 25% вероятность того, что первые 2 бита равны нулю, 12,5% вероятности, что первые 3 бита равны нулю и т. д. Блок не имеет значения: вероятности не меняются. Что касается использования 64-битного целого числа, я не понимаю, как это может работать, видно, что, если я не ошибаюсь, сложность биткойнов, когда я пишу, уже требует больше, чем 64 первых бита, чтобы все были нулями...   -  person TacticalCoder    schedule 24.10.2014
comment
Спасибо за ваш ответ. что касается целого числа, я не спрашиваю о результате хеширования (да, оно больше 64 бит). Я говорил о вводе хеш-функции (это блок плюс случайное число).   -  person Bill Yan    schedule 25.10.2014
comment
Это отличный вопрос. Насколько я понимаю, вы спрашиваете: можно ли доказать, что всегда существует одноразовый номер, который приведет к хэшу ≤ сложности?   -  person Geremia    schedule 10.03.2015
comment
Только по истощению. k-SAT является NP-полным.   -  person thwd    schedule 03.04.2018

Ответы (1)


arrow_upward
0
arrow_downward

но как вы можете доказать, что распределение решений в блоке является четным (равномерным), чтобы вы действительно могли охватить все результаты хеширования?

SHA256 является детерминированным, поэтому, если вы повторно хешируете txns, он всегда будет предоставлять один и тот же хэш 256. Клиентские узлы хранят все txn и хэши в дереве merkle, чтобы сетевые клиенты могли распространять и проверять максимально длинную цепочку блоков.

Дерево Меркла — это основная структура данных для записи хэшей предыдущих блоков. Оттуда можно отследить цепочку подтверждений хэша от исходного (генезисного) блока.

person JCR000    schedule 07.12.2014