Sender signatures and transition to symmetric cryptography

[alexpyattaev]

Problem

Thanks to @ripatel-fd for helping brainstorm this concept.
Currently, the packets sent over plain UDP (shreds, alpenglow votes, repair etc) look something like this:
IP | UDP | SIG | PAYLOAD

However, in some cases we do not need to be using aymmetric crypto. For example, shreds, when signed by a retransmitter, look something like this instead:
IP | UDP | SIG | PAYLOAD | RTX_SIG
RTX_SIG today is 64 byte public key signature, which is both slow to check and bulky. It is only checked by the receiver of the resigned shred, and then discarded/replaced, so a symmetric key signature could be used instead.

Similar problem exists in the case of votes in both TowerBFT and Alpenglow where we need to quickly discard obviously forged packets.

Proposal

The proposal is to attach a sender signature to the packets that is produced using a symmetric key derived via ECDH from information published over gossip. Gossip provides a highly reliable authenticated channel to broadcast the updated ephemeral keys to other cluster members. From there, we follow the Noise_KK handshake to come up with a symmetric key (sk) on each of the nodes. This key is then used to compute the MAC using ChaCha20-Poly1305. See also diagram below:

sequenceDiagram
loop  Gossip protocol
    Alice -->> Bob: (Public key a)
    Note over Bob: Compute sk for Alice
    Bob -->> Alice: (Public key b)
    Note over Alice: Compute sk for Bob
end
Note over  Alice, Bob: Votes 
    Bob ->> Alice: (Vote, MAC(Vote, sk))
    Alice ->> Bob: (Vote, MAC(Vote, sk))

Loading

We can generally avoid complex key rotation mechanisms in this case, since Solana packets have unique indices (shreds have shred ID, votes have block ID, repair has nonces) and are never repeated.

Only staked nodes require such a mechanism enabled, but due to its low cost all nodes may use it to make the cluster more resilient to attacks.

The sender signature is computed over the bytes of the entire packets as follows:
SENDER_SIG = Poly1305(SK, "UDP pseudoheader | UDP | SIG | PAYLOAD" )

For shreds:

The sender signature is to be truncated to 4 bytes and appended to the shred. We will want to reuse some of the legacy shred flags (chained probably?) to indicate that a given shred has a signature.

For Votes:

The sender signature is to be truncated to 4 bytes and appended to the Vote packet. A magic byte 0x01 should precede the signature to indicate its presence.

For Alpenglow votes:

All vote packets should include sender signatures in their format

This scheme provides 2 critical features:

• Much cheaper than QUIC and/or asymmetric crypto all the time
• Applicable to a variety of protocols
• Backwards compatibility is achieved since legacy implementations do not read past the end of the packet, and will thus ignore the signatures completely

[bw-solana]

Interesting idea. A few thoughts as I read through:

1. Have we quantified how much CPU load / latency retransmit sigs are adding? Back of the napkin math would be 64 shreds * 50us per sig every 400ms = 8ms of CPU load per second. I'm assuming we can sign in parallel, so probably negligible (50us) latency here.
2. Have we quantified the block byte reduction? My understanding is we shave off up to 64 shreds * (64B-17B) = 3008B per block (~0.1% reduction) --> ~7kBps bandwidth
3. I'll need to think through the upgrade/downgrade process a bit more... I think we would need to stage adding the code to receive the key material, use the key material to verify shreds received that conform to the new type, start generating the new type, stop sending the old type, actively reject old types.
4. I haven't looked deeply into how we handle receiving retransmitter signed shreds today. How would it handle this new form? Would it fail deserialization because the signature size is unexpected?
5. I'll need to think more about any complications that arise from this idea + repair nonce

My overall take is this should provide a small improvement to shred pipeline bandwidth and block capacity at the cost of some extra complexity

[alexpyattaev]

@bw-solana you are missing the fact that signatures would apply to all shreds, sent by all nodes, including the leader. This would allow us to drop all non-signed shreds using symmetric key cryptography, as well as remove the need for specail treatment of the last coding batch.

[bw-solana]

thank you, this makes sense