Git Product home page Git Product logo

bulletproofs's Introduction

Bulletproofs++ implementation

License: MIT

Abstract

Present Go library contains the implementation of Bulletproofs++ weight norm linear argument protocol, arithmetic circuit protocol and reciprocal range proof protocol.

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)
	}
}

bulletproofs's People

Contributors

olegfomenko avatar

Stargazers

Artem Skriabin avatar Mykhaylo Velykodnyi avatar Ivan Lele avatar Dmytro Zakharov avatar Nikita Masych avatar Denis Riabtsev avatar  avatar Anton Levochko avatar Kyrylo Riabov avatar Kyrylo Baibula avatar Michael Sokolov avatar  avatar

Watchers

Yaroslav Panasenko avatar xxxvik-xakerxxx avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.