Append data to authenticated ciphertext encrypted using a stream cipher Say we have xSalsa20 authenticated using Poly1305. If $ X $ is the ciphertext, $N$ is the nonce value, and $H$ is the authentication tag such that the final ciphertext is $ N || X || H $, then given the key $K$, is it possible to extend $ X $ with more data, without decrypting it, updating $N$ and $Y$ as needed? (I'm not sure if $N$ would need to be changed.)

To be clearer, say $ X_m $ is the original authenticated ciphertext. I want to append plaintext data $ A $ to it. I'm looking for a scheme to implement $ X_n = Append(X_m, A, K) $ such that $ Decrypt(X_n, K) = Decrypt(X_m, K) \| A $.

Salsa20 is a stream cipher so it produces a CSPR key-stream, $ S $, and then then ciphertext becomes $ X = S \oplus P $, where $P$ is the plaintext. So I intuitively feel as though this should be a lot easier to do than with a block cipher. Perhaps by generating the same key-stream up until the size of the ciphertext and encrypting the new data with the part of the key-stream past that point. If the authentication tag is generated from the ciphertext then decryption wouldn't be necessary for that either. Also the nonce would not really be reused in a scheme like this as far as I can see.

How well would this translate to other stream ciphers like XChaCha20-Poly1305?
Well, no you can't (without rescanning the entire ciphertext), and you probably shouldn't anyways.

The xSalsa20 is the easy half - it is effectively in counter mode, and so it'd be easy to generate a few more bits out of the xSalsa20 to use to encrypt the additional data you're appending (and those additional bits wouldn't change to previous ciphertext bits).

The problem is with the Poly1305 half; it treats the ciphertext as polynomial coefficients (over $GF(2^{130}-5)$) and then evaluates that polynomial for a secret value of $x$ (and then adds a secret nonce-dependent factor) - if that's all it did, then it would be fairly easy to adjust the polynomial result to account for the additional bits (by subtracting out the secret constant term, multiplying by a power of $x$ if necessary, and then adding in the new bits and adding back the secret constant term).  However, it does one further step; it takes the output of the polynomial (which is a value between $0$ and $2^{130}-6$), and takes it mod $2^{128}$.  That means that, for (almost) any tag value, there are 4 possible values that the polynomial would evaluate to, which implies 4 possible tags that the extended polynomial would need to be (because those two higher bits modify the lower bits once we multiply it by $x$), and you have no idea which one it might be (without recomputing the polynomial from scratch.

Now, one could modify the initial Poly1305 implementation to save those two upper bits that the $\bmod 2^{128}$ operation scraps away (and leaking those would not give any advantage to an attacker); this would allow an efficient incremental update.  On the other hand, doing so might not be a great idea - if an adversary sees both ciphertexts (that is, the original and the extended version, both of which uses the same nonce), he can compute an explicit polynomial which has the secret value $x$ as a root - this allows him to recover a good guess of the value of $x$, and that would allow him to modify ciphertexts at will without being detected.

Because of this threat, I believe you really do want to change the nonce whenever you modify the ciphertext; that involves a full decryption and reencryption.