Should a refresh token be linked to a single access token, and what is the ideal refresh flow?

Question

I've been reading about access tokens and refresh tokens, and am implementing it in my own site. Right now, based on an example codebase on GitHub, a refresh token of random characters is created and stored in the database with some details such as the user id and expiry time, and returned alongside the JWT access token. The refresh route accepts both the old access token and refresh token, as well as some other request information (client id and IP), and as long as the refresh token exists in the database and is not expired, is assumed to be valid to grant the user a new access token (which is generated using the payload of the old token) before itself being reissued.

I then read this article, which notes among other things that the refresh route should not require the old token in the request payload (not being tied to a single access token).

Based on this, I have a few questions:

1. Shouldn't the refresh token be linked to a specific access token? If my access token has a jti, should I not store this in the database with the refresh token, so that a single refresh token can only be used for a single access token? If a refresh token is stolen, and it is not linked to an access token, this token can be used to generate a new access token regardless of what the old access token looks like. Sure, if it's being rotated and an expired refresh token is used (i.e. real user attempts to refresh their expired access token), I can detect that the refresh token was breached and invalidate all of the user's refresh tokens, but until then the attacker will be able to continue requesting new access tokens whenever they expire and have access to the user's account.
2. If an access token should not be sent to the refresh route (invalidating question 1), how is the payload for the new access token sourced? Is this retrieved fresh from the database? Should this happen anyway so that any changes made to the database are at most accessTokenTtl stale?
3. What about the other information stored alongside the refresh token? In the example GitHub repo, the client id and user ip address are stored with the refresh token but not used for anything. Should a refresh token only be valid if the same ip address and client id are provided when a refresh is attempted? What if a user is on their mobile phone, for example, where their ip address can change quite frequently? This defeats the purpose of a long-lasting (weeks/months, not minutes or hours) refresh token.
4. Is a refresh token of random characters sufficient? Can it be a JWT itself? I wanted to not store the refresh token in plain-text in the database, but in order to find the right token it needs to be stored alongside a unique identifier which is also a part of the payload. I.e. I could make the refresh token a JWT with a jti that is the id of the corresponding database row, and a random payload. This is sent to the user as a normal JWT, but it is hashed using bcrypt before being stored in the database. Then, when the refresh token is being used in the refresh route, I can validate the token provided by the user, grab the jti, find the hashed token in the database, and then compare them using bcrypt as you would with a user's password.

Answer 1

1. Refresh tokens cannot be tied to access tokens if the access tokens expire "cleanly" (that is, leaving no trace), or else the whole point of the refresh token - obtaining a new access token to refresh the session when the old token expires - won't work. If the access token will stick around even after expiry, you can tie it to the refresh token, but in general this doesn't add much security. How do you propose an attacker steal somebody's refresh token without also being in a position to steal their access token?
2. The new access token is generated the same way the original one was. E.g. If you're using JWTs, you mint a new JWT and sign it. If you're rotating refresh tokens after use, you generate a new one (hopefully via HSM or cryptographically-secure PRNG) and return that too.
3. Session data stored alongside a token is usually used for things like showing the user a list of their active sessions, and detecting fraud. You can do things like allow refresh with a change of IP within a country, but require re-authentication after crossing a border or traveling far, by looking up the IP.
4. A refresh token of random bytes is not only sufficient, it is the usual option. JWTs are poor choices of refresh token; they are overly large if all you need to prove is "this was given to the user at some point", and their primary advantage - no server state - isn't feasible for refresh tokens (they need to be long-lived, which means you need a way to revoke them, which means you need to store state on the server).

One thought: if you're concerned about somebody gaining read (but not write) access to your auth DB and retrieving refresh tokens from there to then use against unsuspecting users, the easiest solution is to run them through a fast secure hash function. Taking 16 bytes from /dev/urandom, and then both returning those bytes to the user as the refresh token and running them through SHA-256 before purging them from the server, will produce a hash value that can be stored in your database, compared against extremely quickly, and reveals absolutely nothing about the actual refresh token value. It's sort of like password hashing, except you don't need a slow hash because the entropy of the actual refresh token is higher than almost any human-generated password.