区块链系统中查找两个区块最近公共祖先的方法和系统

摘要

本发明涉及一种区块链系统中查找两个区块最近公共祖先的方法，包括：以当前节点存储的本地区块链为原始树构建辅助树；通过Access(V)操作，将该辅助树中的区块V旋转到该辅助树的根树链上，形成临时辅助树；通过Access(W)操作，将该临时辅助树中的区块W旋转到该临时辅助树的根树链上，形成最终辅助树；以该最终辅助树的根区块为区块V和区块W的最近公共祖先。本发明的区块链系统中查找两个区块最近公共祖先方法，通过使用Link/Cut Tree算法将该功能的均摊时间复杂度降到了O(logN)，而且省去了大量Hash值比对过程，极大地优化了查找效率。