Nano-node: Integrating Bulletproofs

[skynxt]

Privacy and scaling:
https://web.stanford.edu/%7Ebuenz/pubs/bulletproofs.pdf

[PlasmaPower]

I've been doing some research into this. A potential problem is that they are a bit larger than the maximum safe size for IPv4 UDP packets. That said, they are something I'd like to explore.

[termhn]

Is there a succinct summary of what these are/what they would be used for somewhere? Haven't seen it before and not sure I want to read through the entire whitepaper at this time :)

[PlasmaPower]

They're a way to add privacy to transactions.

[termhn]

Aha found this https://crypto.stanford.edu/bulletproofs/

[skynxt]

Can data in UDP be fragmented and reassembled at the receiving end to accommodate larger data?

The proof size is only 672 bytes according to this:
https://diyhpl.us/wiki/transcripts/blockchain-protocol-analysis-security-engineering/2018/bulletproofs/

Another take away from above wiki:
Bulletproofs for smart contracts:
Another application of bulletproofs is smart contracts. A smart contract, you can write a bulletproof which is a short proof for an arbitrary computation.

Bulletproofs Implemented here:
https://github.com/monero-project/monero/blob/36241552b56b156c08319935baf7afda12deb3c5/src/ringct/bulletproofs.cc

https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs

[termhn]

Yes you can but a lot of work has been done to keep blocks under 1 udp
packet for nano for speed, and udp is an inherently unreliable protocol so
you couldn't guarantee that both pieces would get to the receiver without
extra logic running on top to do so.

On Sun, Mar 11, 2018 at 8:16 PM SkyNxt [e-mail] wrote:

Can data in UDP be fragmented and reassembled at the receiving end to
accommodate larger data?

The proof size is only 672 bytes according to this:

https://diyhpl.us/wiki/transcripts/blockchain-protocol-analysis-security-engineering/2018/bulletproofs/

Another take away from above wiki:
Bulletproofs for smart contracts:
Another application of bulletproofs is smart contracts. A smart contract,
you can write a bulletproof which is a short proof for an arbitrary
computation.

Bulletproofs Implemented here:
https://github.com/bitcoin-core/secp256k1

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/nanocurrency/raiblocks/issues/721#issuecomment-372182983,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AA2Ln4HFdm4MnCcnf7BhqJbOdp4Cd44jks5tdehygaJpZM4SlqIF
.

[ThunderFD]

I was kinda curious about the UDP limitations and ...
since I wasn't able to find a clear-cut answer on packet sizes right away, I did some highly sophisticated Wikipedia search:

https://en.wikipedia.org/wiki/User_Datagram_Protocol

Length
A field that specifies the length in bytes of the UDP header and UDP data. The minimum length is 8 bytes because that is the length of the header. The field size sets a theoretical limit of 65,535 bytes (8 byte header + 65,527 bytes of data) for a UDP datagram. However the actual limit for the data length, which is imposed by the underlying IPv4 protocol, is 65,507 bytes (65,535 − 8 byte UDP header − 20 byte IP header).[4]
In IPv6 jumbograms it is possible to have UDP packets of size greater than 65,535 bytes.[5] RFC 2675 specifies that the length field is set to zero if the length of the UDP header plus UDP data is greater than 65,535.

So UDP packets can carry about 64KB, however:

https://en.wikipedia.org/wiki/Maximum_transmission_unit

The Internet Protocol requires that hosts must be able to process IP datagrams of at least 576 bytes (for IPv4) or 1280 bytes (for IPv6).

you can only guarantee no fragmentation below 576 bytes, and if we lose one of the pieces we've lost our entire UDP packet.
afaik you still have to subtract header data and so on from that, so around 512 bytes should be safe, otherwise you end up with fragmentation of your packet

The proof size is only 672 bytes according to this:

seems to already be too big on its own to guarantee a nonfragmented packet

TL;DR

• UDP can do up to 64KB packet size
• IP can only guarantee ~512 bytes without fragmentation
• fragmentation is bad and results in more packet loss
• you'd have to check the bulletproofs on top of that, CPU intensive?

So what?

The question is how much this actually matters, right now it probably doesn't, but once you go to 10000+ tx/s this must have big impacts.

[cryptocode]

The Internet Protocol requires that hosts must be able to process IP datagrams of
at least 576 bytes (for IPv4) or 1280 bytes (for IPv6).

The magic number for ipv4 UDP payload is actually 508

Minimum reassembly buffer size (576) minus 60 (ip header), minus 8 (udp header) = 508. Anything larger and some routers will start dropping.

Nano's header is an additional 8 bytes, which means our message payload budget is an even 500 bytes.

I've seen claims that 508 is the safe number even for ipv6 (probably due to buggy routers)

[funkspock]

Comparison of the most popular zkp systems

  | SNARKs | STARKs | Bulletproofs
-- | -- | -- | --
Algoritmic complexity: prover | O(N * log(N)) | O(N * poly-log(N)) | O(N * log(N))
Algoritmic complexity: verifier | ~O(1) | O(poly-log(N)) | O(N)
Communication complexity (proof size) | ~O(1) | O(poly-log(N)) | O(log(N))
size estimate for 1 TX | Tx: 200 bytes, Key: 50 MB | 45 kB | 1.5 kb
size estimate for 10.000 TX | Tx: 200 bytes, Key: 500 GB | 135 kb | 2.5 kb
Ethereum/EVM verification gas cost | ~600k (Groth16) | ~2.5M (estimate, no impl.) | N/A
Trusted setup required? | YES 😒 | NO 😄 | NO 😄
Post-quantum secure | NO 😒 | YES 😄 | NO 😒
Crypto assumptions | Strong 😒 | Collision resistant hashes 😄 | Discrete log 😏

source and literature
https://github.com/gluk64/awesome-zero-knowledge-proofs

zk-starks is getting a lot of academic attention at the moment to improve the areas where bulletproofs currently outperforms.

[skynxt]

Thanks for nice comparison.
zk-STARKS seem to address post quantum crypto too.
What do you think about this Microsoft research based picnic library, this has implementation of zero knowledge proof and has post quantum security.

https://microsoft.github.io/Picnic/