{"action":"created","issue":{"url":"https://api.github.com/repos/blockstack/blockstore/issues/146","labels_url":"https://api.github.com/repos/blockstack/blockstore/issues/146/labels{/name}","comments_url":"https://api.github.com/repos/blockstack/blockstore/issues/146/comments","events_url":"https://api.github.com/repos/blockstack/blockstore/issues/146/events","html_url":"https://github.com/blockstack/blockstore/issues/146","id":109404684,"number":146,"title":"suggestion: use a merkle skip list to quickly calculate rolling consensus hashes and support quick querying","user":{"login":"shea256","id":994646,"avatar_url":"https://avatars.githubusercontent.com/u/994646?v=3","gravatar_id":"","url":"https://api.github.com/users/shea256","html_url":"https://github.com/shea256","followers_url":"https://api.github.com/users/shea256/followers","following_url":"https://api.github.com/users/shea256/following{/other_user}","gists_url":"https://api.github.com/users/shea256/gists{/gist_id}","starred_url":"https://api.github.com/users/shea256/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shea256/subscriptions","organizations_url":"https://api.github.com/users/shea256/orgs","repos_url":"https://api.github.com/users/shea256/repos","events_url":"https://api.github.com/users/shea256/events{/privacy}","received_events_url":"https://api.github.com/users/shea256/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/blockstack/blockstore/labels/Fixed%20in%20the%20next%20release","name":"Fixed in the next release","color":"fbca04"},{"url":"https://api.github.com/repos/blockstack/blockstore/labels/in-progress","name":"in-progress","color":"cccccc"},{"url":"https://api.github.com/repos/blockstack/blockstore/labels/protocol","name":"protocol","color":"207de5"}],"state":"closed","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/blockstack/blockstore/milestones/1","html_url":"https://github.com/blockstack/blockstore/milestones/Blockstore%20v0.1.0","labels_url":"https://api.github.com/repos/blockstack/blockstore/milestones/1/labels","id":1116355,"number":1,"title":"Blockstore v0.1.0","description":"First production-ready release of Blockstore, since initial launch (at v0.0.3)","creator":{"login":"muneeb-ali","id":669932,"avatar_url":"https://avatars.githubusercontent.com/u/669932?v=3","gravatar_id":"","url":"https://api.github.com/users/muneeb-ali","html_url":"https://github.com/muneeb-ali","followers_url":"https://api.github.com/users/muneeb-ali/followers","following_url":"https://api.github.com/users/muneeb-ali/following{/other_user}","gists_url":"https://api.github.com/users/muneeb-ali/gists{/gist_id}","starred_url":"https://api.github.com/users/muneeb-ali/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/muneeb-ali/subscriptions","organizations_url":"https://api.github.com/users/muneeb-ali/orgs","repos_url":"https://api.github.com/users/muneeb-ali/repos","events_url":"https://api.github.com/users/muneeb-ali/events{/privacy}","received_events_url":"https://api.github.com/users/muneeb-ali/received_events","type":"User","site_admin":false},"open_issues":8,"closed_issues":6,"state":"open","created_at":"2015-05-18T18:49:06Z","updated_at":"2015-11-10T22:19:08Z","due_on":"2015-11-02T08:00:00Z","closed_at":null},"comments":4,"created_at":"2015-10-01T23:31:41Z","updated_at":"2015-11-10T22:19:08Z","closed_at":"2015-11-10T22:19:08Z","body":"The goal here is to calculate consensus hashes from all previous consensus hashes in O(log(T) + n) instead of O(T) where T is the number of blocks (and thus consensus hashes) since the beginning of time and n is the number of name operations in the current block.\r\n\r\nSaving consensus hashes at all points in time is valuable so that one can easily validate all of the operations that were seen at time t. This is really nice for lightweight node support. Plus we've already established from previous discussions that saving all name operations at every point in time is valuable for verifying a database one gets from a peer for bootstrapping purposes.\r\n\r\nHere's how we can calculate the consensus hashes...\r\n\r\nI define a merkle skip list as a rolling merkle root calculation, where at time t the merkle tree is built from the data added at time t, plus a sublinear set of all previous merkle roots. Then the newly calculated merkle root is saved for future calculations.\r\n\r\nAs an example, if we define the first seen blockstore block as t=0, then the consensus hashes for t=0 to t=7 can be saved, and the hash at t=7 could be calculated by combining all of the name operations at time t=7 with the consensus hashes at times t=6, t=4, and t=0.\r\n\r\nHere is a full table of all the merkle tree calculations at every step through t=7:\r\n\r\nBlock # | Merkle Tree Contents\r\n--- | ---\r\n0 | block 0 ops\r\n1 | block 1 ops, hash from block 0\r\n2 | block 2 ops, hashes from block 1\r\n3 | block 3 ops, hashes from blocks 2 + 0\r\n4 | block 4 ops, hashes from blocks 3 + 1\r\n5 | block 5 ops, hashes from blocks 4 + 2\r\n6 | block 6 ops, hashes from blocks 5 + 3\r\n7 | block 7 ops, hashes from blocks 6 + 4 + 0\r\n15 | block 15 ops, hashes from blocks 14 + 12 + 8 + 0\r\n31 | block 31 ops, hashes from blocks 30 + 28 + 24 + 16 + 0\r\n\r\nNote that the merkle root for any given block validates all merkle roots from the beginning of time, but only requires O(log(T) + n) calculations, as mentioned above. We can assume that T will grow into the hundreds of thousands while n will likely remain in the hundreds or thousands (given limits on block size).\r\n\r\nAlso note that if we have a trusted consensus hash for block 7 and ask an untrusted node for the proof that a given operation in block 5, we only need to be served the block ops from blocks 7 and 5. We don't need to see all previous block ops.\r\n\r\nI'm not sure what to call this data structure but I'll call it a merkle skip list for now. Other thoughts on this are welcome."},"comment":{"url":"https://api.github.com/repos/blockstack/blockstore/issues/comments/155585885","html_url":"https://github.com/blockstack/blockstore/issues/146#issuecomment-155585885","issue_url":"https://api.github.com/repos/blockstack/blockstore/issues/146","id":155585885,"user":{"login":"jcnelson","id":459947,"avatar_url":"https://avatars.githubusercontent.com/u/459947?v=3","gravatar_id":"","url":"https://api.github.com/users/jcnelson","html_url":"https://github.com/jcnelson","followers_url":"https://api.github.com/users/jcnelson/followers","following_url":"https://api.github.com/users/jcnelson/following{/other_user}","gists_url":"https://api.github.com/users/jcnelson/gists{/gist_id}","starred_url":"https://api.github.com/users/jcnelson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jcnelson/subscriptions","organizations_url":"https://api.github.com/users/jcnelson/orgs","repos_url":"https://api.github.com/users/jcnelson/repos","events_url":"https://api.github.com/users/jcnelson/events{/privacy}","received_events_url":"https://api.github.com/users/jcnelson/received_events","type":"User","site_admin":false},"created_at":"2015-11-10T22:19:08Z","updated_at":"2015-11-10T22:19:08Z","body":"Added"}}