Optimization of Storage/Network through BLS Signature Aggregation

[vang1ong7ang]

Summary

As it is comment here Link:

Since every CN must sign its message, best approach here would be to have aggregated Schnorr sigs, so space is not affected by increasing list sizes. This aggregation is good, because it allows other nodes to receive full packages with a least 2f+1 confirmations, proving that state is correct.

Right now we still have not dozens of nodes, so a simple approach would work already... let's discuss this before release Neo 3 (perhaps with Schnorr already, I don't know). But perhaps, direct retransmission is good already too, we must experiment that in some months.

Actually BLS signature can be shorter than schnorr signature, but need more computing resources. But I think it is acceptable for consensus.

Do you have any solution you want to propose?

References are here:

BLS Wikipedia

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps

DEMO implement based on PBC is here:

package pbcsm

import (
	"hash"

	"pbc"
)

type PairingBasedCryptographySignatureMethod struct {
	opair *pbc.Pairing
	og    *pbc.Element
	fhash func() hash.Hash
}

func (p *PairingBasedCryptographySignatureMethod) KeyGeneration() ([]byte, []byte) {
	osk := p.opair.NewZr().Rand()
	opk := p.opair.NewG2().PowZn(p.og, osk)
	return osk.Bytes(), opk.Bytes()
}

func (p *PairingBasedCryptographySignatureMethod) Signing(sk []byte, msg string) []byte {
	oh := p.opair.NewG1().SetFromStringHash(msg, p.fhash())
	osk := p.opair.NewZr().SetBytes(sk)
	osig := p.opair.NewG2().PowZn(oh, osk)
	return osig.Bytes()
}

func (p *PairingBasedCryptographySignatureMethod) Verification(pk []byte, msg string, sig []byte) bool {
	oh := p.opair.NewG1().SetFromStringHash(msg, p.fhash())
	opk := p.opair.NewG2().SetBytes(pk)
	osig := p.opair.NewG2().SetBytes(sig)
	op1 := p.opair.NewGT().Pair(oh, opk)
	op2 := p.opair.NewGT().Pair(osig, p.og)
	return op1.Equals(op2)
}

package pbcsm

type AggregationPairingBasedCryptographySignatureMethod struct {
	*PairingBasedCryptographySignatureMethod
}

func (a *AggregationPairingBasedCryptographySignatureMethod) Aggregation(sigs [][]byte) []byte {
	oret := a.opair.NewG2().Set1()
	for _, v := range sigs {
		osig := a.opair.NewG2().SetBytes(v)
		oret.Mul(oret, osig)
	}
	return oret.Bytes()
}

func (a *AggregationPairingBasedCryptographySignatureMethod) AggregateVerification(pks [][]byte, msgs []string, sig []byte) bool {
	if len(pks) != len(msgs) {
		return false
	}

	op1 := a.opair.NewGT().Set1()

	for i := range pks {
		msg := msgs[i]
		pk := pks[i]
		oh := a.opair.NewG1().SetFromStringHash(msg, a.fhash())
		opk := a.opair.NewG2().SetBytes(pk)
		op := a.opair.NewGT().Pair(oh, opk)
		op1.Mul(op1, op)
	}

	osig := a.opair.NewG2().SetBytes(sig)
	op2 := a.opair.NewGT().Pair(osig, a.og)
	return op1.Equals(op2)
}

Where in software does this update applies to?

• Consensus
• P2P (TCP)

[vang1ong7ang]

Additional Reference Here:

BLS Multi-Signatures With Public-Key Aggregation

The following attack may be useful.

[shargon]

This is something very important in order to reduce the size of the Multisignatures in general, Blocks and ConsensusMessages will reduce his size, that's means: less size + less network overload= more TPS.

[vncoelho]

@vang1ong7ang, it was a great pleasure to meet you.
Good discussions.

Thanks for opening this discussion and sending this nice reference.
About the Rogue Public-Key Attack, as we discussed, maybe it will not be a problem for us. But it is good that you highlighted that here, we should keep that in mind.

Let's move on over this topic and see the impacts on rebroadcasting.

[anatoly-bogatyrev]

I agree with @vang1ong7ang.
If we want to achieve real less-sized blockchain, then maybe it will be good to look at BLS.
Need to research this. BLS is slower than Schnorr signatures, but maybe this is not a big problem since the blocks are in any case accepted with a fixed time interval.
Need to understand how easy it will be to integrate BLS into dBFT consensus.
We are implementing dBFT lib in Golang for NeoGO right now. When this task is complete, we can try to integrate the implementation of BLS into dBFT (as proof-of-concept only) and look how it works.

[vncoelho]

@anatoly-bogatyrev, integrate it into the dBFT consensus will not be problem for us.
For BLS we just need to pick the desired paring friendly curve.

I investigated a little bit more and, for the dBFT, the Schnorr may be enough and since we are going to use them on the P2P CN payloads (which requires fast verification and propagation), I am thinking that Schnorr can be the first improvement for us to move right now.
Schnorr are more costly when we use n x m signature schemes. But we can use m x m since we already know all public keys in advance. In just need nodes to be aware about who is signing, then, the verification will follow smooth.

[erikzhang]

If we want to do it, we should not only consider consensus, but also consider the feasibility of using it for common multiple signature addresses.

[vang1ong7ang]

@anatoly-bogatyrev @vncoelho

If we want to achieve real less-sized blockchain, then maybe it will be good to look at BLS.
Need to research this. BLS is slower than Schnorr signatures, but maybe this is not a big problem since the blocks are in any case accepted with a fixed time interval.

I investigated a little bit more and, for the dBFT, the Schnorr may be enough and since we are going to use them on the P2P CN payloads (which requires fast verification and propagation), I am thinking that Schnorr can be the first improvement for us to move right now.

I agree with both ideas and two additional comments here.

1. Bilinear map in BLS may cost a lot in computing resources, still need experiments to verify how much it can improve the consensus
2. BLS based on PBC is not optimal implement.

[anatoly-bogatyrev]

@vncoelho Yes, about the implementation of BLS to consensus I just told about some fast draft for an experiment as a proof-of-concept, not full implementation.
I agree that the Schnorr may be enough now.
My main interest here is in any multi-signature verification (m-of-n Schnorr or BLS) opcode/syscall, in order to reduce the impact of verification costs within a smart contract of our multisigned structures in the NeoFS smart contract.

Schnorr are more costly when we use n x m signature schemes. But we can use m x m since we already know all public keys in advance. In just need nodes to be aware about who is signing, then, the verification will follow smooth.

But how can we know who signed the transaction during verification from all consensus nodes?
Do you want to do it in the same way as now?: the NextConsensus block header will contain all pubkeys of the consensus nodes, and all possible combinations are checked in the verification method by brute force? Or did I misunderstand?

[anatoly-bogatyrev]

@erikzhang

If we want to do it, we should not only consider consensus, but also consider the feasibility of using it for common multiple signature addresses.

I agree, as was discussed in a separate thread with NeoReaserach and Red4Sec, can be observed such scope as:

Implementation as separate Syscalls to give the possibility to use aggregated signature verification from Smart contracts:

• n-of-n implementation
• m-of-n implementation (the same as n-of-n in case of BLS, Threshold in case of Schnorr (with restriction m>=n/2))

Implementation aggregated signatures verification to Neo protocol:

• Change CheckSig and CheckMultisig Syscalls or use new calls for aggregated signatures
• Migration of Neo multisig addresses to the new approach
• Implementation of aggregated signatures to dBFT consensus protocol to reduce the size of the Neo blockchain

UPD: Also this can be integrated with crypto extensions in the VM ( https://medium.com/neo-smart-economy/behind-pr-149-a-bright-future-for-neovm-and-neo-3-3b779e8749c4 ) described by @igormcoelho and @vncoelho .

[erikzhang]

It's time to vote. BLS or Schnorr.

👍 for BLS, and 👎 for Schnorr.

[vncoelho]

It is still hard for me to vote in one, @erikzhang....aehauheauea I voted for both.
I think Schnorr will be more efficient for the P2P of the Consensus, while the BLS may delay Payload efficiently rebrodcasting. In this sense, I am not sure.

But BLS have other good applications.

[vang1ong7ang]

Add some additional comments to BLS:

The BLS aggregation signature scheme does not have a threshold feature. There are two solutions for adding threshold characteristics:

• From the cryptographic level, use Linear Secret Sharing Scheme (LSSS). n participating nodes jointly generate a secret (signature private key), each holding the corresponding secret share. When signing, cooperate to recover the secret for signature. The interaction between multiple nodes, each node needs to receive and send messages n*(n-1) times when generating secret. This cost a lot in interaction data and latency!
• From a logical level, check the public keys in the block header. If the threshold is not met, the output is false. This scheme can reduce the number of interactions, and each node can generate a public-private key pair by itself, without interaction. But BLS public keys are long. It cost a lot to log all signed public key to block header even offset the advantages of signature aggregation. But we can optimize it (for example log the index of public key or use a bitset to flag who has already signed. Then the cost is acceptable.)

[vang1ong7ang]

Hard for me to vote in one, too. Same idea with @vncoelho

I agree that the schnorr may be enough now and maybe easier implement and BLS is so attractive.

[anatoly-bogatyrev]

Last week, @fyrchik Evgeny Stratonikov prepared proof-of-concept implementation of BLS at the dBFT consensus golang lib.
As he told, It is not too hard to replace signatures in dBFT with BLS signatures.
The only place where changes occurred is a final step of block preparing: instead of storing all signatures in an array we can just combine them into a single signature. In C# code only Neo.SmartContract.ContractParameterContext.AddSignature() is the thing that needs to change its logic. We don’t have it in our current implementation which is used by InnerRing.
All other changes are pretty straightforward.
When the opportunity arises, we will do a series of experiments. But in the zeroth approximation, the transition to BLS signatures is possible and can pass relatively easily.

[vncoelho]

Great to hear, @anatoly-bogatyrev.

From the P2P perspective, the block should support mix signatures. Then we can decide when it is worth to use BLS or singlesig.

[vncoelho]

@vang1ong7ang, let's come back with this, in fact, this improvement can also enter as part of the effort for improving dBFT 2.0 to dBFT 3.0, since it will play an important piece on Block generation and information sharing during the Byzantine agreement.

[eryeer]

@anatoly-bogatyrev @fyrchik Seems BLS signature can also improve the transaction signature verification speed, Could you provide a performance comparison report between BLS signature and current signature algorithm after the BLS implementation completed?

[fyrchik]

#1332 (comment)

I believe signature checking can be made more fast by providing index of validators which have signed the block (may be just as a hint). It takes negligible amount of space (2-byte mask) and in this case it will also be easy to parallelize signature checking.
In case of BLS this hint tells us which keys we should combine. It can significantly speed up restoring from dump.
A possible option is also to fallback to a usual algorithm if a hint is invalid or a check fails, which won't make our life any harder because most of the time signature checks during restore will be ok.

[fyrchik]

I have benchmarked 3 implementations: current algorithm, ecdsa + info about used public keys, BLS.
There were 7 public keys and 5 signatures.
Here are the results.

BenchmarkVerify/ecdsa_no_hint-8         	    2020	    545936 ns/op
BenchmarkVerify/ecdsa_with_hint-8       	    3068	    382955 ns/op
BenchmarkVerify/bls_with_hint-8         	     406	   2936669 ns/op

Most of the time in BLS case is for an actual verification, not an aggregation of public keys.
But I am not sure that I have taken fastest available BLS implementation.

[vncoelho]

@fyrchik, what are the number of the second column? And what are the third, ns/op?

In our previous insights from the literature, we noticed that BLS would be slow on Verification. That is why we were afraid of using it for Blocks, because all nodes need to Verify.

[vncoelho]

Guys, take a look at this, a good cryptographer here from Brazil, that also contributes in MONERO, sent me this idea: https://medium.com/cryptoadvance/ecdsa-is-not-that-bad-two-party-signing-without-schnorr-or-bls-1941806ec36f

[shargon]

Any news about it? i think that it's a good feature

[roman-khimov]

I propose closing this one. It is an interesting feature that really makes signatures shorter, but:

• it's much slower compared to ECDSA (we've tried, really)
• for an already existing network it requires significant changes to exchange additional keys

So I'd say we don't need it now. If there are any other real useful applications for it (just size is not enough to justify), this can be reopened/discussed in future.

[vang1ong7ang]

@roman-khimov yes. let's close this outdated one and propose new ones if needed