{"action":"created","issue":{"url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508","labels_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508/labels{/name}","comments_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508/comments","events_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508/events","html_url":"https://github.com/bitcoin/bitcoin/pull/6508","id":98795410,"number":6508,"title":"Switch to a constant-space Merkle root/branch algorithm.","user":{"login":"sipa","id":548488,"avatar_url":"https://avatars.githubusercontent.com/u/548488?v=3","gravatar_id":"","url":"https://api.github.com/users/sipa","html_url":"https://github.com/sipa","followers_url":"https://api.github.com/users/sipa/followers","following_url":"https://api.github.com/users/sipa/following{/other_user}","gists_url":"https://api.github.com/users/sipa/gists{/gist_id}","starred_url":"https://api.github.com/users/sipa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sipa/subscriptions","organizations_url":"https://api.github.com/users/sipa/orgs","repos_url":"https://api.github.com/users/sipa/repos","events_url":"https://api.github.com/users/sipa/events{/privacy}","received_events_url":"https://api.github.com/users/sipa/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/bitcoin/bitcoin/labels/Validation","name":"Validation","color":"6060aa"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/bitcoin/bitcoin/milestones/19","html_url":"https://github.com/bitcoin/bitcoin/milestones/0.12.0","labels_url":"https://api.github.com/repos/bitcoin/bitcoin/milestones/19/labels","id":1092458,"number":19,"title":"0.12.0","description":"","creator":{"login":"laanwj","id":126646,"avatar_url":"https://avatars.githubusercontent.com/u/126646?v=3","gravatar_id":"","url":"https://api.github.com/users/laanwj","html_url":"https://github.com/laanwj","followers_url":"https://api.github.com/users/laanwj/followers","following_url":"https://api.github.com/users/laanwj/following{/other_user}","gists_url":"https://api.github.com/users/laanwj/gists{/gist_id}","starred_url":"https://api.github.com/users/laanwj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/laanwj/subscriptions","organizations_url":"https://api.github.com/users/laanwj/orgs","repos_url":"https://api.github.com/users/laanwj/repos","events_url":"https://api.github.com/users/laanwj/events{/privacy}","received_events_url":"https://api.github.com/users/laanwj/received_events","type":"User","site_admin":false},"open_issues":11,"closed_issues":20,"state":"open","created_at":"2015-05-01T12:31:35Z","updated_at":"2015-11-26T07:43:50Z","due_on":null,"closed_at":null},"comments":18,"created_at":"2015-08-03T17:08:10Z","updated_at":"2015-11-26T11:09:44Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/bitcoin/bitcoin/pulls/6508","html_url":"https://github.com/bitcoin/bitcoin/pull/6508","diff_url":"https://github.com/bitcoin/bitcoin/pull/6508.diff","patch_url":"https://github.com/bitcoin/bitcoin/pull/6508.patch"},"body":"This switches the Merkle tree logic for blocks to one that runs in logspace (effectively constant space, with a limit of 2^32 leaves). The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations:\r\n* Verifies that the old code and new code agree for the Merkle root.\r\n* Verifies that the old code and new code agree for the Merkle branch.\r\n* Verifies that the computed Merkle branch is valid.\r\n* Verifies that mutations don't change the Merkle root.\r\n* Verifies that mutations are correctly detected.\r\n\r\nAdvantages:\r\n* Removes the need for vMerkleTree (a validation-related data structure) from CBlock (a primitive data structure).\r\n* Is slightly faster due to better memory locality and avoiding all heap overhead.\r\n\r\nDisadvantages:\r\n* Requires recomputing the Merkle tree any time a Merkle branch is needed. The wallet depends on this any time a transaction is added. This is not technically necessary, however.\r\n* Longer and harder to read code.\r\n\r\nThe code remains in primitives/block for now. This is not optimal, as one of the purposes is disentangling the Merkle calculation logic from the primitive data structures. TBD."},"comment":{"url":"https://api.github.com/repos/bitcoin/bitcoin/issues/comments/159884260","html_url":"https://github.com/bitcoin/bitcoin/pull/6508#issuecomment-159884260","issue_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508","id":159884260,"user":{"login":"jtimon","id":1008458,"avatar_url":"https://avatars.githubusercontent.com/u/1008458?v=3","gravatar_id":"","url":"https://api.github.com/users/jtimon","html_url":"https://github.com/jtimon","followers_url":"https://api.github.com/users/jtimon/followers","following_url":"https://api.github.com/users/jtimon/following{/other_user}","gists_url":"https://api.github.com/users/jtimon/gists{/gist_id}","starred_url":"https://api.github.com/users/jtimon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jtimon/subscriptions","organizations_url":"https://api.github.com/users/jtimon/orgs","repos_url":"https://api.github.com/users/jtimon/repos","events_url":"https://api.github.com/users/jtimon/events{/privacy}","received_events_url":"https://api.github.com/users/jtimon/received_events","type":"User","site_admin":false},"created_at":"2015-11-26T11:09:44Z","updated_at":"2015-11-26T11:09:44Z","body":"General data structure or not, this is used in checkBlock and will therefore be part of VerifyBlock and the complete libconsensus too.\r\nOnce it is complete, if we want to separate it as a subtree with its own repo, we will have to put all the files in the same dir (ie src/consensus) first."}}