{"action":"created","issue":{"url":"https://api.github.com/repos/zcash/zcash/issues/147","repository_url":"https://api.github.com/repos/zcash/zcash","labels_url":"https://api.github.com/repos/zcash/zcash/issues/147/labels{/name}","comments_url":"https://api.github.com/repos/zcash/zcash/issues/147/comments","events_url":"https://api.github.com/repos/zcash/zcash/issues/147/events","html_url":"https://github.com/zcash/zcash/issues/147","id":64635851,"number":147,"title":"select difficulty adjustment algorithm","user":{"login":"nathan-at-least","id":4369700,"avatar_url":"https://avatars.githubusercontent.com/u/4369700?v=3","gravatar_id":"","url":"https://api.github.com/users/nathan-at-least","html_url":"https://github.com/nathan-at-least","followers_url":"https://api.github.com/users/nathan-at-least/followers","following_url":"https://api.github.com/users/nathan-at-least/following{/other_user}","gists_url":"https://api.github.com/users/nathan-at-least/gists{/gist_id}","starred_url":"https://api.github.com/users/nathan-at-least/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nathan-at-least/subscriptions","organizations_url":"https://api.github.com/users/nathan-at-least/orgs","repos_url":"https://api.github.com/users/nathan-at-least/repos","events_url":"https://api.github.com/users/nathan-at-least/events{/privacy}","received_events_url":"https://api.github.com/users/nathan-at-least/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/zcash/zcash/labels/blockchain%20genesis","name":"blockchain genesis","color":"fbca04"},{"url":"https://api.github.com/repos/zcash/zcash/labels/consensus%20protocol","name":"consensus protocol","color":"f766c7"},{"url":"https://api.github.com/repos/zcash/zcash/labels/economics","name":"economics","color":"80abb5"},{"url":"https://api.github.com/repos/zcash/zcash/labels/in%201.0","name":"in 1.0","color":"ffc987"},{"url":"https://api.github.com/repos/zcash/zcash/labels/performance","name":"performance","color":"b495f9"},{"url":"https://api.github.com/repos/zcash/zcash/labels/PoW%20and%20mining","name":"PoW and mining","color":"903b00"},{"url":"https://api.github.com/repos/zcash/zcash/labels/question","name":"question","color":"cc317c"},{"url":"https://api.github.com/repos/zcash/zcash/labels/research","name":"research","color":"0052cc"},{"url":"https://api.github.com/repos/zcash/zcash/labels/SECURITY","name":"SECURITY","color":"e01010"},{"url":"https://api.github.com/repos/zcash/zcash/labels/special%20to%20Daira","name":"special to Daira","color":"ffa480"},{"url":"https://api.github.com/repos/zcash/zcash/labels/special%20to%20Nathan","name":"special to Nathan","color":"a485d9"}],"state":"open","locked":false,"assignee":{"login":"str4d","id":4993799,"avatar_url":"https://avatars.githubusercontent.com/u/4993799?v=3","gravatar_id":"","url":"https://api.github.com/users/str4d","html_url":"https://github.com/str4d","followers_url":"https://api.github.com/users/str4d/followers","following_url":"https://api.github.com/users/str4d/following{/other_user}","gists_url":"https://api.github.com/users/str4d/gists{/gist_id}","starred_url":"https://api.github.com/users/str4d/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/str4d/subscriptions","organizations_url":"https://api.github.com/users/str4d/orgs","repos_url":"https://api.github.com/users/str4d/repos","events_url":"https://api.github.com/users/str4d/events{/privacy}","received_events_url":"https://api.github.com/users/str4d/received_events","type":"User","site_admin":false},"milestone":{"url":"https://api.github.com/repos/zcash/zcash/milestones/34","html_url":"https://github.com/zcash/zcash/milestones/Protocol%202016.0-beta","labels_url":"https://api.github.com/repos/zcash/zcash/milestones/34/labels","id":1770018,"number":34,"title":"Protocol 2016.0-beta","description":"","creator":{"login":"nathan-at-least","id":4369700,"avatar_url":"https://avatars.githubusercontent.com/u/4369700?v=3","gravatar_id":"","url":"https://api.github.com/users/nathan-at-least","html_url":"https://github.com/nathan-at-least","followers_url":"https://api.github.com/users/nathan-at-least/followers","following_url":"https://api.github.com/users/nathan-at-least/following{/other_user}","gists_url":"https://api.github.com/users/nathan-at-least/gists{/gist_id}","starred_url":"https://api.github.com/users/nathan-at-least/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nathan-at-least/subscriptions","organizations_url":"https://api.github.com/users/nathan-at-least/orgs","repos_url":"https://api.github.com/users/nathan-at-least/repos","events_url":"https://api.github.com/users/nathan-at-least/events{/privacy}","received_events_url":"https://api.github.com/users/nathan-at-least/received_events","type":"User","site_admin":false},"open_issues":6,"closed_issues":18,"state":"open","created_at":"2016-05-16T22:10:32Z","updated_at":"2016-05-30T22:32:00Z","due_on":"2016-05-25T07:00:00Z","closed_at":null},"comments":44,"created_at":"2015-03-26T21:14:41Z","updated_at":"2016-05-31T02:16:37Z","closed_at":null,"body":"Are there improvements to availability if difficulty is adjusted each block? Is there any larger vulnerability (eg: DOSing a nodes peer connections to starve it of blocks lowering it's local belief about difficulty)?\r\n\r\nAre there any known advantages or risks which clearly make this worthwhile to spend time on or avoid?\r\n\r\nWe suspect this may be important in the long term, because PoW mining may eventually lead to cascading exit of miners when their margins go <= 0 (Brad Templeton Death Spiral, #95), or during sudden-withdrawal infanticide, or during sudden withdrawal due to side-chain knock-on effects (see #146). This *may* help with availability during those kinds of events (although it won't mitigate those events directly).\r\n\r\nIs the implementation complexity low? (It would seem like changing a single constant K to 1 in \"calculate difficulty every K blocks\".)"},"comment":{"url":"https://api.github.com/repos/zcash/zcash/issues/comments/222578189","html_url":"https://github.com/zcash/zcash/issues/147#issuecomment-222578189","issue_url":"https://api.github.com/repos/zcash/zcash/issues/147","id":222578189,"user":{"login":"defuse","id":4211072,"avatar_url":"https://avatars.githubusercontent.com/u/4211072?v=3","gravatar_id":"","url":"https://api.github.com/users/defuse","html_url":"https://github.com/defuse","followers_url":"https://api.github.com/users/defuse/followers","following_url":"https://api.github.com/users/defuse/following{/other_user}","gists_url":"https://api.github.com/users/defuse/gists{/gist_id}","starred_url":"https://api.github.com/users/defuse/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/defuse/subscriptions","organizations_url":"https://api.github.com/users/defuse/orgs","repos_url":"https://api.github.com/users/defuse/repos","events_url":"https://api.github.com/users/defuse/events{/privacy}","received_events_url":"https://api.github.com/users/defuse/received_events","type":"User","site_admin":false},"created_at":"2016-05-31T02:16:37Z","updated_at":"2016-05-31T02:16:37Z","body":"**(Warning: I haven't read *any* of the comments in this issue).** Here's an attempt at defining concrete *short-term* security of a difficulty adjustment algorithm. It's too general to be applicable, I just wrote it to help myself understand the problem and bring out all of the minutia. I don't suggest we follow the path of trying to prove security -- we don't have the bandwidth -- but this might be useful for thinking about the problem.\r\n\r\nThe idea is we assume there's some \"core\" of the network whose hashrate never changes, not even in response to an adversary's actions. All change in hashrate is lumped into an adversary who can, at each block, decide how much of it to apply to try and win the next block. Their hashrate is assumed to be less than the \"core\" hash rate, i.e. the real-life adversary's maximum hashrate plus hashrate that fluctuates \"benignly\" makes up less than 50% of the network (otherwise there are worse problems).\r\n\r\nDefinition 1: A **difficulty adjustment algorithm** D of window size w is a map R<sup>{w+1}</sup> x R<sup>w</sup> -> R. The first parameter is the past w+1 timestamps and the second is the past w difficulties. It returns the next block's difficulty.\r\n\r\nDefinition 2: A **difficulty adversary** is a tuple (s, S, A) where S is a set of adversary states, s is the initial state, A<sub>r</sub> is a real number in [0, 1], A is a map S x R<sup>w</sup> x R<sup>w</sup> x {0,1}<sup>w</sup> -> S x R x R producing the next adversary state, the amount of hashrate they're going to devote to this block, and what they will chose as the timestamp if they win the block from their current state, the past w timestamps and difficulties, and the knowledge of which blocks they won in the past.\r\n\r\nDefinition 3: A difficulty adjustment algorithm DiffAlg is (p, WINS)-secure if no difficulty adversary (s, S, A) wins the following game with probability greater than p. This should look awfully similar to the simulation code:\r\n\r\n```\r\nconst CORE_RATE = 1.0;\r\nconst TARGET_TIME = 1.0;\r\n// The network starts out without any adversarial hash rate.\r\nT = [... w copies of CORE_RATE...];\r\nD = [... w copies of CORE_RATE*TARGET_TIME...];\r\nC = [... w copies of 0...];\r\nwall_clock_time = 0.0;\r\n\r\na_state = s;\r\n\r\nloop 2*w times {\r\n    // Adversary decides how much hashrate to use on this block\r\n    // and what they'll put as the timestamp if they win it.\r\n    (a_state, a_r, a_t) = A(a_state, T, D, C); // TODO\r\n    assert(a_r <= 1.0);\r\n\r\n    // Calculate the expected time for someone to solve this block.\r\n    expected_time = D.last() / (a_r + CORE_RATE);\r\n    // Assumption: The adversary broadcasts their won block right away.\r\n    wall_clock_time += expected_time;\r\n\r\n    if (rand_real(0.0, a_r + CORE_RATE) <= a_r) {\r\n        // Adversary wins this block, they can use an arbitrary timestamp.\r\n        T.push(a_t); // .push() drops the oldest to make room for the one being added\r\n    } else {\r\n        // Adversary loses, timestamp for this block is correct.\r\n        T.push(wall_clock_time);\r\n    }\r\n\r\n    // Update the difficulty.\r\n    // C is not an input because nobody except the adversary knows which blocks the adversary won.\r\n    D.push(DiffAlg(T, D));\r\n}\r\n\r\n// TODO: define winning criteria.\r\nreturn WINS(T, D);\r\n```\r\n\r\nProblem 1: I haven't defined the criteria for winning! This should be defined to check some combination of *fairness*, where for all users the probability of winning the next block is close to their share of the overall hashrate as well as *availability* which checks that the timestamps aren't too far off from what they should be with the right target time (in the above pseudocode it's 1.0). This could be as simple as summing the absolute value differences from the target time and ensuring it's below some threshold.\r\n\r\nProblem 2: This definition conflates window size with the duration of time you want to define security properties over.\r\n\r\nProblem 3: The 2*w block count is arbitrary. An adversary that takes advantage of resonance in the network or something like that might be able to do better with more time.\r\n\r\nProblem 4: The game is way too complicated to reason about. Can it be simplified? Perhaps make adversaries stateless (get rid of s and S) or non-adaptive (make them output the next w hashrates and timestamps all at once).\r\n\r\nProblem 5: In reality, the \"core\" will respond to the adversary's actions (e.g. the death spiral), but modeling that would be super complicated. Hopefully w is small enough that the core's response is negligible over that time period.\r\n\r\n"}}
{"actor":{"display_login":"defuse"}}