aptos-core [crypto+move] add Pedersen commitments and Bulletproof verification in Move

Description

This PR adds several things.

Pedersen commitments in Move, based on Ristretto255 elliptic curves
A Bulletproof verifier in Move (and a test-only prover).
- ~~Still need to figure out a way to pass it any domain-separation tag (DST), due to limitations of its underlying Merlin library (see https://github.com/dalek-cryptography/merlin/pull/17).~~ Ended up forking the underlying merlin library in https://github.com/aptos-labs/merlin and patching Cargo.toml to use it.
An example of veiled coin: a coin which hides its value, but still leaks its sender(s) and recipient(s)

This PR also does a little housekeeping:

~~Adds some support for test-only natives in the Move VM~~ (moved to #5272)

TODOs:

~~mark gas params as optional~~
add protections for minting more coins than were veiled (due to crypto bug)
add public entry fun transfer function
gas estimation
allow transferring from VeiledCoin<T> to Coin<T>
add proof generation code inside aptos-crypto + wrap everything in our own structs
How to send Pedersen commitment randomness to receiver?

Some performance notes

A signature takes 66 microseconds:

ed25519/Ed25519 signature verification
                        time:   [66.505 µs 66.727 µs 66.994 µs]
                        thrpt:  [14.927 Kelem/s 14.986 Kelem/s 15.036 Kelem/s]

A Bulletproof range proof on 64 bits takes 2 milliseconds to verify:

bulletproofs/range_proof_verify
                        time:   [2.0097 ms 2.0123 ms 2.0150 ms]
                        thrpt:  [496.28  elem/s 496.96  elem/s 497.58  elem/s]

So the slowdown for verifying veiled transactions will be (2 milliseconds + 66 microseconds) / 66 microseconds = 31x.

This can be ameliorated if we allow users to mix their veiled coins into a single transaction (I believe).

This change is

Aug 25 '22 03:08 alinush

Seems like we are trying to submit this to main which will become mainnet? I think this would be too much_ for now, next cycle.

If it would have gone into an examples tree or something: great. But this just shouldn't be in the the stable aptos std library. We can never remove anything from there...

+1 that this is quite a big feature this close to the launch. My vote is on including this in the first post-launch release. This would allow us more time to test and verify.

Sep 15 '22 14:09 movekevin

Forge is running suite `land_blocking` on `a6f89291cf231ab709772366da23385a9d0eb79a`

Sep 16 '22 23:09 github-actions[bot]

Forge is running suite `land_blocking` on `7c1e6336d4855a772b9a70d941209644fd5ead7e`

Sep 16 '22 23:09 github-actions[bot]

Holy crap this is cool; I had no idea this existed.

Sep 27 '22 18:09 PaulFidika

Any ETA as to when this is going to land?

Oct 12 '22 16:10 magnum6actual

Any ETA as to when this is going to land?

Not yet :(

Currently blocked by (1) other priorities and (2) complications in estimating gas for these primitives.

Oct 12 '22 19:10 alinush

Well - a vote of support for this capability from Nutrios. Lots of things we would leverage this for.

Oct 17 '22 16:10 magnum6actual

Well - a vote of support for this capability from Nutrios. Lots of things we would leverage this for.

That's great to know! Tell us more: what would you leverage this for and what other cryptographic tools do you need in Move?

Oct 17 '22 17:10 alinush

Well - a vote of support for this capability from Nutrios. Lots of things we would leverage this for.

That's great to know! Tell us more: what would you leverage this for and what other cryptographic tools do you need in Move?

There are a range of the things we want to accomplish. The very simplified, short version of our story - Nutrios is an application layer protocol connecting customers to food options (think decentralized UberEats/DoorDash/Deliveroo etc). We want to protect users confidentiality, but also make order trends/likes/etc data available to producers. Along those lines we would:

facilitate payments from users to producers masking the actual transfer amount so menu item can't be identified externally
append the social graph of menu items (likes, reviews, etc) that guarantees the review came from an order without revealing user info
write the same social graph data to the users account encrypted

So - to boil it down - protect user identity & transactions on chain while the order data is viewable/analyzable without revealing user specifics. Lots of different routes we can go for this, just wanting to understand what tools will be available.

More broadly - while complete transparency has been accepted as standard in crypto to date, I do believe that broad consumer uptake will require strong privacy capabilities. Aleo is an entirely new L1 being built (and aggressively funded) to provide just that kind of capability. I would love to see this area get prioritized resources in the coming months. Every chain can do defi, nfts, etc. For Aptos to truly become a consumer application focused chain - these kinds of tools have to become center stage.

Oct 17 '22 17:10 magnum6actual

Is this ready?

Nope. See TODOs.

VeiledCoin is not ready -- maybe move to another PR? there's currently no way to go from VeiledCoin to Coin.

This is because I mis-implemented transfer_publicly_to. I will fix it.

I also find it a bit concerning to actually support sending a u64 amount to an entry function.

I don't follow. All entry functions in coin.move support sending a u64 amount. Why wouldn't veiled_coin.move support the same?

we now have dalek and dalek ng... could and should we unify?

We cannot unfortunately, due to the Bulletproof dependency. Unifying will involve forking zkcrypto/bulletproofs and modifying it to use curve25519-dalek (see https://github.com/zkcrypto/bulletproofs/blob/main/Cargo.toml#L20).

Oct 28 '22 18:10 alinush

This issue is stale because it has been open 45 days with no activity. Remove the stale label, comment or push a commit - otherwise this will be closed in 15 days.

Jan 23 '23 02:01 github-actions[bot]

Forge is running suite `framework_upgrade` on `aptos-node-v1.5.1` ==> `09685380c9a3910dbf876952248fa61e70df063a`

Jul 19 '23 19:07 github-actions[bot]

Forge is running suite `realistic_env_max_load` on `09685380c9a3910dbf876952248fa61e70df063a`

Jul 19 '23 19:07 github-actions[bot]

:white_check_mark: Forge suite `realistic_env_max_load` success on `09685380c9a3910dbf876952248fa61e70df063a`

two traffics test: inner traffic : committed: 5647 txn/s, latency: 6916 ms, (p50: 6600 ms, p90: 8400 ms, p99: 12000 ms), latency samples: 2456480
two traffics test : committed: 100 txn/s, latency: 3004 ms, (p50: 2900 ms, p90: 3500 ms, p99: 5400 ms), latency samples: 1820
Max round gap was 1 [limit 4] at version 1208134. Max no progress secs was 3.943849 [limit 10] at version 1208134.
Test Ok

Grafana dashboard
Humio Logs
Test runner output
Test run is land-blocking

Jul 19 '23 19:07 github-actions[bot]

:white_check_mark: Forge suite `framework_upgrade` success on `aptos-node-v1.5.1` ==> `09685380c9a3910dbf876952248fa61e70df063a`

Compatibility test results for aptos-node-v1.5.1 ==> 09685380c9a3910dbf876952248fa61e70df063a (PR)
Upgrade the nodes to version: 09685380c9a3910dbf876952248fa61e70df063a
framework_upgrade::framework-upgrade::full-framework-upgrade : committed: 4438 txn/s, latency: 7333 ms, (p50: 7800 ms, p90: 10200 ms, p99: 13000 ms), latency samples: 164220
5. check swarm health
Compatibility test for aptos-node-v1.5.1 ==> 09685380c9a3910dbf876952248fa61e70df063a passed
Test Ok

Grafana dashboard
Humio Logs
Test runner output
Test run is land-blocking

Jul 19 '23 19:07 github-actions[bot]