Verification of BLS signatures and BGLS aggregate signatures in Ethereum

README.md

I created the snippet above during my research on blockchain oracles in 2019. You can read more about my outcomes in this paper.

The code is based on Zokrates/ZoKrates. Like Zokrates, this implementation has only been used for experimentation purposes and should not be seen as production-ready.

algorithms.go

// Copyright (C) 2018 Authors
// distributed under Apache 2.0 license

package bgls

import (
	"crypto/rand"
	"math/big"
	"github.com/bjornvdlaan/go-solidity-sha3"
)


//AggSig holds paired sequences of keys and messages, and one signature
type AggSig struct {
	keys []Point
	msgs [][]byte
	sig  Point
}

//KeyGen generates a *big.Int and Point2
func KeyGen(curve CurveSystem) (*big.Int, Point, Point, error) {
	//Create private key
	x, err := rand.Int(rand.Reader, curve.GetG1Order())

	//Check for error
	if err != nil {
		return nil, nil, nil, err
	}

	//Compute public key
	W, X := ComputePublicKey(curve, x)

	return x, W, X, nil
}

//ComputePublicKey turns secret key into a public key of type Point2
func ComputePublicKey(curve CurveSystem, sk *big.Int) (Point, Point) {
	W := curve.GetG1().Mul(sk)
	X := curve.GetG2().Mul(sk)
	return W, X
}


// Creates a signature on a message with a private key, with prepending the public key to the message.
func Sign(curve CurveSystem, x *big.Int, v Point, msg []byte) Point {
	//Prepend public key to message
	m := msg

	//Hash message to element in G1
	h := hashToG1(curve, m)

	//Compute signature
	sigma := h.Mul(x)

	return sigma
}

// Checks that a single BLS signature is valid
func VerifySingleSignature(curve CurveSystem, sig Point, pubkey Point, m []byte) bool {
	//msg := append(pubkey.MarshalUncompressed(), m...)
	msg := m
	h := hashToG1(curve, msg)

	pairing1, _ := curve.Pair(sig, curve.GetG2())
	pairing2, _ := curve.Pair(h, pubkey)

	return pairing1.Equals(pairing2)
}

// Aggregates an array of signatures into one BGLS aggregate signature.
func AggregateSignatures(sigs []Point) Point {
	return AggregatePoints(sigs)
}

// Checks whether an aggregate is valid
func VerifyAggregateSignature(curve CurveSystem, aggsig Point, keys []Point, messages [][]byte) bool {
	//Verify that the number of keys and messages is equal
	if len(keys) != len(messages) {
		return false
	}

	//Prepend public key (optional modification proposed by Boneh et al.)
	/*msgs := make([][]byte, len(messages))
	for i := 0; i < len(msgs); i++ {
		msgs[i] = append(keys[i].MarshalUncompressed(), messages[i]...)
	}*/
	
	msgs := messages

	//array of hashes
	h_arr := make([]Point, len(keys)+1)
	//array of public keys
	v_arr := make([]Point, len(keys)+1)

	//Add signature and the negation of generator g2
	h_arr[0] = aggsig
	v_arr[0] = curve.GetG2().Mul(new(big.Int).SetInt64(-1))

	//Add all hashes and keys
	for i := 0; i < len(msgs); i++ {
		h_arr[i+1] = hashToG1(curve, msgs[i])
		v_arr[i+1] = keys[i]
	}

	aggPt, ok := curve.PairingProduct(h_arr, v_arr)
	if ok {
		return aggPt.Equals(curve.GetGTIdentity())
	}
	return ok
}

// Verify verifies an aggregate signature type.
func (a *AggSig) Verify(curve CurveSystem) bool {
	return VerifyAggregateSignature(curve, a.sig, a.keys, a.msgs)
}

func hashToG1(curve CurveSystem, message []byte) Point {
	h := solsha3.SoliditySHA3(message)
	return curve.GetG1().Mul(new(big.Int).SetBytes(h))
}

BLSExample.sol

pragma solidity ^0.4.14;

/*
Example of how to verify BLS signatures and BGLS aggregate signatures in Ethereum.

Signatures are generated using https://github.com/Project-Arda/bgls
Code is based on https://github.com/jstoxrocky/zksnarks_example
*/

contract BLSExample {
    struct G1Point {
        uint X;
        uint Y;
    }
    // Encoding of field elements is: X[0] * z + X[1]
    struct G2Point {
        uint[2] X;
        uint[2] Y;
    }

    /// @return the generator of G1
    function P1() internal returns (G1Point) {
        return G1Point(1, 2);
    }

    /// @return the generator of G2
    function P2() internal returns (G2Point) {
        return G2Point(
            [11559732032986387107991004021392285783925812861821192530917403151452391805634,
            10857046999023057135944570762232829481370756359578518086990519993285655852781],

            [4082367875863433681332203403145435568316851327593401208105741076214120093531,
            8495653923123431417604973247489272438418190587263600148770280649306958101930]
        );
    }

    //Example of BLS signature verification
    function verifyBLSTest() returns (bool) {

        bytes memory message = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f31";

        G1Point memory signature = G1Point(11181692345848957662074290878138344227085597134981019040735323471731897153462, 6479746447046570360435714249272776082787932146211764251347798668447381926167);

        G2Point memory v = G2Point(
            [18523194229674161632574346342370534213928970227736813349975332190798837787897, 5725452645840548248571879966249653216818629536104756116202892528545334967238],
            [3816656720215352836236372430537606984911914992659540439626020770732736710924, 677280212051826798882467475639465784259337739185938192379192340908771705870]
        );

        G1Point memory h = hashToG1(message);

        return pairing2(negate(signature), P2(), h, v);
    }

    //Example of BGLS signature verification with 2 signers
    //Note that the messages differ in their last character.
    function verifyBGLS2() returns (bool) {

        uint numberOfSigners = 2;

        G1Point memory signature = G1Point(7985250684665362734034207174567341000146996823387166378141631317099216977152, 5471024627060516972461571110176333017668072838695251726406965080926450112048);

        bytes memory message0 = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f30";
        bytes memory message1 = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f31";

        G2Point memory v0 = G2Point(
            [15516709285352539082439213720585739724329002971882390582209636960597958801449, 19324541677661060388134143597417835654030498723817274130329567224531700170734],
            [16550775633156536193089672538964908973667410921848053632462693002610771214528, 10154483139478025296468271477739414260393126999813603835827647034319242387010]
        );

        G2Point memory v1 = G2Point(
            [14125383697019450293340447180826714775062600193406387386692146468060627933203, 10886345395648455940547500614900453787797209052692168129177801883734751834552],
            [13494666809312056575532152175382485778895768300692817869062640713829304801648, 10580958449683540742032499469496205826101096579572266360455646078388895706251]
        );

        G1Point memory h0 = hashToG1(message0);
        G1Point memory h1 = hashToG1(message1);

        G1Point[] memory a = new G1Point[](numberOfSigners + 1);
        G2Point[] memory b = new G2Point[](numberOfSigners + 1);
        a[0] = negate(signature);
        a[1] = h0;
        a[2] = h1;
        b[0] = P2();
        b[1] = v0;
        b[2] = v1;

        return pairing(a, b);
    }

    //Example of BGLS signature verification with 3 signers
    //Note that the messages differ in their last character.
    function verifyBGLS3() returns (bool) {

        uint numberOfSigners = 3;

        G1Point memory signature = G1Point(385846518441062319503502284295243290270560187383398932887791670182362540842, 19731933537428695151702009864745685458233056709189425720845387511061953267292);

        bytes memory message0 = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f30";
        bytes memory message1 = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f31";
        bytes memory message2 = hex"7b0a2020226f70656e223a207b0a20202020227072696365223a2039353931372c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333134323430302c0a2020202020202269736f223a2022323031362d31322d33315430303a30303a30302e3030305a220a202020207d0a20207d2c0a202022636c6f7365223a207b0a20202020227072696365223a2039363736302c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d2c0a2020226c6f6f6b7570223a207b0a20202020227072696365223a2039363736302c0a20202020226b223a20312c0a202020202274696d65223a207b0a20202020202022756e6978223a20313438333232383830302c0a2020202020202269736f223a2022323031372d30312d30315430303a30303a30302e3030305a220a202020207d0a20207d0a7d0a6578616d706c652e636f6d2f6170692f32";

        G2Point memory v0 = G2Point(
            [1787282038370667094324364195810339512415273589223814213215040505578200405366, 414568866548933554513940840943382696902163788831396286279770126458218272940],
            [6560020551439455112781785895092032589010633560844445112872109862153018855017, 19411093226570397520343120724285433000937737461010544490862811136406407315543]
        );

        G2Point memory v1 = G2Point(
            [14831125462625540363404323739936082597729714855858291605999144010730542058037, 8342129546329626371616639780890580451066604883761980695690870205390518348707],
            [808186590373043742842665711030588185456231663895663328011864547134240543671, 1856705676948889458735296604372981546875220644939188415241687241562401814459]
        );

        G2Point memory v2 = G2Point(
            [12507030828714819990408995725310388936101611986473926829733453468215798265704, 16402225253711577242710704509153100189802817297679524801952098990526969620006],
            [18717845356690477533392378472300056893077745517009561191866660997312973511514, 20124563173642533900823905467925868861151292863229012000403558815142682516349]
        );

        G1Point memory h0 = hashToG1(message0);
        G1Point memory h1 = hashToG1(message1);
        G1Point memory h2 = hashToG1(message2);

        G1Point[] memory a = new G1Point[](numberOfSigners + 1);
        G2Point[] memory b = new G2Point[](numberOfSigners + 1);
        a[0] = negate(signature);
        a[1] = h0;
        a[2] = h1;
        a[3] = h2;
        b[0] = P2();
        b[1] = v0;
        b[2] = v1;
        b[3] = v2;

        return pairing(a, b);
    }

    /// @return the result of computing the pairing check
    /// e(p1[0], p2[0]) *  .... * e(p1[n], p2[n]) == 1
    /// For example pairing([P1(), P1().negate()], [P2(), P2()]) should
    /// return true.
    function pairing(G1Point[] p1, G2Point[] p2) internal returns (bool) {
        require(p1.length == p2.length);
        uint elements = p1.length;
        uint inputSize = elements * 6;
        uint[] memory input = new uint[](inputSize);

        for (uint i = 0; i < elements; i++)
        {
            input[i * 6 + 0] = p1[i].X;
            input[i * 6 + 1] = p1[i].Y;
            input[i * 6 + 2] = p2[i].X[0];
            input[i * 6 + 3] = p2[i].X[1];
            input[i * 6 + 4] = p2[i].Y[0];
            input[i * 6 + 5] = p2[i].Y[1];
        }

        uint[1] memory out;
        bool success;

        assembly {
            success := call(sub(gas, 2000), 8, 0, add(input, 0x20), mul(inputSize, 0x20), out, 0x20)
        // Use "invalid" to make gas estimation work
            switch success case 0 {invalid}
        }
        require(success);
        return out[0] != 0;
    }

    /// Convenience method for a pairing check for two pairs.
    function pairing2(G1Point a1, G2Point a2, G1Point b1, G2Point b2) internal returns (bool) {
        G1Point[] memory p1 = new G1Point[](2);
        G2Point[] memory p2 = new G2Point[](2);
        p1[0] = a1;
        p1[1] = b1;
        p2[0] = a2;
        p2[1] = b2;
        return pairing(p1, p2);
    }

    function hashToG1(bytes message) internal returns (G1Point) {
        uint256 h = uint256(keccak256(message));
        return mul(P1(), h);
    }

    function modPow(uint256 base, uint256 exponent, uint256 modulus) internal returns (uint256) {
        uint256[6] memory input = [32, 32, 32, base, exponent, modulus];
        uint256[1] memory result;
        assembly {
            if iszero(call(not(0), 0x05, 0, input, 0xc0, result, 0x20)) {
                revert(0, 0)
            }
        }
        return result[0];
    }

    /// @return the negation of p, i.e. p.add(p.negate()) should be zero.
    function negate(G1Point p) internal returns (G1Point) {
        // The prime q in the base field F_q for G1
        uint q = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
        if (p.X == 0 && p.Y == 0)
            return G1Point(0, 0);
        return G1Point(p.X, q - (p.Y % q));
    }

    /// @return the sum of two points of G1
    function add(G1Point p1, G1Point p2) internal returns (G1Point r) {
        uint[4] memory input;
        input[0] = p1.X;
        input[1] = p1.Y;
        input[2] = p2.X;
        input[3] = p2.Y;
        bool success;
        assembly {
            success := call(sub(gas, 2000), 6, 0, input, 0xc0, r, 0x60)
        // Use "invalid" to make gas estimation work
            switch success case 0 {invalid}
        }
        require(success);
    }
    /// @return the product of a point on G1 and a scalar, i.e.
    /// p == p.mul(1) and p.add(p) == p.mul(2) for all points p.
    function mul(G1Point p, uint s) internal returns (G1Point r) {
        uint[3] memory input;
        input[0] = p.X;
        input[1] = p.Y;
        input[2] = s;
        bool success;
        assembly {
            success := call(sub(gas, 2000), 7, 0, input, 0x80, r, 0x60)
        // Use "invalid" to make gas estimation work
            switch success case 0 {invalid}
        }
        require(success);
    }

}

main.go

package main

import (
	"crypto/rsa"
	"fmt"
	"crypto/rand"
	"os"
	"math/big"
	. "./bgls"
)

func bls() {
	curve := CurveSystem(Altbn128)

	//generate key
	x, _, X, _ := KeyGen(curve)

	message := []byte("TEST")

	//create signature
	sig := Sign(curve, x, X, message)

	//verify
	fmt.Println("verification:", VerifySingleSignature(curve, sig, X, message))

	fmt.Println("sig:", sig.ToAffineCoords())
	fmt.Println("message:", bytestohex(message))
	fmt.Println("key", X.ToAffineCoords())
}

func bgls() {
	number_of_signers := 10
	curve := CurveSystem(Altbn128)

	var sigs []Point
	var publickeys []Point
	var msgs [][]byte

	//Initialization
	for i := 0; i < number_of_signers; i++ {
		//generate key
		x, _, X, _ := KeyGen(curve)

		//create message
		message := []byte("TEST" + string(i))

		//create signature
		sig := Sign(curve, x, X, message)

		//save for later
		publickeys = append(publickeys, X)
		msgs = append(msgs, message)
		sigs = append(sigs, sig)
	}

	//aggregate signature
	aggsig := AggregateSignatures(sigs)

	//verify
	fmt.Println(VerifyAggregateSignature(curve, aggsig, publickeys, msgs))

	//print signature
	fmt.Println("sig:", aggsig.ToAffineCoords())

	//print keys
	for j := 0; j < len(publickeys); j++ {
		fmt.Println("key:", j, publickeys[j].ToAffineCoords())
	}

	//print messages
	for k := 0; k < len(publickeys); k++ {
		fmt.Println("msg:", k, bytestohex(msgs[k]))
	}
}

@roman-kashitsyn @enzoh

Thanks for providing such a complex bls implementation in Solidity.

I have one question
BlsExample: Line:60
What is the size of each signature component of G1 ??

Hi there, it has been a while but will give it a try. The G1Point struct is given in the same file. It has two attributes, both of type uint. According to the docs, uint has a size of 256 bits.

Thanks for clarity on this and I am very happy to see your response here.
I have a public key and signature (48 bytes and 96 bytes)

How to convert them into G1 and G2 format so that this smart contract can understand.

Steps to get sample public key and private key from bls dkg rust

git clone https://github.com/amitcz/bls-12-381/blob/master/src/key_gen/tests.rs
Run the testcase : Threshold Signature ()
Again thankful for you precious time :)
Awaiting response.

Hi Amit, thanks for your interest in my gist but I left cryptography years ago and do not plan to get back into it. The gist above is based on another github repo. Some links that might be useful:

• StackExchange post by me
• Nicely written more recent article
• My paper for which I built this code

Hope this helps you and good luck!

Is it possible to verify that one specific public key is part of the aggregated signature?
Basically instead of

VerifyAggregateSignature(curve, aggsig, publickeys, msgs)

something like

VerifyAggregateSignature(curve, aggsig, singlePublicKey, singleMsg)