Probabilistic Proofs in DePIN

In my last post, I introduced the economic concepts underlying Local Protocol, a general decentralized marketplace protocol.

Local protocol aims to address key challenges for decentralized physical infrastructure networks (DePINs) where services are limited by the availability or cost of proofs. We argue that the number of services that have hard cryptographic service-proofs is especially limited in physical networks, which has reduced the surface area and design space for DePIN in general. Local aims to expand this surface area for physical services that can be both peer-to-peer and token-incentivized.

Our approach acknowledges a spectrum of verifiability and provides a path forward for networks that may not have access to hard or cost-effective service proofs.

Local Protocol is an expressive architecture whose approach to verifiability is adaptable to a wide range of DePIN projects. In the root case, the protocol assumes that services do not have access to robust service-proofs.

In this post, I discuss incorporating service-proofs and identity-proofs for network's that have access to such things. I'll share why modeling proofs in Local Protocol is more cost effective than opinionated or narrow DePIN architectures, and argue that DePIN requires Local Protocol to unlock new use cases that are limited by the availability or cost of proofs.

Local Protocol Design Recap

Local Protocol is a cryptoeconomic game where buyers and sellers develop connectivity by fulfilling transactions. As users complete transactions, the protocol creates a trustless transaction graph. The block reward for the subsequent transaction is dictated by a relative connectivity ranking (more specifically, their eigenvector centrality (EC)). Self-interested actors aim to enhance their connectivity ranking which requires cooperation with transacting parties that are transacting with similar cohorts of the network. The network incentivizes users with a large reward for developing connectivity, providing the network with a strong bootstrapping and referral mechanism that doubles as the network's security guarantee.

Difficulty in Manufacturing Connectivity

Achieving a high EC score requires not only a large number of connections but also connections to other well-connected nodes. This property makes it challenging for malicious actors to manufacture high connectivity rankings, as they would need to establish links with reputable, central nodes in the network.

Legitimate, highly-connected nodes are more likely to scrutinize and avoid suspicious or low-quality nodes. As a result, attackers face significant hurdles to manipulate their EC scores.

Proofs as Graph Attributes

In graph theory, a node is a point representing an entity (buyer, seller), and an edge is a connection between two nodes (transactions). In Local protocol, we model identity-proofs (and other trust attributes for users) as node attributes and service-proofs as edge attributes.

We can assign a degree of confidence to such proofs and propagate the trust assumptions that we derive from each proof through the graph to neighboring nodes with a dampening factor over longer path lengths from the trusted node. This allows us to reduce the requirement of capturing potentially cost-prohibitive proofs for every transaction without sacrificing the security guarantee for the network.

You can think of both identity and service proofs as injecting trust into the network. As the network becomes more trustworthy, the protocol becomes more confident in distributing rewards that are greater than the fees collected for each transaction. This unlocks a rich surface area for capital formation to bootstrap new markets. New markets can inherit the security from existing markets providing the network with a strong cross-market network effect.

For immature local networks that want to prioritize bootstrapping trust, EC rankings can help establish trust vectors through a combination of service proofs and identity proofs. As the network grows and trust is established, the reliance on expensive service-proofs can be gradually reduced with a dampening factor over time.

Trust Propagation

The boost in eigenvector centrality (EC) resulting from any proof—be it an identity proof or a service proof—doesn't just affect the individual node or transaction; it propagates through the network due to the recursive nature of the EC calculation. Nodes directly connected to the node or edge associated with the proof will also see an increase in their EC because their centrality depends on the centrality of their neighbors.

The effect of any proof diminishes exponentially over longer paths in the graph. The modified EC calculation naturally captures this phenomenon, as the solution to the inhomogeneous eigenvalue problem (more on this later) accounts for the additional trust introduced by the proofs (the doping vector for nodes or adjusted weights for edges).

You can visualize the network as a series of concentric circles centered around the node or edge that has incorporated a proof. The nodes directly connected form the first circle; these are the immediate neighbors who have direct interactions with the proof-bearing node or transaction. The second circle consists of nodes connected to those immediate neighbors, which are two steps away, and so on for subsequent circles. The influence of the proof's boost in eigenvector centrality is strongest at the center and decreases exponentially as you move outward.

Nodes that transact with those who have submitted proofs benefit more than they would have without the proofs. This results in higher rewards for both parties and increases their attractiveness as transaction partners in the network. In this way, nodes in the network might view the submission of proofs, and thus the increase in security for the network, as an investment in their EC. When self-interested actors perform actions that have positive security externalities, we achieve strong design properties.

Identity Proofs as Node Attributes

Examples of identity proofs include World ID, zkPassport, or a zkTLS authentication with a relevant Web2 provider using Opacity Network. These proofs can be assigned a score that unlocks a larger block rewards for both this node and any transacting counterparties. Specifically, we boost nodes that have evidence of realness because it provides the network with stronger sybil resistance.

Incorporating Identity Proofs into Eigenvector Centrality

We represent the network as a bipartite graph $G = (U, V, E)$, where $U$ and $V$ are disjoint sets of nodes representing producers (sellers) and buyers, respectively, and $E$ is the set of edges representing transactions between them.

The eigenvector centrality (EC) $x$ of the nodes in the graph is calculated by solving the eigenvalue problem:

$$\lambda_{\text{max}} \mathbf{x} = \mathbf{A} \mathbf{x},$$

where $A$ is the adjacency matrix of the graph, and $\lambda_{\text{max}}$ is the largest eigenvalue.

When a user provides an identity proof, we model this as adding a doping vector $b$ to the eigenvalue equation This can be captured by modifying the EC formula to become an inhomogeneous eigenvalue problem. Suppose user $u$ submits an identity proof that translates into a boost of $b$ in eigenvector centrality. We then define a "doping vector" $\vec{b}_u = (0,0,\dots,0,b,0,\dots,0)$, where the nonzero element $b$ appears in the $u$-th position. The inhomogeneous eigenvalue problem to solve is then:

$$x = \frac{1}{\lambda_{\rm max}} Ax + \vec{b}$$

Service Proofs

While identity proofs enhance trust in individual nodes, service proofs strengthen the reliability of specific transactions (edges) between nodes. Some existing examples in the wild:

• Wireless Networks

  • Proof of Coverage (PoC)

• Mobility and Logistics

  • Proof of Route Compliance

• Energy

  • Proof of Green Energy Generation (PoGG)

• Compute and Storage

  • Proof of Spacetime
  • Proof of Replication
  • Proof of Useful Work

• Domain Agnostic

  • Proof of Location
  • Proof of Presence
  • Proof of Time

Service Proofs in the Adjacency Matrix

Each edge $(u, v) \in E$ in the graph has a weight $w_{uv}$ representing the cumulative fees or value from transactions between producer $u$ and buyer $v$. When a service proof is available, we adjust the edge weight to reflect the increased confidence in that transaction:

$$w_{uv} \leftarrow w_{uv} + b,$$

where $b$ is the boost provided by the service proof.

Alternatively, in terms of the adjacency matrix $\mathbf{A}$, we update the entry:

$$A_{uv} \leftarrow A_{uv} + b.$$

This adjustment increases the significance of the edge $(u, v)$ in the calculation of EC.

Impact on Eigenvector Centrality and Rewards

By increasing the weight of the edge $(u, v)$, both nodes $u$ and $v$ receive a higher EC score due to their strengthened connection. This boost is again propagated through the network.

Higher EC scores translate into increased graph values $G_u$ and $G_v$, which are used to calculate block rewards. Therefore, providing service proofs directly benefits the involved parties and indirectly enhances the trustworthiness of their neighbors.

In the next EC calculation, both $x_u$ and $x_v$ will increase more than they would have without the proof. This results in higher rewards for both parties and increases their attractiveness as transaction partners in the network; transacting with high EC nodes boosts ones own EC.

Proofs as Probabilities

Modeling proofs as increments in edge weights allows us to treat proofs as probabilistic assessments, rather than binary evidence of service. This approach acknowledges that proofs for physical services can vary in strength and reliability which is particularly useful for networks that lack hard cryptographic proofs-of-service.

By quantifying the confidence level $b$, we can proportionally adjust the influence of each proof in the network, unlocking a wider range of evidence and increasing the applicability for networks that do not have deterministic proofs or where capturing / computing proofs is cost-prohibitive (which could break the unit economics of the service in question).

Said another way, physical networks have a spectrum of proofs. Local Protocol reduces the reliance on absolute measures of trust, which may be impractical or costly, and instead uses the aggregate trust derived from various proofs and interactions within the network.

Random Sampling and Slashing

To ensure that the graph doesn't lose its security guarantees as new nodes enter the game, the network can randomly sample for service-proofs or service-approximations if proofs aren't available. If a node fails to provide their proofs, the network can slash the edge weights (tokens staked in the graph), and add a inverse doping vector to the nodes that fail to provide their proofs. This localized penalty system encourages self-policing and allows the network to remain secure without necessitating costly proofs for every transaction.

Inverse Doping Vector

When the network randomly samples a transaction and requests a service proof, the involved nodes must submit the required proof. If they fail to do so, we model this as an inverse doping vector in the eigenvector centrality (EC) calculation. Specifically, we decrease the EC scores of the nodes in question and remove the edge representing the fake transaction. This slashing not only impacts the penalized nodes but also affects their neighboring nodes, with the effect diminishing exponentially over longer paths in the graph.

$$\mathbf{x} = \frac{1}{\lambda_{\text{max}}} \mathbf{A} \mathbf{x} - \vec{d},$$

where $\vec{d}$ is a vector with positive entries corresponding to the penalized nodes, effectively reducing their EC scores.

For example, if node $u$ fails to submit a proof, the inverse doping vector $\vec{d}$ has a positive value $d_u$ at position $u$ and zeros elsewhere:

$$\vec{d} = (0, 0, \dotsc, d_u, \dotsc, 0)^\top.$$

The impact of this penalty propagates through the network due to the nature of the EC calculation and the edge weights $w_{uv}$ associated with the failed transaction are also decreased or set to zero:

$$w_{uv} \leftarrow w_{uv} \times (1 - \gamma),$$

Slashing Neighbors

To further encourage self-policing, we can extend the penalty to nodes directly connected to the penalized node. This is modeled by adjusting the inverse doping vector to include these neighboring nodes with scaled penalties.

Let $N(u)$ denote the set of nodes directly connected to node $u$. We define the inverse doping vector $\vec{d}$ as:

$$d_i = \begin{cases} d_u & \text{if } i = u, \\ \alpha \times d_u & \text{if } i \in N(u), \\ 0 & \text{otherwise}, \end{cases}$$

where $0 < \alpha < 1$ is the decay factor representing the reduced penalty on neighboring nodes. For each node $i \in N(u)$, we can adjust the edge weights $w_{ui}$ associated with the neighboring node where $0 < \beta < \gamma$ is a smaller slashing factor for the connected edges.

$$w_{ui} \leftarrow w_{ui} \times (1 - \beta),$$

The effect of the penalty diminishes exponentially over longer paths in the network. Mathematically, this is inherent in the properties of the EC calculation. The further a node is from the penalized node, the less impact the inverse doping vector has on its EC score.

This decay can be adjusted through the choice of decay factor $\alpha$ and slashing factors $\gamma$ and $\beta$, allowing network designers to balance between strictness and leniency based on the desired security level.

This slashing mechanism encourages nodes to maintain genuine connections and discourages malicious behavior.

Conclusion

Incorporating identity proofs and service proofs into the Local Protocol graph enhances the network's ability to verify users and transactions without relying solely on network connectivity. By modeling proofs as probabilistic boosts in eigenvector centrality (EC), we allow trust to propagate organically through the network. This approach balances the need for security with the practical limitations of obtaining proofs in various markets.

By integrating proofs into the mathematical framework of the graph, we create a system where security (trust) is directly linked to economic rewards. Nodes are incentivized to provide proofs, not just for their own benefit, but also to enhance the trustworthiness of transacting partners in their Local network.

Local Protocol supports a wide range of decentralized services, even those without hard cryptographic proofs, expanding the design space for DePIN projects. This enables more services to be both peer-to-peer and token-incentivized.