bulletproofs

Пуленепробиваемость

Bulletproofs — это короткие аргументы с нулевым разглашением, которые не требуют надежной настройки. Системы аргументов — это системы доказательств, обладающие вычислительной надежностью.

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

Базовым алгоритмом Bulletproofs является алгоритм внутреннего продукта, представленный Гротом [2]. Алгоритм предоставляет аргумент знания двух обязательств Педерсена вектора связывания, которые удовлетворяют заданному отношению внутреннего продукта. Пуленепробиваемость основана на методах Бутла и др. [3] чтобы представить эффективное коммуникативное доказательство внутреннего продукта, которое снижает общую коммуникативную сложность аргумента только до где – это размерность двух векторов обязательств.

Доказательства диапазона

Bulletproofs представляет собой протокол для проведения испытаний на короткой и совокупной дистанции. Они кодируют доказательство диапазона зафиксированного числа во внутреннем продукте, используя полиномы. Доказательства диапазона — это доказательства того, что секретное значение находится в определенном интервале. Доказательства диапазона не раскрывают никакой информации о секретном значении, кроме того факта, что они лежат в интервале.

Алгоритм доказательства можно представить в виде 5 шагов:

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

• - где и ослеплены обязательствами Педерсена и .

• - Верификатор отправляет вызовы и исправить и .

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

,

• - Верификатор бросает вызов проверяющему с ценностью .

• - Проверщик отправляет несколько обязательств, которые затем проверит верификатор.

Подробности реализации см. в Prover.hs.

Описанное взаимодействие становится неинтерактивным с помощью преобразования Фиата-Шамира, в котором все случайные вызовы, выполненные V, заменяются хэшем транскрипта до этого момента.

Доказательство внутреннего ассортимента продукции

Размер доказательства еще больше уменьшается за счет использования компактного внутреннее доказательство продукта.

Аргумент внутреннего продукта в протоколе позволяет доказать знание векторов. и , внутренний продукт которого равен и приверженность является объединение этих двух векторов. Поэтому мы можем заменить отправку ( ) с переносом ( ) и выполнение аргумента внутреннего продукта.

Тогда вместо того, чтобы делиться и , стоимость связи которого составляет элементы, аргумент внутреннего продукта передает только элементы. Всего прувер отправляет только элементы группы и 5 элементов в

Агрегирование логарифмических доказательств

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

Доказательство совокупного диапазона использует аргумент внутреннего продукта. Он использует ( ) элементы группы и 5 элементов в .

См. пример проверки нескольких диапазонов.

Использование

Доказательство одного диапазона

 import Data.Curve.Weierstrass.SECP256K1 (Fr)импортировать квалифицированные Bulletproofs.RangeProof как RPimport Bulletproofs.Utils (commit)testSingleRangeProof :: Integer -> (Fr, Fr) -> IO BooltestSingleRangeProof UpperBound (v, vBlinding) = do let vCommit = commit v vBlinding -- Доказательство
  proofE <- runExceptT (RP.generateProof UpperBound (v, vBlinding)) — случай проверкиproofE of Left err -> паника (показать ошибку) [email protected]{..} -> pure (RP.verifyProof UpperBound vCommit доказательство) )

Многодиапазонное доказательство

 import Data.Curve.Weierstrass.SECP256K1 (Fr)импортировать квалифицированные Bulletproofs.MultiRangeProof как MRPimport Bulletproofs.Utils (commit)testMultiRangeProof :: Integer -> [(Fr, Fr)] -> IO BooltestMultiRangeProof UpperBound vsAndvBlindings = do let vCommits = fmap ( необузданный commit) vsAndvBlindings -- Доказательство
  доказательствоE <- runExceptT (MRP.generateProof UpperBound vsAndvBlindings) — случай проверки доказательствоE левой ошибки -> паника (показать ошибку) Право доказательство@RP.RangeProof{..} -> чистое (MRP.verifyProof UpperBound vCommits доказательство)

Обратите внимание, что верхняя граница должно быть таким, что , где также является степенью 2. В этой реализации используется эллиптическая кривая secp256k1, кривая Коблица, имеющая 128-битную безопасность. Дополнительную информацию см. в разделе «Примеры проверки диапазона».

Доказательства с нулевым разглашением для арифметических схем

Арифметическая схема над полем и переменными представляет собой ориентированный ациклический граф, вершины которого называются вентилями.

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

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

В протоколе Доказывающий доказывает, что произведение Адамара и и выполняется набор линейных ограничений. Входные значения используемые для создания доказательства, затем фиксируются и передаются проверяющему.

 import Data.Curve.Weierstrass.SECP256K1 (Fr)import Data.Field.Galois (rnd)import Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (adamard, commit) -- Пример: -- 2 линейных ограничения (q = 2): -- aL [0] + aL[1] + aL[2] + aL[3] = v[0]-- aR[0] + aR[1] + aR[2] + aR[3] = v[1]---- 4 ограничения умножения (неявные) (n = 4):-- aL[ 0] * aR[0] = aO[0]-- aL[1] * aR[1] = aO[1]-- aL[2] * aR[2] = aO[2]-- aL[3] * aR[3] = aO[3]---- 2 входных значения (m = 2)arithCircuitExample :: ArithCircuit FrarithCircuitExample = ArithCircuit
  { веса = GateWeights
    { wL = [[1, 1, 1, 1]
           ,[0, 0, 0, 0]]
    , wR = [[0, 0, 0, 0]
           ,[1, 1, 1, 1]]
    , wO = [[0, 0, 0, 0]
           ,[0, 0, 0, 0]]
    }
  , обязательстваВес = [[1, 0]
                        ,[0, 1]]
  , cs = [0, 0]
  }testArithCircuitProof :: ([Fr], [Fr]) -> ArithCircuit Fr -> IO BooltestArithCircuitProof (aL, aR) arithCircuit = do let m = 2 -- Ограничения умножения let aO = aL `hadamard` aR -- Линейные ограничения
      v0 = сумма aL
      v1 = сумма aR

  commitBlinders <- replicationM m rnd let commits = zipWith commit [v0, v1] commitBlinders let arithWitness = ArithWitness
        { присвоение = присвоение aL aR aO
        , обязательства = обязательства
        , commitBlinders = commitBlinders
        }

  доказательство <-generateProof arithCircuit arithWitness pure (verifyProof обязательства доказательства arithCircuit)

Дополнительную информацию см. в примере арифметической схемы.

Ссылки :

1. Бунц Б., Бутл Дж., Бонех Д., Поэльстра А., Вуилле П., Максвелл Г. «Пуленепробиваемые доказательства: краткие доказательства конфиденциальных транзакций и многое другое». Стэнфорд, UCL, Blockstream, 2017 г.

2. Грот Дж. «Линейная алгебра с сублинейными аргументами с нулевым разглашением». Университетский колледж Лондона, 2009 г.

3. Бутл Дж., Серулли А., Чайдос П., Грот Дж., Пети К. «Эффективные аргументы с нулевым разглашением для арифметических схем в настройке дискретного журнала». Университетский колледж Лондона и Оксфордский университет, 2016 г.

Обозначение :

• : произведение Адамара

• :Внутренний продукт

• : Вектор

Отказ от ответственности

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

Лицензия

Copyright 2018-2022 Stephen Diehl

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.