针对marlin零知识证明协议的矩阵计算装置、方法及设备

摘要

本发明公开了一种针对marlin零知识证明协议的矩阵计算装置、方法及设备，装置包括：数据存储器，用于存储marlin零知识证明协议中的第一电路矩阵A、第二电路矩阵B和第三电路矩阵C；矩阵编码器，用于根据电路矩阵A、B、C的稀疏性特点，以及marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息，并将每个行列索引信息存入数据存储器；有限域数据计算器，用于根据运算需求，按照每个行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。该装置可提高电路矩阵计算效率，减少电路矩阵计算时间。

说明书

技术领域

本发明涉及加密计算领域，尤其涉及一种针对marlin零知识证明协议的矩阵计算装置、方法及设备。

背景技术

零知识证明，指证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。

Marlin协议是众多零知识证明协议中的一种，该协议改进了诸多其他协议的证明计算量大、存储空间利用率低的缺点，利用一种有效的代数投影协议实现了对于一阶线性系统的线性长度证据以及常数次的询问交互。然而，该协议中存在大规模矩阵运算，且对于多读者多写者环境，还必须引入原子操作，造成计算效率大幅降低，计算耗时长。

发明内容

本发明旨在至少在一定程度上解决相关技术中的技术问题之一。为此，本发明的目的在于提出一种针对marlin零知识证明协议的矩阵计算装置、方法及设备，以提高电路矩阵的计算效率，减少电路矩阵的计算时间。

第一方面，本发明提出了一种针对marlin零知识证明协议的矩阵计算装置，所述装置包括：数据存储器，用于存储marlin零知识证明协议中的第一电路矩阵A、第二电路矩阵B和第三电路矩阵C；矩阵编码器，用于根据电路矩阵A、B、C的稀疏性特点，以及所述marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息，并将每个所述行列索引信息存入所述数据存储器；有限域数据计算器，用于根据所述运算需求，按照每个所述行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。

另外，本发明上述实施例的针对marlin零知识证明协议的矩阵计算装置还可以具有如下附加的技术特征：

根据本发明的一个实施例，所述矩阵编码器具体用于：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，所述第一存储表存储所述电路矩阵M每一行非零元素的列号和非零数值，所述行指针数组中的指针指向所述第一存储表中存储的所述电路矩阵M对应行的首个非零元素，所述第二存储表存储所述电路矩阵M每一列非零元素的行号和指向所述第一存储表中对应非零数值的指针，所述列指针数组中的指针指向所述第二存储表中存储的所述电路矩阵M对应列的首个非零元素；基于所述第一存储表、所述行指针数组、所述第二存储表和所述列指针数组得到所述电路矩阵M的行列索引信息。

根据本发明的一个实施例，所述矩阵编码器具体用于：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，所述第一存储表存储所述电路矩阵M每一行非零元素的列号和指向所述第二存储表中对应非零数值的指针，所述行指针数组中的指针指向所述第一存储表中存储的所述电路矩阵M对应行的首个非零元素，所述第二存储表存储所述电路矩阵M每一列非零元素的行号和非零数值，所述列指针数组中的指针指向所述第二存储表中存储的所述电路矩阵M对应列的首个非零元素；基于所述第一存储表、所述行指针数组、所述第二存储表和所述列指针数组得到所述电路矩阵M的行列索引信息。

根据本发明的一个实施例，所述有限域数据计算器的数量为多个，且多个所述有限域数据计算器并行设置。

根据本发明的一个实施例，针对电路矩阵点乘输入向量的情况，每个所述有限域数据计算器负责所述电路矩阵的多行与所述输入向量的点乘计算，所述有限域数据计算器在进行所述电路矩阵的第u1行与所述输入向量的点乘计算时，具体用于：初始化第一结果向量的每个位置值为0，根据所述行指针数组和所述第一存储表得到所述电路矩阵第u1行每个非零元素的列号和非零数值，并根据所述第u1行每个非零元素的列号得到所述输入向量对应的数值，以及将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的所述第一结果向量中对应位置值进行有限域加法计算。

根据本发明的一个实施例，针对输入向量点乘电路矩阵的情况，每个所述有限域数据计算器负责所述输入向量与所述电路矩阵的多列的点乘计算，所述有限域数据计算器在进行所述输入向量与所述电路矩阵的第u2列的点乘计算时，具体用于：初始化第二结果向量的每个位置值为0，根据所述列指针数组、所述第二存储表和所述第一存储表得到所述电路矩阵第u2列每个非零元素的行号和非零数值，并根据所述第u2列每个非零元素的列号得到所述输入向量对应的数值，以及将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的所述第二结果向量中对应位置值进行有限域加法计算。

第二方面，本发明提出了一种针对marlin零知识证明协议的矩阵计算方法，所述方法包括以下步骤：获取marlin零知识证明协议中的第一电路矩阵A、第二电路矩阵B和第三电路矩阵C；根据电路矩阵A、B、C的稀疏性特点，以及所述marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息；根据所述运算需求，按照每个所述行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。

另外，本发明上述实施例的针对marlin零知识证明协议的矩阵计算方法还可以具有如下附加的技术特征：

根据本发明的一个实施例，所述根据电路矩阵A、B、C的稀疏性特点，以及所述marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息，包括：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，所述第一存储表存储所述电路矩阵M每一行非零元素的列号和非零数值，所述行指针数组中的指针指向所述第一存储表中存储的所述电路矩阵M对应行的首个非零元素，所述第二存储表存储所述电路矩阵M每一列非零元素的行号和指向所述第一存储表中对应非零数值的指针，所述列指针数组中的指针指向所述第二存储表中存储的所述电路矩阵M对应列的首个非零元素；基于所述第一存储表、所述行指针数组、所述第二存储表和所述列指针数组得到所述电路矩阵M的行列索引信息。

根据本发明的一个实施例，针对输入向量点乘电路矩阵的情况，在进行所述输入向量与所述电路矩阵的第u2列的点乘计算时，所述有限域的矩阵计算包括：初始化第二结果向量的每个位置值为0；根据所述列指针数组、所述第二存储表和所述第一存储表得到所述电路矩阵第u2列每个非零元素的行号和非零数值；根据所述第u2列每个非零元素的列号得到所述输入向量对应的数值；将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的所述第二结果向量中对应位置值进行有限域加法计算。

第三方面，本发明提出了一种电子设备，包括上述第一方面的针对marlin零知识证明协议的矩阵计算装置。

本发明实施例的针对marlin零知识证明协议的矩阵计算装置、方法及设备，针对marlin零知识证明协议中的A、B、C三个超大规模电路矩阵，根据其稀疏性特点和marlin零知识证明协议的运算需求，按行与列进行索引排列，可实现降低矩阵存储容量需求的目标；根据索引排列对相应电路矩阵进行读取并进行相应的矩阵运算，可提高电路矩阵的计算效率，减少电路矩阵的计算时间。

附图说明

图1是本发明实施例的针对marlin零知识证明协议的矩阵计算装置的结构框图；

图2是本发明一个实施例的行列索引信息示意图；

图3是本发明一个实施例的按行索引的示意图；

图4是本发明一个实施例的按列索引的示意图；

图5是相关技术中的矩阵计算的示意图；

图6是本发明实施例的针对marlin零知识证明协议的矩阵计算方法的流程图；

图7是本发明实施例的电子设备的结构框图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

下面参考附图描述本发明实施例的针对marlin零知识证明协议的矩阵计算装置、方法及设备。

图1是本发明实施例的针对marlin零知识证明协议的矩阵计算装置的结构框图。

如图1所示，针对marlin零知识证明协议的矩阵计算装置100包括：数据存储器110、矩阵编码器120和有限域数据计算器130。

其中，数据存储器110用于存储marlin零知识证明协议中的第一电路矩阵A、第二电路矩阵B和第三电路矩阵C。矩阵编码器120用于根据电路矩阵A、B、C的稀疏性特点，以及marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息，并将每个行列索引信息存入数据存储器110。有限域数据计算器130用于根据运算需求，按照每个行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。

具体地，在零知识证明协议中，算法协议要证明证明者具有且并不暴露某个信息，需满足公开的某个计算关系。该计算关系可以通过大量的有限域加法和乘法表达(R1SC)，具体可通过三个电路矩阵(A、B、C)表达，其中A、B表示乘法或者加法的输入信号，C表示输出信号。满足的计算关系，指存在一组输入向量z，使得(Az)*(Bz)＝Cz，其中，*表示hardmard乘。由于每个加法或者乘法只由两个输入和一个输出组成，所以A、B、C三个电路矩阵的每一行至多只有两个非零元素。一般情况下，该特定的计算关系会由数以万计的加法、乘法门电路组成，造成电路矩阵的维度非常大，进而造成了电路矩阵的稀疏性非常高。并且，在具体的marlin零知识证明协议中，运算需求不仅包括上述电路矩阵与向量的点乘运算，还包括向量与电路矩阵的点乘运算。

为此，本发明通过矩阵编码器根据电路矩阵A、B、C的稀疏性特点，以及marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码(即进行了行列双索引)，得到电路矩阵A、B、C的行列索引信息，并将每个行列索引信息存入数据存储器110。进而有限域数据计算器130可根据运算需求，按照每个行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。由此，可提高电路矩阵的计算效率，减少电路矩阵的计算时间。

在一些实施例中，矩阵编码器120具体用于：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，第一存储表存储电路矩阵M每一行非零元素的列号和非零数值，行指针数组中的指针指向第一存储表中存储的电路矩阵M对应行的首个非零元素，第二存储表存储电路矩阵M每一列非零元素的行号和指向第一存储表中对应非零数值的指针，列指针数组中的指针指向第二存储表中存储的电路矩阵M对应列的首个非零元素；基于第一存储表、行指针数组、第二存储表和列指针数组得到电路矩阵M的行列索引信息。

具体地，以电路矩阵M为m行m列为例，假设每一行每一列均包含至少一个非零元素个数，则矩阵编码器120遍历电路矩阵M每一行、每一列的非零元素个数，可得到遍历结果[R

基于遍历结果[R

例如，参见图2，0行指针指向第一存储表中的列号c1，1行指针指向第一存储表中的列号cn，基于此，可得到第一存储表中依次存储的列号c1(包括)至列号cn(不包括)均为电路矩阵第0行的非零元素的列号，每个列号对应的数值即为其后的数值。同理，可根据行指针数组中的其他行指针从第一存储表得到电路矩阵其他行的非零元素的位置(即列号)和数值，以便后续进行矩阵与向量的点乘计算。

参见图2，0列指针指向第二存储表中的行号r1，1列指针指向第二存储表中的行号r2，基于此，可得到第二存储表中存储的行号r1为电路矩阵第0列的非零元素的行号，该行号对应的指针p1指向的第一存储表中的数值v2即为第0列第r1行的数值。同理，可根据行指针数组中的其他列指针从第二存储表得到电路矩阵其他行的非零元素的位置(即行号)，并基于该位置和其后指针从第一存储表得到相应数值，以便后续进行向量与矩阵的点乘计算。

在另一些实施例中，矩阵编码器120具体用于：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，第一存储表存储电路矩阵M每一行非零元素的列号和指向第二存储表中对应非零数值的指针，行指针数组中的指针指向第一存储表中存储的电路矩阵M对应行的首个非零元素，第二存储表存储电路矩阵M每一列非零元素的行号和非零数值，列指针数组中的指针指向第二存储表中存储的电路矩阵M对应列的首个非零元素；基于第一存储表、行指针数组、第二存储表和列指针数组得到电路矩阵M的行列索引信息。

需要说明是的，该实施例与上一实施例(图2所示实施例)的区别在于行列编码进行了交换，其他均相同。

在一些实施例中，有限域数据计算器130的数量为多个，且多个有限域数据计算器130并行设置，即可同时开启矩阵计算。由此，可进一步提升计算效率，减少计算时间。

具体地，在一些示例中，针对电路矩阵点乘输入向量的情况，每个有限域数据计算器130负责电路矩阵的多行(具体行数可根据需要标定)与输入向量的点乘计算。

有限域数据计算器130在进行电路矩阵的第u1行与输入向量的点乘计算时，具体用于：初始化第一结果向量的每个位置值为0，根据行指针数组和第一存储表得到电路矩阵第u1行每个非零元素的列号和非零数值(如图3所示)，并根据第u1行每个非零元素的列号得到输入向量对应的数值，以及将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的第一结果向量中对应位置值进行有限域加法计算。其中，u1为整数，取值范围即为电路矩阵的行数。

在另一些示例中，针对输入向量点乘电路矩阵的情况，每个有限域数据计算器130负责输入向量与电路矩阵的多列(具体列数可根据需要标定)的点乘计算。

有限域数据计算器130在进行输入向量与电路矩阵的第u2列的点乘计算时，具体用于：初始化第二结果向量的每个位置值为0，根据列指针数组、第二存储表和第一存储表得到电路矩阵第u2列每个非零元素的行号和非零数值(如图4所示)，并根据第u2列每个非零元素的列号得到输入向量对应的数值，以及将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的第二结果向量中对应位置值进行有限域加法计算。其中，u2为整数，取值范围即为电路矩阵的列数。

举例而言，电路矩阵

为此，本发明采用行和列同时索引的方式，可快速按列读取矩阵数据。同时，每个有限域数据计算器130均初始化一结果，且根据每列每个非零元素的列号得到输入向量对应的数值，并仅对该列号与向对应数值计算，计算量少，计算效率高，计算用时少。

图6是本发明实施例的针对marlin零知识证明协议的矩阵计算方法的流程图。

如图6所示，方法包括以下步骤：

S1，获取marlin零知识证明协议中的第一电路矩阵A、第二电路矩阵B和第三电路矩阵C。

S2，根据电路矩阵A、B、C的稀疏性特点，以及marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息。

S3，根据运算需求，按照每个行列索引信息读取相应电路矩阵中非零元素的位置信息和数值信息，进行有限域的矩阵计算。

在一些实施例中，根据电路矩阵A、B、C的稀疏性特点，以及marlin零知识证明协议中的运算需求，分别对电路矩阵A、B、C进行行列位置索引编码，得到电路矩阵A、B、C的行列索引信息，包括：遍历电路矩阵M每一行、每一列的非零元素个数，其中，M∈{A,B,C}；根据遍历结果构建第一存储表、行指针数组、第二存储表和列指针数组，其中，第一存储表存储电路矩阵M每一行非零元素的列号和非零数值，行指针数组中的指针指向第一存储表中存储的电路矩阵M对应行的首个非零元素，第二存储表存储电路矩阵M每一列非零元素的行号和指向第一存储表中对应非零数值的指针，列指针数组中的指针指向第二存储表中存储的电路矩阵M对应列的首个非零元素；基于第一存储表、行指针数组、第二存储表和列指针数组得到电路矩阵M的行列索引信息。

在一些实施例中，针对输入向量点乘电路矩阵的情况，在进行输入向量与电路矩阵的第u2列的点乘计算时，有限域的矩阵计算包括：初始化第二结果向量的每个位置值为0；根据列指针数组、第二存储表和第一存储表得到电路矩阵第u2列每个非零元素的行号和非零数值；根据第u2列每个非零元素的列号得到输入向量对应的数值；将非零数值与对应的输入向量数值进行有限域乘法计算，并与初始化的第二结果向量中对应位置值进行有限域加法计算。

需要说明的是，本发明实施例的针对marlin零知识证明协议的矩阵计算方法的其他具体实施方式，可参见本发明上述实施例的针对marlin零知识证明协议的矩阵计算装置的具体实施方式。

图7是本发明实施例的电子设备的结构框图。

如图7所示，电子设备1000包括上述实施例的针对marlin零知识证明协议的矩阵计算装置100。

综上，本发明实施例的针对marlin零知识证明协议的矩阵计算装置、方法及设备，针对marlin零知识证明协议中的A、B、C三个超大规模电路矩阵，根据其稀疏性特点和marlin零知识证明协议的运算需求，按行与列进行索引排列，可实现降低矩阵存储容量需求的目标；根据索引排列对相应电路矩阵进行读取并进行相应的矩阵运算，可避免由于多读者多写者环境造成的必须引入原子操作而造成的计算效率降低的问题，减少了计算时间。

需要说明的是，在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门的离散逻辑，具有合适的组合逻辑门的专用集成，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

在本发明的描述中，需要理解的是，术语“中心”、“纵向”、“横向”、“长度”、“宽度”、“厚度”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”、“顺时针”、“逆时针”、“轴向”、“径向”、“周向”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。