{"action":"created","issue":{"url":"https://api.github.com/repos/mimblewimble/grin/issues/836","repository_url":"https://api.github.com/repos/mimblewimble/grin","labels_url":"https://api.github.com/repos/mimblewimble/grin/issues/836/labels{/name}","comments_url":"https://api.github.com/repos/mimblewimble/grin/issues/836/comments","events_url":"https://api.github.com/repos/mimblewimble/grin/issues/836/events","html_url":"https://github.com/mimblewimble/grin/issues/836","id":307283760,"number":836,"title":"Investigate batch rangeproof verification","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":465821400,"url":"https://api.github.com/repos/mimblewimble/grin/labels/question","name":"question","color":"cc317c","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":4,"created_at":"2018-03-21T15:04:22Z","updated_at":"2018-03-21T17:54:56Z","closed_at":null,"author_association":"MEMBER","body":"See #832 for some context.\r\n\r\nRangeproof verification is _expensive_.\r\nDuring fast sync it takes approx 70 seconds to verify approx 4,000 rangeproofs.\r\n\r\nFrom https://blockstream.com/2018/02/21/bulletproofs-faster-rangeproofs-and-much-more.html\r\n> ... reduced the speed of 147 multiplications to only 15.5 microseconds each, getting the total verification time of a Bulletproof down to 2.3 ms, vs 5.8 ms for the old proofs.\r\n\r\nFrom the above times, we should be able to verify 4,000 rangeproofs in approx 10 seconds.\r\nWe should investigate why we are seeing 70 seconds here.\r\n\r\nIn #832 we modified txhashset validation to allow rangeproof verification to be skipped.\r\nSo during check_compact() we can skip this step as we do not need to (re)verify rangeproofs.\r\n\r\nWe currently verify rangeproofs in 2 places - \r\n* `txhashset.verify_rangeproofs()`\r\n  * used during fast sync\r\n  * skipped during compaction\r\n* `Committed::sum_commitments()`\r\n  * when validating a transaction\r\n  * when validating a full block\r\n\r\nIn both cases we have multiple rangeproofs to verify.\r\nBatching would be useful in both cases.\r\n\r\nAnother thing we may want to investigate is whether we need to verify all rangeproofs _every_ time we validate a transaction or a block?\r\nFor example - when building a new block we validate all the transactions to be included in that block and presumably all these txs have already had their rangeproofs verified?\r\n\r\nCould we safely assume a tx previously accepted by the tx pool contains only outputs with valid rangeproofs?\r\n\r\nhttps://github.com/mimblewimble/grin/blob/ed78e1a721d2cf9bec2462c19824b4444a188eec/core/src/core/block.rs#L519-L526\r\n\r\nI guess this only happens within a mining node when building a new block so maybe the benefits are minimal here anyway?\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/mimblewimble/grin/issues/comments/375038090","html_url":"https://github.com/mimblewimble/grin/issues/836#issuecomment-375038090","issue_url":"https://api.github.com/repos/mimblewimble/grin/issues/836","id":375038090,"user":{"login":"yeastplume","id":7074070,"avatar_url":"https://avatars3.githubusercontent.com/u/7074070?v=4","gravatar_id":"","url":"https://api.github.com/users/yeastplume","html_url":"https://github.com/yeastplume","followers_url":"https://api.github.com/users/yeastplume/followers","following_url":"https://api.github.com/users/yeastplume/following{/other_user}","gists_url":"https://api.github.com/users/yeastplume/gists{/gist_id}","starred_url":"https://api.github.com/users/yeastplume/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yeastplume/subscriptions","organizations_url":"https://api.github.com/users/yeastplume/orgs","repos_url":"https://api.github.com/users/yeastplume/repos","events_url":"https://api.github.com/users/yeastplume/events{/privacy}","received_events_url":"https://api.github.com/users/yeastplume/received_events","type":"User","site_admin":false},"created_at":"2018-03-21T17:54:55Z","updated_at":"2018-03-21T17:54:55Z","author_association":"MEMBER","body":"Nope, sorry. It is the implementation:\r\n\r\n```\r\n-   99.56%     0.00%  pedersen::tests  secp256k1zkp-650646405640bde9  [.] secp256k1_bulletproof_rangeproof_verify_single_w_scratch                                                                             ▒\r\n     secp256k1_bulletproof_rangeproof_verify_single_w_scratch                                                                                                                                                  ▒\r\n   - secp256k1_bulletproof_rangeproof_verify                                                                                                                                                                   ▒\r\n      - 99.21% secp256k1_bulletproof_rangeproof_verify_impl                                                                                                                                                    ▒\r\n         - 94.16% secp256k1_bulletproof_inner_product_verify_impl                                                                                                                                              ▒\r\n            - 90.93% secp256k1_ecmult_multi_var                                                                                                                                                                ▒\r\n               - 90.92% secp256k1_ecmult_pippenger_batch                                                                                                                                                       ▒\r\n                  - 78.67% secp256k1_ecmult_pippenger_wnaf                                                                                                                                                     ▒\r\n                     + 57.56% secp256k1_gej_add_ge_var                                                                                                                                                         ▒\r\n                     + 17.44% secp256k1_gej_add_var                                                                                                                                                            ▒\r\n                     + 0.92% secp256k1_ge_neg                                                                                                                                                                  ▒\r\n                       0.71% secp256k1_gej_double_var                                                                                                                                                          ▒\r\n                       0.70% secp256k1_wnaf_fixed                                                                                                                                                              ▒\r\n                  + 6.69% secp256k1_bulletproof_innerproduct_vfy_ecmult_callback                                                                                                                               ▒\r\n                  + 5.22% secp256k1_ecmult_endo_split                                                                                                                                                          ▒\r\n            + 2.93% secp256k1_scalar_inverse_var                                                                                                                                                               ▒\r\n         + 3.03% secp256k1_scalar_inverse_var                                                                                                                                                                  ▒\r\n         + 1.34% secp256k1_bulletproof_update_commit                                                                                                                                                           ▒\r\n         + 0.65% secp256k1_bulletproof_deserialize_point\r\n```"}}
{"actor":{"display_login":"yeastplume"}}