CN109885259B - Lightweight capacity proving method based on directed acyclic graph and storage medium - Google Patents

Abstract

The invention provides a lightweight capacity proving algorithm based on a directed acyclic graph, which comprises the following steps: s1, verifying that the two parties generate a logic node sequence by using the same DAG node generation instruction and the seed random number; s2 generating capacity filling data according to the logic node sequence; s3, the verification party initiates a challenge to the proving party and designates a challenge node to prove the challenge node; the S4 proving party gives a first proof according to the challenge node; the verifying party of S5 performs the first check on the first certification, thereby obtaining the check result, thereby effectively reducing the storage space and transmission time required by the capacity certification and the required bandwidth consumption, and improving the verification efficiency of the capacity certification as a whole.

Description

Lightweight capacity proving method based on directed acyclic graph and storage medium

Technical Field

The invention relates to the technical field of capacity certification, in particular to a lightweight capacity certification method based on a directed acyclic graph and a storage medium thereof.

Background

Space attestation (posspace), also known as capacity attestation (PoC), refers to an attestation party claiming itself to own storage space of a certain capacity and providing a mathematically based attestation (Proof) to an authenticating party so that the authenticating party can be sure that the proving party really owns the claimed storage space.

The traditional capacity certification is usually based on the content, that is, the verifier generates data with the same size as the capacity generated by the prover, and ensures that the data cannot be obtained by the prover in advance, generally generated randomly, and then sends the data to the prover, and then initiates a challenge (generally based on Merkle tree) to the prover.

Due to traditional capacity certification, a verifier is required to construct data to send to the prover before verifying the prover's space. But if the space required for verification is very large, the verifier will also need to construct an equivalent amount of very large data. This is very time consuming and also inconvenient to transmit. Therefore, a capacity attestation based on a Directed Acyclic Graph (DAG) was born.

Based on the capacity certification of the directed acyclic graph, both verification parties are required to generate the same directed acyclic graph in advance. And generating data based on each node in the directed acyclic graph, and then combining the generated data in an organized manner according to the sequence of the directed acyclic graph nodes to form large data blocks. During the course of choosing, the two parties must provide the proof of the data corresponding to the directed acyclic graph based on the structure of the directed acyclic graph. The verifier must verify the validity of the proof and whether the proof matches a preset directed acyclic graph to determine the validity of the proof given by the prover.

But the storage of directed acyclic graphs also requires a lot of space and the transmission of directed acyclic graphs will also take a lot of bandwidth and time. Therefore, how to reduce the data volume of the directed acyclic graph to improve the proving efficiency is one of the technical problems to be solved urgently in the technical field.

Disclosure of Invention

The invention mainly aims to provide a lightweight capacity proving method based on a directed acyclic graph, which generates an instruction through DAG nodes to replace the traditional directed acyclic graph, thereby effectively reducing the storage consumption, transmission time and required bandwidth consumption required by capacity proving, reducing the required storage space requirements of both capacity proving parties, and integrally improving the verification efficiency of the capacity proving.

In order to achieve the above object, according to an aspect of the present invention, there is provided a lightweight volume attestation method based on a directed acyclic graph, including the steps of:

s1, verifying that the two parties store the same DAG node generation instruction and seed random number on the memories of the respective computers, so that the processors of the computers can process and generate a logic node sequence according to the logic node sequence generation step;

the S2 computer generates capacity filling data according to the logic node sequence;

s3, the verifier computer sends challenge request to the prover computer, and appoints the challenge node to prove it;

s4 the proving computer gives a first proof according to the challenge node sent by the verifying computer;

s5 the verifier computer makes a first ping of the first proof to arrive at a ping result. .

In a preferred embodiment, the lightweight volume proving method based on the directed acyclic graph further includes the steps of: when the verifier computer verifies that the first check result is true, the verifier orders the computer to initiate a second challenge to the father node of the challenge node; s7 repeats steps S4 to S5 to obtain the result of the ping.

In a preferred embodiment, the lightweight volume proving method based on the directed acyclic graph further includes the steps of: the S8 verifier computer repeats steps S6 through S7 until the challenge node has no parent node, and the challenge is ended to obtain the final verification result.

Under a preferred embodiment, wherein the first proof comprises: the number of the challenge node and all father nodes thereof, and the Label value of the challenge node and all father nodes thereof.

In a preferred embodiment, the first verification step includes: comparing parent node numbers of the challenge nodes; comparing the Label values corresponding to the nodes; and if any one checking step fails, the checking step is false, and if all the checking steps pass, the checking step is true.

In a preferred embodiment, the logic node sequence generating step includes: a computer processing DAG node generates an instruction and randomly generates a seed random number according to a Hash function; generating a parent node number set of a node i based on a getParants function according to the seed random number by a computer processing DAG node generation instruction; and the computer generates a logic node sequence according to the obtained father node number sequence.

In a preferred embodiment, wherein the capacity filling data generating step comprises; a processor of the computer calculates a Label value of a top node based on the logic node sequence, and other nodes sort the father nodes and then combine the father nodes with the self node numbers to calculate the Label value of the nodes; and continuously storing all the node Label values in sequence to generate capacity filling data.

To achieve the above object, according to another aspect of the present invention, there is also provided a storage medium storing computer-executable instructions that, when executed by a processor, the processor performs the above lightweight volume attestation method based on directed acyclic graphs.

The lightweight capacity proving method and the storage medium based on the directed acyclic graph effectively replace the existing directed acyclic graph stored in actual physics, reduce the problems of large storage space occupation and bandwidth occupation, thereby effectively reducing the storage space and transmission time required by capacity proving and the consumption of required bandwidth, and integrally improving the verification efficiency of the capacity proving.

Drawings

The accompanying drawings, which are incorporated in and constitute a part of this application, illustrate embodiments of the invention and, together with the description, serve to explain the invention and not to limit the invention. In the drawings:

FIG. 1 is a diagram illustrating a structure of a directed acyclic graph according to the lightweight volume attestation method based on the directed acyclic graph of the present invention;

FIG. 2 is an exemplary diagram of a volume filling data structure of the lightweight volume attestation method based on directed acyclic graph according to the present invention.

Detailed Description

It should be noted that the embodiments and features of the embodiments in the present application may be combined with each other without conflict. The present invention will be described in detail below with reference to the embodiments with reference to the attached drawings.

In order to make those skilled in the art better understand the technical solution of the present invention, the technical solution in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be obtained by a person skilled in the art without making any creative effort based on the embodiments in the present invention, shall fall within the protection scope of the present invention.

It should be noted that the terms "first", "second", "S1", "S2", and the like in the description and claims of the present invention and the above-described drawings are used for distinguishing similar objects and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used is interchangeable under appropriate circumstances such that the embodiments of the invention described herein are capable of operation in sequences other than those illustrated or described herein. Furthermore, the terms "comprising" and "having," as well as any variations thereof, are intended to cover non-exclusive inclusions.

The essence of the capacity certification is to prove that a direction verifier certifies that filling data generated based on a directed acyclic graph necessarily occupies a certain storage space as long as the filling data exists, thereby indirectly proving that a certifier has the storage space.

The lightweight capacity proving method based on the directed acyclic graph is characterized in that the two verifying parties do not need to generate data of the directed acyclic graph at the beginning of verification, but respectively store the same DAG node generation instruction with smaller capacity, and randomly generate a seed random number with extremely small capacity to the proving party through negotiation of the two verifying parties or the verifying party based on the DAG node generation instruction, so that the logic DAG graphs generated by the two verifying parties can be unified.

In principle, the logic DAG graph is essentially the collection data of the DAG nodes, so compared with the traditional DAG graph, the logic DAG graph has the advantages that the node data can be calculated at any time without complete storage as the traditional DAG graph, and therefore the storage capacity occupied by the data is extremely small.

Based on the principle, the lightweight capacity proving method based on the directed acyclic graph mainly comprises the following implementation steps: s1 verifying that both parties generate a sequence of logical nodes with the same DAG node generation instruction and seed random number, wherein the logical node sequence generating step includes: a DAG node generation instruction randomly generates a seed random number according to a Hash function; generating a father node number set of the node i by a DAG node generation instruction according to the seed random number and based on a getParants function; and generating a logic node sequence according to the obtained father node number sequence.

For example, the logic for generating a sequence of logical nodes with DAG node generation instructions is as follows, as an example of the function pseudocode:

func getParents(i uint64)[]uint64{

the number of father nodes and the number of each father node are generated according to the seed random number.

And// ensuring the same seed random number, the same node number and the same returned father node set.

// return the set of parent node numbers.

}

The seed random number is an unpredictable random number generated by the verifier for each prover, and once generated, the prover can choose to always use the seed random number.

The getnodes function is mainly used for acquiring a parent node number set of the node i, so as to generate a logical node sequence. Therefore, by generating the instruction through the DAG node, the numbers of all father nodes of a certain node can be obtained according to the node numbers, the structure of the whole directed acyclic graph is indirectly obtained, and a directed acyclic graph is logically formed. But only one storage space of the seed random number is occupied for the storage space.

In an actual application process, for example, after the verifying party receives a verification request, if a seed random number has not been generated for the proving party, a new random number seed (with a reference length of 32 bytes) can be generated, and meanwhile, a unique identifier of the proving party, that is, an IP address plus a port number generally, or any other identifier capable of identifying an identity, and a corresponding relationship between the two identifiers are recorded; if the seed random number has already been generated for the proving party, the verification process can be started by selecting the seed random number that has already been generated without repeated generation.

Then executing step S2 to generate capacity filling data according to the logical node sequence, wherein the capacity filling data generating step includes; based on the logic node sequence, calculating a Label value of the top node, sequencing the father node of the rest nodes, then combining the sequenced father node with the node number of the rest nodes, and calculating the node Label value of the rest nodes; and continuously storing all the node Lable values in sequence to generate capacity filling data.

For example, taking the proving party as an example to prove that the proving party has 14 × 32 (i.e., 448 bytes) storage capacity, after the proving party receives the seed random number, the proving party substitutes the seed random number into the DAG node to generate an instruction, so as to obtain a logic node sequence of the DAG graph, thereby obtaining a parent node number of each node.

Wherein, the seed random number: 0x08ab6c67.. for example, a DAG graph is logically generated for the DAG node generation instruction from the seed random number, i.e., a functional reference example of a sequence of logical nodes, as follows:

the proving party generates a logical DAG graph based on the above function, as shown in fig. 1, and generates padding data according to the calculated logical node sequence.

Specifically, the rule for generating the volume fill data is to calculate a Label value for each node in the directed acyclic graph. Such as: the Label value of the ith node, Label _ i ═ Hash (Label _ i _ p1, Label _ i _ p 2.., i), where i is the node number, Label _ i _ p1 is the Label value of the first parent node of node i, Label _ i _ p2 is the Label value of the second parent node of node i, and so on. And Hash is a Hash function. Namely, the Label value of the node i is obtained by calculating all the parent nodes of the node i and the node number i. If the node i has no parent node, the Label value of the node i can be obtained by directly Hash the Label of the node i with the serial number. Namely, Label _ i ═ hash (i).

Then, the Label values of each node are sequentially calculated in the order of increasing node numbers, and all the Label values are sequentially and continuously stored together, so that the capacity filling data shown in table 1 and fig. 2 can be formed.

TABLE 1

It is worth mentioning that as shown in table 1 and fig. 1, the nodes 0-2 are top-level nodes without father nodes, so that the Hash values of the top-level nodes Label are relatively simple to calculate, and the Hash calculation is directly performed on the node numbers. For example, the Label Hash value of node 1 is Label (1) ═ Hash (0x 0000000000000001).

When the parent node is provided for other nodes, the parent node needs to calculate the Hash value by piecing the Label value of the parent node and the number of the current node together according to the sequence of the node numbers from small to large when calculating the Label value (the Hash value of the Label). Taking node 7 as an example, and its parent nodes are 4 and 5, the calculation method is:

Label(7)＝Hash(Label(4),Label(5),7)

＝Hash(0x381d83c0..c0616ee6..0000000000000007)

＝9500afd0..

since the Hash value is 32 bytes long, only the first 4 bytes are cut out for the sake of convenience in this example, and are indicated by ".", while the actual Hash value is more than 4 bytes long. And then, connecting the Label values according to the node numbers to form filling data. That is, 14 × 32 is 448 bytes in total, and the internal structure thereof is shown in table 2, for example. The proving party constructs the capacity padding data as shown in fig. 2 with the following 448 bytes of data.

TABLE 2

Then according to step S3, the verifying party starts to initiate challenge to the proving party, and designates the challenge node to prove it; step S4 the proving party gives according to the challenge node including: the challenge node and the father node number thereof, and a first proof of the Hash value of the corresponding node; then the verification step S5 includes that the verifier needs to perform a first verification on the first certificate to compare the parent node number of the challenge node and the Hash value corresponding to the node; and if any one checking step fails, the checking step is false, and if all the checking steps pass, the checking step is true.

Specifically, in the challenge phase, the verifier may choose to continuously initiate multiple rounds of challenges to the prover, and each round of challenge verifier may choose to randomly choose a vertex j among all vertices to challenge the prover. After the prover receives the challenge number j, the label value of the node j, and the numbers and label values of all the parents of the node j must be given within a specified time.

The verifier recalculates the label value of the node j for the information given by the prover, compares the calculated label value with the label value of the node j given by the prover, and if the calculated label value is different from the label value of the node j given by the prover, the challenge fails, which indicates that the prover has cheating behavior. If the two nodes are the same, continuing the challenge, the verifying party randomly selects one parent node k from the several parent nodes of the node j to challenge, and the proving party needs to give the label value of the node k and the numbers and the label values of all the parent nodes of the node k within a specified time.

If the challenge is passed, one parent node of the node k continues to be randomly chosen for the challenge until the top node without the parent node is challenged. At the moment, the proving party only needs to give the number and the label value of the top-level node, and the verifying party can directly calculate the label value according to the number of the top-level node, so that whether the label value given by the proving party is correct or not is judged. The proof party who can successfully pass a round of challenge flow only passes a round of proof.

In addition, the capacity proof can set different challenge frequencies and times according to actual service requirements, and further carry out multiple rounds of continuous challenges as required, and the verification accuracy is improved. Because the essence of the capacity certification is to prove the existence of the filling data generated based on the directed acyclic graph by the direction verifier, as long as the filling data exists, the filling data inevitably occupies a certain storage space, thereby indirectly proving that the proving party owns the storage space

For example, when the proving party initiates a challenge, the challenge is one of the node Label numbers, and the node number is within the range of the capacity claimed by the proving party, and is random, and cannot be predicted by the proving party. For example, if the prover claims to own capacity of 14 × 32 ═ 448, the prover-initiated challenge has node Label numbers ranging from 0 to 13.

For example, in the example of fig. 1, when the proving party receives the challenge, the first proof needs to be given within a specified time. Taking Label number with 13 as challenge as an example, the first contents of certification that the certifying party needs to respond to include: what the Label (13) is, the set of parents of the node 13, and the Label values of all the parents of the node 13. Namely, Label (13), the parents 7 and 9 of node 13, and Label (7) and Label (9).

After receiving the first certificate, the verifier needs to make a first verification. The checking process is as follows, firstly, according to the same seed random number, GetParants (13) is calculated to obtain whether the father node of the node 13 is consistent with the 7 and 9 node numbers given by the prover. If not, the verification fails.

If the two are consistent, calculating Hash (Label (7), Label (9) and Label (13) according to the calculation method of Label (13), comparing the result with the Label (13) value given by a proving party, and verifying whether the two are consistent. If not, the verification fails. If the above two verifications pass, then the capacity attestation can be selected to be completed, believing that the proving party has the corresponding storage capacity.

In order to improve the accuracy of the verification and prevent the proving party from forging Label (7) and Label (9), step S6 may be performed, and then the parent node of the challenge node is issued with the second challenge, and step S7 is performed to repeat steps S4 to S5 to obtain the checking result.

For example, the second challenge is essentially a challenge to the parent node, and the verifier randomly or specifically chooses a challenge node to challenge the prover again in the parent node of the node 13. For example, the prover randomly selects node 7 of the two parents of node 13 to continue challenging the prover. At this time, the process returns to step S7 to repeat steps S4 to S5, and the challenge and verification are continued, so that the verification result can be obtained. A more reliable authentication result is obtained.

In a preferred embodiment, if the verification accuracy is further improved, step S8 may be performed, that is, steps S6 to S7 are repeated until the challenge node has no parent node, and the challenge is ended, so as to obtain the final verification result.

For example, after challenging node 7, the prover also gives the correct Label (7), parent number 4, parent number 5, Label (4), and Label (5) values. The proving party continues to challenge one parent of node 7, e.g. 5. Then if it passes, it continues to challenge parent node 1 of node 5. When the node 1 is challenged, the node 1 does not have a parent, so that the proving party only needs to give the Label value Label (1) of the node 1, and the verifying party calculates whether the Hash (1) is equal to the Label (1) given by the proving party or not. If not, the verification fails. If equal, this indicates that the proving party successfully passed the challenge of one round of capacity proving.

Up to this point, the verifier may assume that the proving party does have the purported capacity 14 × 32 — 448 bytes. If the business needs the proving party to continuously prove that the business has the corresponding capacity, the verifying steps are repeated continuously, and the situation that the proving party releases the space for other use after one round of proving can be prevented.

In order to achieve the above object, according to another aspect of the present invention, there is provided a storage medium storing computer-executable instructions that, when executed by a processor, execute the above lightweight capacity attestation method based on a directed acyclic graph, so that both verification parties complete capacity attestation.

In summary, the lightweight capacity proving method and the storage medium based on the directed acyclic graph provided by the present invention can dynamically generate the logical directed acyclic graph according to the DAG node generation instruction, replace the existing directed acyclic graph of the actual physical storage, and eliminate the problems of requiring a large amount of storage space and bandwidth occupation in the prior art, thereby effectively reducing the storage space and transmission time required for capacity proving, and the required bandwidth consumption, reducing the hardware requirement of the storage space required by both sides of the capacity proving, and integrally improving the verification efficiency of the capacity proving, and having strong popularization and commercial values.

The preferred embodiments of the invention disclosed above are intended to be illustrative only. The preferred embodiments are not intended to be exhaustive or to limit the invention to the precise embodiments disclosed. Obviously, many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and the practical application, to thereby enable others skilled in the art to best utilize the invention. The invention is limited only by the claims and the full scope and equivalents thereof, and any modification, equivalent replacement, or improvement made within the spirit and principle of the invention should be included in the protection scope of the invention.

Those skilled in the art will understand that all or part of the steps in the method according to the above embodiments may be implemented by a program, which is stored in a storage medium and includes several instructions to enable a single chip, a chip, or a processor (processor) to execute all or part of the steps in the method according to the embodiments of the present application. And the aforementioned storage medium includes: a U-disk, a removable hard disk, a Read-Only Memory (ROM), a Random Access Memory (RAM), a magnetic disk or an optical disk, and other various media capable of storing program codes.

In addition, any combination of various different implementation manners of the embodiments of the present invention can be made, and the embodiments of the present invention should also be regarded as the disclosure of the embodiments of the present invention as long as the combination does not depart from the spirit of the embodiments of the present invention.

Claims (4)

1. The lightweight capacity proving method based on the directed acyclic graph comprises the following steps:

s1, verifying that the computers of the two parties generate a logic node sequence by using the same DAG node generation instruction and the seed random number, wherein the steps comprise: a DAG node generation instruction randomly generates a seed random number according to a Hash function; generating a parent node number set of a node i by a DAG node generation instruction based on a getParants function according to the seed random number; generating a logic node sequence according to the obtained father node number sequence;

s2 the prover computer generating capacity filling data from the sequence of logical nodes, the steps comprising: based on the logic node sequence, calculating a Label value of the top node, sequencing the father node of the rest nodes, then combining the sequenced father node with the node number of the rest nodes, and calculating the node Label value of the rest nodes; continuously storing all node Lable values in sequence to generate capacity filling data;

s3 the verifier computer sends a challenge request to the prover computer, and assigns a challenge node to perform a proving computation, comprising: the verifying party randomly selects a node challenge proving party from all the vertex nodes to require the proving party to give a label value of the challenge node within a specified time after receiving the challenge node;

s4 the proving party computer providing to the proving party according to the challenge node sent by the proving party computer including: a challenge node number, and a first proof of a Label value for the challenge node;

s5 the verifier computer performing a first verification of the first proof, comprising: and recalculating the label value of the challenge node, comparing the calculated label value with the label value of the challenge node given by the proving party, and if the calculated label value is the same as the label value of the challenge node, determining that the first checking result is true to obtain a checking result.

2. The lightweight volume attestation method based on directed acyclic graph of claim 1, the steps further comprising:

s6 when the verifier computer verifies that the first verification result is true, the verifier then issues a second challenge to the parent node of the challenge node, including: the verifier randomly selects a father node from all father nodes of the previous challenge node to challenge, and the prover needs to give the label value of the father node and the numbers and the label values of all the father nodes of the father node within a specified time;

s7 repeats steps S4 to S5 to obtain the result of the ping.

3. The lightweight volume attestation method based on directed acyclic graph of claim 2, the steps further comprising:

the S8 verifier computer repeats steps S6 through S7 until the challenge node has no parent node, and the challenge is ended to obtain the final verification result.

4. A storage medium storing computer-executable instructions that, when executed by a processor, perform a method for lightweight capacity attestation based on directed acyclic graphs as claimed in any one of claims 1 to 3.

Images