Hi @davinet ,
thanks for your questions, nice to see that you were diving into the details of the Lisk-BFT paper 
.
I don’t name a concrete signature scheme in the paper, but a suitable signature scheme with the desired properties would be the BLS signature schema as introduced in LIP 0038. Note that we will already use this signature scheme as part of interoperability in the upcoming release (Lisk Core 4.0 and Lisk SDK 6.0), but not yet as part of the consensus protocol.
What this scheme allows is basically the following: Assume you have a message m and n public-private key pairs (pk_1, sk_1), ..., (pk_n, sk_n). Further, assume a subset of these keys sign the message m. Without loss of generality, let us assume that m is signed by the first k keys and the corresponding signatures are sig_1, ..., sig_k. Then you can aggregate sig_1, ..., sig_k into one signature sig and instead of checking each of the sign_i with respect to the public key pk_i and message m, you can just do one verification of sign with respect to m and the aggregate public key computed from pk_1, ..., pk_k. Efficient means here:
-
Space efficient: Instead of having to transmit
k signatures over the network, you can just transmit the aggregate BLS signature sig and a bitmap saying which key-pair signed over the network. Note that strictly speaking the space requirement is still O(n) for n participants as you need at least one bit for each participant due to the bitmap.
-
Time efficient: You just need to run one signature verification instead of
k. The number of operations still scales linearly with k as you need to compute the aggregate public key from k public key. This operation is a lot faster than signature verification in the case of BLS signatures. I believe the asymptotic performance should be O(k) as checking signatures in a signature scheme with fixed size keys is constant time.
Apart from these asymptotic theoretic bounds, I think it is more relevant to consider the actual running times in practice. Here is a benchmark for the JavaScript library from ChainSafe, for instance. Another insightful reference might be this old discussion about introducing BLS signatures in Ethereum.
Now, to how this could help to improve the Lisk-BFT protocol. Recall that in the general consensus framework there are two types of messages:
-
Prevote(B, T, V ), a prevote of validator V for block B where T is the tip of the chain of validator V.
-
Precommit(B, T, V ), a precommit of validator V for block B where T is the tip of the chain of validator V.
Concretely, in an implementation a validator with key-pair (pk_i, sk_i) could sign the following message
"LSK_PREVOTE_" + 256 bit hash of B + 256 bit hash of T
and this would be the same as sending the message Prevote(B, T, V ). Note that the string “LSK_PREVOTE_” is a message tag as introduced in LIP 0037 to make it clear that the validator is signing a prevote. Then you could aggregate all the signatures of validators signing this message into one signature of the same message as described above. This would allow for a very compact message with one aggregate signature that proves that at least 68 validators prevote for a certain block. The same technique could be used for precommits.
Overall, an improved version of Lisk-BFT could then work as follows:
- Block
B_1 is generated an added to the chain.
- At least 68 validators prevote for
B_1. The prevotes are aggregated into one message and added to the child block B_2 of B_1.
- At least 68 validators precommit for
B_1. The precommits are aggregated into one message and added to the child block B_3 of B_2. This means B_1 is now final.
I hope that clarifies your questions. Let me know if you have any further questions.
