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:
espresso-cash/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

[0xx400]

Thanks. then, e.g. what a canonical way to sign offline nonced transaction, like here from web3?
https://docs.solana.com/offline-signing/durable-nonce

With cli I just write (in code with rust lib the same)

servsign3=`solana transfer $dest 0.1 -u devnet  --blockhash $nonceblockhash --nonce $nonceaddr    --from $clientaddr --fee-payer $clientaddr  --nonce-authority $server --sign-only | grep $serveraddr`

clientsign1=`$solana transfer $dest 0.1 -u devnet  --blockhash $nonceblockhash --nonce $nonceaddr    --from $clientaddr --nonce-authority $serveraddr -k $client --sign-only | grep $clientaddr`

solana transfer $dest 0.1 -u devnet  --blockhash $nonceblockhash --nonce $nonceaddr --from $clientaddr --fee-payer $clientaddr --allow-unfunded-recipient --nonce-authority $serveraddr --signer $servsign3 --signer $clientsign1

But, if one ot this signature are generating by web3 - I got different order of accounts - diffrent transaction and Signature verification failed.

[0xx400]

also, this reordering broke order of transaction for complex transaction. E.g.
for this transaction https://explorer.solana.com/tx/3mr8xU5ivLNTNv5MwkLWhvVvAKg69bEqNJgaJWwe1tmcivgnVtFBkbn1DGVjSPQUnw94oD66xEbi3ofQBGxQh5S1

we always have first account - is payer, second is new NFT address &etc.
But with this fix - nft addr could be on 3 or 4 place, for example. So, order depends not only the transaction, but also of the base58 string of accounts.

[Sotatek-DucPham]

I faced the same problem with the latest version of @solana/web3.js. So I have a temporary solution

Instead of Sign => Serialize => Deserialize => Serialize. I choose Serialize => Deserialize => Sign => Serialize.

[jordaaash]

I dug into the code and came up with what I think is causing this. Related: #23641, #23610, anza-xyz/wallet-adapter#350

1. solana/web3.js/src/message.ts

   Lines 12 to 25 in 17cc095

   	/**
   	* The message header, identifying signed and read-only account
   	*/
   	export type MessageHeader = {
   	/**
   	* The number of signatures required for this message to be considered valid. The
   	* signatures must match the first `numRequiredSignatures` of `accountKeys`.
   	*/
   	numRequiredSignatures: number;
   	/** The last `numReadonlySignedAccounts` of the signed keys are read-only accounts */
   	numReadonlySignedAccounts: number;
   	/** The last `numReadonlySignedAccounts` of the unsigned keys are read-only accounts */
   	numReadonlyUnsignedAccounts: number;
   	};

   
   Message, and the wire format of the message, does not store information that allows AccountMeta to be recreated per instruction. Only the number of signatures required, and the numbers of read-only accounts (signed and unsigned) are stored in the message header.

2. solana/web3.js/src/transaction.ts

   Lines 705 to 709 in 17cc095

   	isSigner:
   	transaction.signatures.some(
   	keyObj => keyObj.publicKey.toString() === pubkey.toString(),
   	) || message.isAccountSigner(account),
   	isWritable: message.isAccountWritable(account),

   
   Because of 1), when a Transaction is populated from a Message, if an account has isSigner or isWritable flags for any instruction, these flags will be propagated to the account for every instruction in the transaction. 


3. solana/web3.js/src/transaction.ts

   Lines 261 to 270 in 17cc095

   	// Sort. Prioritizing first by signer, then by writable
   	accountMetas.sort(function (x, y) {
   	const pubkeySorting = x.pubkey
   	.toBase58()
   	.localeCompare(y.pubkey.toBase58());
   	const checkSigner = x.isSigner === y.isSigner ? 0 : x.isSigner ? -1 : 1;
   	const checkWritable =
   	x.isWritable === y.isWritable ? pubkeySorting : x.isWritable ? -1 : 1;
   	return checkSigner || checkWritable;
   	});

   
   Because of 2), when AccountMeta are sorted by isSigner and isWritable, accounts that didn’t have isSigner or isWritable flags before serialization may have them after deserialization. The order of these is likely to change.


4. solana/web3.js/src/transaction.ts

   Lines 272 to 285 in 17cc095

   	// Cull duplicate account metas
   	const uniqueMetas: AccountMeta[] = [];
   	accountMetas.forEach(accountMeta => {
   	const pubkeyString = accountMeta.pubkey.toString();
   	const uniqueIndex = uniqueMetas.findIndex(x => {
   	return x.pubkey.toString() === pubkeyString;
   	});
   	if (uniqueIndex > -1) {
   	uniqueMetas[uniqueIndex].isWritable =
   	uniqueMetas[uniqueIndex].isWritable || accountMeta.isWritable;
   	} else {
   	uniqueMetas.push(accountMeta);
   	}
   	});

   
   Because of 3), AccountMeta will be iterated over in a different order to gather the unique keys.


5. solana/web3.js/src/transaction.ts

   Lines 327 to 343 in 17cc095

   	// Split out signing from non-signing keys and count header values
   	const signedKeys: string[] = [];
   	const unsignedKeys: string[] = [];
   	uniqueMetas.forEach(({pubkey, isSigner, isWritable}) => {
   	if (isSigner) {
   	signedKeys.push(pubkey.toString());
   	numRequiredSignatures += 1;
   	if (!isWritable) {
   	numReadonlySignedAccounts += 1;
   	}
   	} else {
   	unsignedKeys.push(pubkey.toString());
   	if (!isWritable) {
   	numReadonlyUnsignedAccounts += 1;
   	}
   	}
   	});

   
   Because of 4), the signed and unsigned keys will be collected in a different order and concatenated.

6. solana/web3.js/src/message.ts

   Lines 191 to 196 in 17cc095

   	keys: this.accountKeys.map(key => toBuffer(key.toBytes())),
   	recentBlockhash: bs58.decode(this.recentBlockhash),
   	};
   	let signData = Buffer.alloc(2048);
   	const length = signDataLayout.encode(transaction, signData);

   
   Because of 5), the keys will be serialized as bytes in a different order. When these bytes are signed, this will result in a different signature.

In short, because of 1), Transaction to Message performs lossy compression. You can’t deterministically serialize a Transaction to a Message and deserialize this Message back to the original Transaction.

[jstarry]

I dug into the code and came up with what I think is causing..

Cool, this is what I was referring above when I said that "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."

So I think we're all in agreement that Transaction.populate needs to go away?

[t-nelson]

I think most of the Transaction API needs to go away. It's nearly all a broken wrapper for things that should be on Message. Such a refactor is alluded to here. Seems like we might additionally need a second Message type that can be deserialized to, but not modified in any way?

So we'd have something like...

Message --> CompiledMessage <+-> bytes
                             +-> Transaction

[vpontis]

Cool, this is what I was referring above when I said that "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."

Thanks for investigating this all! @jstarry fwiw, I missed the implications of your comment so it was helpful to have @jordansexton's longer explanation.

So I think we're all in agreement that Transaction.populate needs to go away?

I wonder if it makes sense to remove the class Message abstraction and instead merge the message into the transaction. And on transaction you may still have getMessageToSign.

Btw, another thing that @jordansexton and I were talking about is that when you set an account to not writable for an instruction, you expect it to stay that way. But if another instruction increases permission levels (makes an account writable) then you lose that guarantee in your first instruction.

[t-nelson]

I wonder if it makes sense to remove the class Message abstraction and instead merge the message into the transaction.

No. Wrong direction. Transaction is a container for a Message and its signatures, nothing more

[jordaaash]

So I think we're all in agreement that Transaction.populate needs to go away?

What if we throw an error if a Transaction that was created with populate is compiled for signing again, or don't recompile the message to sign it?

I think populating a transaction from a message is still valuable for inspecting the instructions, fee payer, etc. but it needs to be clear that you can't sign it that way.

Seems like we might additionally need a second Message type that can be deserialized to, but not modified in any way?

This seems consistent with what I'm thinking.

[jordaaash]

PR attempt @ #23720, please review!

[ftelnov]

So what's about this issue? As for me, I'm still getting "Signature verification failed" sometimes. It's very strange, sometimes transactions are passed, sometimes not, despite the fact that algorithm of building on backend-side is the same in all the cases.
I'm as well using offline signing, forming and serialising transaction on back-side, deserialising and confirming on frontend-side. And this lead to errors.
I saw the workaround above, but that didn't help in my case at all. On backend I added Transaction.from(tx.serialize(...)), but on frontend - still signature errors sometimes.
Pls, tell me, maybe someone solved it through provided workaround? @apeTim?

[ftelnov]

I think populating a transaction from a message is still valuable for inspecting the instructions, fee payer, etc. but it needs to be clear that you can't sign it that way.

Do you mean that signing "pre-signed -> serialized -> deserilized" transaction is the dead-concept at all? Maybe you can suggest something else? Sorry, I just trying to overcome this bug, but can't find any 100% working solution.

[jordaaash]

Fix should be released in @solana/[email protected]

[juchiast]

I'm still seeing a similar issue when signing with backpack and phantom wallets

https://github.com/orgs/phantom/discussions/162