bulletproofs
1.1 Release
방탄은 신뢰할 수 있는 설정이 필요하지 않은 지식에 대한 짧은 영지식 주장입니다. 논증 시스템은 계산상의 건전성을 갖춘 증명 시스템입니다.
방탄은 범위 증명, 검증 가능한 서플, 산술 회로 등과 같은 커밋된 값에 대한 설명을 증명하는 데 적합합니다. 방탄은 이산 로그 가정에 의존하며 Fiat-Shamir 휴리스틱을 사용하여 비대화형으로 만들어집니다.
Bulletproofs의 핵심 알고리즘은 Groth[2]가 제시한 내적 알고리즘이다. 알고리즘은 주어진 내적 관계를 만족시키는 두 개의 바인딩 벡터 Pedersen 공약에 대한 지식에 대한 인수를 제공합니다. 방탄은 Bootle 등의 기술을 기반으로 구축되었습니다. [3] 인수의 전반적인 통신 복잡성을 다음과 같이 줄이는 통신 효율적인 내부 제품 증명을 도입합니다. 
어디 
는 약속의 두 벡터의 차원입니다.
방탄은 단기 및 집계 가능한 범위 증명을 수행하기 위한 프로토콜을 제공합니다. 다항식을 사용하여 내부 곱의 커밋된 숫자 범위 증명을 인코딩합니다. 범위 증명은 비밀 값이 특정 간격에 있다는 것을 증명하는 것입니다. 범위 증명은 비밀 값이 간격에 있다는 사실 외에는 비밀 값에 대한 정보를 유출하지 않습니다.
증명 알고리즘은 5단계로 개략적으로 설명할 수 있습니다.
허락하다 
가치가 있다 
그리고 
다음과 같은 비트의 벡터 
. 구성 요소 의 이진수는 다음과 같습니다. . 우리는 상보적인 벡터를 구성합니다 
그리고 그것을 요구한다 
보유하고 있습니다.
- 어디 
그리고 
눈이 먼 Pedersen의 약속은 다음과 같습니다. 그리고 
.
- 검증자가 챌린지를 보냅니다. 
그리고 
고치다 그리고 .
- 어디 
그리고 
계수에 대한 약속입니다. 
, 다항식의 
프로토콜의 기존 값으로 구성됩니다.
, 
- 검증자는 가치를 가지고 검증자에게 도전합니다. 
.
- 증명자는 검증자가 확인할 몇 가지 약속을 보냅니다.
구현 세부 사항은 Prover.hs를 참조하세요.
설명된 상호 작용은 Fiat-Shamir 변환을 사용하여 비대화형으로 만들어지며 V가 만든 모든 무작위 문제는 해당 시점까지의 성적표 해시로 대체됩니다.
컴팩트를 활용하여 증명의 크기를 더욱 줄입니다. 
내부 제품 증명.
프로토콜의 내적 인수를 통해 벡터에 대한 지식을 증명할 수 있습니다. 
그리고 
, 그의 내적은 다음과 같습니다. 그리고 헌신 
이 두 벡터의 약속입니다. 따라서 우리는 전송을 대체할 수 있습니다( 
)의 양도로 ( 
) 및 내부 곱 인수의 실행입니다.
그렇다면 공유하는 대신 그리고 , 통신 비용은 
요소의 경우 내부 곱 인수는 
강요. 전체적으로 증명자는 다음과 같이 전송합니다. 
그룹 요소 및 5개 요소 
추가 공간 비용만 발생시키면서 여러 값의 범위에 대한 단일 증명을 구성할 수 있습니다. 
~을 위한 
추가 값 , 곱셈 요소와는 반대로 생성할 때 독립적인 범위 증명.
집계 범위 증명은 내부 곱 인수를 사용합니다. 그것은 ( 
) 그룹 요소와 5개의 요소 .
다중 범위 증명 예를 참조하세요.
단일 범위 증명
import Data.Curve.Weierstrass.SECP256K1 (Fr)적격한 Bulletproofs.RangeProof를 RPimport로 가져오기 Bulletproofs.Utils (commit)testSingleRangeProof :: 정수 -> (Fr, Fr) -> IO BooltestSingleRangeProof upperBound (v, vBlinding) = do let vCommit = 커밋 v vBlinding -- 증명자 proofE <- runExceptT (RP.generateProof upperBound (v, vBlinding)) -- 검증자 케이스proofE of Left 오류 -> 패닉(오류 표시) [email protected]{..} -> 순수(RP.verifyProof upperBound vCommit 증명 )
다중 범위 증명
import Data.Curve.Weierstrass.SECP256K1 (Fr) MRPimport로 자격을 갖춘 Bulletproofs.MultiRangeProof 가져오기 Bulletproofs.Utils (commit)testMultiRangeProof :: 정수 -> [(Fr, Fr)] -> IO BooltestMultiRangeProof upperBound vsAndvBlindings = do let vCommits = fmap ( 커밋하지 않음) vsAndvBlindings -- 증명자 proofE <- runExceptT (MRP.generateProof upperBound vsAndvBlindings) -- 검증자 케이스proofE of Left err -> 패닉(오류 표시) [email protected]{..} -> pure(MRP.verifyProof upperBound vCommits 증명)
상한선에 유의하세요. 
그래야 한다 
, 어디 또한 2의 거듭제곱입니다. 이 구현에서는 128비트 보안을 갖춘 Koblitz 곡선인 타원 곡선 secp256k1을 사용합니다. 자세한 내용은 범위 증명 예를 참조하세요.
필드와 변수에 대한 산술 회로 
는 정점을 게이트라고 부르는 방향성 비순환 그래프입니다.
산술 회로는 게이트의 입력 및 출력과 관련된 선형 일관성 방정식 모음을 포함하는 곱셈 게이트 목록으로 대안적으로 설명할 수 있습니다. 비순환 그래프로 설명된 모든 회로는 이 대체 설명으로 효율적으로 변환될 수 있습니다.
Bulletproofs는 크기 증명을 얻을 수 있는 내부 곱 인수를 사용하여 산술 회로에 대한 영지식 인수를 생성하는 프로토콜을 제시합니다. 
요소를 포함하고 산술 회로에 대한 입력으로 커밋된 값을 포함합니다.
프로토콜에서 증명자는 하다마드 제품이 다음과 같다는 것을 증명합니다. 그리고 일련의 선형 제약 조건이 유지됩니다. 입력 값 증거를 생성하는 데 사용된 데이터는 검증자와 커밋되고 공유됩니다.
import Data.Curve.Weierstrass.SECP256K1 (Fr)import Data.Field.Galois (rnd)import Bulletproofs.ArithmeticCircuitimport Bulletproofs.Utils (hadamard, 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 <-pliplicateM m rnd let commits = zipWith 커밋 [v0, v1] commitBlinders let arithWitness = ArithWitness
{ 과제 = 과제 aL aR aO
, 약속 = 약속
, commitBlinders = commitBlinders
}
증명 <- generateProof arithCircuit arithWitness pure(verifyProof 약속 증명 arithCircuit)자세한 내용은 산술 회로 예제를 참조하세요.
참고자료 :
Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G. "방탄: 기밀 거래 및 기타에 대한 짧은 증명". 스탠포드, UCL, 블록스트림, 2017
Groth J. "하선형 영지식 인수를 사용한 선형 대수학". 유니버시티 칼리지 런던, 2009
Bootle J., Cerully A., Chaidos P., Groth J, Petit C. "이산 로그 설정의 산술 회로에 대한 효율적인 영지식 인수". 유니버시티 칼리지 런던과 옥스퍼드 대학교, 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.
