sounds promising, narodnik. I'm pleased you'd like to work on that problem

it's not just that monero would maintain its position as using the best tech available for the problem, but fmpov also that if monero does not solve this problem then it probably becomes more of a comparative potential liability than a boon

if monero loses involvement of researchers and another project gains it.. and ends up with a ccs too.. mainly all that's left is network effect for monero, kinda like btc.

the great filter for cryptocurrency projects?

it'd surprise me if researchers left monero ... it has a unique combination of longevity and changing rapidly/dramatically

i mean.. a handful did

and devs do too

burnout

for one thing

a lot did... what about sarang?

i guess some left because of the toxic community

btw the above work is on spender membership proofs .. how does this play with dummy and to-self outputs, out of curiosity?

it's not just toxic

it's risky

i have a couple ideas on that .. soon...

endogenic: simplicity, mostly ... we are hoping to launch it on liquid "soon" and in the meantime we're finally exploring ZKPs again after years

i was a coauthor on the original BP paper which i think came out in jan of 2018 ... and i basically haven't thought about ZKPs since :(

ohh nice

but now we're looking at getting a prod-quality bp++ impl into secp256k1-zkp, and we'd like to make a validator that we could run inside simplicity so that we could verify ZKPs on liquid

that sounds useful

and maaybe switch liquid's asset/amount logic from the old-school rangeproof to BP++. this is nontrivial bceause BP++ has a new asset scheme that isn't compatible, so we need to figure out conversion logic (and figure out whether it still amkes sense to do)

endogenic: yeah, i'm hopeing that we'll be able to start experimenting/iterating way faster with simplicity as a platform, vs doing stuff directly on L1

because liquid can't hardfork all the time, it's actually super inflexible because we've got a federation of people who aren't interested in doing fulltime work on it

at least, not on crypto experiments :)

at least you get plaintext scripts (i think?)

ie we monero plebs are still in the stone ages eprint.iacr.org/2022/499

andytoshi: this is the first I’ve heard about other people being interested in bp++, do you have a grasp on how much reach and review the paper has received? There is a pending ccs proposal to get bp++ reviewed and implemented.

i will ask again for a follow up from the bp++ author this coming week (still no update received 😟)

UkoeHB: not a lot of uptake, mainly because the paper exists only on eprint, is poorly organized from an academic POV, and is incomplete/imprecise (from a programmer POV)

i introduced liam to dan boneh, who provided us a ton of advice for how to fix these things, and liam is going over the paper. we hope to submit to a conference this year (2023)

that's good news :)

in case you didn't see, someone did benchmarks: monero-project/research-lab #101

nice :)

i'm not quite sure how to read those but i -think- we can probably do better in libsecp256k1-zkp

added a comment explaining it

i can never remember what the true/false param of monero's rangeproof benchmarks are, nor which number is the number of bits and which is teh number of aggregates

UkoeHB: then another piece of news is that we hired liam at blockstream to help us with the secp-zkp implementation and the simplicity implementetation ... and to sponsor him to finish the paper ... and to explain to us his other papers (e.g. mucash which i think is directly relevant to monero)

ooh very cool news for liam!

monero rangeproofs are always on 64 bits

we don't actually have the code for these benchmarks... so it would be awesome to see a reference implementation in another library

vtnerd: is planning to try and translate liam's haskell implementation to C++

ah cool!

ok, so if i'm reading this right, the verification speed of a single 64-bit BP has roughly tripled from BPs to BP++?

yeah

incredible :)

i still think we could do better in -zkp, since we did better on the original BPs ... very excited to find out

Although batched verification only seems to be ~15% better. I am most excited about how much cheaper proof construction is (BPs are by far the most expensive part of making monero txs).

yeah, ditto, i was thrilled to find out about the prover verification stuff

andytoshi: did you do better because of implementation or because of underlying curve? afaik monero's implementation minimizes crypto ops

it does use keccak which may be slower than your hash function too

i initially thought those parts of the paper were about verification, and told liam that i was pretty sure we had better stuff ... and he said no, these are for the prover (and we had basically no prover tricks) :)

UkoeHB: i never investigated in detail, but but my impression at the time was that our curve library was faster

though sha2 vs keccak may have contributed

ah, and i think we had a better multi-exponentiation algorithm

and we were able to pretty-efficiently convert a BP verification into a single 150ish-point multiexp

hmm

I think the current impl is pretty close to as fast as we can get it, but might be worth looking again

i think monero was (is?) also multiplying all its input points everything by the curve order to eliminate cofactors

UkoeHB: well, maybe wait until we've done an implementation to see if we can actually beat you :)

we don't have an impl of BP++, only BP and BP+; the BP++ perf results are from someone's private tests (you know - 'crypto people')

oh, i see, you're asking about BPs

when deserializing a tx, monero multiplies amount commitments by 1/8 for the BP proofs; then the BP implementation multiplies by 8 internally

our impl is at ElementsProject/secp256k1-zkp #23 fwiw

thanks

ok, multiplication by 8 wouldn't cause a huge perf hit

i could imagine 10% or so coming from that, it's not trivial, but we were able to get 2.4ms for a 64-bit verification vs 4.4ms

also lol idk if we ever did benchmarks on the same computer

Yeah dealing with the ed25519 cofactor accounts for probably around 2-5% of tx verification cost. Thankfully most proof points can be pre-multiplied by 1/8 during proof construction, which saves a lot. Only range proofed amount commitments and key images need a full scalar multiplication.

(amount commitments when deserializing a compact tx blob, key images when verifying a tx)

<UkoeHB> "Yeah dealing with the ed25519..." <- That's interesting

I have to say I don't know how division works with curve points.. how does it?

You use invert the scalar then multiply

Ah, that's cool

To chime in on curve commentary, COPZ's DLEq proof would be feasible to port commitments under and I wouldn't be against moving to a curve cycle. I'm currently more interested in the existing tower of curves. The issue is we're stuck with linear verification time instead of logarithmic. It's just going to be what the least people bitch about by the time an actual proposal is put forth, and yes, is a lot more sane with

respect to the current stack.

Would there be issues with switching to the ristretto point serialization? To avoid the "multiply by 1/8" hacks and other cofactor-related issues. Old key images could be migrated to the new format.

Oh? Don't you already use ristretto points?

it would require pretty massive code changes

At the very least it could be used with BP++. That would not require any changes to existing code.

Then you couldn't batch-verify with grootle proofs

in one big multiexp (which is what I'm doing now)

although there may be ways around that

doesn't multiexp receive already deserialized points?

since the multiexp only needs to know ge_p3 representation

Ristretto only affects how you load points from the wire/database.

it might make building proofs more annoying, because all crypto functions are built around standard point serialization

i.e. you'd need some bare minimum of crypto library additions

basically wrappers around deserialize + call to core crypto + reserialize

also, amount commitments used in a proof would need to be converted to standard serialization for use elsewhere in the protocol (some overhead, although not more than what we have now)

for example, the "octuple-spend" inflation bug would have been avoided with ristretto

yes

it would take some work but has the potential to save a lot of headache later

Ristretto is definitely something to use when starting from scratch. For an established project it is a large undertaking that expands the crypto interface greatly, invites interoperability questions, imposes a burden on every implementation that wants to support monero things, etc.

We can create an outgoing view key based on BP(+) steganography.

If a BP is from a seeded RNG (some derivation of the view pair), then it'll have a very specific output. You can perform stegnography via taking one of its scalars and adding/substracting some intended message. Recovery would be generating the same BP, and checking for a difference. There will always be a difference (as it'll either be completely different, and gibberish, or the encoded message). By checking if the message

is the desired value (hash of the private view key), we can confirm if the BP sender is saying it's by us.

We can also not use a hash of the private view key yet a distinct outgoing view key. Anyone with the incoming view key can forge these messages :/

Instead of seeding the entire BP, we can also seed a single scalar (preventing requiring mass-generating BPs for any inputs using your outputs as decoys)

This is already solved with Seraphis.

There's no privacy implications, unlike some-CLSAG based schemes. There's also no additional outputs/data in TX extra.

tevador: I know. I'm just still contributing as I can to RingCT, when relevant. I don't plan to implement this, just wanted it written down.

I'm not working on new ring sigs :p I did define a new address format to remove the burning bug since I don't have 1-2y to wait on Seraphis deployment.

... I I actually may need this for a problem I have 🤔

new address format that no other wallet software supports?

tevador: narodnik UkoeHB I commented I was more interested in a tower of curves than a cycle earlier. I already have a circuit partially done roughly meeting Seraphis's requirements. It's just a massive background task for me while I have more urgent obligations.

also andytoshi

Kayaba, in case you missed it, pls comment on rust node

tevador: On the one hand, I only need it for my project. On the other hand, I defined a formal spec so if someone else has the same issue, they can adopt it.

monerobull: I did in -community and monero

👍

I'd also note it wasn't feasible to do a membership BP before the tower. I asked andytoshi if they had a tower a couple months ago, coincidentally right after one happened to have been found (thanks to Eagen). I have an impl of it. It's horrifically slow because I haven't done such low level math abefore nd am unsure how to efficiently optimize it but...

It exists.

I'm currently working on a circuit under bellman, very nice lib. Next would be BPs generic to curve. After that would be BPs supporting arbitrary circuits. Then I'd need to bind it into bellman.

And by currently working, I mean I have code sitting on a repo. I'm quite busy with my own work :/

I don't recommend pasta. I do recommend Ristretto.

We can (theoretically) promote without any curves. It just invalidates all addresses. It's still notably faster than three additions to decode. I'll caveat, if we compress to transcript, that we may lose perf in the long run.

*if we encode to transcript often enough

But for the safety boons...

Just saw the GH issue. Replied to narodnik's code there as well.

so the key masking seems to be the biggest issue?

It's not feasible without a tower/cycle. We do have a tower.

We could move to Halo 2 as COPZ has published a sufficiently performant DLEq proof... one month ago? Within the last month? Prior to that we couldn't

I don't personally see a reason to compared to a BP tower. Less dev work? Rn we have to maintain the tower yet ECC already maintains their cycle? I also expect far more research/opportunities with the cycle than the tower

But if I can't even get Ristretto in, I know I can't get Halo 2 in, especially when we can do BPs over a tower.

The issue is verification time is linear. With a cycle, it becomes logarithmic IIRC.