The growth of misinformation technology necessitates the need to identify fake videos. One approach to preventing the consumption of these fake videos is provenance which allows the user to authenticate media content to its original source. This research designs and investigates the use of provenance indicators to help users identify fake videos. We first interview users regarding their experiences with different misinformation modes (text, image, video) to guide the design of indicators within users' existing perspectives. Then, we conduct a participatory design study to develop and design fake video indicators. Finally, we evaluate participant-designed indicators via both expert evaluations and quantitative surveys with a large group of end-users. Our results provide concrete design guidelines for the emerging issue of fake videos. Our findings also raise concerns regarding users' tendency to overgeneralize from misinformation warning messages, suggesting the need for further research on warning design in the ongoing fight against misinformation.