A method of labeling video to provide authentication acquires an instruction to apply timestamp labeling. Each recorded video is labeled with a timestamp based on the instruction. The first mark information is generated based on a content of each recorded video as a hash value and is uploaded into a blockchain. Second mark information is generated based on a content of at least one video under investigation. By comparing the first mark information and the second mark information, a video under investigation is found to be undistorted and authentic when the first mark information is the same as the second mark information. The video under investigation is found to be non-authentic when the first mark information is different from the second mark information. A terminal device and a computer readable storage medium applying the method are also disclosed.