00:29:56 https://github.com/monero-project/research-lab/issues/65#issuecomment-580888136 step 4 14:42:37 Hello all 14:43:02 More work on Triptych today :D 16:04:22 Just came across an interesting paper on tagging and tracing Zcash transactions, from November: https://dl.acm.org/doi/10.1145/3319535.3345663 16:04:50 Perhaps relevant to this channel since it provides some interesting examples of transaction non-uniformity 16:33:13 Sarang every time I sit down to be finally be productive, you post an interesting paper and derail me for a few hours 16:33:19 That's like the third time this week 16:33:41 =p 16:34:14 Look like its dataset stops in January 2019, so not many Sapling transactions are considered 16:34:36 * Isthmus steeples fingers 16:34:42 * Isthmus launches BigQuery 16:35:51 No wait, I was trying to be productive. Gahhhhh. I'll be back. 16:37:13 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 16:37:29 it's interesting from a tagging perspective, but seems unrealistic 17:08:18 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 17:09:57 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 17:10:18 I suppose the risk is having the malicious prover/wallet publicly share the information needed to recover the hidden data 17:10:46 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) 17:10:50 I assume the wallet is a trojan, and needs to broadcast information with no ooff-chain telemetry 17:11:05 that's an interesting use case 17:11:11 Actually, 3 assumptions/goals that I make 17:11:51 Trojan wallet wants to communicate sensitive information to its creator in a way that uses (1) NO off 17:12:01 (1) NO off-chain telemetry 17:12:25 (2) Must not impact functionality of transaction in any way 17:12:36 There are legitimate use cases for data hiding 17:12:51 Isthmus: Encrypting data like that is hard, though 17:12:59 We had earlier discussed the idea of using PRNG seeding to track signing indices for your own other wallet clients 17:13:00 (3) Must not create any obvious fungibility defects 17:13:03 Say you have to find a hash, and you can brute-force say the last 5 bytes 17:13:06 It's possible to do this safely 17:13:18 And encode stuff. You want to encrypt with a public key. 17:13:48 Or for that matter a symmetric key 17:13:49 how do you do this? 17:13:55 I have a clarifying note but need a second to figure out how to articulate it 17:15:17 yanmaani: MLSAG/CLSAG signatures have `n-1` random scalars and a single non-random (but uniformly distributed) scalar, at an unknown index 17:15:34 You can set the `n-1` random scalars to an indexed hash value using secret data 17:15:47 and on another client with the same secret data, use those hash values to determine the signing index 17:16:06 it's not implemented anywhere (that we know of!), but it's an interesting use case 17:16:12 But that requires secret data? 17:16:23 There's no asymmetric crypto that can do that from what I understand 17:16:27 Yes, if you don't want the whole world to be able to recover this data 17:16:48 yanmaani: the idea would be that you have multiple wallets and want them all to know the signing indices for your own transactions 17:16:50 The closest you could get is to encode it using some puzzle that you need to brute-force with a GPU, right? 17:16:59 so they all use a secret-key-derived seed 17:17:09 this isn't for public consumption, just your own wallets 17:17:25 I only mention it as one example where non-random data hiding can have a useful functionality 17:17:49 yeah but for Isthmus' use-case 17:17:51 There's no asymmetric crypto with small size, right? 17:18:52 In the trojan example, the malicious wallets could just have a hard-coded value 17:19:08 Yeah, but then anyone could see it 17:19:20 Is there such a thing as an asymmetric scheme? 17:21:03 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? 17:21:37 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. 17:21:48 If you want to obsessively cover your tracks, you’d need some complicated few-bit public encryption scheme. 17:21:49 (so that f has a runtime of ~high and f2 has a runtime of ~instant) 17:21:51 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. 17:21:55 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. 17:22:56 Oooh very interesting @yanmaani 17:24:23 Well of course you want to enable the constraint; it makes things much easier ;) 17:24:50 uh I mean harder 17:24:50 and more interesting 17:25:25 Also, in the event of a serious attacker who makes it public, relay nodes could just censor the offending transactions. 17:25:49 (or a softfork, or whatever) 17:25:50 So such an attacker would either have to find such a scheme or be betting against their own success 17:30:19 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. 17:30:25 In that case, it could go unnoticed for years 17:30:50 Right. So is there such a function? 17:31:18 Function for which piece? 17:31:20 If you change the 256-bit int to whatever the blocksize of good pubkey encryption is, it should work 17:31:41 good pubkey encryption today is 256bit 17:31:48 the function above, f(x) 17:32:38 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. 17:32:50 Wait, we don't have 256 bits 17:32:50 Make that say 64 bits 17:34:06 Is it one ecdh op? 18:49:23 The size and complexity scaling was poor 18:49:40 I see, yeah bulletproofs were quite impressive 18:49:49 very much so 18:50:02 i believe the scaling was worse than zk-snarks but better in the sense that it did not require a trusted setup 18:50:13 and by worse I mean ever so slightly worse 18:50:24 Size scaling is actually very, very good 18:50:47 yeah it looked comparable, I'm just remembering the chart I saw in his talk 18:50:48 Verifier complexity is much worse, but you can take advantage of certain optimizations to mitigate that 18:51:06 and TBH, for one-time proof operations like you're discussing, presumably the scaling is not nearly as important 18:51:22 indeed 18:51:52 so anyhow at this point I feel like I need some better direction. I initially thought this would be a great first project 18:52:09 because the implementation is an area I can make good progress on 18:52:25 however coming up with a more general zkp is a bit more challenging 18:52:35 There have been suggestions to look into adaptor signatures that may be able to use cross-curve discrete log representations, instead of hash preimages 18:52:38 as I don't have the background. I am willing to learn it however 18:52:42 but I have not had a chance to look into this yet 18:52:55 was this the work of a previous member? 18:53:04 ArticMine's? 18:53:06 We already know a method to prove equivalence of cross-group DL preimages, and it's much simpler 18:53:15 I remember you linked a paper previously 18:53:19 andytoshi had brought it up, and I'd heard it elsewhere too 18:53:24 ah yes 18:54:09 will proving cross-group preimages work? 18:54:14 I first saw the method in a posting by andytoshi, and wrote it up to for clarity and to fix some notation 18:54:20 It's MRL-0010 here: https://web.getmonero.org/resources/research-lab/ 18:54:35 thanks, yes 18:54:49 Again, the method described there is general, and not a specific application 18:55:24 hmm 18:55:33 I haven't looked into the details of how to apply this to the particular application of swaps 18:55:40 I see, but could this method work if we figure a way to apply it to the atomic swap zkp 18:55:47 So I won't be of much help to you at this point, I'm afraid 18:55:56 many projects on my plate :) 18:55:57 no worries, this is already helpful 18:56:22 I feel like I have been going in circles the last couple days 18:56:30 so this is indeed helpful 18:56:30 Welcome to research =p 18:56:38 haha yeah :) 18:56:46 it is rarely a neat line from problem to solution 18:56:50 at least for me :/ 18:57:03 same for me as well, this is why I wanted to reach out to you lol 18:57:13 but this atleast gives something new to look into 18:57:27 It's a fascinating problem, to be sure 18:58:20 new goal: see if proving equivalence of cross-group DL preimages can be applied to atomic swaps 18:58:58 or rather the equivalence proof that atomic swaps requires 18:59:07 require* 18:59:15 I will come back to you with more updates 19:00:05 Cool, have fun 19:01:21 thanks, also I should mention that looking into the various protocols that Monero deploys (through Ztm2) and the protocols Zcash uses 19:01:52 has been very useful so it will definitely help me going forward 19:04:02 Yeah, ZtM is a fantastic resource 19:04:27 and the Zcash protocol specs are very complete (perhaps not a great starting resource, but that's not really their intent) 19:24:12 yeah I also pulled out a cryptography textbook to fill in the gaps 19:27:14 Which one? 19:29:36 Serious Cryptography by Jean-Philippe Aumasson 19:30:04 How is it? I remember seeing him posting about it, but have not read it yet 19:30:17 although if I get some more time, I'd love to ready: An Introduction to Mathematical Cryptography by Hoffstein 19:30:35 It's quite good. I like it because it strikes a good balance in length 19:30:41 Hoffstein is good, but is really about the math and not the protocol stuff, nor secure implementation topics 19:30:52 It's fairly concise at around 300 pages 19:31:07 yeah that's what I figured 19:31:32 I feel like I would end up needing a more applied version even if I did read that one 19:31:34 first 19:34:34 Yeah it seems to be more of an introduction to the basic number theory 19:34:41 also fun fact, Serious Cryptography has a foreward written by Mathew Green (the inventor of Zerocoin) 19:35:04 which I believe is an earlier version of Zcash 19:35:35 ah I see. I'll keep that in mind. I do enjoy number theory books from time to time. Hardy wrote a good one 19:36:38 Zerocoin is maybe better thought of as an ancestor to Zcash =p 19:36:54 The progression was Zerocoin -> Zerocash -> Zcash protocols 19:37:31 Ah I see. What was Zerocash? 19:37:44 Maybe let's take this to #monero-research-lounge to clear this channel 19:37:54 sure 20:54:25 Better timing test for Triptych: https://github.com/SarangNoether/monero/commit/323a501253f493e09adca3e5be98e5cea12a43d3 22:12:59 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 22:13:07 https://medium.com/grinswap/first-grin-atomic-swap-a16b4cc19196 22:37:09 https://github.com/vault713/grinswap/blob/master/doc/grin_btc_swap/grin_btc_swap.png 23:39:33 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. 23:40:20 Might be a typo. Let me check 23:41:17 Nah, it's fine 23:41:37 Using a separate domain-separated hash function isn't problematic 23:42:09 and the proofs follow if you replace the challenge `H_0` with a distinct function 23:42:38 In general, we're trying to use distinct separation across the project where possible, to mitigate any possible collisions (remote as they may be) 23:43:53 Namely, to prevent reuse across different parts of the transaction protocol 23:46:00 yes, so as an implementation guide, is ZtoM "more" correct, since it separates it again for the challenge calculation? 23:56:29 I wouldn't say it's more correct. It's more consistent with the handling of other hash function applications