owned this note
owned this note
Published
Linked with GitHub
# An Excess-Based Economic Model for Resource Allocation in Peer-to-Peer Networks
###### tags: `Tag(HashCloak - Validator Privacy)`
Authors: Christian Grothof
Paper(s):
1. https://pdfs.semanticscholar.org/46a3/a71ea37d7024c8309dbb1412c84ffbc7a942.pdf
### Table of Contents
[toc]
:::info
>Abstract: This paper describes economic aspects of GNUnet, a peer-topeer framework for anonymous distributed file-sharing. GNUnet is decentralized; all nodes are equal peers.
:::
### 1. An Excess-Based Economic Model for Resource Allocation in Peer-to-Peer Networks
> Christian Grothof, Department of Computer Sciences, Purdue University
#### Introduction
> Resource allocation in collaborative peer-to-peer networks with untrusted hosts is a significant problem, since it is difficult to establish which nodes are worth spending resources on.
The main requirement for the GNUnet economic system is to prevent abuse of the network. This economic system is supposed to detect nodes that use the network without contribution and limit their impact by giving preferential treatment to nodes that do contribute.
A node keeps track of transactions performed with other nodes in the past and learns which nodes behave well. Nodes that consistently contribute to the network earn the trust of their peers.
If a node runs into a resource shortage it uses its trust records to determine which requests to serve, and which to ignore. The economic model presented in this paper is excess-based in the sense that it allocates resources in times of resource-shortage based upon prior behavior of peers, including times where resources were available in excess. These times where resources are available in excess are used to induce the economy with trust.
Digital cash schemes leak information about a transaction to third parties that are otherwise not involved in the protocol, reducing the anonymity of the participants
In GNUnet it must be possible for peers to join or leave the network at any time. Furthermore, new nodes cannot be required to perform any kind of key exchange, authentication, or registration with a central authority; this would introduce a central point of failure. Joining GNUnet only requires the establishment of a link-to-link encrypted connection with an arbitrary node on the network. No node is critical for the operation of the network. For the economic model, nodes can only trust their own records. Note that every host can create a new identity, the secret key that identifies a peer, at any time. It is assumed to be impossible for a host to forge the identity of another node.
One of the main goals of gnunet’s economic model is to make it impossible for adversaries to use the multiplier effect to attack the network. Note that a solution to this problem should still allow the use of protocol elements that require a node to multiply traffic, e.g. forwarding a request to multiple peers in a distributed search.
#### Related Work
> Anonymity has always been a key issue in the research on digital cash since the beginning. The problem with all existing digital cash systems is that they require the existence of a bank, which is a trusted authority that has a secret key which is used to create cash.
**Mojo Nation**
A distributed file sharing system in which hosts must provide bandwidth and drive space to earn Mojo. Mojo can then be used to request services from other hosts.
Mojo Nation relies on a central authority to govern the use of Mojo. Mojo Nation also does not provide anonymity for its users.
**NICE**
A peer-to-peer framework in which peers exchange certificates for resources. In contrast to Mojo Nation, NICE fully decentralizes all economic components of the system. Peers can issue their own resource certificates in a distributed fashion.
Malicious peers are detected if they fail to honor the resource certificates that they issue. NICE attempts to solve the problem of detecting malicious peers that constantly use fresh identities by giving new identities a low exchange rate for their currency.
**Free Haven**
A censorship-resistant storage that uses a “buddy system” to detect if servers fail to keep their promise to store a certain document. While the buddy system can fail if nodes conspire, this system charges for storage, whereas GNUnet charges for requests.
> In our opinion, it is much better to reward hosts that make content available than to penalize them.
**Hash Cash**
A host that wants to initiate a transaction (e.g. send E mail) must perform an expensive computation for the receiver in order to have the request processed. The original goal of Hash Cash was to fight spam. The approach has problems with transitivity and applications which create legitimate large amounts of traffic (e.g. mailing-lists).
#### Trust Economy
> GNUnet does not use money. While some of the properties of money would be desirable for GNUnet, most are not required to meet the goal of allocating resources for entities that have contributed to the network and limiting the impact of attackers.
**Trust**
* GNUnet’s economy uses trust instead of money for its currency.
* The first thing to notice with this setup is that no node owns trust. The amount of trust a node has earned is stored at the other nodes.
* Trust is not symmetric and nodes that have never communicated have no opinion about one another.
* Gambling can still be a reasonable strategy if the available information based on trust is insufficient to make a decision.
**Building Trust**
> In gnunet, each node evaluates the behavior of the other nodes that it communicates with and forms its own opinion.
Nodes form their opinions about other nodes based upon n the two basic protocol primitives that exist in gnunet: requests, and replies.
* A request is considered network usage, and nodes that send large numbers of requests will lose trust.
* A reply is considered to be a contribution to the network. Nodes that send replies earn trust.
1. Each request in gnunet comes with a priority.
2. This priority defines the amount of trust that the sender node S is willing to risk for this request.
3. The receiver R of the request can reduce the amount of trust that R has in S by that amount.
4. If the receiver can answer the request, the sender S of the request will increase its trust in the receiver R by the priority of the request.
**Example**
* Suppose S sends a request with priority 10 to R and receives an answer from R.
* In this case, S will increase the trust that it has in R by 10.
* If R is idle, it may decide not to charge S for the request, which will then increase the overall amount of trust available in the system. If R is busy, it will decide to charge S.
* If R has a trust value of t in node S, it will give the request the effective priority min(10, t) and charge S that amount. If R is very busy and can only answer a subset of the requests, it will drop the requests with the lowest effective priorities.
> Note that R can charge a processing fee to S even if R does not send an answer.
> Furthermore, R never tells S how much it actually charged for a request. This ensures that S will always be well-behaved, even if R does not trust S at all, since S cannot tell that it would have nothing to lose by behaving ”badly”.
> Personal Note: Could R then attack the network by charging too much? Could an attacker attack a network/node by changing the value that (a) node(s) charge as their processing fee?
New nodes that join the network start as untrusted. The reason for this is that the creation of a new identity only requires the creation of a new public key pair.
> If a host S sends a request with a priority that is higher than the amount of trust t that the receiver R has in S, the priority is automatically bounded by t. This ensures that no host ever has anything to gain by creating a new identity.
**Resource Allocation and Excess**
> Remember that the main motivation for the introduction of an economic model is resource allocation.
This scheme has the desirable property that nodes that
contributed to the network will receive better service than nodes that did not contribute. Furthermore, client applications will try to keep priorities as low as possible in order to avoid being charged unnecessarily. This makes it possible for gnunet to allocate resources to the important requests.
Most of the time, computers and networks have excess resources, meaning that their capacity is not fully used. As long as the network has excess resources, freeloading is
harmless.
GNUnet nodes detect the current load at the local node and stop charging for service if the load is under a certain threshold. At this point, requests to that node will be answered without the node reducing the trust it has in the sender. However, the economic model is not entirely disabled. If a node receives replies, it still credits the sender for the reply. In this manner, this process infuses the network with trust.
> It is essential in order for the economic model to work that it be possible to increase the trust of well-behaved nodes without decreasing the trust of other nodes by the same amount (i.e., no zero-sum in the trust economy). Otherwise, no node would ever trust any other node because no one has trust to start with.
#### Knowledge
> In any peer-topeer system, a node can never be guaranteed that a service that it has provided in the past will pay off in the future.
The only important decision that B makes that depends upon its trust in A is whether it should drop a request from A or a request from C if B is so busy that it can only answer one of them. Remember that the priority that a request from A is granted is limited by the amount of trust that B has in A (the effective priority for discarding requests is the minimum of the requested priority and the trust that the receiver has in the sender).
Suppose A is a good host and has answered thousands of B’s requests in the past, and B decides to purge its trust in A. Then, a new node1 M starts to flood B with requests. B does its best to answer the requests from M, but can’t really answer all of them. At this point, A decides to send an important request to B. B has no proper records of A’s past, thus B cannot decide if it should keep answering requests from M or if it should answer A’s request. B might drop A’s request, missing a great opportunity to increase its own standing with A. When B later asks A about something, A may now have decided that B is a malicious node and prefer answering requests from C.
This is similar to human relationships in which knowing who is trustworthy is beneficial for both sides. The major difference is that it is much harder for humans to obtain a new identity and thus “negative” trust is also useful in human relationships.
**Transitivity**
> A fundamental requirement for an economic model is transitivity
The problem with transitivity is the requirement that a group of collaborating malicious hosts not be able to trick a set of intermediaries into providing resources for free.
This problem can be solved by having B charge for its service such that the sum of the priorities of the forwarded requests is less than (and not equal to) the priority of the request that was received. In this way, the trust that B has in A, C and D would degrade over time given the scenario above.
**Under Attack!**
> One of the goals for doing resource allocation with the presented economic model is to fend of attacks by malicious hosts.
Malicious peers can flood the network with requests, or make excessive use of the network without contributing in return. If the economic model denies resources to peers that abuse the network, it can limit the impact of these types of attacks.
#### Discussion
> The economic model described so far is not able to solve all the resource allocation problems in gnunet. In this section, potential problems are discussed and some open issues with the current model are described.
**Implications for Anonymity**
> The trust scheme has only minimal implications for anonymity.
Since the knowledge required by the scheme is purely local, the only trust-related information that is added to the peer-to-peer protocol is the amount of trust the sender node is offering for an answer.
There are two cases in which an adversary can use that
number to break anonymity:
1. Involving a node that offers an extraordinary amount of trust, the adversary might be able to tell that the node is the originator of a request since it may be unlikely that the node trusts anybody else enough to indirect a request with a priority this high.
2. If a node uses the importance of the requests to decide whether to process it at all, but does not apply this test to its own requests, the requests originating from the node may have a distinctively low priority compared to indirected requests.
**The Zero Priority Problem**
> The most significant indicator for valuable content is a matching request with a high priority (from a host that had an adequate trust-level). The problem here is that if a node is idle, it will not charge for requests.
In order not to be charged for the indirection itself, it will reduce the priority to zero when forwarding (the node cannot tell if the node that it forwards the request to is also idle).
The receiver of this zero-priority request now has two problems.
1. First, the receiver node cannot earn any trust when answering that request.
2. It is generally desirable to have nodes directly connected to many other nodes.
**Content migration with zero-priority requests** is another problem. Because the priority of the request serves as an indicator for the value of the content, only nodes that have excess space will copy zero-priority content that floats by. All other nodes will decide that the content that they are storing has a higher priority and will merely forward the reply without replicating the content. A critical problem preventing a solution is an attack by a malicious node using zero-priority requests for useless data with the goal to make the network store the useless and discard valuable data.
A trivial solution to the zero-priority problem would be to charge a little bit for forwarding even when idle. The problem with this solution is that it then becomes harder for the system to infuse the network with trust.
**Reply Verification**
> Forwarding requests and replies for other anonymous participants poses another problem.
If B can not learn anything about the contents transmitted, B can not effectively be forced to monitor or censor the data flow. However, the economic model requires B to ensure that the reply from C is a valid answer to the request. Otherwise, C would be able to profit by replying to a request with extraneous data in order to earn credit. If B cannot verify the validity of the reply, C could answer all requests with invalid data and earn credibility while disrupting the system.
>In [BGHP02], a scheme in which an intermediary is able to verify that a reply matches a request without being able to decrypt the reply is described. The scheme requires the responder to either have the content or to invert a oneway-function in order to be able to prove that the responder actually knows the answer to the request. This makes it impossible for a malicious node to send back invalid data as an answer to arbitrary requests.
**Beyond Request-Reply**
> The current model is geared toward the simple request reply service that is used for the file-sharing application of GNUnet.
For other applications, like E-mail, other types of messages will be required. Some of these applications may have different requirements for the economic model (e.g. the sender of the E-mail should probably be charged, and not the receiver).
#### Future Work
> User feedback is the only reliable way to determine with any degree of certainty that content is actually valuable.
Currently, it would be possible to share the Patriot Act under the keyword US Constitution, and only the end-user can tell that this is not the content that was desired. This feedback is hard to implement in an anonymous network, particularly because malicious users could lie.
Another possibility for user feedback is to have users sign content that they insert into the network using pseudonyms and to use rankings for these pseudonyms to evaluate content rather than node-rankings. The primary problem with pseudonyms is that they may open the network to intersection attacks against anonymity (which nodes were on-line when content under this pseudonym was made available).
#### Conclusion
> We have presented an accounting system that allows accountability without a central server in an anonymous peer-to-peer network based on trust.