CN-121997350-A - Enhanced distributed zero knowledge proof generation

Abstract

Zero Knowledge Proof (ZKP) generation may be managed and performed in an enhanced manner. The attestation manager may decompose a Directed Acyclic Graph (DAG) representing a data analysis workflow into respective sub-DAGs representing respective workflow portions. Based on the respective sub-DAGs, the attestation manager may determine respective sub-ZKPs related to the respective workflow portions and the sub-DAGs. The respective sub ZKPs may be determined simultaneously using the respective servers. The attestation manager may hash the respective input and output values of the respective child DAGs and include the respective hashed values in the respective child ZKPs. Based on linking respective sub-ZKPs having respective hash values meeting prescribed matching criteria, the attestation manager may determine and generate a ZKP related to the workflow that includes the calculation result. The attestation manager may communicate the ZKP to a verifier in order to verify the correctness of the ZKP including the calculation result. The attestation manager may store the sub-ZKP and reuse the stored sub-ZKP in connection with the computation of the sub-DAG of another workflow.

Inventors

• MA PINGCHUAN
• WANG SHUAI
• WANG CHAOYU

Assignees

• 香港科技大学

Dates

Publication Date

20260508

Application Date

20250630

Priority Date

20241101

Claims (20)

1. 1. A method, comprising: decomposing, by a system comprising at least one processor, a graph representing a workflow into respective subgraphs representing respective portions of the workflow; based on the respective subgraph, the system determines a respective sub-proof related to the respective portion of the workflow and the respective subgraph, and Based on the respective sub-proof, the system generates a proof related to the workflow.
2. 2. The method of claim 1, wherein the proof is a zero-knowledge proof and the respective sub-proof is a respective zero-knowledge sub-proof.
3. 3. The method of claim 1, wherein the workflow is a data analysis workflow, wherein the graph is a directed acyclic graph, and wherein the respective subgraph is a respective directed acyclic subgraph.
4. 4. The method of claim 1, further comprising: Based on respective computing operations performed within the respective subgraph, the system determines respective sub-result data items related to the workflow, wherein the respective sub-proof includes the respective sub-result data items, and Based on the respective sub-attestation, the system determines the attestation related to the workflow that includes result data, wherein the result data is determined based on the respective sub-result data item.
5. 5. The method of claim 4, further comprising: the system communicates the attestation to a verifier device, wherein the attestation facilitates verifying that the attestation including the result data is correct without revealing underlying data of the workflow used to determine and generate the attestation to the verifier device.
6. 6. The method of claim 4, wherein respective edges between the respective subgraphs represent respective data dependencies, wherein the respective subgraphs comprise respective input values and respective output values, and wherein the method further comprises: The system hashes the respective input value and the respective output value of the respective sub-graph to generate a respective hashed input value and a respective hashed output value of the respective sub-graph, wherein the respective hashed input value and the respective hashed output value of the respective sub-graph are included in the respective sub-attestation, wherein the respective hashed input value and the respective hashed output value are submitted in the respective sub-attestation as respective hashed commitments to ensure integrity of the workflow, including integrity of data flows between the respective sub-graphs, and The system links the respective sub-proof to generate the proof based on the respective hash input value and the respective hash output value of the respective sub-proof.
7. 7. The method of claim 6, wherein the respective sub-proof comprises a first sub-proof and a second sub-proof, wherein the first sub-proof comprises a first hashed input value and a first hashed output value, wherein the second sub-proof comprises a second hashed input value and a second hashed output value, and wherein the method further comprises: Based on determining that the first hashed output value of the first sub-proof meets a prescribed matching criterion with respect to the second hashed input value of the second sub-proof, the system determines that an output of the first sub-proof is to be linked to an input of the second sub-proof, wherein the linking includes linking the output of the first sub-proof to the input of the second sub-proof based on determining that the output of the first sub-proof is to be linked to the input of the second sub-proof.
8. 8. The method of claim 1, wherein the workflow is a first workflow, wherein the proof is a first proof, and wherein the method further comprises: The system stores the respective sub-proof in a data store, wherein the respective sub-proof is associated with a respective computing task, the respective sub-proof comprising a first sub-proof associated with a first computing task performed within a first one of the respective sub-graphs; Based on an analysis of a second computing task associated with the second workflow and the first computing task associated with the first sub-proof, the system determines that the second computing task meets prescribed similarity criteria with respect to the first computing task in conjunction with a second workflow, wherein the second computing task is associated with a second sub-graph representing a portion of the second workflow; retrieving, by the system, the first sub-attestation from the data store based on determining that the second computing task associated with the second workflow meets the prescribed similarity criteria with respect to the first computing task associated with the first sub-attestation, and The system utilizes the first sub-proof as a second sub-proof with respect to the second sub-graph to facilitate generating a second proof related to the second workflow, wherein the second sub-graph represents the portion of the second workflow.
9. 9. The method of claim 1, wherein the respective sub-graph comprises a first sub-graph representing a first portion of the workflow and a second sub-graph representing a second portion of the workflow, wherein the respective sub-proof comprises a first sub-proof related to the first sub-graph and a second sub-proof related to the second sub-graph, and wherein determining the respective sub-proof comprises: Determining the first sub-proof based on the first sub-graph, and In parallel with determining the first sub-proof, the second sub-proof is determined based on the second sub-graph.
10. 10. A system, comprising: At least one memory storing computer-executable components, and At least one processor executing computer executable components stored in the at least one memory, wherein the computer executable components comprise: a decomposer which decomposes a graph representing a workflow into respective sub-graphs relating to respective portions of the workflow, an A proof generator that determines, based on the respective sub-graph, a respective sub-proof related to the respective portion of the workflow and the respective sub-graph, to facilitate generating a proof related to the workflow.
11. 11. The system of claim 10, wherein the workflow is a data analysis workflow, wherein the proof is a zero knowledge proof and the respective sub-proof comprises a respective zero knowledge sub-proof, and wherein the graph is a directed acyclic graph and the respective sub-graph comprises a respective directed acyclic sub-graph.
12. 12. The system of claim 10, wherein the attestation generator determines a respective item of sub-result information related to the workflow based on a respective computing task performed within the respective sub-graph and determines and generates the attestation related to the workflow including result information based on the respective sub-attestation, and wherein the respective sub-attestation includes the respective item of sub-result information data.
13. 13. The system of claim 12, wherein the attestation generator transmits or facilitates transmission of the attestation to a verifier device, and wherein the attestation facilitates verification that the attestation including the result information is correct without revealing underlying information of the workflow used to determine and generate the attestation to the verifier device.
14. 14. The system of claim 13, wherein respective edges between the respective subgraphs represent respective data dependencies, wherein the respective subgraphs include respective input values and respective output values, and wherein the computer-executable components further comprise: A hasher that hashes the respective input value and the respective output value of the respective sub-graph to generate a respective hashed input value and a respective hashed output value of the respective sub-graph as part of the respective sub-proof, wherein the respective hashed input value and the respective hashed output value are submitted in the respective sub-proof as respective hashed commitments to ensure integrity of the workflow and integrity of a data flow between the respective sub-graphs, and A linker linking the respective sub-proof based on the respective hash input value and the respective hash output value of the respective sub-proof to facilitate generating the proof.
15. 15. The system of claim 14, wherein the respective sub-proof comprises a first sub-proof and a second sub-proof, wherein the first sub-proof comprises a first hashed input value and a first hashed output value, wherein the second sub-proof comprises a second hashed input value and a second hashed output value, wherein the linker determines that an output of the first sub-proof is to be linked to an input of the second sub-proof based on determining that the first hashed output value of the first sub-proof meets a prescribed matching criterion with respect to the second hashed input value of the second sub-proof, and wherein the linker links the output of the first sub-proof to the input of the second sub-proof in response to determining that the output of the first sub-proof is to be linked to the input of the second sub-proof.
16. 16. The system of claim 10, wherein the workflow is a first workflow, wherein the respective sub-attestation is associated with a respective computing task, the respective sub-attestation including a first sub-attestation associated with a first computing task performed within a first of the respective sub-graphs, wherein the attestation is a first attestation, wherein the attestation generator stores or facilitates storage of the respective sub-attestation in a data store; Wherein, in connection with a second workflow, the attestation generator determines that a second computing task associated with the second workflow is associated with a second sub-graph representing a portion of the second workflow based on an analysis result of the second computing task associated with the second workflow and the first computing task associated with the first sub-attestation that the second computing task meets prescribed similarity criteria with respect to the first computing task; Wherein the attestation generator obtains the first sub-attestation from the data store based on determining that the second computing task meets the prescribed similarity criteria with respect to the first computing task, and Wherein the attestation generator utilizes the first sub-attestation as a second sub-attestation for the second sub-graph to facilitate generation of a second attestation related to the second workflow, wherein the second sub-graph represents the portion of the second workflow, or the attestation generator modifies the first sub-attestation to generate a modified sub-attestation and utilizes the modified sub-attestation as the second sub-attestation for the second sub-graph to facilitate generation of the second attestation.
17. 17. The system of claim 10, wherein the respective sub-graph comprises a first sub-graph representing a first portion of the workflow and a second sub-graph representing a second portion of the workflow, wherein the respective sub-proof comprises a first sub-proof related to the first sub-graph and a second sub-proof related to the second sub-graph, and wherein a first server is to facilitate determining the first sub-proof based on the first sub-graph, while a second server is to facilitate determining the second sub-proof based on the second sub-graph.
18. 18. The system of claim 10, wherein the decomposer or the proof generator comprises or utilizes an accelerator unit, a graph processing unit, a field programmable gate array, or an application specific integrated circuit.
19. 19. A non-transitory machine-readable medium comprising executable instructions that when executed by at least one processor facilitate performance of operations comprising: partitioning a directed acyclic graph representing a workflow into respective directed acyclic subgraphs related to respective portions of the workflow; Generating a respective child proof relating to said respective portion of said workflow and said respective directed acyclic subgraph based on said respective directed acyclic subgraph, and Based on the respective sub-proof, a proof relating to the workflow is generated.
20. 20. The non-transitory machine-readable medium of claim 19, wherein the workflow is a data analysis workflow, wherein the proof is a zero-knowledge proof, and the respective sub-proof comprises a respective zero-knowledge sub-proof, and wherein the operations further comprise: determining respective sub-result data items related to the data analysis workflow based on respective computing tasks performed within respective directed acyclic subgraphs, wherein the respective zero-knowledge sub-proof includes the respective sub-result data items; determining the zero-knowledge proof including result data related to the data analysis workflow based on the respective zero-knowledge sub-proof, wherein the result data is determined based on the respective sub-result data item, and Transmitting the zero-knowledge proof to a verifier device, wherein the zero-knowledge proof facilitates verifying that the zero-knowledge proof including the result data is correct without revealing underlying data of the data analysis workflow for determining and generating the zero-knowledge proof to the verifier device.

Description

Enhanced distributed zero knowledge proof generation Cross Reference to Related Applications This patent application claims priority from U.S. provisional patent application No.63/714,884 entitled "A NewApproach for Distributed Zero-Knowledge Proof Generation for DataAnalytics Workflow (a novel method for distributed zero knowledge proof generation of data analysis workflow)" filed on month 11 of 2024, the entire contents of which are incorporated herein by reference. Background Various cryptographic tools may be used to secure data. For example, the zero-knowledge proof may be a cryptographic tool that may enable a prover to convince a verifier of the correctness of the computation without revealing underlying data used in performing the computation and generating the zero-knowledge proof. The above description is intended only to provide a contextual overview of cryptographic tools and certificates, and is not intended to be exhaustive. Disclosure of Invention The following presents a simplified summary in order to provide a basic understanding of some aspects described herein. This summary is not an extensive overview of the disclosed subject matter. It is intended to neither identify key or critical elements of the disclosure nor delineate the scope thereof. Its sole purpose is to present some concepts in a simplified form as a prelude to the more detailed description that is presented later. In some embodiments, the disclosed subject matter can include a method that can include decomposing, by a system including at least one processor, a graph representing a workflow into respective subgraphs representing respective portions of the workflow. The method may further include, based on the respective sub-graph, the system determining a respective sub-proof related to the respective portion of the workflow and the respective sub-graph. The method may further include the system generating a proof relating to the workflow based on the respective sub-proof. In some embodiments, the disclosed subject matter can include a system that can include at least one memory that can store computer-executable components, and at least one processor that can execute the computer-executable components stored in the at least one memory. The computer-executable components may include a decomposer that can decompose a graph representing a workflow into respective sub-graphs associated with respective portions of the workflow. The computer-executable components may also include a attestation generator that may determine respective sub-attestations relating to respective portions of the workflow and the respective sub-graphs based on the respective sub-graphs to facilitate generating attestations relating to the workflow. In other embodiments, the disclosed subject matter may include a non-transitory machine-readable medium comprising executable instructions that, when executed by at least one processor, may facilitate performance of operations. The operations may include partitioning a directed acyclic graph representing a workflow into respective directed acyclic subgraphs related to respective portions of the workflow. The operations may also include generating respective child proof relating to the respective portion of the workflow and the respective directed acyclic subgraph based on the respective directed acyclic subgraph. The operations may also include generating a proof relating to the workflow based on the respective sub-proof. The following description and the annexed drawings set forth in detail certain illustrative aspects of the disclosure. These aspects are indicative, however, of but a few of the various ways in which the principles of the various aspects disclosed may be employed and the present disclosure is intended to include all such aspects and their equivalents. Other advantages and features will become apparent from the following detailed description when considered in conjunction with the drawings. Drawings FIG. 1 illustrates a block diagram of a non-limiting example system that can desirably execute and manage attestation generation of a data set in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 2 illustrates a block diagram of a non-limiting exemplary credential manager component that can desirably perform and manage credential generation (including credential generation and distributed credential generation for larger scale data sets) in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 3 illustrates a schematic diagram of a non-limiting example attestation generation process that can include decomposing a graph related to a workflow into sub-graphs, generating sub-attestations based at least in part on the sub-graphs, and generating attestations related to the workflow based at least in part on the sub-attestations, in accordance with aspects and embodiments of the disclosed subject matter. FIG. 4 illustrates a block diagram