BeRGeR
ByzantinE Resistant GEometric Routing
WiP: Work in Progress
Table of Contents
- 1. Overview
- 2. Mathematical Formalism
- 3. Assumptions
- 3.1. polyhedral (3-connected & planar)
- 3.2. The Triconnectivity Assumption
- 3.3. infinite bandwidth
- 3.4. nodes know their position
- 3.5. nodes know their neighbors’ positions (even if Byzantine)
- 3.6. source node knows target node’s position
- 3.7. no nodes lie on the source-target line, WLoG
- 3.8. one faulty node (cannot be
or ) - 3.9. we use a source-target line segment
- 4. Potential Additional Assumptions
- 5. Facts
- 5.1. Our nodes are not embedded in Euclidean space
- 5.2. Polyhedral graphs can be represented as a polyhedron
- 5.3. Polyhedral graphs have a unique dual graph that is also polyhedral
- 5.4. Polyhedral faces share <3 nodes in common
- 5.5. PROVE once we venture further than a blue face, we are lost
- 5.6. PROVE counting non-green nodes is not useful
- 6. Definitions
- 6.1. green face: a face that intersects the source-target line segment
- 6.2. green node: a node that lies on the green face
- 6.3. blue face: a face adjacent to a green face
- 6.4. junction: a node that has a neighbor across the source-target line
- 6.5. interchange: an edge that crosses the
line - 6.6. highway: all green nodes between two consecutive junctions
- 6.7. mitigate (a node): achieve safety and liveness even if the node is Byzantine
- 6.8. recoverable: the algorithm generalizes optimally to non-3-connected graphs
- 7. Cores
- 8. Braiding
- 9. QUESTION How can we improve the message complexity of braiding?
- 10. 2 Cores, 4 snakes, and 4 dogs
- 11. Modulo Braiding
- 12. TODO
[0/5]
- 12.1. TODO prove algorithm terminates in case of a Byzantine node
- 12.2. TODO (briefly) check if algorithm works for 2 faults on 5-connected graphs
- 12.3. TODO see if it can be used to geocast
- 12.4. TODO understand the abstract implementation code in Stateless Reliable Geocasting
- 12.5. TODO consider other possible attacks
- 13. Other ideas
- 14. Citations
Anything marked with a 1 is awaiting verification by Prof. Nesterenko or Prof. Sharma.
1. Overview
We have a network (graph),
The simplest solution without a Byzantine node would be to greedy route; at each step going to the node geometrically closest to
The state of the art1 in geographic routing is GOAFR+ (Kuhn et al. 2003) where they route packets within an ellipse, increasing the size of the ellipse if progress is not made. They demonstrate practical efficiency and prove their algorithm is asymptotically optimal in the worst-case:
Finally, (Friedman et al. 2007) proves a correspondence between interactive consensus conditions (ICCs) and error-correcting codes (ECCs). But I believe the ICCs apply to broadcast networks1 (complete graphs), so are not directly applicable here.
2. Mathematical Formalism
See also: 8.1
Formally, each node, except for 1, uses the same routing algorithm,
Alternatively, you can imagine that there is a copy of
Which is a directed graph, modified to be sensitive to the proximal source of the message. More formally, a directed graph,
It is critical that this graph is acyclic, otherwise our algorithm will not terminate.
Our solution only uses very weak assumptions. E.g. We only use the message for the
3. Assumptions
3.1. polyhedral (3-connected & planar)
3.2. The Triconnectivity Assumption
3.3. infinite bandwidth
3.4. nodes know their position
3.5. nodes know their neighbors’ positions (even if Byzantine)
3.6. source node knows target node’s position
3.7. no nodes lie on the source-target line, WLoG
3.8. one faulty node (cannot be or )
3.9. we use a source-target line segment
4. Potential Additional Assumptions
Below are some additional assumptions that we could make if they lead to a nice solution.
4.1. the line does not intersect an external face
4.2. alternatively: nodes can tell if they lie on the external fice 1
4.3. message size is logarithmic in the number of nodes 1
4.4. we have a unit-disk graph
5. Facts
5.1. Our nodes are not embedded in Euclidean space
5.2. Polyhedral graphs can be represented as a polyhedron
5.4. Polyhedral faces share <3 nodes in common
5.5. PROVE once we venture further than a blue face, we are lost
5.6. PROVE counting non-green nodes is not useful
6. Definitions
6.1. green face: a face that intersects the source-target line segment
6.2. green node: a node that lies on the green face
6.3. blue face: a face adjacent to a green face
6.4. junction: a node that has a neighbor across the source-target line
6.5. interchange: an edge that crosses the line
6.6. highway: all green nodes between two consecutive junctions
6.7. mitigate (a node): achieve safety and liveness even if the node is Byzantine
6.8. recoverable: the algorithm generalizes optimally to non-3-connected graphs
7. Cores
We form 2 disjoint paths from the faces that intersect the
We call
Assuming only 1 Byzantine node, if the target receives matching green packets from both of target’s green neighbors, we know that these messages took disjoint paths and so must be correct. So from now on we can consider the case where only green nodes are Byzantine.
7.1. PROVE this works by induction
7.2. PROVE that we can avoid non-green nodes sending green messages
8. Braiding
Now, we need to modify one side of the source-target line such that either:
- No more than 1 vertex to the target carries an incorrect message, or
- One correct message arrives. Because if target sees equivocation on one side of the source-target line, it knows the other side is correct.
The idea is that we will braid around green nodes, so in addition to sending a message A → B → C → D, we will also send A → C and B → D:
%%{init: {'theme':'neutral'}}%% graph LR A((A))-..->C((C)) A((A))-->B((B)) B((B))-->C((C)) C((C))-->D((D)) B((B))-..->D((D))
Braiding is implemented by the core not only sending a packet to the next green node, but also sending a packet to bypass that node. It does this by adding the next green node to a “bypass” field in the message and then routing it around the blue face (see 13.4). This message is routed the same as a core, except that, in addition to nodes across the
This is quadratic w.r.t core length. It is not exponential because a node does not create new braids for messages that contain a bypass field, and the bypass field is never removed. This does not cause issues because if
was Byzantine, in which case we can assume that no further nodes are Byzantine and core routing the rest of the way will succeed, or was not Byzantine, in which case provides no useful information.
8.1. Pseudocode
8.2. PROVE braiding terminates
8.3. PROVE braiding terminates in the presence of Byzantine nodes
9. QUESTION How can we improve the message complexity of braiding?
Ideally we would like to send 2 braids: one which skips odd green nodes, and another which skips even green nodes. It does not seem that this is possible, at best I believe we need a number of braids proportional to the maximum number of nodes on a green face. But I strongly suspect a solution better than quadratic.
9.1. DRAFT NOTES: How can braiding mitigate consecutive junction nodes
10. 2 Cores, 4 snakes, and 4 dogs
We partition the graph into cores/non-cores. Then we form 2 orthogonal partitions within cores, left/right and junctions/highways.
- Cores: the set of all nodes on a face intersecting the
line- Left/Right
- Left (North): CW core
- Right (South): CCW core
- Junctions/Highways
- Junction: A node that has a neighbor across the
line, excluding junctions whose only highways connect to earlier junction nodes. The order is determined by the interchange that intersects the line closest to - Highway: A set of green nodes between two consecutive junction nodes. May be empty.
- Junction: A node that has a neighbor across the
- Left/Right
So we have partitioned the graph into:
We have developed simple algorithms that will visit partitions in a particular pattern as shown in the table below.
- Left/right cores stick to their respective side.
- 0-snakes (not included in the table) work like cores, except they cross and change chirality at each junction node. After crossing, they exclude all junction nodes that neighbor the vertices of the interchange they just crossed. This has the effect of simplifying the graph such that each junction has exactly one interchange.
- 1-snakes work the same, except they cross every other junction. The even snake
will cross at even interchanges. - TODO: explain algorithm for dogs
left nodes of L | HL0 | JL1 | HL1 | JL2 | HR2 | JR3 | HR3 | JL4 | HL4 | JL5 | HL5 | JL6 | ⋯ | ||
right nodes L | ⋯ | ||||||||||||||
left nodes R | ⋯ | ||||||||||||||
right nodes of R | HL0 | JL1 | HL1 | JL2 | HR2 | JR3 | HR3 | JL4 | HL4 | JL5 | HL5 | JL6 | ⋯ | ||
left nodes of S0L | HL0 | JL1 | HL1 | JL2 | JL4 | HL4 | JL5 | HL5 | JL6 | ⋯ | |||||
right nodes of S0L | JR2 | HR2 | JR3 | HR3 | JR4 | JR6 | ⋯ | ||||||||
left nodes of S0R | JL2 | HL2 | JL3 | HL3 | JL4 | JL6 | ⋯ | ||||||||
right nodes of S0R | HR0 | JR1 | HR1 | JR2 | JR4 | HR4 | JR5 | HR5 | JR6 | ⋯ | |||||
left nodes of S1L | HL0 | JL1 | JL3 | HL3 | JL4 | HL4 | JL5 | ⋯ | |||||||
right nodes of S1L | JR1 | HR1 | JR2 | HR2 | JR3 | JR5 | HR5 | JR6 | ⋯ | ||||||
left nodes of S1R | JL1 | HL1 | JL2 | HL2 | JL3 | JL5 | HL5 | JL6 | ⋯ | ||||||
right nodes of S1R | HR0 | JR1 | JR3 | HR3 | JR4 | HR4 | JR5 | ⋯ | |||||||
left nodes of D0L | HL0 | JL1 | JL2 | HL2 | JL3 | JL4 | HL4 | JL5 | JL6 | ⋯ | |||||
right nodes of D0L | HR0 | HR1 | JR2 | HR2 | HR3 | JR4 | HR4 | HR5 | JR6 | ⋯ | |||||
left nodes of D0R | HL0 | HL1 | JL2 | HL2 | HL3 | JL4 | HL4 | HL5 | JL6 | ⋯ | |||||
right nodes of D0R | HR0 | JR1 | JR2 | HR2 | JR3 | JR4 | HR4 | JR5 | JR6 | ⋯ | |||||
left nodes of D1L | JL1 | HR1 | JL2 | JL3 | HL3 | JL4 | JL5 | HL5 | JL6 | ⋯ | |||||
right nodes of D1L | HR0 | JR1 | HR1 | HR2 | JR3 | HR3 | HR4 | JL5 | HR5 | ⋯ | |||||
left nodes of D1R | HL0 | JL1 | HR1 | HL2 | JL3 | HL3 | HL4 | JL5 | HL5 | ⋯ | |||||
right nodes of D1R | JR1 | HR1 | JR2 | JR3 | HR3 | JR4 | JL5 | HR5 | JR6 | ⋯ |
The even left dog,
We are exploring a new type of path that partitions the network into forward/rear parts.
11. Modulo Braiding
An alternative way of braiding is to assume all nodes have an arbitrary ID. This could be their GPS coordinates, a hash of their GPS coordinates, or anything else.
Now we send out 5 braids:
More generally, we can send out n braids:
This guarantees that for all
%%{init: {'theme':'neutral'}}%% graph LR s((s))---A((A)) s---E((E)) subgraph 1[" "] A---B((B)) B---C((C)) C---D((D)) end subgraph 2[" "] E---F((F)) F---G((G)) G---H((H)) end A---E B---F C---G D---t((t)) H---t D---H style 1 opacity:0 style 2 opacity:0
We can touch only one core, so that leaves us with a 2-connected network, which I believe in the worst case looks like the above: The packet has only two options to progress forward: Either go directly forward, or go sideways and then forward. So at each step, the probability of being blocked at that step is:
And the probability of not being blocked after
which means if we hold
If this is correct, the number of braids required using this naïve approach is sublinear in distance, meaning the congestion is subquadratic compared to the core.
Unfortunately, this relies on the assumption that the other green path is on the other side of the