{"action":"created","comment":{"url":"https://api.github.com/repos/solana-labs/solana/pulls/comments/241614463","pull_request_review_id":184933631,"id":241614463,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDI0MTYxNDQ2Mw==","diff_hunk":"@@ -0,0 +1,95 @@\n+# Fork Selection\n+ This RFC defines Solana's *Nakomoto Fork Selection* algorithm based on time locks. It satisfies the following properties:\n+\n+\n+* A voter can eventually recover from voting on a fork that doesn't become the fork with the desired finality.\n+* If the voters share a common ancestor then they will converge to a fork containing that ancestor no matter how they are partitioned, although it may not be the latest possible ancestor at the start of the fork.\n+* Rollback requires exponentially more time for older votes than for newer votes.\n+* Voters have the freedom to set a minimum finality threshold before committing a vote to a higher lockout.  This allows each voter to make a trade-off between risk and reward. See [finality](#economic-finality).\n+\n+## Time\n+\n+For networks like Solana, time can be the PoH hash count, which is a VDF that provides a source of time before consensus. Other networks adopting this approach would need to consider a global source of time.\n+\n+For Solana, time uniquely identifies a specific leader for fork generation.  At any given time only 1 leader, which can be computed from the ledger itself, can propose a fork.  For more details, see [fork generation](fork-generation.md) and [leader rotation](leader-rotation.md).\n+\n+## Algorithm\n+\n+The basic idea to this approach is to stack consensus votes.  Votes in the stack must be for forks that descend from each other and for forks that are valid in the ledger they are submitted to.  Each consensus vote has a `lockout` in units of time before it can be discarded.  When a vote is added to the stack, the lockouts of all the previous votes in the stack are doubled (see [Rollback](#Rollback)).  With each new vote, a voter commits the previous votes to an ever-increasing lockout.  Since at 32 votes we can consider the system to be at `max lockout` any votes with a lockout above `1<<32` are dequeued (FIFO).  Dequeuing a vote is the trigger for a reward.  If a vote expires before it is dequeued, it and all the votes above it are popped (LIFO) from the vote stack.  The voter needs to start rebuilding the stack from that point.\n+\n+\n+### Rollback\n+\n+Before a vote is pushed to the stack, all the votes leading up to vote with a lower lock time than the new vote are popped.  After rollback lockouts are not doubled until the voter catches up to the rollback height of votes.\n+\n+For example, a vote stack with the following state:\n+\n+| vote | vote time | lockout | lock expiration time |\n+|-----:|----------:|--------:|---------------------:|\n+|    4 |         4 |      2  |                    6 |\n+|    3 |         3 |      4  |                    7 |\n+|    2 |         2 |      8  |                   10 |\n+|    1 |         1 |      16 |                   17 |\n+\n+*Vote 5* is at time 9, and the resulting state is\n+\n+| vote | vote time | lockout | lock expiration time |\n+|-----:|----------:|--------:|---------------------:|\n+|    5 |         9 |      2  |                   11 |\n+|    2 |         2 |      8  |                   10 |\n+|    1 |         1 |      16 |                   17 |\n+\n+*Vote 6* is at time 10\n+\n+| vote | vote time | lockout | lock expiration time |\n+|-----:|----------:|--------:|---------------------:|\n+|    6 |        10 |       2 |                   12 |\n+|    5 |         9 |       4 |                   13 |\n+|    2 |         2 |       8 |                   10 |\n+|    1 |         1 |      16 |                   17 |\n+\n+At time 10 the new votes caught up to the previous votes.  But *vote 2* expires at 10, so the when *vote 7* at time 11 is applied the votes including and above *vote 2* will be popped.\n+\n+| vote | vote time | lockout | lock expiration time |\n+|-----:|----------:|--------:|---------------------:|\n+|    7 |        11 |       2 |                   13 |\n+|    1 |         1 |      16 |                   17 |\n+\n+The lockout for vote 1 will not increase from 16 until the stack contains 5 votes.\n+\n+### Slashing and Rewards\n+\n+The purpose of the lockout is to force a voter to commit opportunity cost to a specific fork.  Voters that violate the lockouts and vote for a diverging fork within the lockout should be punished.  Slashing or simply freezing the voter from rewards for a long period of time can be used as punishment.\n+\n+Voters should be rewarded for selecting the fork that the rest of the network selected as often as possible.  This is well-aligned with generating a reward when the vote stack is full and the oldest vote needs to be dequeued.  Thus a reward should be generated for each successful dequeue.\n+\n+### Economic Finality\n+\n+Economic finality can be calculated as the total opportunity cost due to the vote lockout at a given fork.  As votes get further and further buried, the economic finality increases because the cost of unrolling would be the total loss of all the reward from the lockouts at that fork.","path":"book/src/fork-selection.md","position":null,"original_position":68,"commit_id":"551e2b272eb740910324fe1976eedaba7f284d3e","original_commit_id":"f0045d924ac34b3981b69f1cffde65f6ff3d0e5b","user":{"login":"aeyakovenko","id":1029046,"node_id":"MDQ6VXNlcjEwMjkwNDY=","avatar_url":"https://avatars0.githubusercontent.com/u/1029046?v=4","gravatar_id":"","url":"https://api.github.com/users/aeyakovenko","html_url":"https://github.com/aeyakovenko","followers_url":"https://api.github.com/users/aeyakovenko/followers","following_url":"https://api.github.com/users/aeyakovenko/following{/other_user}","gists_url":"https://api.github.com/users/aeyakovenko/gists{/gist_id}","starred_url":"https://api.github.com/users/aeyakovenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeyakovenko/subscriptions","organizations_url":"https://api.github.com/users/aeyakovenko/orgs","repos_url":"https://api.github.com/users/aeyakovenko/repos","events_url":"https://api.github.com/users/aeyakovenko/events{/privacy}","received_events_url":"https://api.github.com/users/aeyakovenko/received_events","type":"User","site_admin":false},"body":"@garious The **Economic Finality** of *fork A* can be calculated as the loss of all the                                                                                                                                                                                                                                                                                               rewards from rollback of *fork A* and its descendants, plus the opportunity cost of reward                                                                                                                                                                                                                                                                                                \r\ndue to the exponentially growing lockout of the votes that have confirmed *fork A*.","created_at":"2018-12-14T00:53:02Z","updated_at":"2018-12-14T00:53:02Z","html_url":"https://github.com/solana-labs/solana/pull/2061#discussion_r241614463","pull_request_url":"https://api.github.com/repos/solana-labs/solana/pulls/2061","author_association":"MEMBER","_links":{"self":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/comments/241614463"},"html":{"href":"https://github.com/solana-labs/solana/pull/2061#discussion_r241614463"},"pull_request":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/2061"}},"in_reply_to_id":241460249},"pull_request":{"url":"https://api.github.com/repos/solana-labs/solana/pulls/2061","id":237025614,"node_id":"MDExOlB1bGxSZXF1ZXN0MjM3MDI1NjE0","html_url":"https://github.com/solana-labs/solana/pull/2061","diff_url":"https://github.com/solana-labs/solana/pull/2061.diff","patch_url":"https://github.com/solana-labs/solana/pull/2061.patch","issue_url":"https://api.github.com/repos/solana-labs/solana/issues/2061","number":2061,"state":"open","locked":false,"title":"Add fork selection RFC","user":{"login":"aeyakovenko","id":1029046,"node_id":"MDQ6VXNlcjEwMjkwNDY=","avatar_url":"https://avatars0.githubusercontent.com/u/1029046?v=4","gravatar_id":"","url":"https://api.github.com/users/aeyakovenko","html_url":"https://github.com/aeyakovenko","followers_url":"https://api.github.com/users/aeyakovenko/followers","following_url":"https://api.github.com/users/aeyakovenko/following{/other_user}","gists_url":"https://api.github.com/users/aeyakovenko/gists{/gist_id}","starred_url":"https://api.github.com/users/aeyakovenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeyakovenko/subscriptions","organizations_url":"https://api.github.com/users/aeyakovenko/orgs","repos_url":"https://api.github.com/users/aeyakovenko/repos","events_url":"https://api.github.com/users/aeyakovenko/events{/privacy}","received_events_url":"https://api.github.com/users/aeyakovenko/received_events","type":"User","site_admin":false},"body":"#### Problem\r\n\r\nLack of RFC on fork selection.\r\n\r\n#### Summary of Changes\r\n\r\nRFC on fork selection and simulation.\r\n\r\nFixes # #1983 (choice based on maximizing finality should be censorship resistant)\r\n","created_at":"2018-12-08T00:00:17Z","updated_at":"2018-12-14T00:53:02Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b50005977aa4747b44623814b4af69827ea61dd0","assignee":null,"assignees":[],"requested_reviewers":[{"login":"carllin","id":3374799,"node_id":"MDQ6VXNlcjMzNzQ3OTk=","avatar_url":"https://avatars1.githubusercontent.com/u/3374799?v=4","gravatar_id":"","url":"https://api.github.com/users/carllin","html_url":"https://github.com/carllin","followers_url":"https://api.github.com/users/carllin/followers","following_url":"https://api.github.com/users/carllin/following{/other_user}","gists_url":"https://api.github.com/users/carllin/gists{/gist_id}","starred_url":"https://api.github.com/users/carllin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/carllin/subscriptions","organizations_url":"https://api.github.com/users/carllin/orgs","repos_url":"https://api.github.com/users/carllin/repos","events_url":"https://api.github.com/users/carllin/events{/privacy}","received_events_url":"https://api.github.com/users/carllin/received_events","type":"User","site_admin":false}],"requested_teams":[],"labels":[{"id":982887376,"node_id":"MDU6TGFiZWw5ODI4ODczNzY=","url":"https://api.github.com/repos/solana-labs/solana/labels/noCI","name":"noCI","color":"b60205","default":false}],"milestone":null,"commits_url":"https://api.github.com/repos/solana-labs/solana/pulls/2061/commits","review_comments_url":"https://api.github.com/repos/solana-labs/solana/pulls/2061/comments","review_comment_url":"https://api.github.com/repos/solana-labs/solana/pulls/comments{/number}","comments_url":"https://api.github.com/repos/solana-labs/solana/issues/2061/comments","statuses_url":"https://api.github.com/repos/solana-labs/solana/statuses/551e2b272eb740910324fe1976eedaba7f284d3e","head":{"label":"aeyakovenko:branch_generation_rfc_with_locktower","ref":"branch_generation_rfc_with_locktower","sha":"551e2b272eb740910324fe1976eedaba7f284d3e","user":{"login":"aeyakovenko","id":1029046,"node_id":"MDQ6VXNlcjEwMjkwNDY=","avatar_url":"https://avatars0.githubusercontent.com/u/1029046?v=4","gravatar_id":"","url":"https://api.github.com/users/aeyakovenko","html_url":"https://github.com/aeyakovenko","followers_url":"https://api.github.com/users/aeyakovenko/followers","following_url":"https://api.github.com/users/aeyakovenko/following{/other_user}","gists_url":"https://api.github.com/users/aeyakovenko/gists{/gist_id}","starred_url":"https://api.github.com/users/aeyakovenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeyakovenko/subscriptions","organizations_url":"https://api.github.com/users/aeyakovenko/orgs","repos_url":"https://api.github.com/users/aeyakovenko/repos","events_url":"https://api.github.com/users/aeyakovenko/events{/privacy}","received_events_url":"https://api.github.com/users/aeyakovenko/received_events","type":"User","site_admin":false},"repo":{"id":124140461,"node_id":"MDEwOlJlcG9zaXRvcnkxMjQxNDA0NjE=","name":"solana","full_name":"aeyakovenko/solana","private":false,"owner":{"login":"aeyakovenko","id":1029046,"node_id":"MDQ6VXNlcjEwMjkwNDY=","avatar_url":"https://avatars0.githubusercontent.com/u/1029046?v=4","gravatar_id":"","url":"https://api.github.com/users/aeyakovenko","html_url":"https://github.com/aeyakovenko","followers_url":"https://api.github.com/users/aeyakovenko/followers","following_url":"https://api.github.com/users/aeyakovenko/following{/other_user}","gists_url":"https://api.github.com/users/aeyakovenko/gists{/gist_id}","starred_url":"https://api.github.com/users/aeyakovenko/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aeyakovenko/subscriptions","organizations_url":"https://api.github.com/users/aeyakovenko/orgs","repos_url":"https://api.github.com/users/aeyakovenko/repos","events_url":"https://api.github.com/users/aeyakovenko/events{/privacy}","received_events_url":"https://api.github.com/users/aeyakovenko/received_events","type":"User","site_admin":false},"html_url":"https://github.com/aeyakovenko/solana","description":"a high performance blockchain","fork":true,"url":"https://api.github.com/repos/aeyakovenko/solana","forks_url":"https://api.github.com/repos/aeyakovenko/solana/forks","keys_url":"https://api.github.com/repos/aeyakovenko/solana/keys{/key_id}","collaborators_url":"https://api.github.com/repos/aeyakovenko/solana/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/aeyakovenko/solana/teams","hooks_url":"https://api.github.com/repos/aeyakovenko/solana/hooks","issue_events_url":"https://api.github.com/repos/aeyakovenko/solana/issues/events{/number}","events_url":"https://api.github.com/repos/aeyakovenko/solana/events","assignees_url":"https://api.github.com/repos/aeyakovenko/solana/assignees{/user}","branches_url":"https://api.github.com/repos/aeyakovenko/solana/branches{/branch}","tags_url":"https://api.github.com/repos/aeyakovenko/solana/tags","blobs_url":"https://api.github.com/repos/aeyakovenko/solana/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/aeyakovenko/solana/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/aeyakovenko/solana/git/refs{/sha}","trees_url":"https://api.github.com/repos/aeyakovenko/solana/git/trees{/sha}","statuses_url":"https://api.github.com/repos/aeyakovenko/solana/statuses/{sha}","languages_url":"https://api.github.com/repos/aeyakovenko/solana/languages","stargazers_url":"https://api.github.com/repos/aeyakovenko/solana/stargazers","contributors_url":"https://api.github.com/repos/aeyakovenko/solana/contributors","subscribers_url":"https://api.github.com/repos/aeyakovenko/solana/subscribers","subscription_url":"https://api.github.com/repos/aeyakovenko/solana/subscription","commits_url":"https://api.github.com/repos/aeyakovenko/solana/commits{/sha}","git_commits_url":"https://api.github.com/repos/aeyakovenko/solana/git/commits{/sha}","comments_url":"https://api.github.com/repos/aeyakovenko/solana/comments{/number}","issue_comment_url":"https://api.github.com/repos/aeyakovenko/solana/issues/comments{/number}","contents_url":"https://api.github.com/repos/aeyakovenko/solana/contents/{+path}","compare_url":"https://api.github.com/repos/aeyakovenko/solana/compare/{base}...{head}","merges_url":"https://api.github.com/repos/aeyakovenko/solana/merges","archive_url":"https://api.github.com/repos/aeyakovenko/solana/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/aeyakovenko/solana/downloads","issues_url":"https://api.github.com/repos/aeyakovenko/solana/issues{/number}","pulls_url":"https://api.github.com/repos/aeyakovenko/solana/pulls{/number}","milestones_url":"https://api.github.com/repos/aeyakovenko/solana/milestones{/number}","notifications_url":"https://api.github.com/repos/aeyakovenko/solana/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/aeyakovenko/solana/labels{/name}","releases_url":"https://api.github.com/repos/aeyakovenko/solana/releases{/id}","deployments_url":"https://api.github.com/repos/aeyakovenko/solana/deployments","created_at":"2018-03-06T21:24:10Z","updated_at":"2018-12-12T23:14:42Z","pushed_at":"2018-12-13T18:46:17Z","git_url":"git://github.com/aeyakovenko/solana.git","ssh_url":"git@github.com:aeyakovenko/solana.git","clone_url":"https://github.com/aeyakovenko/solana.git","svn_url":"https://github.com/aeyakovenko/solana","homepage":"https://solana.com","size":14813,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"other","name":"Other","spdx_id":"NOASSERTION","url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"solana-labs:master","ref":"master","sha":"647e5d76b0f80c37dfe76ba743dd4d01e6fee9ec","user":{"login":"solana-labs","id":35608259,"node_id":"MDEyOk9yZ2FuaXphdGlvbjM1NjA4MjU5","avatar_url":"https://avatars3.githubusercontent.com/u/35608259?v=4","gravatar_id":"","url":"https://api.github.com/users/solana-labs","html_url":"https://github.com/solana-labs","followers_url":"https://api.github.com/users/solana-labs/followers","following_url":"https://api.github.com/users/solana-labs/following{/other_user}","gists_url":"https://api.github.com/users/solana-labs/gists{/gist_id}","starred_url":"https://api.github.com/users/solana-labs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solana-labs/subscriptions","organizations_url":"https://api.github.com/users/solana-labs/orgs","repos_url":"https://api.github.com/users/solana-labs/repos","events_url":"https://api.github.com/users/solana-labs/events{/privacy}","received_events_url":"https://api.github.com/users/solana-labs/received_events","type":"Organization","site_admin":false},"repo":{"id":121470383,"node_id":"MDEwOlJlcG9zaXRvcnkxMjE0NzAzODM=","name":"solana","full_name":"solana-labs/solana","private":false,"owner":{"login":"solana-labs","id":35608259,"node_id":"MDEyOk9yZ2FuaXphdGlvbjM1NjA4MjU5","avatar_url":"https://avatars3.githubusercontent.com/u/35608259?v=4","gravatar_id":"","url":"https://api.github.com/users/solana-labs","html_url":"https://github.com/solana-labs","followers_url":"https://api.github.com/users/solana-labs/followers","following_url":"https://api.github.com/users/solana-labs/following{/other_user}","gists_url":"https://api.github.com/users/solana-labs/gists{/gist_id}","starred_url":"https://api.github.com/users/solana-labs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solana-labs/subscriptions","organizations_url":"https://api.github.com/users/solana-labs/orgs","repos_url":"https://api.github.com/users/solana-labs/repos","events_url":"https://api.github.com/users/solana-labs/events{/privacy}","received_events_url":"https://api.github.com/users/solana-labs/received_events","type":"Organization","site_admin":false},"html_url":"https://github.com/solana-labs/solana","description":"Blockchain Rebuilt for Scale","fork":false,"url":"https://api.github.com/repos/solana-labs/solana","forks_url":"https://api.github.com/repos/solana-labs/solana/forks","keys_url":"https://api.github.com/repos/solana-labs/solana/keys{/key_id}","collaborators_url":"https://api.github.com/repos/solana-labs/solana/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/solana-labs/solana/teams","hooks_url":"https://api.github.com/repos/solana-labs/solana/hooks","issue_events_url":"https://api.github.com/repos/solana-labs/solana/issues/events{/number}","events_url":"https://api.github.com/repos/solana-labs/solana/events","assignees_url":"https://api.github.com/repos/solana-labs/solana/assignees{/user}","branches_url":"https://api.github.com/repos/solana-labs/solana/branches{/branch}","tags_url":"https://api.github.com/repos/solana-labs/solana/tags","blobs_url":"https://api.github.com/repos/solana-labs/solana/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/solana-labs/solana/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/solana-labs/solana/git/refs{/sha}","trees_url":"https://api.github.com/repos/solana-labs/solana/git/trees{/sha}","statuses_url":"https://api.github.com/repos/solana-labs/solana/statuses/{sha}","languages_url":"https://api.github.com/repos/solana-labs/solana/languages","stargazers_url":"https://api.github.com/repos/solana-labs/solana/stargazers","contributors_url":"https://api.github.com/repos/solana-labs/solana/contributors","subscribers_url":"https://api.github.com/repos/solana-labs/solana/subscribers","subscription_url":"https://api.github.com/repos/solana-labs/solana/subscription","commits_url":"https://api.github.com/repos/solana-labs/solana/commits{/sha}","git_commits_url":"https://api.github.com/repos/solana-labs/solana/git/commits{/sha}","comments_url":"https://api.github.com/repos/solana-labs/solana/comments{/number}","issue_comment_url":"https://api.github.com/repos/solana-labs/solana/issues/comments{/number}","contents_url":"https://api.github.com/repos/solana-labs/solana/contents/{+path}","compare_url":"https://api.github.com/repos/solana-labs/solana/compare/{base}...{head}","merges_url":"https://api.github.com/repos/solana-labs/solana/merges","archive_url":"https://api.github.com/repos/solana-labs/solana/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/solana-labs/solana/downloads","issues_url":"https://api.github.com/repos/solana-labs/solana/issues{/number}","pulls_url":"https://api.github.com/repos/solana-labs/solana/pulls{/number}","milestones_url":"https://api.github.com/repos/solana-labs/solana/milestones{/number}","notifications_url":"https://api.github.com/repos/solana-labs/solana/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/solana-labs/solana/labels{/name}","releases_url":"https://api.github.com/repos/solana-labs/solana/releases{/id}","deployments_url":"https://api.github.com/repos/solana-labs/solana/deployments","created_at":"2018-02-14T04:26:27Z","updated_at":"2018-12-14T00:50:34Z","pushed_at":"2018-12-14T00:50:31Z","git_url":"git://github.com/solana-labs/solana.git","ssh_url":"git@github.com:solana-labs/solana.git","clone_url":"https://github.com/solana-labs/solana.git","svn_url":"https://github.com/solana-labs/solana","homepage":"https://solana.com","size":14858,"stargazers_count":398,"watchers_count":398,"language":"Rust","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":69,"mirror_url":null,"archived":false,"open_issues_count":180,"license":{"key":"other","name":"Other","spdx_id":"NOASSERTION","url":null,"node_id":"MDc6TGljZW5zZTA="},"forks":69,"open_issues":180,"watchers":398,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/2061"},"html":{"href":"https://github.com/solana-labs/solana/pull/2061"},"issue":{"href":"https://api.github.com/repos/solana-labs/solana/issues/2061"},"comments":{"href":"https://api.github.com/repos/solana-labs/solana/issues/2061/comments"},"review_comments":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/2061/comments"},"review_comment":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/solana-labs/solana/pulls/2061/commits"},"statuses":{"href":"https://api.github.com/repos/solana-labs/solana/statuses/551e2b272eb740910324fe1976eedaba7f284d3e"}},"author_association":"MEMBER"}}
{"actor":{"display_login":"aeyakovenko"}}