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

[ChewingGlass]

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

[ChewingGlass]

Created a PR to fix this issue

[apeTim]

Hey, do you think you can help me? #22391
I think you have described my problem. But Im using offline signing, so I cant user partialSign because I dont have signer object. If you will refactor my code to needed or just give advice I would be really happy!

[0xx400]

Hmm. After this change (#21724) , I can't sign offline transaction, generating by solana cli tool.

As soon as solana cli tool generate transaction with this order:

                const transaction2 = new web3.Transaction({
                    recentBlockhash: nonceBlockHash, //recentBlockhash.blockhash,
                    nonceInfo: {
                        nonce: nonceBlockHash,
                        nonceInstruction: new web3.TransactionInstruction({
                            keys: [
                                {isSigner: false, isWritable: true, pubkey: new web3.PublicKey(noncePubkey)},
                                {isSigner: false, isWritable: false, pubkey: new web3.PublicKey("SysvarRecentB1ockHashes11111111111111111111")},
                                {isSigner: true, isWritable: true, pubkey: serverPK}
                            ],
                            programId: new web3.PublicKey("11111111111111111111111111111111"),
                            data: toBuffer([4,0,0,0])
                        })
                    },
                    feePayer: mypk
                }).add(
                    web3.SystemProgram.transfer({
                        fromPubkey: wallet.publicKey,
                        toPubkey: serverPK,
                        lamports: price,
                    })
                );

this is example of transaction(done by this code with version 1.31):
https://explorer.solana.com/tx/5y5tbJVThh6p4KcgvaF6jF2KcctF4pN2Q7jFdSSd87T81k4MxGVku6mXywtRTC1NxULCmiFfjE4sHCAa4QQeV7uP?cluster=devnet

My workscenario:

1. 1st party sign transaction. (transaction is the same as solana with nonce generates) and send signature to 2nd party
2. I could create transation and use signature with regular solana tool like this:

solana transfer 8AsHVKhkMyRE2YLu4H7irCtMRXKuFkSjDUF6iSPJFuU3 0.022 -u devnet  --blockhash 4CdZtAxxztyx8dHsx6AdZoWjRHgFbPUWNuJ28ByuPnM1  --nonce 3fZWUdQoyoNoqgap5erQ8XpPebT3tieYtnpKF3HPbCHZ --allow-unfunded-recipient --nonce-authority 8AsHVKhkMyRE2YLu4H7irCtMRXKuFkSjDUF6iSPJFuU3 --signer 8AsHVKhkMyRE2YLu4H7irCtMRXKuFkSjDUF6iSPJFuU3=4Qcf5grANwL7LDcv6UiBhEe54ywDSGwmCiYV5T36tzbdToF4Uhs5G5unhQ1D7YhqFJSaU835CtuYWLAZ5TUhFUF5  -k /home/solana/soldata/wallet_tests_dest.json

3. with 1.31 I could sign transaction with ts code above. But with 1.32+ I got an error "Signature verification failed"

Same issue as #22391

PS. this is not a support message. Looks like sorting account breaks some working code.
PS2.

solana/sdk/program/src/message/legacy.rs

Line 87 in 7ba57e7

/// including program ids, are placed last in the set. No duplicates and order is preserved.

Here sorting is stable, so order of all accounts is determined by transaction list.

[0xx400]

Created PR. I think it could work. But I don't sure, I can't build it locally. If I got problem correct - problem with unstable sort in js. my bad. Problem is not only in sort order. we just can't recover original sort order from serialized msg.
Looks like rust lib have the same problem as soon as instruction store only index to accountMeta.
But make alphabetical sort of accounts breaks compatibility with rust library.
test suit is great!

[romeo4934]

Hi @jstarry!
Is the order of serialization part of the Solana spec officially?
Should the Solana Documentation be updated?
We have some problem here when we need to communicate between Dart Library and Js Library:
brij-digital/espresso-cash-public#184

[jstarry]

I don't think it's useful to enforce or follow any kind of canonical account key sorting method. The way Transaction.populate is decompiling the message account keys is losing the ordering used by the processed transaction so I think we have to get rid of that.

[ChikinDeveloper]

Hi!
Totally agree that it isn't useful to enforce it, but don't you think there should be some kind of deterministic developer standard for transaction serializations, in order to prevent this kind of issue?
Right now there's no guarantee that this implementation won't change in the future.

[romeo4934]

What would be the next step?
There are incompatibilities between librairies (Js, Dart etc..) when we are passing a serialization between different librairies.

[t-nelson]

IMO the next step is what jstarry mentioned above, deser needs to not be reordering anything. That's the fix.

Generally I question the motivation for doing a ser -> deser -> ser loop. There's not really any valid reason to do that. Only a compiled Message should be passed around for signing. Perhaps partialSign is implying it's intended for things that it's not