US-20260128896-A1 - ENHANCED ZERO-KNOWLEDGE ANALYSIS

US20260128896A1US 20260128896 A1US20260128896 A1US 20260128896A1US-20260128896-A1

Abstract

Zero-knowledge (ZK) analysis, including causal analysis, and ZK proof (ZKP) generation can be enhancedly managed and performed. A graph processor can perform first analysis of graph data of a graph relating to a cause, effect, or event based on one or more ZK graph primitives. The one or more ZK graph primitives can be tailored for causal analysis in ZK applications. A proof manager can determine and generate a ZKP, comprising computation results, relating to the cause, effect, or event, based on a second result of second analysis of result data of a first result of the first analysis, wherein the result data can comprise graph primitive data representative of or relating to the at least one ZK graph primitive. The proof manager can communicate the ZKP to a verifier to facilitate verification of correctness of the ZKP, including the computation results.

Inventors

Pingchuan MA
Shuai Wang
Zhaoyu Wang

Assignees

THE HONG KONG UNIVERSITY OF SCIENCE AND TECHNOLOGY

Dates

Publication Date: 20260507
Application Date: 20250701

Claims (20)

1 . A method, comprising: performing, by a system comprising at least one processor, a first analysis of graph data representative of a graph relating to a cause, an effect, or an event based on at least one zero-knowledge graph primitive; and determining, by the system, a zero-knowledge proof relating to the cause, the effect, or the event based on a second result of a second analysis of result data of a first result of the first analysis, wherein the result data comprises graph primitive data representative of the at least one zero-knowledge graph primitive.
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 graph primitive is tailored for a causal analysis of data in a zero-knowledge application, and wherein the data comprises the graph primitive data or the graph data.
3 . The method of claim 1 , wherein the at least one zero-knowledge graph primitive comprises a zero-knowledge graph primitive comprising a group of nodes and a group of edges associated with the group of nodes, the zero-knowledge graph primitive having a graph primitive characteristic whereby removal of any edge of the group of edges from the zero-knowledge graph primitive results in disconnection of the zero-knowledge graph primitive.
4 . The method of claim 1 , wherein the at least one zero-knowledge graph primitive comprises a first zero-knowledge graph primitive for identification of descendant nodes and ancestor nodes of a node in the graph, a second zero-knowledge graph primitive that determines whether the graph is acyclic and performs acyclic or cyclic graph processing, a third zero-knowledge graph primitive that assesses whether two subgroups of a group of nodes of the graph are d-separated, or a fourth zero-knowledge graph primitive that generates an interventional graph for a target node of the graph.
5 . The method of claim 1 , wherein the first result comprises a causal result, wherein the performing of the first analysis comprises performing, by the system, a causal analysis of data relating to the cause, the effect, or the event based on the at least one zero-knowledge graph primitive, and wherein the determining of the zero-knowledge proof comprises determining the zero-knowledge proof relating to the cause, the effect, or the event based on the causal result of the causal analysis and a cryptographic key.
6 . The method of claim 1 , further comprising: communicating, by the system, the zero-knowledge proof to a verifier device, wherein the zero-knowledge proof facilitates verification that the zero-knowledge proof, comprising analysis or computational result data, is correct, without revealing, to the verifier device, underlying data that was utilized to determine and generate the zero-knowledge proof, and wherein the underlying data comprises at least one of the graph data, data utilized to generate the graph data representative of the graph, or the graph primitive data.
7 . The method of claim 1 , wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge graph primitive comprises a zero-knowledge graph primitive for identification of descendant nodes 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 into an upper triangular matrix outside of a zero-knowledge circuit, wherein correctness of the matrix transformation within the zero-knowledge circuit is ensured based on a group of circuit constraints; determining, by the system, an inverse of a difference between an identity matrix and the upper triangular matrix outside of the zero-knowledge circuit; verifying, by the system, correctness of the inverse of the difference between the identity matrix and the upper triangular matrix within the zero-knowledge circuit; and in a resulting matrix relating to the identity matrix and the upper triangular matrix, identifying, by the system, respective descendant nodes and respective ancestor nodes associated with respective nodes of the causal directed acyclic graph.
8 . The method of claim 1 , wherein the graph is a causal graph, wherein the at least one zero-knowledge graph primitive comprises a zero-knowledge graph primitive relating, in part, to determining whether the causal graph is acyclic, and wherein the method further comprises: performing, by the system, cycle detection on the causal graph, outside of a zero-knowledge circuit; based on the performing of the cycle detection, determining, by the system, whether the causal graph is cyclic or acyclic; and in response to determining that the causal graph is acyclic: applying, by the system, a matrix transformation to convert the causal graph into an upper triangular matrix outside of a zero-knowledge circuit, wherein correctness of the matrix transformation within the zero-knowledge circuit is ensured based on a group of circuit constraints; or in response to determining that the causal graph is cyclic, comprising cycles: determining, by the system, a path corresponding to a cycle of the cycles outside of the zero-knowledge circuit; and enforcing, by the system, a constraint that the path starts and ends at a same node within the zero-knowledge circuit.
9 . The method of claim 1 , wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge graph primitive comprises a zero-knowledge graph primitive that assesses whether a first subgroup of nodes and a second subgroup of nodes of a group of nodes of the causal directed acyclic graph are d-separated, and wherein the method further comprises: removing, by the system, nodes that are determined to not be in an ancestor group of nodes to obtain an ancestor subgraph, wherein the ancestor group of nodes is determined based on a union operation of the first subgroup of nodes, the second subgroup of nodes, and the group of nodes; applying, by the system, moralization to the ancestor subgraph to generate a moralized ancestor subgraph; transforming, by the system, the moralized ancestor subgraph into a matrix, wherein correctness of the moralized ancestor subgraph is verified within a zero-knowledge circuit based on a first group of constraints; and determining, by the system, whether there is d-separation between the first subgroup of nodes and the second subgroup of nodes based on a third result of determining, utilizing matrix operations, whether there is any path between respective nodes of interest of the first subgroup of nodes and the second subgroup of nodes, wherein a second group of constraints is enforced within the zero-knowledge circuit to verify correctness of the matrix operations.
10 . The method of claim 9 , further comprising: determining, by the system, there is the d-separation between the first subgroup of nodes and the second subgroup of nodes based on the third result indicating non-existence of a path between the respective nodes of interest; or determining, by the system, there is no d-separation between the first subgroup of nodes and the second subgroup of nodes based on the third result indicating an existence of the path between the respective nodes of interest.
11 . The method of claim 1 , wherein the graph is a causal directed acyclic graph, wherein the at least one zero-knowledge graph primitive comprises a zero-knowledge graph primitive that generates an interventional 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 entries in a column of the adjacency matrix corresponding to the target node to zero values, wherein the modifying of the adjacency matrix facilitates eliminating influences of other nodes of the causal directed acyclic graph on the target node; and adding, by the system, one or more constraints to ensure that the modifying of the adjacency matrix is enforced within a zero-knowledge circuit.
12 . A system, comprising: at least one memory that stores computer executable components; and at least one processor that executes computer executable components stored in the at least one memory, wherein the computer executable components comprise: a graph processor that performs a first analysis of graph information representative of a graph relating to a cause, an effect, or an event based on at least one zero-knowledge graph primitive; 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 a first result of the first analysis, wherein the result information comprises graph primitive information representative of the at least one zero-knowledge graph primitive.
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 graph primitive is customized to facilitate a causal analysis of information in a zero-knowledge application, and wherein the information comprises the graph primitive information or the graph information.
14 . The system of claim 12 , wherein the at least one zero-knowledge graph primitive comprises a first zero-knowledge graph primitive for identification of descendant nodes and ancestor nodes of a node in the graph, a second zero-knowledge graph primitive that determines whether the graph is acyclic and performs acyclic or cyclic graph processing, a third zero-knowledge graph primitive that assesses whether two subgroups of a group of nodes of the graph are d-separated, or a fourth zero-knowledge graph primitive that generates an interventional graph for a target node of the graph.
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 the causal analysis of information relating to the cause, the effect, or the event based on the at least one zero-knowledge graph primitive, and, based on the causal result of the causal analysis and a cryptographic key, determines the zero-knowledge proof relating to the cause, the effect, or the event.
16 . The system of claim 12 , wherein the proof generator transmits or facilitates transmission of the zero-knowledge proof to a verifier device, wherein the zero-knowledge proof facilitates validation that the zero-knowledge proof, comprising analysis or computational result information, is accurate, without divulging, to the verifier device, underlying information that was utilized to determine and generate the zero-knowledge proof, and wherein the underlying information comprises at least one of the graph information, information utilized to generate the graph information, or the graph primitive information.
17 . The system of claim 12 , wherein the graph processor or the proof generator comprises or utilizes an accelerator unit, a graphics processing unit, a field-programmable gate array, or an application specific integrated circuit.
18 . A non-transitory machine-readable medium, comprising executable instructions that, when executed by at least one processor, facilitate performance of operations, comprising: performing a first analysis of graph data of a graph relating to a cause, an effect, or an event based on at least one zero-knowledge graph primitive; and generating a zero-knowledge proof relating to the cause, the effect, or the event based on a second result of a second analysis of result data of a first result of the first analysis, wherein the result data comprises graph primitive data of the at least one zero-knowledge graph primitive.
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 graph primitive is tailored for a causal analysis of data in a zero-knowledge application, wherein the data comprises the graph primitive data or the graph data, and wherein the at least one zero-knowledge graph primitive comprises a first zero-knowledge graph primitive for identification of descendant nodes and ancestor nodes of a node in the graph, a second zero-knowledge graph primitive that determines whether the graph is acyclic and performs acyclic or cyclic graph processing, a third zero-knowledge graph primitive that assesses whether two subgroups of a group of nodes of the graph are d-separated, or a fourth zero-knowledge graph primitive that generates an interventional graph for a target node of the graph.
20 . The non-transitory machine-readable medium of claim 18 , wherein the operations further comprise: communicating the zero-knowledge proof to a verifier device, wherein the zero-knowledge proof facilitates verification that the zero-knowledge proof, comprising analysis or computational result data, is correct, without exposing, to the verifier device, underlying data that was utilized to determine and generate the zero-knowledge proof, and wherein the underlying data comprises at least one of the graph data, data utilized to generate the graph data representative of the graph, or the graph primitive data.

Description

CROSS-REFERENCE TO RELATED APPLICATION This patent application claims priority to U.S. Provisional Patent Application No. 63/714,883, filed Nov. 1, 2024, and entitled, “A New Approach for Efficient Zero-Knowledge Causal Analysis,” the entirety of which application is hereby incorporated by reference herein. BACKGROUND For a variety of applications and services, and in a variety of situations, it can be desirable to protect personal and/or sensitive data. Various cryptographic tools can be utilized to protect data. For instance, zero-knowledge proofs can be a cryptographic tool that can enable a prover to convince a verifier of the correctness of computations without revealing the underlying data utilized in performing the computations and generating the zero-knowledge proof. The above-described description is merely intended to provide a contextual overview regarding cryptographic tools and proofs, and is not intended to be exhaustive. SUMMARY 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 comprise a method that can comprise performing, by a system comprising at least one processor, a first analysis of graph data that can be representative of a graph relating to a cause, an effect, or an event based on at least one zero-knowledge (ZK) graph primitive. The method also can comprise determining, by the system, a ZK proof (ZKP) relating to the cause, the effect, or the event based on a second result of a second analysis of result data of a first result of the first analysis, wherein the result data can comprise graph primitive data that can be representative of the at least one ZK graph primitive. In certain embodiments, the disclosed subject matter can comprise a system that can comprise at least one memory that can store computer executable components, and at least one processor that can execute computer executable components stored in the at least one memory. The computer executable components can comprise a graph processor that can perform a first analysis of graph information that can be representative of a graph relating to a cause, an effect, or an event based on at least one ZK graph primitive. The computer executable components also can comprise a proof generator that can determine a ZKP relating to the cause, the effect, or the event based on a second result of a second analysis of result information of a first result of the first analysis, wherein the result information can comprise graph primitive information that can be representative of the at least one ZK graph primitive. In still other embodiments, the disclosed subject matter can comprise a non-transitory machine-readable medium, comprising executable instructions that, when executed by at least one processor, can facilitate performance of operations. The operations can comprise performing a first analysis of graph data of a graph relating to a cause, an effect, or an event based on at least one ZK graph primitive. The operations also can comprise generating a ZKP relating to the cause, the effect, or the event based on a second result of a second analysis of result data of a first result of the first analysis, wherein the result data can comprise graph primitive data of the at least one ZK graph primitive. The following description and the annexed drawings set forth in detail certain illustrative aspects of the subject disclosure. These aspects are indicative, however, of but a few of the various ways in which the principles of various disclosed aspects can be employed and the 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. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 illustrates a block diagram of a non-limiting example system that can desirably perform and manage data analysis and proof generation relating to such data analysis utilizing graph primitives, in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 2 depicts a block diagram of a non-limiting example proof manager component that can desirably perform and manage data analysis and proof generation relating to such data analysis utilizing graph primitives, in accordance with various aspects and embodiments of the disclosed subject matter. FIG. 3 depicts a diagram of a non-limiting example directed acyclic graph (DAG) that can be representative of a non-limiting example dataset, in accordance with various aspects and embodiments of the disclosed subje