CN-121998108-A - Enhanced zero knowledge analysis

Abstract

Zero Knowledge (ZK) analysis, including causal analysis and ZK proof (ZKP) generation, may be managed and performed in an enhanced manner. The graph processor may perform a first analysis of graph data of a graph related to a cause, effect, or event based on one or more ZK primitives. One or more ZK primitives may be customized for causal analysis in ZK applications. The attestation manager may determine and generate ZKP related to a cause, effect, or event based on a second result of a second analysis of result data of the first result of the first analysis, including a calculation result, wherein the result data may include primitive data representing or related to at least one ZK primitive. The attestation manager may communicate the ZKP to a verifier in order to verify the correctness of the ZKP including the calculation result.

Inventors

• MA PINGCHUAN
• WANG SHUAI
• WANG CHAOYU

Assignees

• 香港科技大学

Dates

Publication Date

20260508

Application Date

20250711

Priority Date

20241101

Claims (20)

1. 1. A method, comprising: performing, by a system comprising at least one processor, a first analysis of graph data representing a graph relating to a cause, effect or event based on at least one zero-knowledge graph element, and A zero-knowledge proof relating to the cause, the effect, or the event is determined by the system based on a second result of a second analysis of result data of the first result of the first analysis, wherein the result data includes primitive data representing the at least one zero-knowledge primitive.
2. 2. The method of claim 1, wherein the graph is a causal directed acyclic graph or a causal cyclic graph, wherein the at least one zero-knowledge primitive is customized for causal analysis of data in a zero-knowledge application, and wherein the data comprises the primitive data or the graph data.
3. 3. The method of claim 1, wherein the at least one zero-knowledge primitive comprises a zero-knowledge primitive comprising a node group and a set of edges associated with the node group, the zero-knowledge primitive having primitive features such that removing any edge in the set of edges from the zero-knowledge primitive results in a break of the zero-knowledge primitive.
4. 4. The method of claim 1, wherein the at least one zero-knowledge primitive comprises a first zero-knowledge primitive for identifying descendent and ancestor nodes of a node in the graph, a second zero-knowledge primitive for determining whether the graph is loop-free and performing loop-free or loop-bound graph processing, a third zero-knowledge primitive for evaluating whether two subgroups of a group of nodes of the graph are d-split, or a fourth zero-knowledge primitive for generating an intervention graph for a target node of the graph.
5. 5. The method of claim 1, wherein the first result comprises a causal result, wherein the performing the first analysis comprises performing, by the system, a causal analysis of data related to the cause, the effect, or the event based on the at least one zero knowledge primitive, and wherein determining the zero knowledge proof comprises determining the zero knowledge proof related to the cause, the effect, or the event based on the causal result of the causal analysis and a cryptographic key.
6. 6. The method of claim 1, further comprising: The method includes transmitting, by the system, the zero-knowledge proof to a verifier device, wherein the zero-knowledge proof facilitates verification that the zero-knowledge proof including analysis or computation result data is correct without revealing to the verifier device underlying data for determining and generating the zero-knowledge proof, and wherein the underlying data includes at least one of the graph data, data for generating the graph data representing the graph, or the primitive data.
7. 7. The method of claim 1, wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge primitive comprises a zero-knowledge primitive for identifying descendent and ancestor nodes of a node in the graph, and wherein the method further comprises: Applying, by the system, a matrix transformation to convert the causal directed acyclic graph to an upper triangular matrix external to a zero-knowledge circuit, wherein correctness of the matrix transformation within the zero-knowledge circuit is ensured based on a set of circuit constraints; Determining, by the system, an inverse of a difference between an identity matrix and the upper triangular matrix external to the zero-knowledge circuit; verifying, by the system, correctness of the inverse of the difference between an identity matrix and the upper triangular matrix within the zero-knowledge circuit, and In the resulting matrices associated with the identity matrix and the upper triangular matrix, respective descendant nodes and respective ancestor nodes associated with respective nodes of the causal directed acyclic graph are identified by the system.
8. 8. The method of claim 1, wherein the graph is a causal graph, wherein the at least one zero-knowledge primitive comprises a zero-knowledge primitive that is partially involved in determining whether the causal graph is loop-free, and wherein the method further comprises: Performing, by the system, loop detection on the causal graph outside of a zero knowledge circuit; Determining, by the system, whether the causal graph is cyclic or acyclic based on the performing the loop detection, and In response to determining that the causal graph is acyclic: Applying, by the system, a matrix transformation to convert the causal graph to an upper triangular matrix external to a zero-knowledge circuit, wherein correctness of the matrix transformation within the zero-knowledge circuit is ensured based on a set of circuit constraints, or In response to determining that the causal graph is looped, including each loop: determining, by the system, paths corresponding to ones of the respective loops external to the zero-knowledge circuit, and Constraints are enforced by the system that the path starts and ends at the same node within the zero-knowledge circuit.
9. 9. The method of claim 1, wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge primitive comprises a zero-knowledge primitive that evaluates whether a first subset of nodes and a second subset of nodes of a node group of the causal directed acyclic graph are d-separated, and wherein the method further comprises: Removing, by the system, nodes determined not to be in an ancestor group of nodes to obtain an ancestor subgraph, wherein the ancestor group of nodes is determined based on a merge operation of the first node subgroup, the second node subgroup, and the node group; applying, by the system, a daylighting to the ancestor subgraph to generate a daylighted ancestor subgraph; Transforming, by the system, the dade ancestor subgraph into a matrix, wherein correctness of the dade ancestor subgraph is verified within a zero knowledge circuit based on a first set of constraints, and Determining, by the system, whether a d-separation exists between the first subset of nodes and the second subset of nodes based on a third result of determining whether any paths exist between the respective nodes of interest of the first subset of nodes and the second subset of nodes using a matrix operation, wherein a second set of constraints is implemented within the zero-knowledge circuit to verify the correctness of the matrix operation.
10. 10. The method of claim 9, further comprising: Determining, by the system, that there is a d-separation between the first subset of nodes and the second subset of nodes based on the third result indicating that no path exists between the respective nodes of interest, or Determining, by the system, that there is no d-separation between the first subset of nodes and the second subset of nodes based on the third result indicating that the path exists between the respective nodes of interest.
11. 11. The method of claim 1, wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge primitive comprises a zero-knowledge primitive that generates an intervention graph for a target node of the causal directed acyclic graph, and wherein the method further comprises: Modifying, by the system, an adjacency matrix associated with the causal directed acyclic graph by setting an entry in a column of the adjacency matrix corresponding to the target node to a zero value, wherein modifying the adjacency matrix helps to eliminate effects of other nodes of the causal directed acyclic graph on the target node, and One or more constraints are added by the system to ensure that modifications to the adjacency matrix are implemented within zero-knowledge circuitry.
12. 12. 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 graph processor performing a first analysis of graph information representing a graph related to a cause, effect or event based on at least one zero-knowledge graph element, and A proof generator that determines a zero-knowledge proof relating to the cause, the effect, or the event based on a second result of a second analysis of result information of the first result of the first analysis, wherein the result information includes primitive information representing the at least one zero-knowledge primitive.
13. 13. The system of claim 12, wherein the graph is a causal directed acyclic graph or a causal cyclic graph, wherein the at least one zero-knowledge primitive is custom to facilitate causal analysis of information in a zero-knowledge application, and wherein the information comprises the primitive information or the graph information.
14. 14. The system of claim 12, wherein the at least one zero-knowledge primitive comprises a first zero-knowledge primitive for identifying descendent and ancestor nodes of a node in the graph, a second zero-knowledge primitive for determining whether the graph is loop-free and performing loop-free or loop-bound graph processing, a third zero-knowledge primitive for evaluating whether two subgroups of a group of nodes of the graph are d-split, or a fourth zero-knowledge primitive for generating an intervention graph for a target node of the graph.
15. 15. The system of claim 12, wherein the first analysis comprises a causal analysis, wherein the first result comprises a causal result, and wherein the proof generator performs a causal analysis of information related to the cause, the effect, or the event based on the at least one zero knowledge primitive, and determines the zero knowledge proof related to the cause, the effect, or the event based on a causal result of the causal analysis and a cryptographic key.
16. 16. The system of claim 12, wherein the attestation generator is to send or facilitate sending the zero-knowledge attestation to a verifier device, wherein the zero-knowledge attestation facilitates verification that the zero-knowledge attestation including analysis or computation result information is accurate without revealing underlying information to the verifier device for determining and generating the zero-knowledge attestation, and wherein the underlying data includes at least one of the graph information, information for generating the graph information, or the primitive information.
17. 17. The system of claim 12, wherein the graph processor 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.
18. 18. A non-transitory machine-readable medium comprising executable instructions that when executed by at least one processor facilitate performing operations comprising: performing a first analysis of graph data of a graph relating to a cause, effect or event based on at least one zero-knowledge primitive, and A zero-knowledge proof is generated relating to the cause, the effect, or the event based on a second result of a second analysis of result data of the first result of the first analysis, wherein the result data includes primitive data of the at least one zero-knowledge primitive.
19. 19. The non-transitory machine readable medium of claim 18, wherein the graph is a causal directed acyclic graph or a causal cyclic graph, wherein the at least one zero-knowledge primitive is customized for causal analysis of data in a zero-knowledge application, wherein the data comprises the primitive data or the graph data, and Wherein the at least one zero-knowledge primitive comprises a first zero-knowledge primitive for identifying descendent and ancestor nodes of a node in the graph, a second zero-knowledge primitive for determining whether the graph is loop-free and performing loop-free or loop-free graph processing, a third zero-knowledge primitive for evaluating whether two subgroups of a group of nodes of the graph are d-separated, or a fourth zero-knowledge primitive for generating an intervention graph for a target node of the graph.
20. 20. The non-transitory machine-readable medium of claim 18, wherein the operations further comprise: the zero-knowledge proof is transmitted to a verifier device, wherein the zero-knowledge proof facilitates verification that the zero-knowledge proof including analysis or calculation result data is correct without exposing underlying data to the verifier device for determining and generating the zero-knowledge proof, and wherein the underlying data includes at least one of the graph data, data for generating the graph data representing the graph, or the primitive data.

Description

Enhanced zero knowledge analysis Cross Reference to Related Applications This patent application claims priority from U.S. provisional patent application No.63/714,883 entitled "A New Approach for Efficient Zero-Knowledge Causal Analysis (New method of efficient zero knowledge causal analysis)" filed on 1 month 2024, the entire contents of which are incorporated herein by reference. Background For various applications and services, and in various situations, it may be desirable to protect personal and/or sensitive data. Various cryptographic tools may be used to secure data. For example, zero-knowledge proof (zero-knowledge proofs) may be a cryptographic tool that may enable a prover to convince a verifier of the correctness of a 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 performing, by a system including at least one processor, a first analysis of graph data that can represent a graph related to a cause, effect, or event based on at least one Zero Knowledge (ZK) primitive. The method may further include determining, by the system, a ZK proof (ZKP) related to the cause, the effect, or the event based on a second result of a second analysis of result data of the first result of the first analysis, wherein the result data may include primitive data that may represent the at least one ZK primitive. 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 graph processor that may perform a first analysis of graph information that may represent a graph related to a cause, effect, or event based on at least one ZK primitive. The computer-executable component may further comprise a proof generator that may determine ZKP related to the cause, the effect, or the event based on a second result of a second analysis of result information of the first result of the first analysis, wherein the result information may include primitive information that may represent the at least one ZK primitive. 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 performing operations. The operations may include performing a first analysis of graph data of a graph related to a cause, effect, or event based on at least one ZK primitive. The operations may further include generating ZKP associated with the cause, the effect, or the event based on a second result of a second analysis of result data of the first result of the first analysis, Wherein the result data may comprise primitive data of the at least one ZK primitive. 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 perform and manage data analysis and proof generation related to such data analysis utilizing primitives (GRAPH PRIMITIVES) 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 data analysis and credential generation related to such data analysis utilizing primitives in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 3 illustrates a schematic diagram of a non-limiting example directed acyclic graph (DIRECTED ACYCLIC GRAPH, DAG) that can represent a non-limiting example dataset, in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 4 illustr