In this work we propose a new algorithm for fragile, high capacity yet file-size preserving watermarking of MPEG-2 bitstreams. Watermarking is performed entirely in the compressed domain with no need for full or even partial decompression thus providing the speed necessary for real time video applications. The algorithm is based on the idea that that not every code word in the entropy coded portion of video is used. By mapping used variable length codes to unused ones a watermark situation can be realized. However, by examining MPEG-2 streams it was realized that the unused codespace is practically nonexistent. The solution lies in expanding the codespace. This expansion is achieved by creating a paired codespace defined over individual blocks of video. Although every VLC may have been used in the video, there are numerous VLC pairs that do not occur in any block together. This situation creates the redundancy within the codespace necessary for watermarking. We show that the watermarked video is resistant to forgery attacks and remains secure to watermark detection attempts.