Другими словами, какова вероятность того, что Боб солгал о корне Меркла после N запросов?
Что ж, вот один из способов, которым Боб мог сжульничать; он мог взять список $ млн $ ценности $$V_1, V_2, ..., V_M$$ и вместо того, чтобы формировать на его основе дерево Меркла, выберите значение $с$ индекс и значение $V'_c \ne V_c$, а вместо этого сформируйте список $$V_1, V_2, ..., V_{c-1}, V'_c, V_{c+1}, ..., V_M$$ и сформировать дерево Меркла на основе этого списка (и дать Алисе вычисленный корень, который с достаточно высокой вероятностью отличается от корня из исходного списка).
Затем, когда Алиса дает ему $К$ индексы, на основе которых $К$ доказательства, он формирует их на основе модифицированного списка и вычисленного дерева. Он будет обнаружен как мошенник только в том случае, если один из индексов, которые она запросила, окажется индексом $с$; если ни один из индексов, которые она просила, не был для индекса $с$, то все доказательства, которые она получит, действительны и согласуются друг с другом (поскольку они соответствуют самосогласованному дереву Меркла, где раскрытые листья являются ожидаемыми значениями)
Вероятность того, что Боба поймают на мошенничестве, то есть вероятность того, что один из индексов, выбранных Алисой, равен $с$, является $К/М$. Следовательно, вероятность обнаружения против любой стратегии не больше (она может быть меньше, если есть еще лучшая стратегия, которую мог бы использовать Боб).
Итак, чтобы обнаружить обман Боба с вероятностью 0,99, мы имеем $ К > 0,99 млн $; в этот момент для Алисы фактически будет меньше вычислений, если она просто перевычислит дерево сама.
Нам это показалось интересным, потому что это может быть формой доказательства пространства-времени, если список дорого построить.
Теперь немного интереснее взглянуть на проблему как на доказательство работы (доказательство пространства не работает, так как дерево и пути аутентификации могут быть вычислены без значительного увеличения объема требуемых вычислений); Очевидно, что стратегия обмана, которую я описал выше, не решает эту проблему, поскольку Боб выполняет весь объем работы. Если бы у меня было больше времени, я бы попытался исследовать это подробнее...
