bulletproofs

package module
v0.0.0-...-111e1d7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 20, 2024 License: MIT Imports: 6 Imported by: 0

README

Bulletproofs++ implementation

⚠️ Please note - this crypto library has not been audited, so use it at your own risk.

Abstract

Present Go library contains the implementation of Bulletproofs++ weight norm linear argument protocol, arithmetic circuit protocol and reciprocal range proof protocol described in Distributed Lab's Bulletproofs++ Construction and Examples.

Explore the circuit_test.go to check the examples of circuit prove and verification. It contains several circuits:

  • Prove that we know such x, y that x+y=r and x*y=z for public r, z. This example encoded directly into the BP++ circuits.
  • Prove the range for 4-bits value: x is in [0..2^n) range (simple binary range proof).

Also, reciprocal_test.go contains example of proving that value lies in [0, 16^n) range.

Implemented protocol has 2G points advantage over existing BP and BP+ protocols on proving of one 64-bit value and this advantage will increase for more values per proof.

Protocol G F
BP 16 5
BP+ 15 3
Our BP++ 13 3

Reciprocal range proofs

Check the following snippet as an example of usage of range proof protocol:

package main

import (
	"github.com/cloudflare/bn256"
	"github.com/distributed-lab/bulletproofs"
	"math/big"
)

func main() {
	// The uint64 in 16-base system will be encoded in 16 digits. 
	// The 16 base is selected as the most optimal base for this case.

	// Our private value is 0xab4f0540ab4f0540. 
	x := uint64(0xab4f0540ab4f0540)
	X := new(big.Int).SetUint64(x)

	// Let's encode it as a list of digits:
	digits := bulletproofs.UInt64Hex(x) // [0 4 5 0 15 4 11 10 0 4 5 0 15 4 11 10]

	// Public poles multiplicities i-th element corresponds to the 'i-digit' multiplicity (the count of 'i-digit' in digits list)
	m := bulletproofs.HexMapping(digits) // [4 0 0 0 4 2 0 0 0 0 2 2 0 0 0 2]

	Nd := 16 // digits size
	Np := 16 // base size

	var G *bn256.G1
	// Length of our base points vector should be a power ot 2 to be used in WNLA protocol. 
	// So cause the real HVec size in circuit is `Nd+10` the nearest length is 32   
	var GVec []*bn256.G1 // len = 16
	var HVec []*bn256.G1 // len = 32

	public := &bulletproofs.ReciprocalPublic{
		G:    G,
		GVec: GVec[:Nd],
		HVec: HVec[:Nd+10],
		Nd:   Nd,
		Np:   Np,

		// Remaining points that will be used in WNLA protocol
		GVec_: GVec[Nd:],
		HVec_: HVec[Nd+10:],
	}

	private := &bulletproofs.ReciprocalPrivate{
		X:      x,                // Committed value
		M:      m,                // Corresponding multiplicities
		Digits: digits,           // Corresponding digits
		S:      MustRandScalar(), // Blinding value (secret) used for committing value as: x*G + Sx*H
	}

	VCom := public.CommitValue(private.X, private.Sx) // Value commitment: x*G + Sx*H

	// Use NewKeccakFS or your own implementation for the Fiat-Shamir heuristics.
	proof := bulletproofs.ProveRange(public, bulletproofs.NewKeccakFS(), private)

	// If err is nil -> proof is valid.
	if err := bulletproofs.VerifyRange(public, VCom, bulletproofs.NewKeccakFS(), proof); err != nil {
		panic(err)
	}
}

Weight norm linear argument (WNLA)

The wnla.go contains the implementation of weight norm linear argument protocol. This is a fundamental basis for arithmetic circuit protocol. It uses the Fiat-Shamir heuristics from fs.go to generate challenges and make protocol non-interactive.

Check the following snippet with an example of WNLA usage:

package main

import (
	"github.com/distributed-lab/bulletproofs"
	"math/big"
)

func main() {
	public := bulletproofs.NewWeightNormLinearPublic(4, 2)

	// Private
	l := []*big.Int{big.NewInt(4), big.NewInt(5), big.NewInt(10), big.NewInt(1)}
	n := []*big.Int{big.NewInt(2), big.NewInt(1)}

	proof := bulletproofs.ProveWNLA(public, public.Commit(l, n), bulletproofs.NewKeccakFS(), l, n)
	if err := bulletproofs.VerifyWNLA(public, proof, public.Commit(l, n), bulletproofs.NewKeccakFS()); err != nil {
		panic(err)
	}
}

Arithmetic circuit

The circuit.go contains the implementation of BP++ arithmetic circuit protocol. It runs the WNLA protocol as the final stages of proving/verification. Uses the Fiat-Shamir heuristics from fs.go to generate challenges and make protocol non-interactive.

Check the following snippet with an example of arithmetic circuit protocol usage:

package main

import (
	"github.com/cloudflare/bn256"
	"github.com/distributed-lab/bulletproofs"
)

func main() {
	public := &bulletproofs.ArithmeticCircuitPublic{
		Nm,
		Nl, // Nl = Nv * K
		Nv, // Size on any v witness vector
		Nw, // Nw = Nm + Nm + No
		No,
		K, // count of v witnesses vectors
		G,

		// points that will be used directly in circuit protocol
		GVec[:Nm],   // Nm
		HVec[:Nv+9], // Nv+9

		// Circuit definition 
		Wm, // Nm * Nw
		Wl, // Nl * Nw
		Am, // Nm
		Al, // Nl
		Fl,
		Fm,

		// Partition function
		F: func(typ bulletproofs.PartitionType, index int) *int {
			// define
			return nil
		},

		// points that will be used in WNLA protocol to make vectors 2^n len
		HVec[Nv+9:], // 2^x - (Nv+9) dimension
		GVec[Nm:],   // 2^y - Nm dimension
	}

	private := &bulletproofs.ArithmeticCircuitPrivate{
		V,  // witness vectors v, dimension k*Nv
		Sv, // witness blinding values, dimension k
		Wl, // Nm
		Wr, // Nm
		Wo, // No
	}

	// Commitments to the v witness vectors
	V := make([]*bn256.G1, public.K)
	for i := range V {
		V[i] = public.CommitCircuit(private.V[i], private.Sv[i], public.G, public.HVec)
	}

	proof := bulletproofs.ProveCircuit(public, bulletproofs.NewKeccakFS(), private)

	if err := bulletproofs.VerifyCircuit(public, V, bulletproofs.NewKeccakFS(), proof); err != nil {
		panic(err)
	}
}

Documentation

Overview

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package bulletproofs Copyright 2024 Distributed Lab. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func HexMapping 

func HexMapping(digits []*big.Int) []*big.Int

func MustRandPoint 

func MustRandPoint() *bn256.G1

func MustRandScalar 

func MustRandScalar() *big.Int

func UInt64Hex 

func UInt64Hex(x uint64) []*big.Int

func VerifyCircuit 

func VerifyCircuit(public *ArithmeticCircuitPublic, V []*bn256.G1, fs FiatShamirEngine, proof *ArithmeticCircuitProof) error

VerifyCircuit verifies BP++ arithmetic circuit zero-knowledge proof using WNLA protocol. If err is nil then proof is valid. Use empty FiatShamirEngine for call.

func VerifyRange 

func VerifyRange(public *ReciprocalPublic, V *bn256.G1, fs FiatShamirEngine, proof *ReciprocalProof) error

VerifyRange verifies BP++ reciprocal argument range proof on arithmetic circuits. If err is nil then proof is valid. Use empty FiatShamirEngine for call.

func VerifyWNLA 

func VerifyWNLA(public *WeightNormLinearPublic, proof *WeightNormLinearArgumentProof, Com *bn256.G1, fs FiatShamirEngine) error

VerifyWNLA verifies the weight norm linear argument proof. If err is nil then proof is valid. Use empty FiatShamirEngine for call. Also, use the same commitment that has been used during proving.

Types

type ArithmeticCircuitPrivate 

type ArithmeticCircuitPrivate struct {
	V  [][]*big.Int // k*Nv
	Sv []*big.Int   // k
	Wl []*big.Int   // Nm
	Wr []*big.Int   // Nm
	Wo []*big.Int   // No
}

type ArithmeticCircuitProof 

type ArithmeticCircuitProof struct {
	CL, CR, CO, CS *bn256.G1
	WNLA           *WeightNormLinearArgumentProof
}

func ProveCircuit 

func ProveCircuit(public *ArithmeticCircuitPublic, V []*bn256.G1, fs FiatShamirEngine, private *ArithmeticCircuitPrivate) *ArithmeticCircuitProof

ProveCircuit generates zero knowledge proof that witness satisfies BP++ arithmetic circuit. Use empty FiatShamirEngine for call.

type ArithmeticCircuitPublic 

type ArithmeticCircuitPublic struct {
	Nm, Nl, Nv, Nw, No int // Nw = Nm + Nm + No (for L, R, O parts), Nl = Nv * K
	K                  int // Count of witness vectors v.
	G                  *bn256.G1
	GVec               []*bn256.G1 // Nm
	HVec               []*bn256.G1 // Nv+9

	Wm [][]*big.Int // Nm * Nw
	Wl [][]*big.Int // Nl * Nw

	Am []*big.Int // Nm
	Al []*big.Int // Nl

	Fl bool
	Fm bool

	F PartitionF

	// Vectors of points that will be used in WNLA protocol
	GVec_ []*bn256.G1 // 2^n - Nm
	HVec_ []*bn256.G1 // 2^n - (Nv+9)
}

func (*ArithmeticCircuitPublic) CommitCircuit 

func (p *ArithmeticCircuitPublic) CommitCircuit(v []*big.Int, s *big.Int) *bn256.G1

CommitCircuit creates a commitment for v vector and blinding s. Com = v[0]*G + s*H[0] + <v[1:], H[9:]>

type FiatShamirEngine 

type FiatShamirEngine interface {
	AddPoint(*bn256.G1)
	AddNumber(*big.Int)
	GetChallenge() *big.Int
}

func NewKeccakFS 

func NewKeccakFS() FiatShamirEngine

type KeccakFS 

type KeccakFS struct {
	// contains filtered or unexported fields
}

func (*KeccakFS) AddNumber 

func (k *KeccakFS) AddNumber(v *big.Int)

func (*KeccakFS) AddPoint 

func (k *KeccakFS) AddPoint(p *bn256.G1)

func (*KeccakFS) GetChallenge 

func (k *KeccakFS) GetChallenge() *big.Int

type PartitionF 

type PartitionF = func(typ PartitionType, index int) *int

type PartitionType 

type PartitionType int
const (
	PartitionLO PartitionType = iota
	PartitionLL
	PartitionLR
	PartitionNO
)

type ReciprocalPrivate 

type ReciprocalPrivate struct {
	X      *big.Int // Committed value
	M      []*big.Int
	Digits []*big.Int
	S      *big.Int // Blinding value (secret)
}

type ReciprocalProof 

type ReciprocalProof struct {
	*ArithmeticCircuitProof
	V *bn256.G1
}

func ProveRange 

func ProveRange(public *ReciprocalPublic, fs FiatShamirEngine, private *ReciprocalPrivate) *ReciprocalProof

ProveRange generates zero knowledge proof that corresponding to the committed digits vector value lies in [0, 2^n) range. Use empty FiatShamirEngine for call.

type ReciprocalPublic 

type ReciprocalPublic struct {
	G      *bn256.G1
	GVec   []*bn256.G1 // Nm
	HVec   []*bn256.G1 // Nv+9
	Nd, Np int

	// Vectors of points that will be used in WNLA protocol
	GVec_ []*bn256.G1 // 2^n - Nm
	HVec_ []*bn256.G1 // 2^n - (Nv+9)
}

ReciprocalPublic dimensions: Nd - count of private proles (size of committed value), Np - count of public poles (number system base). Nm = Nd, No = Np Nv = 1 + Nd G and HVec[0] will be used for the value commitment: VCom = value*G + blinding*HVec[0]

func (*ReciprocalPublic) CommitPoles 

func (p *ReciprocalPublic) CommitPoles(r []*big.Int, s *big.Int) *bn256.G1

func (*ReciprocalPublic) CommitValue 

func (p *ReciprocalPublic) CommitValue(v *big.Int, s *big.Int) *bn256.G1

type WeightNormLinearArgumentProof 

type WeightNormLinearArgumentProof struct {
	R, X []*bn256.G1
	L, N []*big.Int
}

WeightNormLinearArgumentProof contains the proof of knowledge of vectors L, N for corresponding commitment C (is not included into the proof structure).

func ProveWNLA 

func ProveWNLA(public *WeightNormLinearPublic, Com *bn256.G1, fs FiatShamirEngine, l, n []*big.Int) *WeightNormLinearArgumentProof

ProveWNLA generates zero knowledge proof of knowledge of two vectors l and n that satisfies the commitment C (see WeightNormLinearPublic.Commit() function). Use empty FiatShamirEngine for call.

type WeightNormLinearPublic 

type WeightNormLinearPublic struct {
	G          *bn256.G1
	GVec, HVec []*bn256.G1
	C          []*big.Int
	Ro, Mu     *big.Int // mu = ro^2
}

WeightNormLinearPublic contains the public values to be used in weight norm linear argument proof. The GVec and HVec sizes are recommended to be a powers of 2 and equal to the `n` and `l` private vector sizes.

func NewWeightNormLinearPublic 

func NewWeightNormLinearPublic(lLen int, nLen int) *WeightNormLinearPublic

func (*WeightNormLinearPublic) CommitWNLA 

func (p *WeightNormLinearPublic) CommitWNLA(l []*big.Int, n []*big.Int) *bn256.G1

CommitWNLA creates a commitment for vectors n, l based on public parameters p. Commit(l, n) = v*G + <l, H> + <n, G> where v = <c, l> + |n^2|_mu

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.