[mnet-devel] Grid Of Trust -- pre-design
Zooko O'Whielacronx
zooko at zooko.com
Tue Nov 25 06:37:31 PST 2003
Some Guy wrote:
>
> Hey guys who ever wants to take first peek at my baby DHT/premix idea please
take a peek and
> crtitique it. It's a bit rough around the edges and there's plenty of room
for modification, but
> I'm pretty sure the ideas are sound.
>
> http://de.geocities.com/amichrisde/Grid_Of_Trust.html
>
> The basic idea is to force data and nodes to be randomly distributed in a
grid. This provides
> resistance against serveral types of attacks.
>
> Feel free to comment on or off list.
Here is the text of that web page, for the sake of future generations who are
required to read the mnet-devel archives as part of their education:
Grid Of Trust
This isn't a design document. It's more of a proposal for what could be
to make sure all the attacks are really covered.
Topology
Nodes are distributed randomly into cells of a hypercube with d
dimensionals. Each axis is broken down into g pieces such that the
hypercube contains gd cells.
Nodes in a cell can connect to all nodes in cells whose coordinates vary
in at most one dimension. This is different than CAN where only dirrect
neighbors have links. A DHT based on this type of a network should only
require d hops to handle a request. The cost is of coarse a higher
neihbor count.
We will define x as the expected population or a cell and N as the total
number of nodes.
x = N/(gd)
We will define m as the expected neighbor count.
m = x(d*(g-1)+1)
So let us visualize a small network with g=8 and d=2 which looks like a
chess board. Let N=256 so x=4. Messages can move like rooks on this
chess board, so requests can be handled in 2 hops. So we can caculate the
neihbor count as:
m = 4*(15) = 60
--todo add pretty picture
Now let us consider a larger network g=10 d=6 and x=4, so N=4,000,000.
Messages should be routable in 6 hops and for the niehbor count we get:
m = 4*(6*9+1) = 220
This still would be acceptable for freenet like applications.
When x and g are held constant m is O(log(N)) just like CAN.
For large N the probability a cell is vacant is e-x. So at x=4 this
chance is about 1.83%. This should be acceptable if some redundancy is
used. Not that when a message has serveral dimensions to move along, the
chance that there is no dirrect way becomes very low.
Node Placement
Nodes must be placed randomly into the network to prevent, serveral types
of attacks which involve an adversary selecting the locations of the grid
he would like to control. In order to do this a node is forced to pay for
it's identity with a large hash cash calculation. The hash cash then
determines the node's location in the grid.
One space optimization, is to store all the identification in the public
key. The first time user picks an N=pq. He then tries to make an e such
that it's first 32 bits contain the julian date, it is relatively prime to
(p-1)(q-1), and SHA-1(<e,N>) has the first h bits zero. We can then set h
to be so high it takes a 1CPU-day to calculate the key.
We then use some globaly defined salt per dimension Si, which we encript
with the <e,N> to give us the identities location L in the grid.
Li = (Si emod N) mod g
Boot Strapping
Boot strapping is pretty straight forward. A new node must have contact
with one node in the system. It uses this node to route a message to the
target cell, a node there sends its IP:Port encripted with the public key
of the identity back. The node the decrypts this to get the IP out. It
never has dirrect contact to any of the other nodes along the routing
path. Once the new node connects to the node in its home cell, it can get
all the other IPs and keys from it.
It could be the case that the cell is vacant, or that one doesn't want to
trust the single node from the home cell. It is easy for such a boot
strap message to be routed to find a node from a cell connected to the
target cell. The same protocol can be used. So one might have to repeat
the process d times to get nodes from all the dimensions.
Note that this type of bootstrapping will probably only have to happen
once for a node. Once a strip of g*x nodes all know each other, some of
them can leave and join with out having to worry too much about not being
able to find anyone when they come back.
DHT Functionality
Similar to the way in which a node must be kept from deciding what cell it
wants to serve in, we must ensure that the cells to which keys for
requests and inserts are mapped can not be selected by an advesary. Based
on the application key of which there may be many types a routing key is
calculated based on a small hash cash proportional to the some
requirements of the key like:
* size of the data
* priority of messages
* possiblity and maximum rate of rewrite
* expiration rate of the data
* expiration date of the key
The hash cash which is calculated will then be given back to the
application to use for the a pointer. The actual routing key is the hash
of the hash cash and other key data that went into the hash cash
calculation. This ensures that a hard hash cash calculation must be done
before determining what node(s) will be responsible for handling the key.
For example you want to make a pretty picture freesite. For your picture
you know it's not going to change or at least nobody is going to link
dirrectly to the picture, so you calculate a cheap on time hash cash for
it, which is included in your HTML. For your HTML you decide you want to
be able to change it once a day so you buy a more expensive hash cash for
it. This is given to others who want to see or link to your site.
Requests with substandard hash cash don't have to be dropped they can just
be treated with lower priority.
File sharing data should ooz slowly through a network, while browsing
requests should skip over them.
Premix Routing
Tarzan provides a very good model for premix routing. One problem is that
they rely on IP subnets as a resource to limit adversaries and they
require all nodes to contact all other nodes periodically in order to
verify identities. The Grid solves this problem.
Since an advesary can only create a certain amount of valid identities and
those identities are spread around evenly, there is no way for an
advesarial node to present a large list of faulty neighbors. If the
advesary provides the tunnel user with a very small list this would be
obvious too.
If that weren't enough, we could demand certificates from multiple nodes
in a cell to verify neighbor lists.
It should also be noted that the DHT traffic can provide perfect cover
traffic.
Resource Accounting
Since the relationships between nodes are long term and identity isn't
free, barder is a great economic model. Over the long term two neihbor
nodes can add up how much work they did for each other, and do some simple
statistics to see if anyone is being a "leach". No centralized authority
is required.
Premix bandwidth is always charged back the dirrection the tunnel
originates from.
Topology Aware Routing
Since routing can go in multiple dimensions and mutliple nodes inhabit the
same cells, there is great flexibility in which way messages can be
routed. Messages can be forwarded along the path with the lowest latency
and to nodes with low load. This is similare to how you navigate American
streets with a car avoiding the streets and avenues with too much traffic.
Attack Models
Cancer Node Censorship Attack
In this model an adversary runs a few nodes where particular requests are
likely to be handled in order to drop or mishandle them.
The Grid prevents this by randomly distributing expensive identities
throughout. In that large 4,000,000 node network only 1 in a million
identities would be in the target cell. If each identity cost 1 CPU-day,
an adversary would have to buy lots of hardware and work really long.
Spy and Flood
There is a slightly better chance of getting a node to wind up connected
to the target cell: 54/1,000,000. From here the advesary could lauch
classic SYN floods or try to hack nodes in the target cell, since he would
know thier IPs.
This still is a prohibitive amount of work. A little bit of redundacy
will also dramatically increase resistance further.
DHT Flood
In this attack model the advesary tries to generate messages, which all
must be handeled by nodes in the target area. The hash cash should
prevent this from happening for most types of keys. Since you have to pay
first and then you know the route. Messages for things with more
expensive hash cash could be processed first, to avoid shortcoming of
cheaper key types.
boconstrictor attack --naa
Other Wacky Ideas
Clusters
Big Clusters
Using levels to deal with heterogenity
Baby Mode - Slower bootstrap
setstats 1
-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
Does SourceForge.net help you be more productive? Does it
help you create better code? SHARE THE LOVE, and help us help
YOU! Click Here: http://sourceforge.net/donate/
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel
----- End forwarded message -----
-- Eugen* Leitl <a href="http://leitl.org">leitl</a>
______________________________________________________________
ICBM: 48.07078, 11.61144 http://www.leitl.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE
http://moleculardevices.org http://nanomachines.net
[demime 0.97c removed an attachment of type application/pgp-signature]
More information about the cypherpunks-legacy
mailing list