本发明公开了一种云环境下远程数据完整性认证数据结构的实现方法，其包括：利用认证数据结构来认证存放于云端数据的完整性包括是否被修改，是否有数据丢失；在云端服务器不可信的情况下，利用认证数据结构来认证存放于云端数据的下标正确性；利用认证数据结构来支持云端数据的动态更新，所述动态更新包括修改操作、插入操作和删除操作。本发明还公开了一种云环境下远程数据完整性认证数据结构，包括：认证二叉树的生成的伪代码模块；证明路径的生成和验证的伪代码模块；节点的修改操作的伪代码模块；节点的插入操作的伪代码模块；节点删除三种情形的操作的伪代码模块。具有降低了在用户端和云端的计算在时间复杂度和存储空间的消耗等优点。