Manipulated signals in DePIN protocols

In a typical Decentralized Physical Infrastructure Network (DePIN) application, a network of suppliers is tasked with providing a service — weather readings in designated locations, broadband access, or energy, for example — to a client. Because self-interested suppliers can’t be trusted to self-report on their status, the question then becomes: How and when can a network truthfully elicit the status of a supplier?

For example, suppose a client relies on a physical service being accessible and reliable in a particular area. The client would want to verify that service exists in that location, and is motivated enough to provide compensation for service provision but can’t trust the provider to accurately self-report because it might be cheaper for the provider to offer the service elsewhere and just spoof the location. This is the problem of location verification, which we’ll use as our illustrative example throughout.

In new research, we formally characterize the two fundamental obstacles — manipulation and self-dealing — that stand in the way of verifying the level of service provided by a supplier (in our example, its location). Importantly, knowing that these are the only two obstacles also suggests approaches for how to resolve them. Our framework is the first to provide a basis from which to reason about what types of services can and cannot be incentivized in DePIN applications.

Our model

Our model has three types of participants: the client, who requests the service; the source, who claims to provide the service; and the observers, who can at least partially verify the extent to which the source performed the expected service. We focus on the source and the observers.

The source of the information in our location verification example is the object that must report its location. The observers (e.g., sensors) receive signals from the source that may be noisy and/or manipulated by the source. For example, perhaps each observer communicates with the source and measures the round-trip latency; the source may deliberately delay before responding to communication requests and thereby manipulate the imputed distance.

The order of operations is as follows:

1. The source picks a strategy. The person or entity with private information gets to influence the information received by observers. It selects a way to “manipulate” the signals the observers will get, using only options that are allowed based on its private information (e.g., its true location) and other constraints (e.g., it can use message delays to increase the perceived distances but cannot decrease perceived distances via that same method).
2. Signals are created. Then, signals (e.g., perceived distances between observers and the source) are generated (possibly probabilistically) using the method the source picked.
3. Each observer sees only their own signal. Observers get to see only their own signal — they don’t know what the others saw.
4. Each participant self-reports their information. After seeing their signals, the source and the observers participate in an elicitation/verification mechanism in which the source and the observers report whatever they like — including things that aren’t necessarily true.

The goal is then to design a mechanism in which the source and observers are incentivized to truthfully report their private information and signals, respectively.

Two fundamental challenges revealed 

Our paper establishes that there are two challenges inherent in accurately eliciting information in signal networks. We show that these challenges are fundamental to the problem, rather than simply being an artifact of our currently nascent understanding of the application domain.

1. Manipulation 

The first challenge concerns the manipulation of measurements of the provided service, and the fact that any one or even all of the observers may not be able to detect those manipulations. That is, a source may lie to the observers — and it may be hard to tell when it does so. To incentivize accurate measurements, network participants’ utility (i.e., how they are rewarded) should be tied to visible behavior in the protocol’s mechanism (e.g., whether observers’ reports are logically consistent with one another). For example, a network participant (source or observer) could be rewarded in a project’s native token for providing information requested by the protocol that appears consistent with the information provided by the other participants.

Our first formal theorem proves that the problem of incentivizing accurate information from the source and observers is unsolvable unless the setting satisfies a condition that we term “source identifiability.” This condition requires that the source’s information cannot be completely and always (in a statistical sense) manipulated to seem exactly the same to all observers under two different true source signals; we’ll say more on this below. We show that when such ambiguity is present, there’s nothing a protocol designer can do to guarantee truthful elicitation: The source can always exploit the ambiguity to undetectably misrepresent its information. This impossibility result holds even when the protocol has native tokens or other incentives at its disposal.

2. Self-dealing

In incentive design, sometimes the cure is worse than the disease. In the context of decentralized service provision, a particular worry is that a source may additionally masquerade as one or more observers  (so-called sybils) and pretend to request or verify service from themselves, or team up (i.e., collude) with other network participants to do so. In the language of our model, the source might collude with some observer(s) (or itself, under a sybil identity) with the intention of exploiting the mechanism for its rewards.

Our second theorem establishes that when such collusion is present, truthful elicitation of the source’s information is essentially impossible (unless a condition much stronger than source identifiability holds, in which potentially colluding agents are ignored).

The good news

Our results show that source non-identifiability and self-dealing are fundamental obstacles to verification in DePIN applications. The good news is that we show a sense in which these are the only two obstacles: We give a formal mechanism that, under the assumptions of source identifiability and no self-dealing, achieves full information revelation at the equilibrium.

How DePIN protocol designers can move forward

Our results suggest two key lessons for DePIN protocol designers. The first is to take steps to ensure that source identifiability is possible. This is not as abstract as it sounds — for example, in location verification, source identifiability is equivalent to the geometric condition that the source’s location lies in the convex hull of observers’ locations. So if you want to ensure that you can truthfully elicit a source’s location, be sure to “surround” its possible locations appropriately with observers.

The second lesson is that DePIN protocol designers need to address self-dealing concerns outside of the protocol. Ways to do this include, for example, restrictions to permissionless entry (thereby justifying stronger trust assumptions) or randomizing between many different sources who might perform a service for the client (thereby assigning a non-zero cost to pretending to request service).

***

We hope that our work helps DePIN designers think crisply about their verification problems and the different options for addressing them. DePIN protocols are already exploring these and related ideas, and we’re excited to see how it plays out.

***

For deeper technical analysis and discussion of our model of and results on signal networks, please see our paper, “Incentive-Compatible Recovery from Manipulated Signals, with Applications to Decentralized Physical Infrastructure.”

***

Jason Milionis is a Ph.D. student in the Computer Science Department at Columbia University, where he is advised by Christos Papadimitriou and Tim Roughgarden. He is broadly interested in Game Theory, especially in conjunction with Machine Learning, and DeFi. He has also been an intern at the a16z crypto research lab.

Jens Ernstberger works at the intersection of cryptography and computer security. Most recently, he was a research intern at a16z crypto. Previously, he was a PhD student at Technical Univeristy of Munich, under the supervision of Prof. Sebastian Steinhorst and Dr. Arthur Gervais.

Joseph Bonneau is a Technical Advisor on the a16z crypto team and an Associate Professor in the Computer Science Department at the Courant Institute, New York University.

Scott Duke Kominers is the Sarofim-Rock Professor of Business Administration at Harvard Business School, a Faculty Affiliate of the Harvard Department of Economics, and a Research Partner at a16z crypto. He also advises a number of companies on web3 strategy, as well as marketplace and incentive design; for further disclosures, see his website. He’s also the coauthor of The Everything Token: How NFTs and Web3 Will Transform the Way We Buy, Sell, and Create.

Tim Roughgarden is a Professor of Computer Science and a member of the Data Science Institute at Columbia University, and Head of Research at a16z crypto.

The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.

This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.

The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.