This is the second part of Understanding Wave protocol, if you haven’t read the first post, we recommend to read it first. This post will be more technical and we recommend to read the white papers for more detailed explanations.
Now it’s time to talk about the server-server protocol, the Federation protocol. This protocol is used to communicate servers that have participants of the same wave. How does this work? Every communication between servers starts from a client that wants to do an operation. The client sends the operation to his server. The server adds an order tag to this operation and add operations into a bundle. After that, the server signs the bundle and sends it to the rest of the servers. This is the big picture of federation protocol.
Let’s see in details each part of the communication. The first part is explained on the Client-server protocol post. The second one, where the server adds an order tag, is one of the most important parts of the federation. This example will help understand what kind of problems can be found. In server-server protocol all messages have something else than in client-server protocol. In server-server protocol, the bundles have a verification hint used to make the verification more efficient. They have also an order tag as the client-server protocol. The Server sends bundles of data to the Ordering Server. This server is the responsible to order all the bundles they get and do the necessary to prevent branching in hash chain. This picture represents a normal server usage. We can see 3 server (S1,S2,S3) and the Ordering server. Each line simulate a sent message. Every message has an order tag put it by his own server. For example the first message of S1 is m0. This are the basics concepts.
We can see on the example that m2 branch the hash chain because S1 and S2 try to send a bundle to Ordering Server when they haven’t recieved the bundle from the other server. Ordering Server has to un-branch the hash chain combining the branches and reply other servers with the new history hash (m*3 for S2). After that, the next message will have no branching and will continue normally (m4 -> m*4).
To sign a bundle, the server packs messages into bundles. Then, for each message in the bundle, the server calculates the hash value and then create a data store sorting the hash values. After that, for each destination, the server creates a hash tree with the union of all hash values of each server. Once it is done, the server chooses a random nonce of bit length and for each hash tree create a new hash tree with the leaves of the message hash tree, destination and random. Afterwards, server merges the trees corresponding to each destination server into a single tree. At the end, the server signs that hash tree.
This is an example of a well formed hash tree.
There is a problem on this tree. If we send this tree to S1 and S2, we can think that it is correct. But if we look in detail, S2 doesn’t have to get m1 because this message only S1. So, we have to remove some subtrees and move the leaves to send the correct information to S2 and nothing else. This procedure is called winnowing a bundle.
Winnowing a bundle means to remove any server from the bundle ( well constructed with data store, hash tree and signature) and, the most important, ensure that the bundle remains verifiable. There are a few steps to follow to achieve it. The first is to identify the part of the hash tree concerning the S1. Later we remove the subtree. After that, we have to remove all the elements of the data store that are no longer referenced by any leaf of the hash tree. And that’s it!
This is the result:
This procedure can be used also to remove messages from the bundle.
The last think we have to do with a bundle is to verify them. There are 2 steps we have to follow:
- Each bundle that arrives must be verified.
- The order tags of the messages that arrive must be verified by verifying their order tags.
To verify a bundle you have to verify that the hash tree is correct and well-formed. Verify the signature and the data signed is the root of the hash tree. At the end for each leaf you have to verify that exists some hash value of the leaf.
To verify the order tags you have to not contradict the agreed total order. It’s easy to check this 2 invariants:
- The message is ordered in a stream after the messages with tags t(m*j1), … , t(m*jk).
- The messages with tags t(m*j1), … , t(m*jk) appear in the stated order in the total message stream order.
I hope this posts will be useful to understand wave federation. There are some coding concepts that are not trivial, but don’t worry to ask, we will try to explain it as well as we can.
Stay onthetopofthewave!
Tags: featured, federation, hash, protocol server, server-server, signs, Wave, Wave Federation, wave server
If you like what you see, please, support us:
Posts that may be of your interest:
- Understanding Wave protocol – Part I
- Google Wave Federation protocol updates
- Wave Federation
- Google Wave in the 2010
- Wave Federation Prototype Server
Understanding Wave protocol – Part II
This is the second part of Understanding Wave protocol, if you haven’t read the first post, we recommend to read it first. This post will be more technical and we recommend to read the white papers for more detailed explanations.
Now it’s time to talk about the server-server protocol, the Federation protocol. This protocol is used to communicate servers that have participants of the same wave. How does this work? Every communication between servers starts from a client that wants to do an operation. The client sends the operation to his server. The server adds an order tag to this operation and add operations into a bundle. After that, the server signs the bundle and sends it to the rest of the servers. This is the big picture of federation protocol.
Let’s see in details each part of the communication. The first part is explained on the Client-server protocol post. The second one, where the server adds an order tag, is one of the most important parts of the federation. This example will help understand what kind of problems can be found. In server-server protocol all messages have something else than in client-server protocol. In server-server protocol, the bundles have a verification hint used to make the verification more efficient. They have also an order tag as the client-server protocol. The Server sends bundles of data to the Ordering Server. This server is the responsible to order all the bundles they get and do the necessary to prevent branching in hash chain. This picture represents a normal server usage. We can see 3 server (S1,S2,S3) and the Ordering server. Each line simulate a sent message. Every message has an order tag put it by his own server. For example the first message of S1 is m0. This are the basics concepts.
We can see on the example that m2 branch the hash chain because S1 and S2 try to send a bundle to Ordering Server when they haven’t recieved the bundle from the other server. Ordering Server has to un-branch the hash chain combining the branches and reply other servers with the new history hash (m*3 for S2). After that, the next message will have no branching and will continue normally (m4 -> m*4).
To sign a bundle, the server packs messages into bundles. Then, for each message in the bundle, the server calculates the hash value and then create a data store sorting the hash values. After that, for each destination, the server creates a hash tree with the union of all hash values of each server. Once it is done, the server chooses a random nonce of bit length and for each hash tree create a new hash tree with the leaves of the message hash tree, destination and random. Afterwards, server merges the trees corresponding to each destination server into a single tree. At the end, the server signs that hash tree.
This is an example of a well formed hash tree.
There is a problem on this tree. If we send this tree to S1 and S2, we can think that it is correct. But if we look in detail, S2 doesn’t have to get m1 because this message only S1. So, we have to remove some subtrees and move the leaves to send the correct information to S2 and nothing else. This procedure is called winnowing a bundle.
Winnowing a bundle means to remove any server from the bundle ( well constructed with data store, hash tree and signature) and, the most important, ensure that the bundle remains verifiable. There are a few steps to follow to achieve it. The first is to identify the part of the hash tree concerning the S1. Later we remove the subtree. After that, we have to remove all the elements of the data store that are no longer referenced by any leaf of the hash tree. And that’s it!
This is the result:
This procedure can be used also to remove messages from the bundle.
The last think we have to do with a bundle is to verify them. There are 2 steps we have to follow:
To verify a bundle you have to verify that the hash tree is correct and well-formed. Verify the signature and the data signed is the root of the hash tree. At the end for each leaf you have to verify that exists some hash value of the leaf.
To verify the order tags you have to not contradict the agreed total order. It’s easy to check this 2 invariants:
I hope this posts will be useful to understand wave federation. There are some coding concepts that are not trivial, but don’t worry to ask, we will try to explain it as well as we can.
Stay onthetopofthewave!
Tags: featured, federation, hash, protocol server, server-server, signs, Wave, Wave Federation, wave server
If you like what you see, please, support us:
Posts that may be of your interest: