bgls

package module
v0.4.2 Latest Latest
Warning

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

 Go to latest Published: Mar 14, 2018 License: Apache-2.0 Imports: 9 Imported by: 0

README

BGLS

Master: Build Status Develop: Build Status

Aggregate and Multi Signatures based on BGLS over Alt bn128

This library provides no security against side channel attacks. We provide no security guarantees of this implementation.

Design

The goal of this library is to create an efficient and secure ad hoc aggregate and multi signature scheme. It relies on alt bn128 for curve and pairing operations. It implements hashing of arbitrary byte data to curve points, the standard BGLS scheme for aggregate signatures, and a custom multi signature scheme.

Multi Signature

The multi signature scheme is a modification of the BGLS scheme, where all signatures are on the same message. This allows verification with a constant number of pairing operations, at the cost of being insecure to chosen key attacks. To fix the chosen key attack, users are required to prove knowledge of their secret key, through the use of the Schnorr scheme applied to their public key.

Curves

Alt bn128

The group G_1 is a cyclic group of prime order on the curve Y^2 = X^3 + 3 defined over the field F_p with p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

The generator g_1 is (1,2)

Since this curve is of prime order, every non-identity point is a generator, therefore the cofactor is 1.

The group G_2 is a cyclic subgroup of the non-prime order elliptic curve Y^2 = X^3 + 3*((i + 9)^(-1)) over the field F_p^2 = F_p[X] / (X^2 + 1) (where p is the same as above). We can write our irreducible element as i. The cofactor of this group is 21888242871839275222246405745257275088844257914179612981679871602714643921549.

The generator g_2 is defined as: (11559732032986387107991004021392285783925812861821192530917403151452391805634*i + 10857046999023057135944570762232829481370756359578518086990519993285655852781, 4082367875863433681332203403145435568316851327593401208105741076214120093531*i + 8495653923123431417604973247489272438418190587263600148770280649306958101930)

The identity element for both groups (The point at infinity in affine space) is internally represented as (0,0)

Benchmarks

The following benchmarks are from a 3.80GHz i7-7700HQ CPU with 16GB ram. The aggregate verification is utilizing parallelization for the pairing operations. The multisignature has parellilization for the two involved pairing operations, and parallelization for the pairing checks at the end.

For reference, the pairing operation (the slowest operation involved) takes ~1.6 milliseconds.

BenchmarkG1-8        	   10000	    141018 ns/op
BenchmarkG2-8        	    3000	    471002 ns/op
BenchmarkPairing-8   	    1000	   1609893 ns/op
PASS
ok  	github.com/ethereum/go-ethereum/crypto/bn256/cloudflare	4.725s
  • Signing ~.22 milliseconds
  • Signature verification ~3.1 milliseconds, using two pairings.
  • Multi Signature verification ~2 milliseconds + ~1.1 microseconds per signer, two pairings + n point additions
  • Aggregate Signature verification ~.36 milliseconds per signer/message pair, with n+1 pairings run in parallel. (4.45x speedup with 8 cores)
$ go test github.com/Project-Arda/bgls/  -v -bench .
BenchmarkKeygen-8                  	    3000	    434484 ns/op
BenchmarkAltBnHashToCurve-8        	   20000	     91947 ns/op
BenchmarkSigning-8                 	   10000	    218670 ns/op
BenchmarkVerification-8            	     500	   3079415 ns/op
BenchmarkMultiVerification64-8     	    1000	   2056798 ns/op
BenchmarkMultiVerification128-8    	    1000	   2140613 ns/op
BenchmarkMultiVerification256-8    	     500	   2334271 ns/op
BenchmarkMultiVerification512-8    	     500	   2617277 ns/op
BenchmarkMultiVerification1024-8   	     500	   3243045 ns/op
BenchmarkMultiVerification2048-8   	     300	   4325183 ns/op
BenchmarkAggregateVerification-8   	    5000	    361270 ns/op
PASS
ok  	github.com/Project-Arda/bgls	31.043s

For comparison, the ed25519 implementation in go yields much faster key generation signing and single signature verification. However, at ~145 microseconds per verification, the multi signature verification is actually faster beyond ~26 signatures.

$ go test golang.org/x/crypto/ed25519 -bench .
BenchmarkKeyGeneration-8   	   30000	     51878 ns/op
BenchmarkSigning-8         	   30000	     54050 ns/op
BenchmarkVerification-8    	   10000	    145063 ns/op
PASS
ok  	golang.org/x/crypto/ed25519	5.750s
Hashing

The hashing algorithm is currently try-and-increment, and we support SHA3, Kangaroo twelve, Keccak256, and Blake2b.

We previously used a direct implementation of Indifferentiable Hashing to Barreto–Naehrig Curves using blake2b. This was removed because it can't be implemented in the EVM due to gas costs, and because it will not work for BLS12-381.

Future work

  • Optimize bigint allocations.
  • Add utility operations for serialization of keys/signatures.
  • Implement a better Hashing algorithm, such as Elligator Squared.
  • Integrate BLS12-381 with go bindings.
  • Integrations with bgls-on-evm.
  • Add tests to show that none of the functions mutate data.
  • More complete usage documentation.
  • Add buffering for the channels used in parallelization.

References

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var Altbn128 = &altbn128{}

Altbn128Inst is the instance for the altbn128 curve, with all of its functions.

Functions

func AltbnBlake2b 

func AltbnBlake2b(message []byte) (p1, p2 *big.Int)

AltbnBlake2b Hashes a message to a point on Altbn128 using Blake2b and try and increment The return value is the x,y affine coordinate pair.

func AltbnKang12 

func AltbnKang12(message []byte) (p1, p2 *big.Int)

AltbnKang12 Hashes a message to a point on Altbn128 using Blake2b and try and increment The return value is the x,y affine coordinate pair.

func AltbnKeccak3 

func AltbnKeccak3(message []byte) (p1, p2 *big.Int)

AltbnKeccak3 Hashes a message to a point on Altbn128 using Keccak3 and try and increment Keccak3 is only for compatability with Ethereum hashing. The return value is the x,y affine coordinate pair.

func AltbnSha3 

func AltbnSha3(message []byte) (p1, p2 *big.Int)

AltbnSha3 Hashes a message to a point on Altbn128 using SHA3 and try and increment The return value is the x,y affine coordinate pair.

func CheckAuthentication 

func CheckAuthentication(curve CurveSystem, v Point2, authentication Point1) bool

CheckAuthentication verifies that this Point2 is valid

func CheckAuthenticationCustHash added in v0.2.0 

func CheckAuthenticationCustHash(curve CurveSystem, v Point2, authentication Point1, hash func([]byte) Point1) bool

CheckAuthenticationCustHash verifies that this Point2 is valid, with the specified hash function

func EthereumSum256 

func EthereumSum256(data []byte) (digest [32]byte)

EthereumSum256 returns the Keccak3-256 digest of the data. This is because Ethereum uses a non-standard hashing algo.

func Verify 

func Verify(curve CurveSystem, pubKey Point2, m []byte, sig Point1) bool

Verify checks that a signature is valid

func VerifyAggregateSignature 

func VerifyAggregateSignature(curve CurveSystem, aggsig Point1, keys []Point2, msgs [][]byte, allowDuplicates bool) bool

VerifyAggregateSignature verifies that the aggregated signature proves that all messages were signed by associated keys Will fail under duplicate messages, unless allow duplicates is True.

func VerifyCustHash added in v0.2.0 

func VerifyCustHash(curve CurveSystem, pubKey Point2, m []byte, sig Point1, hash func([]byte) Point1) bool

VerifyCustHash checks that a signature is valid with the supplied hash function

func VerifyMultiSignature 

func VerifyMultiSignature(curve CurveSystem, aggsig Point1, keys []Point2, msg []byte) bool

VerifyMultiSignature checks that the aggregate signature correctly proves that a single message has been signed by a set of keys, vulnerable against chosen key attack, if keys have not been authenticated

Types

type AggSig 

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

AggSig holds paired sequences of keys and messages, and one signature

func (AggSig) Verify 

func (a AggSig) Verify(curve CurveSystem) bool

Verify checks that all messages were signed by associated keys Will fail under duplicate messages

type CurveSystem added in v0.2.0 

type CurveSystem interface {
	MakeG1Point(*big.Int, *big.Int) (Point1, bool)

	UnmarshalG1([]byte) (Point1, bool)
	UnmarshalG2([]byte) (Point2, bool)
	UnmarshalGT([]byte) (PointT, bool)

	GetG1() Point1
	GetG2() Point2
	GetGT() PointT

	HashToG1(message []byte) Point1
	// contains filtered or unexported methods
}

CurveSystem is a set of parameters and functions for a pairing based cryptosystem It has everything necessary to support all bgls functionality which we use.

type MultiSig 

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

MultiSig holds set of keys and one message plus signature

func (MultiSig) Verify 

func (m MultiSig) Verify(curve CurveSystem) bool

Verify checks that a single message has been signed by a set of keys vulnerable against chosen key attack, if keys have not been authenticated

type Point1 added in v0.2.0 

type Point1 interface {
	Add(Point1) (Point1, bool)
	Copy() Point1
	Equals(Point1) bool
	Marshal() []byte
	Mul(*big.Int) Point1
	Pair(Point2) (PointT, bool)
	ToAffineCoords() (*big.Int, *big.Int)
}

Point1 is a way to represent a point on G1, in the first elliptic curve.

func AggregateG1 added in v0.3.0 

func AggregateG1(sigs []Point1) Point1

AggregateG1 takes the sum of points on G1. This is used to convert a set of signatures into a single signature

func Authenticate 

func Authenticate(curve CurveSystem, sk *big.Int) Point1

Authenticate generates an Authentication for a valid *big.Int/Point2 combo It signs a verification key with x.

func AuthenticateCustHash added in v0.2.0 

func AuthenticateCustHash(curve CurveSystem, sk *big.Int, hash func([]byte) Point1) Point1

AuthenticateCustHash generates an Authentication for a valid *big.Int/Point2 combo It signs a verification key with x. This runs with the specified hash function.

func Sign added in v0.3.0 

func Sign(curve CurveSystem, sk *big.Int, m []byte) Point1

Sign creates a signature on a message with a private key

func SignCustHash added in v0.3.0 

func SignCustHash(sk *big.Int, m []byte, hash func([]byte) Point1) Point1

SignCustHash creates a signature on a message with a private key, using a supplied function to hash to g1.

type Point2 added in v0.2.0 

type Point2 interface {
	Add(Point2) (Point2, bool)
	Copy() Point2
	Equals(Point2) bool
	Marshal() []byte
	Mul(*big.Int) Point2
	ToAffineCoords() (*big.Int, *big.Int, *big.Int, *big.Int)
}

Point2 is a way to represent a point on G2, in the first elliptic curve.

func AggregateG2 added in v0.3.0 

func AggregateG2(keys []Point2) Point2

AggregateG2 takes the sum of points on G2. This is used to sum a set of public keys for the multisignature

func KeyGen 

func KeyGen(curve CurveSystem) (*big.Int, Point2, error)

KeyGen generates a *big.Int and Point2

func LoadPublicKey added in v0.3.0 

func LoadPublicKey(curve CurveSystem, sk *big.Int) Point2

LoadPublicKey turns secret key into a public key of type Point2

type PointT added in v0.2.0 

type PointT interface {
	Add(PointT) (PointT, bool)
	Copy() PointT
	Equals(PointT) bool
	Marshal() []byte
	Mul(*big.Int) PointT
}

PointT is a way to represent a point on GT, in the first elliptic curve.

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.