Duplicate signature detection is probably slow and unnecessary

[garious]

Problem

Validators discard duplicate transactions by caching recent transaction signatures. Because validators can't be expected to cache every signature since genesis, validators require clients include a recent blockhash in each transaction. The validators then organize signatures by block and discard old batches as new ones roll in. The process is burdensome to clients, costly for validators, and requires a 32-byte blockhash in each transaction, a place where every bit affects TPS.

Proposed Solution

Inspired by Libra's resource sequence numbers, we use the Account.data of each user account to store a sequence number. The client would then include the sequence number of the account corresponding to key0, the user account paying the transaction fee. Validators would discard any transactions with a mismatched sequence number, and otherwise execute the transaction and increment the sequence number.

cc: #2497 tag: @aeyakovenko, @sakridge

[sagar-solana]

Just putting some thoughts down. Forgive the ordering.

1. Maybe we can generate sequence numbers on the fly from blockhashes? It's much faster for clients to rpc for a recent blockhash than to rpc for a sequence number stored inside an account.

2. It seems better than to cycle through every system account bumping up sequence numbers.

3. Alternative to 2, Would sequence numbers be bumped for every transaction payed for by an account? Requiring that system account can only be used to. Pay for 1 transaction at a time?

[aeyakovenko]

Lol. Remember I had tried this when building the parallel bank? The problem with sequence numbers is that writes are serialized and ordered. Bench-tps will run at 1k with this scheme.

[garious]

@aeyakovenko, no, just the senders need to be different, which is already the case because of the transaction fee debits. Maybe your earlier work had a global sequence number (like EVM) and not a per-sender sequence number?

[aeyakovenko]

@garious I tried a global and a local counter. The problem is that the spender can only send one request at a time, and needs to wait for it to be confirmed.

[garious]

@sagar-solana, great thoughts! We'd definitely want to flesh out a design doc before moving forward with this one!

Re #1: don't need to RPC much if there's only one client per private key.

[garious]

@aeyakovenko, if the same spender, they can add multiple instructions to the same transaction.

[aeyakovenko]

@garious yea. Of course. But when they send one tx, how many blocks do they wait until the next one?

[aeyakovenko]

The usecase that becomes clunkier is DEX offer price updates. The trader wants the latest price in the offer no matter what order they arrive. It’s almost like a real-time system. So traders would need to round robin through a bunch of accounts to match sequence numbers since they may need a price update before a confirmation.

The second part is that we limit parallelism. If we start exposing more of the types to the runtime we can execute more things in parallel. CO accounts can actually do spends as well, if the total at the end of the slot ends up above 0.

[sagar-solana]

The process is burdensome to clients, costly for validators, and requires a 32-byte blockhash in each transaction, a place where every bit affects TPS.

@garious so the real problem here is the 32-bytes extra in the tx and the validators having to store blockhashes?

Does using the blockhash as a seed to generate a random number address both those issues? Clients can request a recent "number" instead of a recent blockhash and validators only need to generate number once per blockhash generated.

[aeyakovenko]

• “The process is burdensome to clients” - The proposal adds a higher burden on clients. This forces clients to be synchronous with the account state before a transaction is created.
• 32 bytes savings will only improve TPS when we are at that bottleneck. Ripemd-160 is an easy option to save 12 bytes.

[garious]

No need to wait for confirmation. Libra, for example, appears to poll transactions sequentially from a local mempool. The Solana equivalent is to observe the later sequence number and simply re-queue the transaction for the next Entry.

[aeyakovenko]

@garious real time trading usecase:

• Offer program sets the price if the price version is later then what is in the offer
• trader continuously sends price updates with a monotonically increasing version

If the trader has to guess the sequence number for the spending account, it will make this non-real time.

[garious]

@aeyakovenko, I don't see any problem with that usecase. There's no guessing and the transactions would indeed be played in that order as quickly as possible.

[aeyakovenko]

@garious how? I send 3 transactions without confirmation. If 1 or 2 are dropped 3 fails.

[garious]

@aeyakovenko, you can send as many copies of 1 or 2 as you'd like, since duplicates are dropped. In current code, there's no generic mechanism at all. You'd need to implement it in that exchange program. Of course, implementing it in an on-chain program is perfectly reasonable since the code is immutable and one can actually trust the Limit Order that you're emulating with that transaction sequence.

[aeyakovenko]

@garious how would the trader know to continue sending 1 and 2 and 3....?

[garious]

It'd blindly send all three at once and understand the meaning of a sequence number.

[aeyakovenko]

@garious Yep. So you need to RPC to figure out which one failed, and then retry. That adds a feedback loop which will slow things down. This strict sequencing scheme is strictly slower for a real time use case than what we have today.

The current approach the trader sends the latest update without the feedback loop, and the contract ensures that the latest price is whatever is on chain regardless of the order of transaction execution.

[garious]

For reference, the Ethereum community's frustration with account sequence numbers: https://medium.com/kinblog/making-sense-of-ethereum-nonce-sense-3858d5588c64

[garious]

After playing with libra for a bit, I'm seeing how these sequence numbers are pretty awful. Closing.