Signature aggregation for block seal

[sgkim126]

Currently, a header has 30 signatures. It's almost 2KB. If we use signature aggregation for seal field, we can reduce the header size sharply.

[zmanian]

A number of us from Tendermint, Inc are interested reviewing any design work on aggregate schnorr signatures in consensus. Please keep us in the loop on any design specs or code that happens.

[sgkim126]

Hi @zmanian, Thank you for your interests. Our team will share discussions in this thread.

[HoOngEe]

We planned to implement key aggregation with the naive scheme discussed in (https://blockstream.com/2018/01/23/en-musig-key-aggregation-schnorr-signatures/). The problem of the naive scheme was that proving the actual possession of their private keys corresponding to each party's public key is not always possible in general transaction signing situations. But in our case, one can become a validator only after proving one's ownership of his/her private key corresponding to the proposed public key in the self nomination step.

[HoOngEe]

Secondly, we don't want to modify the previous generation of the Schnorr signature, but just want to aggregate it when it is stored in the header of the next proposal block. It would enormously reduce storage that the block header was occupying without interactive steps. However, to prevent modification of the previous Schnorr single signature implementation, we have to examine if H(m) is safe enough to use.

The Bitcoin community recommended to use hashed messages H(R || X || m) where R and X are public (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki). As far as I've thought, the advantages of inserting R in the hash is blocking replay attacks and by inserting X in the hash results in blocking another party from recovering public key X by local calculation with signature (R, S) only. Inserting X also makes transformed signatures, like (R,s + aH(R || m)), calculated from any a, invalid (This is valid for a public key X + aG with private key unknown). However, I still don't think that those three unintended possibilities would harm the Tendermint voting process.

Tomorrow, I'm going to start implementing the simplest scheme and afterwards, I'll revisit the security issue.

[HoOngEe]

Our current Schnorr single signature generation scheme is now hashing (R || m) (R denotes a public random nonce, m denotes a message) already. It is hashed inside of the secp256k1_schnorr_sig_sign function. It is inevitable to modify the signature generation scheme for aggregations. I'm going to investigate whether the Tendermint voting scheme could be secure without concatenating R when hashing.

[HoOngEe]

Without R, the situation will be turned into a disaster. For Schnorr signatures, hashing R is the means of proving the ownership of random nonce r, unlike ECDSA. Let's suppose an attack scenario such as the following:

Alice took a signature (R_1, S_1) for a message m_1, which is originally signed by Bob. Let's also say that Bob's public key is X. Next, Alice can carry out an impersonation attack on any message. If she wants to sign a message m_2 borrowing Bob's authority, then all she has to do is publish (R_2, S_2) = (R_1 + (H(m) - H(m')) * X, S_1) with message m_2. The verification will say S_2 * G = S_1 * G = R_1 + H(m) * X = (R_1 + H(m) * X - H(m') * X) + H(m') * X = R_2 + H(m') * X. She can impersonate Bob completely because the signature did not include the proof of ownership of random nonce r and Alice's signature has become accepted without knowing the random nonce r_2 corresponding to R_2.

In the Tendermint voting scheme, this would result in proxy voting to get more rewards.

[ValarDragon]

The scheme you're referring to AFAIU is the CoSI scheme, with proof of possesion / KOSK. It has been proven that its essentially impossible to prove CoSI secure unless its running in less than a logarithmic number of concurrent instances https://eprint.iacr.org/2018/417.pdf, even with proofs of posession. For this reason, I'd recommend not using CoSI, as it may likely cause problems in the future as you want to integrate more scalability mechanisms, or want validators to share keys across chains.

I suggest implementing mBCJ from the same paper instead, if you feel comfortable with the reviews on the scheme thus far, as it has the great property of being provably secure under normal settings.

[HoOngEe]

@ValarDragon Thank you very much. We'll study the paper especially about mBCJ and examine the usability of it.

[byeongjee]

I'm going to achieve signature aggregation with BLS signature scheme with proof of posession in self nomination step. I'll use https://github.com/algorand/bls_sigs_ref and https://github.com/algorand/pairing-plus for this. I'll also add an account address for each validator because the validator's public key cannot be converted into an account address anymore.

These are TODO checklists:

• [x] Fork the libraries and bring their types into foundry
• [x] Change block signing scheme and aggregate signatures in block seals
• [x] Introduce new account address for each validators
• [x] Add proof of posession to self nomination step

[byeongjee]

Address and public key handling in Foundry should be changed. Since we are planning to use two different signing schemes for transaction and block validation, we cannot share the same public key for the two uses anymore. Therefore, we need an alternative way of registering and searching validation public keys.

I'll change self-nomination message so that users can register their public keys through self-nomination. The public keys would be stored in validator sets, so that any user can search a validator's BLS public key from its transaction address. In other words, I'll change the type of validator set from Vec<Public> to Vec<(Address, BLSPublic)>, where the Address type stands for the transaction address, which is the blake hash of the public key.