(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210810789.1 (22)申请日 2022.07.11 (71)申请人 中国科学技术大学 地址 230026 安徽省合肥市包河区金寨路 96号 (72)发明人 李京　陈聪　王盛姣　熊航　王硕　 (74)专利代理 机构 安徽省合肥新 安专利代理有 限责任公司 34101 专利代理师 陆丽莉　何梅生 (51)Int.Cl. G06Q 40/04(2012.01) G06F 16/27(2019.01) G06F 16/23(2019.01) (54)发明名称 一种基于区块链的并发交易处理方法及其 应用 (57)摘要 本发明公开了一种基于区块链的并发交易 处理方法及其应用， 其步骤包括： 1.更新维护状 态数据库为最新值， 2.区块数据预处理， 3.求解 最大可合并序列集， 4.合并交易。 本发明在处理 区块链中的并发交易时， 能够筛选出只读交易和 必然无效交易， 合并有效且语义合法的交易， 降 低区块内交易发生冲突的可能性， 从而能提高区 块链系统的并发性能。 权利要求书3页 说明书7页 附图2页 CN 115018648 A 2022.09.06 CN 115018648 A 1.一种基于区块链的并发交易处理方法， 其特征是应用于由区块链、 状态数据库S所组 成的交易环境中， 所述区块链的区块中存储有用户进行商品交易所产生的交易信息， 所述 状态数据库S中记录有所有数据对象的最 新值； 所述并发交易处 理方法是按如下步骤进行： 步骤1： 更新维护状态数据库S为 最新值； 步骤1.1、 定义状态数据库S＝{s1,s2,...,si,...,sI}， 其中， si表示第i个数据对象ai的 状态信息， I为状态信息的总条数； 令第i个数据对象ai的状态信息si是一个三元组 其中， 表示第i个数据对象ai的键， 表示第i个数据对象ai的当 前最新的版本号， 表示第i个数据对象ai的当前值； 步骤1.2、 构建待上链区块 的交易信息集合， 记为TX＝{tx1,tx2,...,txp,...,txP}， 其 中， txp表示第p条交易信息， P为交易信息的总条数； 所述第p条交易信息txp包含的操作数 据， 记为 其中， dq,p表示第p条交易信息txp中的第q个操作， Qp 表示第p条交易信息txp包含的最大操作数； 令所述第p条交易信息txp中的第q个操作数据 dq,p包含三元组 其中， keyq,p表示第q个操作数据dq,p访问数据对象的 键， 表示第q个操作数据dq,p读取数据对象的版本号， 表示第q个操作数据dq,p写入 数据对象的值； 步骤1 .3、 遍历交易信息集合TX， 并对第p条交易信息txp构建对应的交易读集 其中， 是第p条交易txp读取的第j个键版本对信息， keyj,p, 分别表示第p条交 易txp读取的第j个数据对象的键和版本号， J是第p条交易txp读取操作的总数； 步骤1.4、 遍历 交易读集RSp中的键版本对信息， 对第j个键版本对信息 如果状态数据库S中不存在键为keyj,p的数据对象或者存在键为keyj,p的数据对象对应的版 本号小于 则更新S中对应条目为 其中， 表示键为keyj,p， 版 本号为 的数据对象的值； 步骤2： 区块数据预处 理； 步骤2 .1、 遍历交易信息集合TX， 对第p条交易信息txp， 构建对应的交易写集 其中， 是第p条交易txp写入的第k个键值对信息， keyk,p, 分别表示第p条交易 txp写入的第k个数据对象的键和值， K 是第p条交易txp写入操作的总数； 步骤2.2、 如果第p 条交易信息txp的交易写集WSp为空， 则表示第p条交易信息txp为读交 易， 并将第p条交易信 息txp在区块中的位置前移到第一位； 否则， 表示第p条交易信 息txp为 写交易， 并保持不动； 步骤2.3、 遍历交易信息集合TX， 如果第p条交易信息txp的交易读 集RSp中存在一个键版 本对 满足 小于状态数据库S中键为keyl,p的数据对象对应的版 本号， 则将相应交易标记出来， 且被标记的交易 不参与步骤3和步骤4；权　利　要　求　书 1/3 页 2 CN 115018648 A 2步骤3： 求 解最大可合并交易序列集； 步骤3.1、 遍历交易信息集合TX， 对第p条交易信息txp， 构建对应的值增量集ΔVp＝{＜ key1,p,Δval1,p＞,＜key2,p,Δval2,p＞,...,＜keye,p,Δvale,p＞,...,＜keyE,p,ΔvalE,p ＞}， 其中， ＜keye,p,Δvale,p＞是第p条交易txp涉及的第e个数据对象的键和增值， E是第p 条交易txp涉及的数据对象总数； 步骤3.2、 判定交易是否语义 合法： 对第p条交易信息txp， 遍历ΔVp， 并根据式(1)计算键为keye,p的数据对象ae的新值 vale,p： 式(1)中， 是键为keye,p的数据对象ae在状态数据库S中记 录的值， 如果第 p条交易信 息txp涉及的所有数据对象的新值都大于等于0， 则判定第p条交易信息txp的语义合法， 否则 标记第p条交易信息txp的语义不合法； 步骤3.3、 定义一个数组arr， 对第p条交易信息txp， 令arr[p]表示以txp作为最后一条交 易信息的最长合法交易序列的长度， 初始化ar r[p]为0； 步骤3.4、 定义 最大可合并交易序列集 为B； 步骤3.5、 记执行第p条交易txp后得到的状态数据库为Sp； 记除txp外任意一条交易为 txg； 记执行第g条交易txg后得到的状态数据库 为Sg； 如果基于状态数据库Sp执行交易txg是 合法的， 则记 是安全的； 步骤3.6、 基于状态数据库S和交易信息集TX， 利用式(2)更新数组arr中的元素arr[p]， 从而更新数组ar r中的所有元 素： 式(2)中， max( ·)表示取最大值， ∧表示且； 步骤3.6、 找到数组arr中的最大值以及其对应 的索引t， 即arr[t]为数组arr中的最大 值， 令arr[t]对应的交易序列为最长合法交易子序列L＝(tx ′1,tx′2,...tx′i,...,tx′t)， i ∈[1,t]， 其中， tx ′i表示交易序列L包含的任意一个交易， 交易序列L包含的交易数|L|≤t， 且在交易信息集 合TX中能找到一个交易txk， 使得tx′t＝txk， k∈[1,t]； 步骤3.8、 将最长合法交易子序列L添加到最大可合并交易序列集B中， 并执行L中交易 后得到的状态数据库记为S ′， 并由除L中的交易以外的所有交易构成余下的交易信息集 TX′； 步骤3.9、 基于状态数据库S ′和余下的交易信息集TX ′重复步骤3.6～3.8， 直至最大可 合并交易序列集B不再 更新为止， 从而得到更新后的最大 可合并交易序列集B ′； 步骤4： 合并交易； 步骤4.1、 根据状态数据库S和更新后的最大可合并交易序列集B ′， 得到新的状态数据 库SB； 步骤4.2、 建立 一个空的读集RS ′和一个空的写集 WS′；权　利　要　求　书 2/3 页 3 CN 115018648 A 3