{"action":"created","comment":{"url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/comments/51778951","id":51778951,"diff_hunk":"@@ -3,378 +3,20 @@\n // given root, and for verifying proofs that a piece of data is in a Merkle\n // tree of a given root. The tree is implemented according to the specification\n // for Merkle trees provided in RFC 6962.\n+//\n+// Package merkletree also supports building roots and proofs from cached\n+// subroots of the Merkle tree. For example, a large file could be cached by\n+// building the Merkle root for each 4MB sector and remembering the Merkle\n+// roots of each sector. Using a cached tree, the Merkle root of the whole file\n+// can be computed by passing the cached tree each of the roots of the 4MB\n+// sector. Building proofs using these cached roots is also supported. A proof\n+// must be build within the target sector using a normal Tree, requiring the","path":"merkletree.go","position":11,"original_position":11,"commit_id":"aaf926421721015f0d9c6a1bbee8761f51a58b1b","original_commit_id":"aaf926421721015f0d9c6a1bbee8761f51a58b1b","user":{"login":"lukechampine","id":3344749,"avatar_url":"https://avatars.githubusercontent.com/u/3344749?v=3","gravatar_id":"","url":"https://api.github.com/users/lukechampine","html_url":"https://github.com/lukechampine","followers_url":"https://api.github.com/users/lukechampine/followers","following_url":"https://api.github.com/users/lukechampine/following{/other_user}","gists_url":"https://api.github.com/users/lukechampine/gists{/gist_id}","starred_url":"https://api.github.com/users/lukechampine/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lukechampine/subscriptions","organizations_url":"https://api.github.com/users/lukechampine/orgs","repos_url":"https://api.github.com/users/lukechampine/repos","events_url":"https://api.github.com/users/lukechampine/events{/privacy}","received_events_url":"https://api.github.com/users/lukechampine/received_events","type":"User","site_admin":false},"body":"spellcheck doesn't catch grammatical errors :P","created_at":"2016-02-03T20:05:09Z","updated_at":"2016-02-03T20:05:09Z","html_url":"https://github.com/NebulousLabs/merkletree/pull/12#discussion_r51778951","pull_request_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12","_links":{"self":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/comments/51778951"},"html":{"href":"https://github.com/NebulousLabs/merkletree/pull/12#discussion_r51778951"},"pull_request":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12"}}},"pull_request":{"url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12","id":57969999,"html_url":"https://github.com/NebulousLabs/merkletree/pull/12","diff_url":"https://github.com/NebulousLabs/merkletree/pull/12.diff","patch_url":"https://github.com/NebulousLabs/merkletree/pull/12.patch","issue_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/12","number":12,"state":"open","locked":false,"title":"Cached tree","user":{"login":"DavidVorick","id":2316841,"avatar_url":"https://avatars.githubusercontent.com/u/2316841?v=3","gravatar_id":"","url":"https://api.github.com/users/DavidVorick","html_url":"https://github.com/DavidVorick","followers_url":"https://api.github.com/users/DavidVorick/followers","following_url":"https://api.github.com/users/DavidVorick/following{/other_user}","gists_url":"https://api.github.com/users/DavidVorick/gists{/gist_id}","starred_url":"https://api.github.com/users/DavidVorick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DavidVorick/subscriptions","organizations_url":"https://api.github.com/users/DavidVorick/orgs","repos_url":"https://api.github.com/users/DavidVorick/repos","events_url":"https://api.github.com/users/DavidVorick/events{/privacy}","received_events_url":"https://api.github.com/users/DavidVorick/received_events","type":"User","site_admin":false},"body":"Did some housekeeping, then added functionality to support cached merkle trees.\r\n\r\nI need to add more documentation on their usage, and probably for the package in general.\r\n\r\nBasically, to make a cached merkle tree, you get the merkle root of a file every X segments, where X is a power of 2. The cached merkle tree needs to have every element at the same level, and every element needs to be complete.\r\n\r\nSo, in  the context of Sia, this means that if we're caching at the 4mb level, every single item thrown into a cached merkle tree needs to be fully padded to 4mb.\r\n\r\nSo, you have a bunch of roots. Then you can throw the roots into the cached tree and you'll get the same merkle root that you would have if you had just taken the merkle root of the whole file all at once.\r\n\r\nThis means it's easy to change or delete stuff. Just modify or toss the 4mb cached node that you don't want anymore and then recompute the root using the cached nodes you have saved. No need to have the whole original file either, just need to have the cached nodes and then the data that's being changed.\r\n\r\nAND, this supports creating storage proof from cached trees too. It's a multi step process though. First, you have to create a storage proof in the 4mb subtree, and then you need to create the storage proof from the cached nodes. You need to hash the whole 4mb structure, and then you need to hash all the cached nodes, but this is probably 100,000x faster (that's not an exaggeration) than hashing the whole file for sufficiently large files.\r\n\r\nI didn't spell check this PR, it's 6am and I'm going to bed.","created_at":"2016-02-02T10:53:18Z","updated_at":"2016-02-03T20:05:09Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0a2bad3e963c1451f9579874ef1e8c1325c7e070","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12/commits","review_comments_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12/comments","review_comment_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/comments{/number}","comments_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/12/comments","statuses_url":"https://api.github.com/repos/NebulousLabs/merkletree/statuses/aaf926421721015f0d9c6a1bbee8761f51a58b1b","head":{"label":"NebulousLabs:cached-tree","ref":"cached-tree","sha":"aaf926421721015f0d9c6a1bbee8761f51a58b1b","user":{"login":"NebulousLabs","id":7471422,"avatar_url":"https://avatars.githubusercontent.com/u/7471422?v=3","gravatar_id":"","url":"https://api.github.com/users/NebulousLabs","html_url":"https://github.com/NebulousLabs","followers_url":"https://api.github.com/users/NebulousLabs/followers","following_url":"https://api.github.com/users/NebulousLabs/following{/other_user}","gists_url":"https://api.github.com/users/NebulousLabs/gists{/gist_id}","starred_url":"https://api.github.com/users/NebulousLabs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NebulousLabs/subscriptions","organizations_url":"https://api.github.com/users/NebulousLabs/orgs","repos_url":"https://api.github.com/users/NebulousLabs/repos","events_url":"https://api.github.com/users/NebulousLabs/events{/privacy}","received_events_url":"https://api.github.com/users/NebulousLabs/received_events","type":"Organization","site_admin":false},"repo":{"id":31486458,"name":"merkletree","full_name":"NebulousLabs/merkletree","owner":{"login":"NebulousLabs","id":7471422,"avatar_url":"https://avatars.githubusercontent.com/u/7471422?v=3","gravatar_id":"","url":"https://api.github.com/users/NebulousLabs","html_url":"https://github.com/NebulousLabs","followers_url":"https://api.github.com/users/NebulousLabs/followers","following_url":"https://api.github.com/users/NebulousLabs/following{/other_user}","gists_url":"https://api.github.com/users/NebulousLabs/gists{/gist_id}","starred_url":"https://api.github.com/users/NebulousLabs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NebulousLabs/subscriptions","organizations_url":"https://api.github.com/users/NebulousLabs/orgs","repos_url":"https://api.github.com/users/NebulousLabs/repos","events_url":"https://api.github.com/users/NebulousLabs/events{/privacy}","received_events_url":"https://api.github.com/users/NebulousLabs/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/NebulousLabs/merkletree","description":"Calculate merkle roots, build and verify proofs that data is in a merkle tree.","fork":false,"url":"https://api.github.com/repos/NebulousLabs/merkletree","forks_url":"https://api.github.com/repos/NebulousLabs/merkletree/forks","keys_url":"https://api.github.com/repos/NebulousLabs/merkletree/keys{/key_id}","collaborators_url":"https://api.github.com/repos/NebulousLabs/merkletree/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/NebulousLabs/merkletree/teams","hooks_url":"https://api.github.com/repos/NebulousLabs/merkletree/hooks","issue_events_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/events{/number}","events_url":"https://api.github.com/repos/NebulousLabs/merkletree/events","assignees_url":"https://api.github.com/repos/NebulousLabs/merkletree/assignees{/user}","branches_url":"https://api.github.com/repos/NebulousLabs/merkletree/branches{/branch}","tags_url":"https://api.github.com/repos/NebulousLabs/merkletree/tags","blobs_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/refs{/sha}","trees_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/trees{/sha}","statuses_url":"https://api.github.com/repos/NebulousLabs/merkletree/statuses/{sha}","languages_url":"https://api.github.com/repos/NebulousLabs/merkletree/languages","stargazers_url":"https://api.github.com/repos/NebulousLabs/merkletree/stargazers","contributors_url":"https://api.github.com/repos/NebulousLabs/merkletree/contributors","subscribers_url":"https://api.github.com/repos/NebulousLabs/merkletree/subscribers","subscription_url":"https://api.github.com/repos/NebulousLabs/merkletree/subscription","commits_url":"https://api.github.com/repos/NebulousLabs/merkletree/commits{/sha}","git_commits_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/commits{/sha}","comments_url":"https://api.github.com/repos/NebulousLabs/merkletree/comments{/number}","issue_comment_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/comments{/number}","contents_url":"https://api.github.com/repos/NebulousLabs/merkletree/contents/{+path}","compare_url":"https://api.github.com/repos/NebulousLabs/merkletree/compare/{base}...{head}","merges_url":"https://api.github.com/repos/NebulousLabs/merkletree/merges","archive_url":"https://api.github.com/repos/NebulousLabs/merkletree/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/NebulousLabs/merkletree/downloads","issues_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues{/number}","pulls_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls{/number}","milestones_url":"https://api.github.com/repos/NebulousLabs/merkletree/milestones{/number}","notifications_url":"https://api.github.com/repos/NebulousLabs/merkletree/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/NebulousLabs/merkletree/labels{/name}","releases_url":"https://api.github.com/repos/NebulousLabs/merkletree/releases{/id}","deployments_url":"https://api.github.com/repos/NebulousLabs/merkletree/deployments","created_at":"2015-03-01T04:13:48Z","updated_at":"2015-12-08T15:33:11Z","pushed_at":"2016-02-03T01:26:54Z","git_url":"git://github.com/NebulousLabs/merkletree.git","ssh_url":"git@github.com:NebulousLabs/merkletree.git","clone_url":"https://github.com/NebulousLabs/merkletree.git","svn_url":"https://github.com/NebulousLabs/merkletree","homepage":null,"size":86,"stargazers_count":6,"watchers_count":6,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":2,"forks":1,"open_issues":2,"watchers":6,"default_branch":"master"}},"base":{"label":"NebulousLabs:master","ref":"master","sha":"3b61bc96e0898ee645bc8b52e5db679d4f2ad20f","user":{"login":"NebulousLabs","id":7471422,"avatar_url":"https://avatars.githubusercontent.com/u/7471422?v=3","gravatar_id":"","url":"https://api.github.com/users/NebulousLabs","html_url":"https://github.com/NebulousLabs","followers_url":"https://api.github.com/users/NebulousLabs/followers","following_url":"https://api.github.com/users/NebulousLabs/following{/other_user}","gists_url":"https://api.github.com/users/NebulousLabs/gists{/gist_id}","starred_url":"https://api.github.com/users/NebulousLabs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NebulousLabs/subscriptions","organizations_url":"https://api.github.com/users/NebulousLabs/orgs","repos_url":"https://api.github.com/users/NebulousLabs/repos","events_url":"https://api.github.com/users/NebulousLabs/events{/privacy}","received_events_url":"https://api.github.com/users/NebulousLabs/received_events","type":"Organization","site_admin":false},"repo":{"id":31486458,"name":"merkletree","full_name":"NebulousLabs/merkletree","owner":{"login":"NebulousLabs","id":7471422,"avatar_url":"https://avatars.githubusercontent.com/u/7471422?v=3","gravatar_id":"","url":"https://api.github.com/users/NebulousLabs","html_url":"https://github.com/NebulousLabs","followers_url":"https://api.github.com/users/NebulousLabs/followers","following_url":"https://api.github.com/users/NebulousLabs/following{/other_user}","gists_url":"https://api.github.com/users/NebulousLabs/gists{/gist_id}","starred_url":"https://api.github.com/users/NebulousLabs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NebulousLabs/subscriptions","organizations_url":"https://api.github.com/users/NebulousLabs/orgs","repos_url":"https://api.github.com/users/NebulousLabs/repos","events_url":"https://api.github.com/users/NebulousLabs/events{/privacy}","received_events_url":"https://api.github.com/users/NebulousLabs/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/NebulousLabs/merkletree","description":"Calculate merkle roots, build and verify proofs that data is in a merkle tree.","fork":false,"url":"https://api.github.com/repos/NebulousLabs/merkletree","forks_url":"https://api.github.com/repos/NebulousLabs/merkletree/forks","keys_url":"https://api.github.com/repos/NebulousLabs/merkletree/keys{/key_id}","collaborators_url":"https://api.github.com/repos/NebulousLabs/merkletree/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/NebulousLabs/merkletree/teams","hooks_url":"https://api.github.com/repos/NebulousLabs/merkletree/hooks","issue_events_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/events{/number}","events_url":"https://api.github.com/repos/NebulousLabs/merkletree/events","assignees_url":"https://api.github.com/repos/NebulousLabs/merkletree/assignees{/user}","branches_url":"https://api.github.com/repos/NebulousLabs/merkletree/branches{/branch}","tags_url":"https://api.github.com/repos/NebulousLabs/merkletree/tags","blobs_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/refs{/sha}","trees_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/trees{/sha}","statuses_url":"https://api.github.com/repos/NebulousLabs/merkletree/statuses/{sha}","languages_url":"https://api.github.com/repos/NebulousLabs/merkletree/languages","stargazers_url":"https://api.github.com/repos/NebulousLabs/merkletree/stargazers","contributors_url":"https://api.github.com/repos/NebulousLabs/merkletree/contributors","subscribers_url":"https://api.github.com/repos/NebulousLabs/merkletree/subscribers","subscription_url":"https://api.github.com/repos/NebulousLabs/merkletree/subscription","commits_url":"https://api.github.com/repos/NebulousLabs/merkletree/commits{/sha}","git_commits_url":"https://api.github.com/repos/NebulousLabs/merkletree/git/commits{/sha}","comments_url":"https://api.github.com/repos/NebulousLabs/merkletree/comments{/number}","issue_comment_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues/comments{/number}","contents_url":"https://api.github.com/repos/NebulousLabs/merkletree/contents/{+path}","compare_url":"https://api.github.com/repos/NebulousLabs/merkletree/compare/{base}...{head}","merges_url":"https://api.github.com/repos/NebulousLabs/merkletree/merges","archive_url":"https://api.github.com/repos/NebulousLabs/merkletree/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/NebulousLabs/merkletree/downloads","issues_url":"https://api.github.com/repos/NebulousLabs/merkletree/issues{/number}","pulls_url":"https://api.github.com/repos/NebulousLabs/merkletree/pulls{/number}","milestones_url":"https://api.github.com/repos/NebulousLabs/merkletree/milestones{/number}","notifications_url":"https://api.github.com/repos/NebulousLabs/merkletree/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/NebulousLabs/merkletree/labels{/name}","releases_url":"https://api.github.com/repos/NebulousLabs/merkletree/releases{/id}","deployments_url":"https://api.github.com/repos/NebulousLabs/merkletree/deployments","created_at":"2015-03-01T04:13:48Z","updated_at":"2015-12-08T15:33:11Z","pushed_at":"2016-02-03T01:26:54Z","git_url":"git://github.com/NebulousLabs/merkletree.git","ssh_url":"git@github.com:NebulousLabs/merkletree.git","clone_url":"https://github.com/NebulousLabs/merkletree.git","svn_url":"https://github.com/NebulousLabs/merkletree","homepage":null,"size":86,"stargazers_count":6,"watchers_count":6,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":2,"forks":1,"open_issues":2,"watchers":6,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12"},"html":{"href":"https://github.com/NebulousLabs/merkletree/pull/12"},"issue":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/issues/12"},"comments":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/issues/12/comments"},"review_comments":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12/comments"},"review_comment":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/pulls/12/commits"},"statuses":{"href":"https://api.github.com/repos/NebulousLabs/merkletree/statuses/aaf926421721015f0d9c6a1bbee8761f51a58b1b"}}}}