Reduce Signatures Ideas

[GalRogozinski]

Summary

Currently we verify the BLS signatures of each message we send on the network. This heavy computation drains cpu resources. This document inspects ways to reduce this load.
This is an attempt to describe a way to do it without forks.

Rationale

Currently SSV operators' signatures, rather than the Validators', are used to verify messages on the wire in the networking layer. Since the operators' use lighter cryptography (~X100 faster), relying on their signatures in the protocol level can result in a significant performance boost.

However, dropping verification of the Validator's sig all together may open up a rouge key attack vector, assuming a malicious operator that signs correctly only with the Operator key.

SignedPartialSignatureMessage

SignedPartialSignatureMessage is a signed wrapper for PartialSignatureMessages which in turn contain an array of partial signed beacon objects that can be aggregated to a fully signed beacon object that can be sent to the beacon chain.

CurrentlyBaseRunner.validatePartialSigMsgForSlot does 2 signature validations:

1. BaseRunner.VerifyByOperators verifies that the wrapper is correctly signed by identifying the operators with their respective Validator's public key.
2. BaseRunner.VerifyBeaconPartialSignature verifies the signature of the beacon objects themselves.

Improving VerifyByOperators

Ensure that the network layer validation checks that
SignedSSVMessage.OperatorID == SignedPartialSignatureMessage.Signer

Then simply skip this VerifyByOperators. We can rely on the network layer validation to authenticate the message via the operator's public key.

Improving VerifyBeaconPartialSignature

Naive

Don't verify your own signature if part of quorum. This works because of network layer validation.
Saves at most one BLS verification.

Optimistic Naive

Assume up to $F$ operators attempt the rouge key attack. Be optimistic and don't verify individual messages. Reconstruct the signature and verify it. If successful the process is done. If not, fall back to Naive verification. Signature validation can stop upon the discovery of $F$ invalid signatures. In the best case, that is expected to occur most of the times, we do only one BLS verification. In the worst case we do one extra BLS verification above naive.

Delegate validation to beacon node.

It may be possible to delegate the validation to the beacon node (we do it today, but we verify all sigs individually before, so it can't fail).

Optimistic with less BLS

Do the same as optimistic naive. The fallback should be different. Instead of validating signatures try to Reconstruct the sigs using different combinations that always include the operator's own partial signature. Once a different signature will be reconstructed, validate it. There will be $N-1 \choose N-F-1$ $- 1$ total combinations. So it certainly worth while for 4-members committee (2 combinations). A 13-members committee will have 494 combinations but it should still be worthwhile because no heavy pairing operations are involved (need to check).

Note

Explanation: If the operator couldn't trust itself it will be $N \choose N-F$. Also, we can omit the combination that triggered the fallback.

Not sure if this is worth doing because most of the times fallback is not expected to occur. Especially if we start helping users weed out malicious actors.

qbft.SignedMessage

In general, Validator's keys are not necessary for consensus, since we are not communicating with the beacon chain so we can rely soley on network layer validation.

However, consensus has justifications that are implemented with nested messages. Those have to be verified independently.

PreConsensusJustifications

As explained before each message is PartialSignatureMessage that has two checks. If we skip the VerifyByOperators check there will not be a network layer validation to back this up. Yet, if the second check succeeds it should be enough in order to verify the message, so it can still be skipped.

The second check, VerifyBeaconPartialSignature can be optimized. Instead of verifying each message in separate simply assume all messages are valid and reconstruct the signature. If the signature is valid we are done. If not, it is immaterial which specific message is the culprit and the check fails.

RoundChangeJustifications && ProposalJustifications

Currently we should note that the justifications are simply RoundChange and Prepared messages. Note that the signing root of each Prepared message is similar. Same goes for RoundChange... This means that we can do blsFastAggregateAndVerify! (Note: DataRound and Root may differ so we need to pre check before we aggregate)

Fork solution

If for qbft.SignedMessage we move fullData into Message, then it can be observed that all of our "SignedMessage" wrappers (both for protocol and network validation) look similar. They contain a signature, operator index(signer) and message data. We can combine them into a single wrapper that only utilizes operator signatures. This will enable us to also totally get rid of BLS in the consensus process.

[GalRogozinski]

@MatheusFranco99 this is an interesting read regarding the subject:
EdDsaBLS.pdf

They seemed to have gotten results that for small committees (like what we are using) changing BLS to EdDSA shouldn't matter much... didn't understand why exactly

[MatheusFranco99]

They conducted the experiments on WANs. It's expected that the message transmission time >>> processing time and, thus, small changes in processing time are insignificant.

[MatheusFranco99]

Nice!

[GalRogozinski]

@MatheusFranco99
did a little change

[MatheusFranco99]

Good work! ;)

Quick note/question:

Note that the signing root of each Prepared message is similar

This seems correct to me. But, regarding

Same goes for RoundChange...

, I think it's not the same case because Round-Change msgs can be diff regarding prepared data. Pls, correct me if I'm wrong.

[GalRogozinski]

I wrote about DataRound but I think you are right and the root can also be different.
So it should also be accounted for in a check

[GalRogozinski]

The main question here is that some optimizations are annoying and not sure if they can all appear in the spec

[GalRogozinski]

Also should we fork?

[GalRogozinski]

Can we quantify the expected performance gain @MatheusFranco99?

[MatheusFranco99]

To estimate a performance gain for each phase, let's assume:

• $bls.Verify \approx bls.Reconstruct$
• $bls.Sign \approx rsa.Sign$
• $bls.Verify \approx 69 \times rsa.Verify$
• $rsa.Sign \approx 32 \times rsa.Verify$
• $Gain = \frac{Old}{New}-1$

---

Approximations were taken from:

BenchmarkHerumiBLSVerify-5                          1011           1177797 ns/op
BenchmarkHerumiBLSSign-5                            2278            527296 ns/op
BenchmarkVerifyPKCS1v15OpenSSLMicrosoft-5          68980             17350 ns/op
BenchmarkSignPKCS1v15OpenSSLMicrosoft-5             2109            569766 ns/op

---

For partial signature phases, for $4$ operators, the gain for a normal case scenario would be:

• $Old = (bls.Sign + rsa.Sign) + 3 * (rsa.Verify + bls.Verify) + bls.Reconstruct + bls.Verify$
• $Now = (bls.Sign + rsa.Sign) + bls.Reconstruct + bls.Verify$
• $Gain \approx \frac{412}{202}-1 = 2.04 - 1 = 104$%

For the consensus phase, for $4$ operators, the gain for a normal case scenario (assuming 1 Proposal - 4 prepares - 3 commits) would be:

• Old:

(bls.Sign + rsa.Sign) + (rsa.Verify + bls.Verify) + # Proposal
(bls.Sign + rsa.Sign) + 4 * (rsa.Verify + bls.Verify) + # 4 Prepare
(bls.Sign + rsa.Sign) + 3 * (rsa.Verify + bls.Verify) # 3 commits

• Now:

(rsa.Sign) + (rsa.Verify) + # Proposal
(rsa.Sign) + 4 * (rsa.Verify) + # 4 Prepare
(rsa.Sign) + 3 * (rsa.Verify) # 3 commits

• $Gain \approx \frac{752}{104}-1 = 7.23 - 1 = 623$%

Note

These are performance improvements for the particular protocol step. They do not translate to an overall improvement since the bottleneck is, currently, outside the protocol nutshell (on message validation).
Nonetheless, once the bottleneck becomes the protocol execution (e.g. with a better network topology), these improvements will be translated into an overall improvement.

[MatheusFranco99]

@lior-blox @GalRogozinski
The requested estimation ⬆️