monero-project/research-lab #65#issuecomment-580888136 step 4

Hello all

More work on Triptych today :D

Just came across an interesting paper on tagging and tracing Zcash transactions, from November: dl.acm.org/doi/10.1145/3319535.3345663

Perhaps relevant to this channel since it provides some interesting examples of transaction non-uniformity

Sarang every time I sit down to be finally be productive, you post an interesting paper and derail me for a few hours

That's like the third time this week

=p

Look like its dataset stops in January 2019, so not many Sapling transactions are considered

No wait, I was trying to be productive. Gahhhhh. I'll be back.

I'm not really sure what to think about the assumption of verifiers colluding with malicious provers without having a side channel to just exchange information

it's interesting from a tagging perspective, but seems unrealistic

That's a threat vector I take very seriously, actually. I've been thinking about that for about a year, back when I realized that a honeypot wallet could use vanity stealth addresses to encode information like which ring member is the true spend, and the last few characters (or a checksum!) of recipient address

And a clever attacker would XOR or encrypt or whatever the data being encoded so that it's cryptographically indistinguishable from random to anybody who doesn't have attacker's schema

I suppose the risk is having the malicious prover/wallet publicly share the information needed to recover the hidden data

If it's just individual entities colluding, they can easily provide that info to each other via side channel, with no data hiding necessary (FWIW, the paper mentions this)

I assume the wallet is a trojan, and needs to broadcast information with no ooff-chain telemetry

that's an interesting use case

Actually, 3 assumptions/goals that I make

Trojan wallet wants to communicate sensitive information to its creator in a way that uses (1) NO off

(1) NO off-chain telemetry

(2) Must not impact functionality of transaction in any way

There are legitimate use cases for data hiding

Isthmus: Encrypting data like that is hard, though

We had earlier discussed the idea of using PRNG seeding to track signing indices for your own other wallet clients

(3) Must not create any obvious fungibility defects

Say you have to find a hash, and you can brute-force say the last 5 bytes

It's possible to do this safely

And encode stuff. You want to encrypt with a public key.

Or for that matter a symmetric key

how do you do this?

I have a clarifying note but need a second to figure out how to articulate it

yanmaani: MLSAG/CLSAG signatures have `n-1` random scalars and a single non-random (but uniformly distributed) scalar, at an unknown index

You can set the `n-1` random scalars to an indexed hash value using secret data

and on another client with the same secret data, use those hash values to determine the signing index

it's not implemented anywhere (that we know of!), but it's an interesting use case

But that requires secret data?

There's no asymmetric crypto that can do that from what I understand

Yes, if you don't want the whole world to be able to recover this data

yanmaani: the idea would be that you have multiple wallets and want them all to know the signing indices for your own transactions

The closest you could get is to encode it using some puzzle that you need to brute-force with a GPU, right?

so they all use a secret-key-derived seed

this isn't for public consumption, just your own wallets

I only mention it as one example where non-random data hiding can have a useful functionality

yeah but for Isthmus' use-case

There's no asymmetric crypto with small size, right?

In the trojan example, the malicious wallets could just have a hard-coded value

Yeah, but then anyone could see it

Is there such a thing as an asymmetric scheme?

Say you want a function f(x) -> y, where x is a 32-bit int and y is a 256-bit int. Let's call the set of all the obtainable values of y S. Is it then possible to make a function f2(y, s) -> bool, which takes a value of y and a secret s and returns a boolean of whether y is in s?

There's a constraint on the problem that you can toggle on or off. It’s whether or not you care if a counter-attacker examining the wallet (presumably serhack, lol) can extract the key to (1) decrypt the messages and (2) identify other compromised transactions on the blockchain.

If you want to obsessively cover your tracks, you’d need some complicated few-bit public encryption scheme.

(so that f has a runtime of ~high and f2 has a runtime of ~instant)

If you loosen that requirement, then you can go ahead just stick a random key in your wallet code and XOR or encrypt or whatever.

When serhack (for whomever) cracks the wallet they’ll be able to decode all such transactions. But that’s 100% fine if you’re some shady coinanalysis entity that dropped the wallet anonymously. And ever better if you’re an anti-monero maximalist who doesn’t mind decoys burning.

Oooh very interesting @yanmaani

Well of course you want to enable the constraint; it makes things much easier ;)

uh I mean harder

and more interesting

Also, in the event of a serious attacker who makes it public, relay nodes could just censor the offending transactions.

(or a softfork, or whatever)

So such an attacker would either have to find such a scheme or be betting against their own success

IMHO the only proper way to do this is such that transaction functionality is not impacted, and the message is cryptographically unnoticeable to anybody without the key from the wallet.

In that case, it could go unnoticed for years

Right. So is there such a function?

Function for which piece?

If you change the 256-bit int to whatever the blocksize of good pubkey encryption is, it should work

good pubkey encryption today is 256bit

the function above, f(x)

Oh yea, how long does it take to calculate a stealth address? I want to figure out how many bits you could encode in 5 seconds.

Wait, we don't have 256 bits

Make that say 64 bits

Is it one ecdh op?

The size and complexity scaling was poor

I see, yeah bulletproofs were quite impressive

very much so

i believe the scaling was worse than zk-snarks but better in the sense that it did not require a trusted setup

and by worse I mean ever so slightly worse

Size scaling is actually very, very good

yeah it looked comparable, I'm just remembering the chart I saw in his talk

Verifier complexity is much worse, but you can take advantage of certain optimizations to mitigate that

and TBH, for one-time proof operations like you're discussing, presumably the scaling is not nearly as important

indeed

so anyhow at this point I feel like I need some better direction. I initially thought this would be a great first project

because the implementation is an area I can make good progress on

however coming up with a more general zkp is a bit more challenging

There have been suggestions to look into adaptor signatures that may be able to use cross-curve discrete log representations, instead of hash preimages

as I don't have the background. I am willing to learn it however

but I have not had a chance to look into this yet

was this the work of a previous member?

ArticMine's?

We already know a method to prove equivalence of cross-group DL preimages, and it's much simpler

I remember you linked a paper previously

andytoshi had brought it up, and I'd heard it elsewhere too

ah yes

will proving cross-group preimages work?

I first saw the method in a posting by andytoshi, and wrote it up to for clarity and to fix some notation

It's MRL-0010 here: web.getmonero.org/resources/research-lab

thanks, yes

Again, the method described there is general, and not a specific application

hmm

I haven't looked into the details of how to apply this to the particular application of swaps

I see, but could this method work if we figure a way to apply it to the atomic swap zkp

So I won't be of much help to you at this point, I'm afraid

many projects on my plate :)

no worries, this is already helpful

I feel like I have been going in circles the last couple days

so this is indeed helpful

Welcome to research =p

haha yeah :)

it is rarely a neat line from problem to solution

at least for me :/

same for me as well, this is why I wanted to reach out to you lol

but this atleast gives something new to look into

It's a fascinating problem, to be sure

new goal: see if proving equivalence of cross-group DL preimages can be applied to atomic swaps

or rather the equivalence proof that atomic swaps requires

require*

I will come back to you with more updates

Cool, have fun

thanks, also I should mention that looking into the various protocols that Monero deploys (through Ztm2) and the protocols Zcash uses

has been very useful so it will definitely help me going forward

Yeah, ZtM is a fantastic resource

and the Zcash protocol specs are very complete (perhaps not a great starting resource, but that's not really their intent)

yeah I also pulled out a cryptography textbook to fill in the gaps

Which one?

Serious Cryptography by Jean-Philippe Aumasson

How is it? I remember seeing him posting about it, but have not read it yet

although if I get some more time, I'd love to ready: An Introduction to Mathematical Cryptography by Hoffstein

It's quite good. I like it because it strikes a good balance in length

Hoffstein is good, but is really about the math and not the protocol stuff, nor secure implementation topics

It's fairly concise at around 300 pages

yeah that's what I figured

I feel like I would end up needing a more applied version even if I did read that one

first

Yeah it seems to be more of an introduction to the basic number theory

also fun fact, Serious Cryptography has a foreward written by Mathew Green (the inventor of Zerocoin)

which I believe is an earlier version of Zcash

ah I see. I'll keep that in mind. I do enjoy number theory books from time to time. Hardy wrote a good one

Zerocoin is maybe better thought of as an ancestor to Zcash =p

The progression was Zerocoin -> Zerocash -> Zcash protocols

Ah I see. What was Zerocash?

Maybe let's take this to #monero-research-lounge to clear this channel

sure

Better timing test for Triptych: SarangNoether/monero 323a501

atoc: check out the btc-grin atomic swap, its all done in DL, like u should do, but then u use the cross-group DL preimages prove to pretend two different groups are the same

sarang I was reading through your toy python CLSAG implementation again today and got hung up on a detail with the hash function domain separation. The paper seems to use H_0^s for both the first aggregated public key and the challenges, while ZtoM uses a separate hash function for each.

Might be a typo. Let me check

Nah, it's fine

Using a separate domain-separated hash function isn't problematic

and the proofs follow if you replace the challenge `H_0` with a distinct function

In general, we're trying to use distinct separation across the project where possible, to mitigate any possible collisions (remote as they may be)

Namely, to prevent reuse across different parts of the transaction protocol

yes, so as an implementation guide, is ZtoM "more" correct, since it separates it again for the challenge calculation?

I wouldn't say it's more correct. It's more consistent with the handling of other hash function applications