Byzantine Resistant Networking Protocols feat. SMT

Secure and reliable data transmission is one of the cornerstones of building an open and decentralized peer-to-peer network protocol like Marlin. Our previous post on ODSBR summarized an interesting technique which used binary search to identify faulty links and proactively modify routes based on a feedback mechanism. 

In this post, we explore “Secure Data Transmission in Mobile Ad Hoc Networks” by Papadimitratos et al, a well cited paper that introduces erasure coding as a way to reliably propagate messages in the presence of malicious actors. Starting with a brief overview of SMT, we continue on to share its assumptions, transmission strategy and the guarantees it provides, concluding with it’s application to P2P networks.

SMT

Secure Message Transmission (SMT) is a protocol which aims to reliably propagate data on paths selected by a secure route discovery protocol in the presence of adversarial actors (yes, route discovery and data transmission are two different phases with a range of protocols  with different trade-offs for each). It provides bounds on the maximum bandwidth loss an intelligent adversary that avoids detection can inflict on the network while being secure against any malicious actor trying to read the data transmitted between the source and destination.

Assumptions

Secure Route Discovery

Secure communication involves securing the route discovery mechanism as well as message transmission. Security lapses in any of the two stages results in insecure communication;  a node acting honestly during the discovery phase may still maliciously drop packets during transmission phase.

SMT assumes that the route discovery mechanism is secure. The source is assumed to use a secure route discovery protocol to find diverse and node-disjoint sets of valid paths (paths with no common nodes) called an Active Path Set (APS) to communicate with the destination.

Security Setup

SMT also assumes that there is a secret known only to the communicating end points. The sender and the receiver should be able to perform cryptographic operations like symmetric encryption based on the shared secret.

Transmission strategy

The transmission strategy in SMT consists of 3 stages.

1. APS Selection
2. Message Dispersion and Transmission
3. APS Adaptation

APS Selection

SMT can operate with any secure route discovery mechanism be they reactive or proactive. It is however necessary for the source to know the actual connectivity of nodes as it uses source routing (here’s a mild discussion on the tradeoffs of having an open topology). The source can thus choose suitable paths based on the historical information of the reliability available with it to increase the success of its data transmission. For example, it can exclude certain nodes known to be misbehaving. Source routing also improves the robustness of the network because it reduces the impact intermediate nodes (which can be malicious) may have in designing and choosing paths.

Note:

In proactive route discovery mechanisms, routes are pre discovered and maintained by the nodes at frequent intervals. This makes the route discovery faster but requires comparatively more time to adapt to network changes as routes are updated only in specific intervals.

In reactive route discovery mechanisms, routes are discovered on demand i.e. when a request for a route is made, the route discovery protocol initiates. Reactive route discovery is efficient when the network changes rapidly but the route discovery process is slower compared to proactive routes.

Table: Comparison of route discovery protocols

In SMT, the source invokes the route discovery protocol and determines the initial APS for communication with a specific destination.

Message Dispersion and Transmission

The source divides the message into multiple pieces, each piece encoded with a secret known only to the source and destination based on Rabin’s Information Dispersal Algorithm (IDA). The shared secret between the sender and the receiver ensures that even if an intermediate node has the necessary number of chunks, the final message is irretrievable while the destination easily can once it receives enough chunks. Rabin’s IDA introduces redundancy due to which even if some messages are lost when certain paths are broken or contain malicious actors, the destination is still able to reconstruct the original message. If a sufficient number of chunks are unable to reach the destination, the destination waits for retransmissions from the source which are capped at Rmax transmissions.

A Message Authentication Code is transmitted along with every chunk to ensure its integrity and the authenticity of its origin. The receiver sends an acknowledgement after a timeout to the source specifying all the pieces received. Along with the acknowledgement, a MAC is again attached to ensure the integrity and authenticity of the acknowledgement. The acknowledgment gives the source enough information about the pieces not received by the destination. Additionally, this feedback mechanism helps it in updating the reliability of each path in the APS.

APS Adaptation

Each path has a short-term rating that is increased or decreased based on the success of every message’s delivery. A long-term rating equal to the ratio of total messages delivered to total messages sent is also associated with each path. If either of the long term or short term ratings fall below a threshold, the path is discarded by the sender for a certain time period. In this way, for a continuous stream of data, SMT either detects the path as faulty or provides an upper limit on the bandwidth loss rate independent of the attack pattern. 

The dual rating structure also enables the protocol to adapt to changing network conditions over time.

SMT in decentralized networks

SMT introduces erasure coding for distributing messages with redundancy which decreases the reliability assumptions of each path to the destination in a multipath environment. This is useful in the context of open decentralized networks where the paths aren't very reliable but are many in number. The protocol also provides a tool to identify malicious paths and in the presence of non-malicious paths bounds packet loss rates independent of individual node behaviour. 

However, SMT is a solution for unicast transmission where the source and destination are known, can be trusted and hence the routes are optimized based on the messages sent and acknowledged. It also assumes source routing which isn’t always practical. SMT can thus not be directly applied to blockchain environments where transmissions are predominantly multicast.

In the protocol as described, the source is only able to rate the path and not each node of the path. Given the requirement that each path in the APS comprise of disjoint nodes, a few malicious coordinating nodes are thus capable of downgrading several paths. Modified route discovery strategies that use feedback to design multiple overlapping paths to pinpoint malicious nodes could be worth exploring. Moreover, the outcome of applying the algorithm recursively on downstream nodes could be analyzed.

The paper also fails to provide an analysis on the fraction of adversaries that it can handle, especially in case a significant portion of the paths contain adversaries who selectively relay messages. A sybil prevention mechanism is required to ensure that coordinated malicious actors can not operate nodes in different paths without additional cost. 

Though SMT cannot be directly applied to blockchains, it provides an interesting approach to explore in multicast environments. Feel free to share your views on this technique to improve the reliability of message transmission in our discord channel or research forum. Do not forget to subscribe to our blog to receive more such interesting content.

Make sure you’re always up to date by following our official channels:

Twitter | Telegram Announcements | Telegram Chat | Discord | Website