In this paper, we propose a butterfly-graph based stream authentication scheme for lossy networks where the streaming packets could be lost in both random and burst ways. Due to the nice properties of butterfly graph, the proposed scheme is quite robust and efficient. Theoretical analysis and simulation results show that the proposed scheme outperforms existing schemes in terms of overhead and authentication probability while maintaining the same levels of sender/receiver delay and robustness.