Aggregate signature schema to aggregate messages in child block of B1

Could you please elaborate about this text from Lisk-BFT scientific paper: “ Using an aggregate signature scheme, these messages could be efficiently aggregated in the network and only added to any child block of Bl by the next proposer. Applying the properties of the general consensus framework analogous to the case of the Lisk-Bft protocol, it is possible to show that a block can be finalized already after two additional blocks are added as descendants.`

Researching about it I realized that exists aggregate signature schema that utilize the public key from a set like all top 101 block proposers requiring only 1 private key from such set of proposers, and the validation of such signature could be done in polynomial time. However, I would like to understand how it would work, even it superficially, and how it would allowing a block be finalized after two additional blocks added as descendants.

1 Like

Hi @davinet ,

thanks for your questions, nice to see that you were diving into the details of the Lisk-BFT paper :grinning:.

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.

1 Like

Hi Jan,

First of all thank you very much for your explanation, very interesting. BLS signature rocks, I want to test it :slight_smile:

Yeah, the mentioned signature is called Ring Digital Aggregate Signature. You can find some more information regarding it in “Digital signature scheme for information
non-repudiation in blockchain: a state of the art review”.

Do you know when will Lisk introduce the BLS signature in the Lisk-BFT consensus protocol? I can say that it is impressive thinking to use Lisk, a javascript-based blockchain, with such efficiency, and within a public blockchain.

Thank you!

1 Like

Do you know when will Lisk introduce the BLS signature in the Lisk-BFT consensus protocol?

Sorry for the late reply, I missed your follow-up question.

So reducing the time to finality has been on our roadmap for the Diamond phase. This topic can potentially include using BLS signatures in the Lisk-BFT consensus protocol. We don’t have any concrete specifications about this yet and I also cannot give you a timeline for it, but as soon as we have something more concrete, we would share the research here.