Robust data broadcast over a distributed network with malicious failures
First Claim
1. A method for transmitting data over a network of nodes interconnected by communication links comprising the steps of:
- A. forming a data packet at an originating node, said packet containing1. an identifier identifying the originating node and2. a count of the packets formed by the originating node;
B. transmitting the packet over at least one of the communication links to a neighboring node;
C. at each neighboring node that receives determining whether the packet is valid and is the newest valid packet formed by the originating node and received by the neighboring node by comparing the count with a stored count corresponding to a previously received from the same originating node, said previously received packet being the newest valid packet previously received by the node;
D.1. for each received packet determined to be the newest valid packet at a given nodei. storing at least the packet count in a memory location at the given node which is associated with the originating node; and
ii. queuing the packet for transmission over a communication link to at least one of the neighbors of the node, andiii. transmitting the packet when an appropriate communication link is available;
2. if the packet is a duplicate of an earlier received packet, discarding the packet; and
E. repeating steps C and D until the packet is transmitted to every node.
1 Assignment
0 Petitions
Accused Products
Abstract
A public-key encryption system is used to reliably transmit packets over a network subject to malicious failures. Each node on the network is associated with a public and private key. A transmission over the network identifies its originating node and also includes a digital-signature code word generated by encoding predetermined portions of the transmission using the private key of the originating node. When a transmission is received, the receiving node verifies that the transmission was originated by the identified originating node by manipulating the packet contents using the public key associated with the originating node. The packet is accepted only if the digital-signature code word in the packet corresponds to contents of the packet and the public key of the originating node.
-
Citations
20 Claims
-
1. A method for transmitting data over a network of nodes interconnected by communication links comprising the steps of:
-
A. forming a data packet at an originating node, said packet containing 1. an identifier identifying the originating node and 2. a count of the packets formed by the originating node; B. transmitting the packet over at least one of the communication links to a neighboring node; C. at each neighboring node that receives determining whether the packet is valid and is the newest valid packet formed by the originating node and received by the neighboring node by comparing the count with a stored count corresponding to a previously received from the same originating node, said previously received packet being the newest valid packet previously received by the node; D. 1. for each received packet determined to be the newest valid packet at a given node i. storing at least the packet count in a memory location at the given node which is associated with the originating node; and ii. queuing the packet for transmission over a communication link to at least one of the neighbors of the node, and iii. transmitting the packet when an appropriate communication link is available; 2. if the packet is a duplicate of an earlier received packet, discarding the packet; and E. repeating steps C and D until the packet is transmitted to every node. - View Dependent Claims (2, 3, 4, 6, 8, 10, 12, 15, 17, 18, 20)
-
-
5. encoding a predetermined portion of the contents of the packet using a private code associated with the originating node to form a digital-signature code word, said private code being unavailable to the other nodes on the network,including the digital-signature code word in the packet;
- and
B. in the step of determining if the received packet is the newest valid packet associated with the originating node 1. manipulating the packet contents and the packet digital-signature code word and a public code associated with the originating node to generate an output value; and 2. analyzing the output value to determine both if the packet was originated by the listed originating node and if the packet contents were unaltered during transmission; - View Dependent Claims (7, 9)
- and
-
11. A method of determining if transmissions over a network of nodes interconnected by communication links are reliable comprising the steps of:
-
A. sending to every node on the network one or more packets containing a list of nodke-identifier information and associated public code information, said list containing information from which to identify the nodes on the network; B. when a node receives a transmmission over the network, said transmission containing an identifier identifying the node originating the transmission and a digital-signature code word generated by encoding predetermined portions of the transmission, verifying that the transmission was originated by the identified originating node by; 1. manipulating the packet contents, including the public code associated with the originating node, to generate a second digital-signature code word, 2. analyzing the second digital-signature code word to determine if it corresponds to the digital signature code word in the transmission, and 3. determining that the listed originating node originated the transmission if the second digital-signature code word corresponds to the digital-signature code word in the transmission, or that the transmission was not originated by the listed originating node if the digital-signature code words do not correspond. - View Dependent Claims (13, 14, 16)
-
-
19. A method of transmitting data in a packet over a network of nodes interconnected by communication links, comprising:
-
including said transmitted data in a data section of the packet; including in the packet an identifier identifying the node which originated the packet; including in the packet a count of the number of packets formed by the originating node; generating a digital-signature code word by manipulating a public code associated with the originating node and a predetermined portion of the contents of the packet, and including said digital-signature code word in the packet in addition to said transmitted data.
-
Specification