View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0001516 | GNUnet | other | public | 2009-11-25 16:37 | 2010-02-15 14:37 |
| Reporter | Corvus | Assigned To | Christian Grothoff | ||
| Priority | normal | Severity | feature | Reproducibility | N/A |
| Status | closed | Resolution | fixed | ||
| Summary | 0001516: Proposal for alternative trust model | ||||
| Description | The current trust model as written in http://gnunet.org/download/ebe.pdf doesn't seem to be working very well in practice, as very little trust is accumulated in the network. I lack the resources to find out what exactly is the false assumption in the current trust model, but my guess is, it too much depends on the free availability of resources, that means a significant amount of nodes not fully utilized, and providing service "free of charge" therefore increasing the overall trust available. In practice this amount is far less than the overall trust loss in the network through requests that never get answered, thus charging nodes for network utilisation, but no reward, forcing the node to resend its request and destroying more trust. A working trust model should probably try to reach a trust equalibrium at around 90% resource utilisation, to not waste resources, but also ensuring each node has enough free capacity to allow operation without too high loss or latency. (whether the actual value needs to be 80% or 97% needs to be found out through tuning I guess, maybe a simulation can determine this) I propose the following: Each peer p of a node n has a base creditability C_0 depending only on the available bandwidth resources of node N and the amount of concurrent peer connections |{P}|. C_0 = k * (total_bandwidth) / |{P}| Each peer p of a node n has a trust value t increased by one with every correct answer to a request received from p by n. Trust is lost over time interval T, so t is altered by a function t := t / (k*T) after every interval T. k is a constant factor. The reason for that is that a well behaving node might change its behaviour over time and become malicious, so there is no need to assume well behaviour if it is not reaffirmed (Additionally t might be decreased if any indication of node misbehaviour is found for example through a heuristic or statistical approach) Every peer p of n has a credit c, initialised with zero. After each time interval T, p is awarded additional credit according to the following formula c := c + X * (( t * C_0 ) - c) where X is based on the bandwidth utilisation U = (used_bandwidth)/(available_bandwidth) Target utilisation U_0 = k (lets say 0.9) X = 0 if U=U_0 X < 0 if U>U_0 X > 0 if U<U_0 for example X:= k * (U_0 - U) / Ts where Ts is the sum of all trust of all currently conected peers. (Making sure a node wont allocate too much credit in case its connected to many very trustworthy peers) though c must not be allowed to go below zero! credit is discharged for bandwidth usage by peer p of node n c := c - (k * request_size * (1+request_priotity)) however if c< (k*request_size * (1+request_priority)) then if priority>1 then reduce priority accordingly and try again else do not reduce c and discard the request! If there are two requests to be processed and not enough resources (bandwidth, etc) available to process both, but both have enough credit c to be sent in theory, then decide according to the following rules: if one request has higher priority then the other, process the request with higher priority, and discard the other if both request have the same priority, process the request whose peer has the higher trust value t and discard the other. if both requests have the same trust value, decide on which peer has the higher current credit c and discard the lower. Additional restrictions could later be added to introduce different queues depending on request priority, to also process higher priority messages first, even in cases where no requests are discarded. This credit based model ensures fair resource utilisations by all peers while also providing a model for arbitrary request priorisation. The additional trust model on top of credit increases the resistance against malicious nodes, by giving trustworthy nodes more resources than others. A node trust of level T could therefore be 'simulated' by operating with T peer connections to a single node at the same time and gain access to the same amount of bandwidth resources. However considering that the amount of peer connections to any node is limited (usually to about 10 or twenty), while the peer trust should easily get much higher if a peer proves itself valuable to its partner repeatedly (since the trust does not get decreased with sent requests but only over time) this should not be a problem. | ||||
| Tags | No tags attached. | ||||
|
|
> if priority>1 then reduce priority accordingly and try again ... must read if priority>0 ... or if (priority+1)> 1 ... instead |
|
|
I think you are ignoring how the existing trust model and bandwidth allocation interact. When a node connects to N peers, each of the N peers already receives a certain, fixed, small basic level of bandwidth allocation (similar to your C0). This allocation is then adjusted over time based on how completely the peer utilizes this share (if a peer sends us much more than we allow, he is cut off; if he sticks closely to the allowed share, its allowed share increases if we have excess bandwidth). Trust only factors in on another level: if a peer earns our trust, he gets extra-special-plenty of bandwidth (if he is sending within his limits AND we would otherwise not be able to increase his bandwidth because it would have to happen at the expense of other peers). Also, trust plays a role outside of bandwidth allocation (if the CPU/disk IO is very busy, we might decide to not service low-priority requests; similarly, important requests from peers we trust can be allowed to be kept in memory longer). So my assumption is that your (terminology-wise confusing credit+trust) system is not all that different from what already happens if one takes the big picture of bandwidth allocation in GNUnet. Now, the part that I've explained above is not really documented anywhere. Finally, I am at this point pretty hesitant to change the code unless I am given some hard data on why the change is beneficial. The heuristic you describe above is a bit too arbitrary to be obviously beneficial. So if you (or someone else) wants this to change, I would recommend doing an implementation and then measuring to see if it actually performs better. |
|
|
I noticed the other day that gnunet-gtk was showing all trust values as "zero" for me, which should not have been the case. After some investigation, it turned out that the code that produced the trust values for the GUI was buggy. Now, if you use gnunet-peerinfo, you should get the actual trust values shown. So if your presumption that the economy did not work was based on not seeing anyone with trust in gnunet-gtk, that's display bug (which is now fixed in SVN HEAD). I thought I should mention this here... |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2009-11-25 16:37 | Corvus | New Issue | |
| 2009-11-25 16:46 | Corvus | Note Added: 0003923 | |
| 2009-12-05 21:34 | Christian Grothoff | Note Added: 0003932 | |
| 2009-12-05 21:35 | Christian Grothoff | Assigned To | => Christian Grothoff |
| 2009-12-05 21:35 | Christian Grothoff | Status | new => closed |
| 2009-12-05 21:35 | Christian Grothoff | Resolution | open => no change required |
| 2009-12-18 10:58 | Christian Grothoff | Status | closed => feedback |
| 2009-12-18 10:58 | Christian Grothoff | Resolution | no change required => reopened |
| 2009-12-18 11:00 | Christian Grothoff | Note Added: 0003956 | |
| 2009-12-18 11:00 | Christian Grothoff | Status | feedback => resolved |
| 2009-12-18 11:00 | Christian Grothoff | Resolution | reopened => fixed |
| 2010-02-15 14:37 | Christian Grothoff | Status | resolved => closed |
