{"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":null,"comments":8,"created_at":"2015-08-03T17:08:10Z","updated_at":"2015-08-11T08:52:36Z","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/129775458","html_url":"https://github.com/bitcoin/bitcoin/pull/6508#issuecomment-129775458","issue_url":"https://api.github.com/repos/bitcoin/bitcoin/issues/6508","id":129775458,"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},"created_at":"2015-08-11T08:52:36Z","updated_at":"2015-08-11T08:52:36Z","body":"There is definitely a wallet performance downside, as you need to recompute\nthe merkle tree for every wallet transaction. If it looked like I claimed\notherwise, sorry. It's only an individual merkle root/branch computation\nthat is made faster.\n\nI'll delay this until we remove the call from the wallet to conpute\nbranches.\n"}}