Dealing with player speed in a online game

So im writing this online game and im kinda having a hard time dealing with how often I should accept a move packet. The problem is that I can't get this to work without trusting the client with some data. Basically my idea was:

Client

/**** [game/client] movePlayer ***/


boolean playerCanMove = Date.now() - player.lastMove > 1000;

if(playerCanMove){

    player.lastMove = Date.now();
    player.move(RIGHT);
    client.send(new PacketMove(RIGHT));
}

Server:

/**** [server] handle a move packet ****/
/** The only data received from the client is the direction(RIGHT) **/
/** the server has its own player.lastMove **/

let playerCanMove  = Date.now() - player.lastMove > 1000; 

if(playerCanMove){
    player.lastMove = Date.now();
    player.move(RIGHT);  
}
else{
   error = "Player is moving too fast"; 
}

The problem with this is that server player.lastMove won't be the same in the client/server because of the time it takes for the packet to arrive.

So if the client send 2 move packets, the first one with a travel time of 100ms and the second one with a travel time of 99ms server will think the player is moving too fast, when that's not the problem, problem is that the travel time varies and server is saving the player.lastMove a bit late, a margin of error doesn't sound too good in this case neither.

Any ideas?

EDIT: The only data that's being sent to the server is the direction the player wants to move for the sake of the example,It only happens to be the same variable names. The server has its own player.lastMove variable

SOLUTION Thanks to @Lev M.

I havent implemented this yet, but I have thought about this quit a bit, and I can't find any weakness, please feel free to comment if you do!

I think is safe to say that the only thing the client can do is change the timestamp, well he can change the clock too but that will have the same effect, so I thought about this only assuming he's changing the packet timestamp

adding an extra && packet.timeStamp < server.clock

to

boolean isTimeStampValid = packet.timeStamp >= player.lastMove + 1000 && packet.timeStamp < server.clock

can't go wrong and it will mark attack #1 isTimeStampValid as false

Here is an idea that I think is simple to implement: Don't use Date.now() to calculate time between moves.

Keep some kind of in game clock. It can be milliseconds since the whole game started, like Unix timestamps, or it could be unique for each player, milliseconds since they logged in.

Keep this independently on the server and in the client. You can synchronize them once in a while using something like SNTP, though that might be overkill in your case.

Whenever player makes a move, have the client insert a timestamp based on this clock in the packet, along with the move data.

Then, have logic on the server check consistency of these time stamps. This way, the time between moves ignores packet travel time.

And if the client wants to cheat, it can not send two moves with timestamps less then 1000 milliseconds apart. If it does, your server will know to ignore the move.

You can also implement some logic that will stop the game if it detects packets arriving together or close (100-200ms) but with timestamps of 1000ms apart or more. This will be an easy way to catch cheaters.

If you want a fast paced game, you can't help but keep state in the client, to let the player see results of their moves without waiting for server response on every keystroke.

In fact, depending on the speed of your game, you may want to report moves to the server in batches, instead of every move on its own, both to save data (if this game is for mobile) and because this would be faster.

Your server can then validate the consistency of the whole batch together.