{"action":"created","issue":{"url":"https://api.github.com/repos/poanetwork/hbbft/issues/309","repository_url":"https://api.github.com/repos/poanetwork/hbbft","labels_url":"https://api.github.com/repos/poanetwork/hbbft/issues/309/labels{/name}","comments_url":"https://api.github.com/repos/poanetwork/hbbft/issues/309/comments","events_url":"https://api.github.com/repos/poanetwork/hbbft/issues/309/events","html_url":"https://github.com/poanetwork/hbbft/issues/309","id":375146155,"node_id":"MDU6SXNzdWUzNzUxNDYxNTU=","number":309,"title":"Examine `Broadcast` for optimization potential.","user":{"login":"mbr","id":110577,"node_id":"MDQ6VXNlcjExMDU3Nw==","avatar_url":"https://avatars1.githubusercontent.com/u/110577?v=4","gravatar_id":"","url":"https://api.github.com/users/mbr","html_url":"https://github.com/mbr","followers_url":"https://api.github.com/users/mbr/followers","following_url":"https://api.github.com/users/mbr/following{/other_user}","gists_url":"https://api.github.com/users/mbr/gists{/gist_id}","starred_url":"https://api.github.com/users/mbr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mbr/subscriptions","organizations_url":"https://api.github.com/users/mbr/orgs","repos_url":"https://api.github.com/users/mbr/repos","events_url":"https://api.github.com/users/mbr/events{/privacy}","received_events_url":"https://api.github.com/users/mbr/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-10-29T18:02:45Z","updated_at":"2018-10-30T14:10:30Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"While debugging an issue with failing tests, I encountered some inefficiency in the reliable broadcast algorithm, at least inside the edge-case of a two node network. Consider the following partial log:\r\n\r\n```\r\nB: [0] -> [1]: HoneyBadger(0, Message { epoch: 0, content: Subset(Broadcast(0, Value(Proof { #1, root_hash: c002..beaa, value: b808..6d14, .. }))) })\r\nD: [0] -> [1]: HoneyBadger(0, Message { epoch: 0, content: Subset(Broadcast(0, Echo(Proof { #0, root_hash: c002..beaa, value: 0000..3a39, .. }))) })\r\nE: [1] -> [0]: HoneyBadger(0, Message { epoch: 0, content: Subset(Broadcast(0, Echo(Proof { #1, root_hash: c002..beaa, value: b808..6d14, .. }))) })\r\nG: [1] -> [0]: HoneyBadger(0, Message { epoch: 0, content: Subset(Broadcast(0, Ready(c002..beaa))) })\r\nJ: [0] -> [1]: HoneyBadger(0, Message { epoch: 0, content: Subset(Broadcast(0, Ready(c002..beaa))) })\r\n```\r\n\r\nThis is almost in line with the algorithm description on [page 7](https://eprint.iacr.org/2016/199.pdf); we are sending `VAL(h, b_i, s_i)` to every node in the network and expect an `ECHO(h, b_i, s_i)` back for each, finally a `READY(h)`. The full text-book message log would look like this:\r\n\r\n```\r\nA: [0->0] VAL(h, b_0, s_0)\r\nB: [0->1] VAL(h, b_1, s_1)\r\nC: [0->0] ECHO(h, b_0, s_0)\r\nD: [0->1] ECHO(h, b_0, s_0)\r\nE: [1->0] ECHO(h, b_1, s_1)\r\nF: [1->1] ECHO(h, b_1, s_1)\r\nG: [1->0] READY(h)\r\nH: [1->1] READY(h)\r\nI: [0->0] READY(h)\r\nJ: [0->1] READY(h)\r\n```\r\n\r\nThis is twice as many messages, because `A`, `C`, `F`, `H` and `I` are messages that need not leave the node and are short-circuited inside the code already (instead of returning it an `Step` output, it is directly handled by calling the respective `handle_` function).\r\n\r\n## Possible optimizations\r\n\r\nThere might be some more room for optimization here; consider message `E`. In this case, node 1 is echoing back what node 0 sent in its `VAL` message. This message contains no new information for node 0, it merely functions as an acknowledgement. The resilience gained here is minimal, a smart attacker that controls a faulty node can always reply with a correct `ECHO` message to avoid suspicion.\r\n\r\nIn general, it might be possible to omit the `ECHO` back to the sender of the `VAL` that triggered it, resulting in the following sequence:\r\n\r\n```\r\nB: [0->1] VAL(h, b_1, s_1)\r\nD: [0->1] ECHO(h, b_0, s_0)\r\nG: [1->0] READY(h)\r\nJ: [0->1] READY(h)\r\n```\r\n\r\nSome other message back to the original node could potentially be dropped, but this a bigger trade-off: We are trading efficiency (less messages) for a weaker \"non-malicious\" error detection; the messages can be checked to ensure nodes that meant well are up, but will not deter a corrupted node that is actively working to deceive the network.\r\n\r\n## Gains\r\n\r\nThe gains per removed message in a network of `N` nodes are modest for large networks: Instead of sending `N-1 + N(N-1) + N(N-1)` messages (`VAR`, `ECHO`, `READY`), we would be sending `N-1 + (N-1)(N-1) + N(N-1)` messages; at 25 nodes this is a 2% reduction per broadcast, smaller networks benefit much more (e.g. around 9% with 5 nodes). Broadcast messages account for about 2/3rds of all messages (correct me if I am wrong), also the `ECHO` message carries a substantial payload (as opposed to `READY`).\r\n\r\nI'd like some feedback on these observations, I don't know if implementing this potential optimization is worthwhile right now, but it is something to keep in mind for the future. More important is verifying that no cryptographic properties are altered by this modification; if that is the case, we can keep this issue around as a warning ;).\r\n"},"comment":{"url":"https://api.github.com/repos/poanetwork/hbbft/issues/comments/434316020","html_url":"https://github.com/poanetwork/hbbft/issues/309#issuecomment-434316020","issue_url":"https://api.github.com/repos/poanetwork/hbbft/issues/309","id":434316020,"node_id":"MDEyOklzc3VlQ29tbWVudDQzNDMxNjAyMA==","user":{"login":"afck","id":7894725,"node_id":"MDQ6VXNlcjc4OTQ3MjU=","avatar_url":"https://avatars0.githubusercontent.com/u/7894725?v=4","gravatar_id":"","url":"https://api.github.com/users/afck","html_url":"https://github.com/afck","followers_url":"https://api.github.com/users/afck/followers","following_url":"https://api.github.com/users/afck/following{/other_user}","gists_url":"https://api.github.com/users/afck/gists{/gist_id}","starred_url":"https://api.github.com/users/afck/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/afck/subscriptions","organizations_url":"https://api.github.com/users/afck/orgs","repos_url":"https://api.github.com/users/afck/repos","events_url":"https://api.github.com/users/afck/events{/privacy}","received_events_url":"https://api.github.com/users/afck/received_events","type":"User","site_admin":false},"created_at":"2018-10-30T14:10:30Z","updated_at":"2018-10-30T14:10:30Z","author_association":"CONTRIBUTOR","body":"Exactly: In the optimistic case, we want to avoid the unnecessary redundancy. Of course we never want to compromise on security and asynchronicity! But I think my proposal wouldn't: It would be asynchronous and still work for up to _f_ faulty nodes; but if there are more than _g_ faulty nodes, it would require one additional message round (sending the missing full `Echo`s)."}}
{"actor":{"display_login":"afck"}}