Settlement

To scale the eigenvector centrality (EC) computation across a distributed network of untrusted peers, we modify the Juxtaposed Approximate PageRank (JXP) algorithm to compute global EC scores. Each peer maintains only its local fragment of the transaction graph and a World Node ($W$) that represents the global state and relative EC scores of all accounts in the supergraph.

Local EC Computation#

We start with the extreme case where each producer $u \in U$ and each buyer $v \in V$ exists in its own individual shard, which we call account-shards. These account-shards can be viewed as separate, interconnected blockchains, each maintaining the state and transactions of their single account.

Code
1Shard (00) { San Francisco }2|3|-- Account-Shard [A]4|   |-- Tx1: [A] -> [B]5|   |-- Tx2: [A] -> [C]6|7|-- Account-Shard [B]8|   |-- Tx1: [A] -> [B]9|10|-- Account-Shard [C]11    |-- Tx2: [A] -> [C]

We then group these account-shards into shard-chains, denoted as $\{G_1, G_2, ..., G_K\}$, where each shard $G_k = (U_k, V_k, E_k)$ is a subgraph of $G$. The edges $E_k$ represent the transactions between accounts within the shard $G_k$. The partitioning method for grouping follows an infinite sharding paradigm and can be defined by the parent domaingraph.

Each peer in the network is assigned to one of the $K$ shards and maintains a local copy of the shard's subgraph. The peers compute local EC scores by solving the eigenvalue problem on their local subgraph:

$$x_u = \frac{1}{\lambda_{max}} \sum_{v \in V_k} w(u,v) x_v$$ $$x_v = \frac{1}{\lambda_{max}} \sum_{u \in U_k} w(u,v) x_u$$

where $\lambda_{max}$ is the largest eigenvalue of the adjacency matrix of the shard's subgraph, and $w(u,v)$ represents the weight of the edge between producer $u$ and buyer $v$.

Merge and Sync Process#

After computing the local EC scores, each shard submits a State Diff List (SDL) to its parent domaingraph, containing the updated EC scores and the corresponding Zero-Knowledge Proof (ZKP) of the local computation. The domaingraph validates the ZKPs and updates the EC scores within its domain.

Code
1Domaingraph 1 (Domain 1)2|3|-- Shard (00) { San Francisco }4|   |-- SDL00: [EC_A, EC_B, EC_C], ZKP005|6|-- Shard (01) { New York }7    |-- SDL01: [EC_D, EC_E], ZKP01

Periodically, the domaingraphs engage in a merge and sync process with the supergraph to update the global EC scores. Each domaingraph submits its aggregated SDLs and ZKPs to the supergraph, which validates the proofs and updates the global EC state.

Code
1Supergraph2|3|-- Domaingraph 1 (Domain 1)4|   |-- SDL1: [EC_A, EC_B, EC_C, EC_D, EC_E], ZKP15|6|-- Domaingraph 2 (Domain 2)7    |-- SDL2: [...], ZKP2

Verification and Settlement#

The ZKPs submitted along with the SDLs allow the supergraph to verify the correctness of the local EC computations without requiring access to the full transaction data within each shard. This enables efficient and secure settlement of EC scores across the network.

Once the supergraph has validated and updated the global EC scores, it broadcasts the updated scores back to the domaingraph, ensuring that all domains have a consistent view of the global EC state for their next

Next Steps#

Now that we have discussed the sharding and infrastructure properties for the Local Blockchain, we will discuss the network's consensus mechanism.