solana: Web3.js transaction serialize => deserialize => serialize can produce "Signature verification failed" due to bug in Message serialization

Problem

The logic here https://github.com/solana-labs/solana-web3.js/blob/74007a55afa29b36e0535bb9bcff3b64dda9b19e/src/transaction.ts#L261-L281

Can lead to different orderings to accountMetas after serializing and deserializing. The “content” of the transaction is the same, however the accountKeys flipped around. So long as the indices still hold true for writable accounts, the transaction will function the same.

The issue is that this is then serialized and used to create a transaction signature. So this non-determinism can mean that a previously correct signature is now incorrect.

Code to reproduce:

    const signer = Keypair.generate();
    const acc0Writable = Keypair.generate();
    const acc1Writable = Keypair.generate();
    const acc2Writable = Keypair.generate();
    const t0 = new Transaction({
      recentBlockhash: "HZaTsZuhN1aaz9WuuimCFMyH7wJ5xiyMUHFCnZSMyguH",
      feePayer: signer.publicKey
    });
    t0.add(new TransactionInstruction({
      keys: [{
        pubkey: signer.publicKey,
        isWritable: true,
        isSigner: true
      }, {
        pubkey: acc0Writable.publicKey,
        isWritable: true,
        isSigner: false
      }],
      programId: Keypair.generate().publicKey
    }))
    t0.add(new TransactionInstruction({
      keys: [{
        pubkey: acc1Writable.publicKey,
        isWritable: false,
        isSigner: false
      }],
      programId: Keypair.generate().publicKey
    }))
    t0.add(new TransactionInstruction({
      keys: [{
        pubkey: acc2Writable.publicKey,
        isWritable: true,
        isSigner: false
      }],
      programId: Keypair.generate().publicKey
    }))
    t0.add(new TransactionInstruction({
      keys: [{
        pubkey: signer.publicKey,
        isWritable: true,
        isSigner: true
      },{
        pubkey: acc0Writable.publicKey,
        isWritable: false,
        isSigner: false
      },  {
        pubkey: acc2Writable.publicKey,
        isWritable: false,
        isSigner: false
      }, {
        pubkey: acc1Writable.publicKey,
        isWritable: true,
        isSigner: false
      }],
      programId: Keypair.generate().publicKey
    }))
    t0.partialSign(signer);
    const t1 = Transaction.from(t0.serialize());
    t1.serialize()

A workaround is to, before pre-signing the transaction, run Transaction.from(tx.serialize({ requireAllSignatures: false })). Then sign the transaction and serialize. This ensures the ordering doesn’t get jumbled.

Proposed Solution

Add a default sorting here based on the alphabetical (or just numerical) sorting of the public keys so that this function is deterministic.

https://github.com/solana-labs/solana-web3.js/blob/74007a55afa29b36e0535bb9bcff3b64dda9b19e/src/transaction.ts#L261