{"action":"created","issue":{"url":"https://api.github.com/repos/mimblewimble/grin/issues/797","repository_url":"https://api.github.com/repos/mimblewimble/grin","labels_url":"https://api.github.com/repos/mimblewimble/grin/issues/797/labels{/name}","comments_url":"https://api.github.com/repos/mimblewimble/grin/issues/797/comments","events_url":"https://api.github.com/repos/mimblewimble/grin/issues/797/events","html_url":"https://github.com/mimblewimble/grin/issues/797","id":305957523,"number":797,"title":"Reduce size of Merkle proofs (we can derive pos for each path sibling)","user":{"login":"antiochp","id":30642645,"avatar_url":"https://avatars2.githubusercontent.com/u/30642645?v=4","gravatar_id":"","url":"https://api.github.com/users/antiochp","html_url":"https://github.com/antiochp","followers_url":"https://api.github.com/users/antiochp/followers","following_url":"https://api.github.com/users/antiochp/following{/other_user}","gists_url":"https://api.github.com/users/antiochp/gists{/gist_id}","starred_url":"https://api.github.com/users/antiochp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/antiochp/subscriptions","organizations_url":"https://api.github.com/users/antiochp/orgs","repos_url":"https://api.github.com/users/antiochp/repos","events_url":"https://api.github.com/users/antiochp/events{/privacy}","received_events_url":"https://api.github.com/users/antiochp/received_events","type":"User","site_admin":false},"labels":[{"id":465821397,"url":"https://api.github.com/repos/mimblewimble/grin/labels/enhancement","name":"enhancement","color":"84b6eb","default":true},{"id":465821398,"url":"https://api.github.com/repos/mimblewimble/grin/labels/help%20wanted","name":"help wanted","color":"128A0C","default":true}],"state":"open","locked":false,"assignee":{"login":"tromp","id":2347227,"avatar_url":"https://avatars2.githubusercontent.com/u/2347227?v=4","gravatar_id":"","url":"https://api.github.com/users/tromp","html_url":"https://github.com/tromp","followers_url":"https://api.github.com/users/tromp/followers","following_url":"https://api.github.com/users/tromp/following{/other_user}","gists_url":"https://api.github.com/users/tromp/gists{/gist_id}","starred_url":"https://api.github.com/users/tromp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tromp/subscriptions","organizations_url":"https://api.github.com/users/tromp/orgs","repos_url":"https://api.github.com/users/tromp/repos","events_url":"https://api.github.com/users/tromp/events{/privacy}","received_events_url":"https://api.github.com/users/tromp/received_events","type":"User","site_admin":false},"assignees":[{"login":"tromp","id":2347227,"avatar_url":"https://avatars2.githubusercontent.com/u/2347227?v=4","gravatar_id":"","url":"https://api.github.com/users/tromp","html_url":"https://github.com/tromp","followers_url":"https://api.github.com/users/tromp/followers","following_url":"https://api.github.com/users/tromp/following{/other_user}","gists_url":"https://api.github.com/users/tromp/gists{/gist_id}","starred_url":"https://api.github.com/users/tromp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tromp/subscriptions","organizations_url":"https://api.github.com/users/tromp/orgs","repos_url":"https://api.github.com/users/tromp/repos","events_url":"https://api.github.com/users/tromp/events{/privacy}","received_events_url":"https://api.github.com/users/tromp/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/mimblewimble/grin/milestones/3","html_url":"https://github.com/mimblewimble/grin/milestone/3","labels_url":"https://api.github.com/repos/mimblewimble/grin/milestones/3/labels","id":2585870,"number":3,"title":"Testnet2","description":"Equivalent of a beta. Almost ready to release, should be feature complete and undergoing more testing or audits.","creator":{"login":"ignopeverell","id":22927561,"avatar_url":"https://avatars1.githubusercontent.com/u/22927561?v=4","gravatar_id":"","url":"https://api.github.com/users/ignopeverell","html_url":"https://github.com/ignopeverell","followers_url":"https://api.github.com/users/ignopeverell/followers","following_url":"https://api.github.com/users/ignopeverell/following{/other_user}","gists_url":"https://api.github.com/users/ignopeverell/gists{/gist_id}","starred_url":"https://api.github.com/users/ignopeverell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ignopeverell/subscriptions","organizations_url":"https://api.github.com/users/ignopeverell/orgs","repos_url":"https://api.github.com/users/ignopeverell/repos","events_url":"https://api.github.com/users/ignopeverell/events{/privacy}","received_events_url":"https://api.github.com/users/ignopeverell/received_events","type":"User","site_admin":false},"open_issues":7,"closed_issues":55,"state":"open","created_at":"2017-06-15T20:42:33Z","updated_at":"2018-03-23T10:34:55Z","due_on":null,"closed_at":null},"comments":37,"created_at":"2018-03-16T14:51:01Z","updated_at":"2018-03-24T09:42:38Z","closed_at":null,"author_association":"MEMBER","body":"Pretty sure we can avoid storing the pos for each node in the path in the Merkle proof.\r\n\r\nFor a given MMR size the pos are all known ahead of time.\r\n\r\nI think if we know the pos of the node we care about and the (unpruned) size of the MMR then we have everything we need to determine the pos of each sibling in the path.\r\n\r\nWe would presumably do something like -\r\n\r\n* for a given node pos -\r\n  * find the parent and the sibling pos (which we know how to do, via family())\r\n  * repeat up to the peak (staying inside the overall MMR based on unpruned size)\r\n\r\nSo as an alternative to storing the pos for each sibling in path - we can simply store the pos of the single leaf node and the total unpruned size of the MMR.\r\n\r\n👉 Might be a good idea to try and get this in before testnet2 to avoid having to think about backward compatibility...\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/mimblewimble/grin/issues/comments/375861402","html_url":"https://github.com/mimblewimble/grin/issues/797#issuecomment-375861402","issue_url":"https://api.github.com/repos/mimblewimble/grin/issues/797","id":375861402,"user":{"login":"tromp","id":2347227,"avatar_url":"https://avatars2.githubusercontent.com/u/2347227?v=4","gravatar_id":"","url":"https://api.github.com/users/tromp","html_url":"https://github.com/tromp","followers_url":"https://api.github.com/users/tromp/followers","following_url":"https://api.github.com/users/tromp/following{/other_user}","gists_url":"https://api.github.com/users/tromp/gists{/gist_id}","starred_url":"https://api.github.com/users/tromp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tromp/subscriptions","organizations_url":"https://api.github.com/users/tromp/orgs","repos_url":"https://api.github.com/users/tromp/repos","events_url":"https://api.github.com/users/tromp/events{/privacy}","received_events_url":"https://api.github.com/users/tromp/received_events","type":"User","site_admin":false},"created_at":"2018-03-24T09:42:37Z","updated_at":"2018-03-24T09:42:37Z","author_association":"CONTRIBUTOR","body":"During a discussion with jasper and yeastplume, I realized that Merkle proofs all the way up to the TXO root are not that useful, since the top sibling changes every block. This makes Merkle proofs very maintenance intensive and fast expiring.\r\nI propose that they instead only prove inclusion under a peak. The verifier should be able to verify that said peak is actually present."}}
{"actor":{"display_login":"tromp"}}