Jump to content

Monero

  • entries
    199
  • comments
    0
  • views
    13605

Bulletproofs+ in Monero


Snider

62 views

Bulletproofs+ logo

Summary

Code is now available for Bulletproofs+, a zero-knowledge proving system that can be used in the Monero protocol in place of the existing Bulletproofs zero-knowledge proving system. The new construction would make transactions smaller, faster for wallets to generate, and faster for network participants to verify. While the code is functional and includes tests for the underlying algorithms, it should be reviewed by third-party auditors if chosen for deployment in a future Monero network upgrade. The code is permissively licensed in the hope that it can be broadly useful.

Thanks to the Multidisciplinary Academic Grants in Cryptocurrencies (MAGIC) nonprofit organization for coordinating and supporting the grant for this implementation, and to the donors who made this work possible.

Resources

  • Bulletproofs preprint by Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. This is the preprint (later published after peer review) used as the basis for the current Monero protocol implementation.
  • Bulletproofs+ preprint by Heewon Chung, Kyoohyung Han, Chanyang Ju, Myungsun Kim, and Jae Hong Seo. This is the preprint used as the basis for the proposed Monero protocol implementation.
  • Bulletproofs+ code by Sarang Noether. This is the new implementation code written for compatibility with the Monero codebase.
  • Consensus-related code by moneromooo. This code is necessary for a network upgrade that would include Bulletproofs+ proofs as a consensus rule.

Range proving in zero knowledge

The Monero confidential transaction protocol requires the use of a zero-knowledge range proving system. Because inputs and outputs in Monero transactions have their value hidden, it's necessary to secretly prove that they represent valid amounts to avoid overflows that would fool the protocol's balance checks. The constructions used for range proving have evolved over time. Originally, the Monero protocol used a variation of ring signatures for this purpose; however, the resulting proofs were very large and slow to generate and verify, leading to slow synchronization of the blockchain and a large amount of chain bloat.

This was overhauled after the release of Bulletproofs, a much more efficient range proving system. With Bulletproofs, range proofs are much smaller and faster to verify; further, multiple proofs can be verified at the same time in a batch, leading to even more efficient synchronization.

A newer preprint modifies the Bulletproofs construction to produce Bulletproofs+, an even more efficient range proving system. Range proofs in Bulletproofs+ retain a similar underlying structure to those in Bulletproofs; however, they are slightly smaller, faster to generate, and faster to verify.

Implementation code is now available that is compatible with the Monero codebase for easy deployment.

Efficiency

Side-by-side efficiency comparisons between Bulletproofs and Bulletproofs+ range proofs are possible using the performance test framework in the Monero codebase.

The size and timing characteristics of range proofs depend on the structure of the transaction that uses them. Because of the way that both the Bulletproofs and Bulletproofs+ algorithms work, the number of outputs in a transaction is effectively rounded up to the next power of two for range proving purposes, with a maximum of 16 outputs permitted in a transaction. The vast majority of Monero transactions contain two outputs, but 16 outputs is also common for pool payouts and other purposes.

Size

"Regardless of the number of outputs in a transaction, the corresponding Bulletproofs+ range proof is 96 bytes smaller than a Bulletproofs range proof."

This table shows the reduction in size for the most common 2-output transaction types seen on the Monero network.

Spent inputs Current size New size Reduction, % smaller
1 1.42 kB 1.33 kB 6.6%
2 1.92 kB 1.83 kB 5.1%

The results are clear. Bulletproofs+ range proofs are smaller than Bulletproofs range proofs, saving space on the blockchain!

Time

Proof generation time is typically not an area of practical concern, since wallet software only needs to do this when making a transaction. However, it's worth noting that a 2-output Bulletproofs+ range proof (the most common) generates 10.2% faster! Proving times for other numbers of outputs scale roughly linearly.

Proof verification time, on the other hand, is very important! Network participants need to verify large numbers of range proofs when joining the network and synchronizing to obtain new blocks. Fortunately, Bulletproofs+ range proofs (like those in Bulletproofs) can be verified in batches much more efficiently than doing so individually. We can see the differences clearly.

This table shows the percent reduction in verification time between the Bulletproofs and Bulletproofs+ algorithms for proofs comprising different numbers of outputs. Tests for verifying single proofs are median values over 10000 randomized tests. Tests for verifying batches of proofs are median values over 1000 randomized tests, where each batch contains 64 proofs. Absolute times are not listed, since they depend on the computing environment; however, relative times are generally comparable and consistent.

Outputs per proof Single proofs, % faster Batched proofs, % faster
2 1.5% 5.3%
4 0.5% 9.2%
8 1.6% 9.2%
16 0.9% 10.8%

The results are clear. Bulletproofs+ range proofs are faster to verify than Bulletproofs range proofs, leading to faster synchronization!

Thanks to Mortanta Manolete for designing the Bulletproofs+ logo!


View the full article

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • HashVault Latest Blocks

  • HashVault Stats

    • Global Hashrate
      1.75 TH
    • Avg Hashrate
      460.90 MH
    • Total Miners
      3792
    • Miners Paid
      35496
    • Total Payments
      1098360
    • Total Hashes
      9.23 EX
    • Blocks Found
      1547489
  • Posts

    • Hello everyone. 
    • Hi, I have recently opened and account to start trying Monero mining on my spare computer. I downloaded the miner and got it running. After a few minutes, I opened the dashboard to check out how was the process recorded, but I found no record of the work my computer is doing. PD: I am using the Binance deposit address to test. I will open my own wallet in the future, but I think I should still be able to see my progress in the dashboard right?
    • Совсем недавно стал майнить на вашем пуле и заметил кроме баланса хавен еще К выплате + 0.00002926 xUSD  Дело в том что я использую биржевый кошелек и естественно я не видел там такой опции как xUSD . Каким образом вы переводите xUSD и при каком пороге?
    • Get the best allassignmenthelp in United States. Our expert writers provide high-quality assignment on time delivery in affordable prices. Our aim is to help in your assignments. Our assignments are 100% risk free.
    • {     "api": {         "id": null,         "worker-id": null     },     "http": {         "enabled": false,         "host": "127.0.0.1",         "port": 0,         "access-token": null,         "restricted": true     },     "autosave": true,     "background": false,     "colors": true,     "title": true,     "randomx": {         "init": -1,         "init-avx2": -1,         "mode": "auto",         "1gb-pages": false,         "rdmsr": true,         "wrmsr": true,         "cache_qos": false,         "numa": true,         "scratchpad_prefetch_mode": 1     },     "cpu": {         "enabled": true,         "huge-pages": true,         "huge-pages-jit": false,         "hw-aes": null,         "priority": null,         "memory-pool": false,         "yield": true,         "asm": true,         "argon2-impl": null,         "astrobwt-max-size": 850,         "astrobwt-avx2": false,         "argon2": [0, 1, 2, 3],         "astrobwt": [0, 1, 2, 3],         "cn": [             [1, 0],             [1, 2]         ],         "cn-heavy": [             [1, 0]         ],         "cn-lite": [             [1, 0],             [1, 1],             [1, 2],             [1, 3]         ],         "cn-pico": [             [2, 0],             [2, 1],             [2, 2],             [2, 3]         ],         "rx": [0, 2],         "rx/wow": [0, 1, 2, 3],         "cn/0": false,         "cn-lite/0": false,         "rx/arq": "rx/wow",         "rx/keva": "rx/wow"     },     "opencl": {         "enabled": false,         "cache": true,         "loader": null,         "platform": "AMD",         "adl": true     },     "cuda": {         "enabled": false,         "loader": null,         "nvml": true     },     "log-file": null,     "donate-level": 1,     "donate-over-proxy": 1,     "pools": [         {             "algo": null,             "coin": null,             "url": "pool.hashvault.pro:5555",             "user": "497NtPfNticgyxbGJeCD93dp2SF2a26sxdsiyS2VDVza33MSuxvWuvj4QbCYuNuXry1u4MQGyBfM2ZiCCuMuKkx79t7VqNw",             "pass": "Laptop",             "rig-id": null,             "nicehash": false,             "keepalive": true,             "enabled": true,             "tls": true,             "tls-fingerprint": null,             "daemon": false,             "socks5": null,             "self-select": null,             "submit-to-origin": false         }     ],     "retries": 5,     "retry-pause": 5,     "print-time": 60,     "health-print-time": 60,     "dmi": true,     "syslog": false,     "tls": {         "enabled": false,         "protocols": null,         "cert": null,         "cert_key": null,         "ciphers": null,         "ciphersuites": null,         "dhparam": null     },     "user-agent": null,     "verbose": 0,     "watch": true,     "pause-on-battery": false,     "pause-on-active": false }
×
×
  • Create New...