sub-addresses

----- Today October 25th, 2016 -----

One-time BOT [12:16 AM]
I was wondering if you guys saw this idea for one-time receiving Monero stealth addresses, and whether there is something wrong with it. From what I could tell, it seems like a promising and natural way to implementthe functionality of HD wallets in Monero. Here is the SE post: http://monero.stackexchange.com/questions/2469/one-time-receiving-monero-address


One-time BOT [12:34 AM]
To be more specific, if the receiver; i.e. the owner of address (A,B) = (aG, bG), picks a number k and shares (C,D) = (a^k A, a^k B) with the sender, then, after the sender chooses random r, forms P = H(rC)G+D, and submits {rG, P, k} to the network, the receiver is able to spend using x = H(a^{k+1}*R)+a^k*b. Also, the view key still works fine in this setup: with k and (a, B), the auditor can still check that P = H(a^{k+1}*R)*G

jollymort [12:36 AM]
(C,D) is just another Monero address


One-time BOT [12:36 AM]
This way, the wallet owner can produce as many stealth addresses as they wish, and check them all in constant time (as opposed to storint many unrelated keys).

[12:36]
Jollymort: That is correct

jollymort [12:36 AM]
with the link to (A,B) by means of k

[12:37]
you could make any (c,d) into a self-standing monero wallet


One-time BOT [12:37 AM]
You could, if you'd like

jollymort [12:37 AM]
it's a HD scheme, where you store k's on the blockchain to optimize scanning for outputs

[12:38]
to me it looks like the terms are getting mixed up

[12:38]
stealth address is never reused as it's generated from an (address + random data)

[12:38]
the address here, can be a normal address, or your sub-addres (C,D)


One-time BOT [12:39 AM]
Yes, I was referring to the pair (C,D) as a stealth address. I thought that was the convention

jollymort [12:39 AM]
nah, stealth address in CryptoNote context is something else


One-time BOT [12:39 AM]
I thought P was the one-ttime address produced from it

jollymort [12:40 AM]
or I misunderstood it too :slightly_smiling_face:


One-time BOT [12:40 AM]
Okay, no problem

jollymort [12:40 AM]
just to avoid confusion


One-time BOT [12:41 AM]
So, the idea is to use the payment ID field to store k, but I guess that is not written in stone

jollymort [12:42 AM]
k would start at 1 and be incremented or just random?


One-time BOT [12:43 AM]
I guess that is a matter of preference, and only depends on the implementation on the client side

jollymort [12:43 AM]
well, if it's incremented, than many transactions belonging to different users would have the same k

[12:43]
and your wallet would scan every one of them

[12:44]
(scan = attempt to decrypt with matching (c,d))

[12:44]
if it's random, there are some other risks involved

[12:44]
like the sender omits the k, and you lose your record of k's issued

[12:44]
and then, there's no way to recover the funds


One-time BOT [12:46 AM]
Our wallets already scan every tx in the blockchain. The advantage is when compared to naively storing many unrelated keys: receiver scans the tx once for (A, B), and then another time using k, so that is at most two tries per output in the blockchain vs. n on a HD wallet with n unrelated keys

jollymort [12:47 AM]
i know. but HD scheme is less risky and more conservative

[12:47]
i've been using mycelium since 2014 and i have like 144 different addresses

[12:47]
doesn't seem too much


One-time BOT [12:48 AM]
Indeed, not including k is a risk. One advantage of having this aproach being enbras=ced by the devs is perhaps having it included in the wallet's code, so that the receiver only broadcasts the tx with k attached to it

jollymort [12:50 AM]
well, if you just have some new address scheme, with a few extra chars to encode the `k` and the wallets would reocgnize this...


One-time BOT [12:50 AM]
Yeah, I was just realizing that...

jollymort [12:50 AM]
you kind of force them to include it

[12:51]
like paymentID now

[12:51]
(when used in integrated address scheme)


One-time BOT [12:52 AM]
Would that require a more profound change in the protocol? Or can we still implement this more or less superficially?

jollymort [12:52 AM]
i think no protocol change needed at all

[12:52]
just a wallet convention thing


One-time BOT [12:54 AM]
Could we just use integrated address, you think? I mean, there is still the possibility that the sender would separate the two in their client, but they would have to actually mean to do that

jollymort [12:55 AM]
i guess you could. 1. generate random payment ID, calculate (C,D), create a integrated address of (C,D)+pID and give to sender

[12:55]
hell, you could be the only one using this scheme and nobody would know

[12:55]
and you'd have your personal HD wallet

[12:56]
without anyone else having to change anything


One-time BOT [12:56 AM]
So, it is just a matter of programming it into the wallet? Maybe there is even no need to bother the devs about this? :)

jollymort [12:56 AM]
if you can code, you could make a branch to experiment with this


One-time BOT [12:57 AM]
True. Sounds like a good exercise

jollymort [12:58 AM]
just one note

[12:58]
i think there's a risk of generating random pID

[12:58]
some incremenal k with some hashing should do it

[12:58]
no, wait, i'm wrong

[12:59]
you can just pretend that every tx with pID is conforming to your scheme and try to decrypti it


One-time BOT [12:59 AM]
Yes, that is what I understand too

jollymort [1:00 AM]
but generating these pIDs with something like pID=hash((A)+k) where k would be incremental

[1:00]
might make everything faster

[1:00]
as you could just check the pID first, without trying the decrypt

[1:01]
dunno, i'm overthinking it now

[1:01]
at first i didn't really like the proposal, but now with this pID scheme i'm kind of getting excited :smile:

[1:02]
best part is, you don't have to tell anyone you use this scheme

[1:02]
you just give out a integrated address

[1:02]
like any other


One-time BOT [1:03 AM]
Yes, I think it is pretty cool too!

jollymort [1:05 AM]
now I'm not versed in cryptography, so I guess we'd want someone to look at the way you go from (a,b) to (c,d) to be sure it can't be linked back or linked together


One-time BOT [1:05 AM]
About your previous comment about the tx with unknown PID, you might want to check that one too, just in the off chance that it was sent to (A,B) and the PID means something else. The sender might decide to put anything as PID after all

jollymort [1:05 AM]
pinging our resident amateur-cyryptographer @theking01

theking01 [1:06 AM]
yo

[1:06]
What's the question?


One-time BOT [1:06 AM]
Sure. That is one of the things I was looking for as well. I am not that confident in my understanding of crypto as well

jollymort [1:07 AM]
you saw this proposal for HD scheme with passing `k` ?

theking01 [1:07 AM]
Me either, but I'm another person, at least.

[1:07]
I think so.


One-time BOT [1:07 AM]
We would like to know how safe a scheme is. I will copy what a I wrote:

theking01 [1:07 AM]
A simply scheme is just to wait for multisig.


One-time BOT [1:07 AM]
To be more specific, if the receiver; i.e. the owner of address (A,B) = (aG, bG), picks a number k and shares (C,D) = (a^k A, a^k B) with the sender, then, after the sender chooses random r, forms P = H(rC)G+D, and submits {rG, P, k} to the network, the receiver is able to spend using x = H(a^{k+1}*R)+a^k*b. Also, the view key still works fine in this setup: with k and (a, B), the auditor can still check that P = H(a^{k+1}*R)*G

theking01 [1:07 AM]
*simpler


One-time BOT [1:08 AM]
Doesn't  that solve a different problem?

jollymort [1:08 AM]
its could already be simple "generate random payment ID, calculate (C,D), create a integrated address of (C,D)+pID and give to sender"

[1:08]
the only change would be on the receiver end

[1:08]
for the sender, it'd be just another integrated address

theking01 [1:09 AM]
It would appear so, but multisig will actually allow you to solve the problem your trying to solve, I think.


One-time BOT [1:09 AM]
This is just so the user doesn't have to handle the same address to different people, websites, exchanges eta

[1:09]
etc

theking01 [1:10 AM]
Like, what you do is you have a base address P, and for each person you need to send to, you give them the address 2-of-2 P, P'

jollymort [1:10 AM]
one-time i think it's a good idea if implemented adequately considering what we discussed

theking01 [1:11 AM]
a is view key, right?

jollymort [1:11 AM]
yeah

[1:11]
a and c


One-time BOT [1:11 AM]
@theking01: Maybe. But even if it does, this seems like an elegant way to solve the issue of address reuse

[1:11]
Yes

[1:11]
And this feels like a low hanging fruit too :)

theking01 [1:12 AM]
You would need a new k for every transaction, for one.

jollymort [1:12 AM]
no

[1:12]
you can reuse it too


One-time BOT [1:12 AM]
no

jollymort [1:12 AM]
no risk

[1:12]
every (C,D) is a regular monero address


One-time BOT [1:12 AM]
Every output would still use the random r, just the same as a regular tx

theking01 [1:12 AM]
People would see reused k's.

jollymort [1:12 AM]
it's just that there's a one-way link (c,d) = f(a,b,k)

theking01 [1:13 AM]
If they are one chain.

[1:13]
Defeating the reason for stealth addresses.

jollymort [1:13 AM]
so what? people reuse payment id's too

theking01 [1:13 AM]
*on chain

jollymort [1:13 AM]
thing is, nobody could tell the difference

theking01 [1:13 AM]
Reusing payment ids are fine if they are encrypted.

jollymort [1:14 AM]
i mean, if you give out a integrated address

theking01 [1:14 AM]
But clear text payment ID reuse is a problem

jollymort [1:14 AM]
all tx sent to it will have same TX_EXTRA data, no?

theking01 [1:14 AM]
No

[1:15]
If you send to an integrated address twice, the tx extra will be unlinkable.

[1:15]
Since encrypted tx keys use a one time key.

[1:15]
*tx ids

jollymort [1:16 AM]
need to read up on this

[1:16]
but i think we're getting somewhere with this idea

theking01 [1:16 AM]
So if I reuse an encrypted payment id, it's fine.

[1:16]
I'm been thinking about the address reuse problem for sometime.

jollymort [1:17 AM]
read up for some ideas :slightly_smiling_face:

theking01 [1:17 AM]
Anyways, a^k would better be a*k.

jollymort [1:17 AM]
EC multiplication?

theking01 [1:17 AM]
Exponents are unnecessary.

[1:17]
Regular multiplication.

[1:17]
Since they are both numbers.

[1:18]
I think bilinear group cryptography would be required for an adequate solution.

[1:19]
The problem is you need to tell the receiver how to receive it, but without knowing what their keys are.

[1:20]
Like, you have Alice, Bob, and the world.

[1:21]
Alice wants Bob to pay her, but not know that she is Alice, and Bob wants to pay Ecila (Alice's pseudonym), without the world linking the transactions.


moneromooo BOT [1:23 AM]
luigi1111w: luigi1114: luigi1112: luigiiiiii: ^

theking01 [1:23 AM]
Alice at least needs to remember her pseudonym with the current methods I think, since if you put it in txextra, the world wins.

[1:23]
Unless Alice gives Bob her keys, and then Bob wins.


One-time BOT [1:23 AM]
@theking01: One thing is that, if k is small, say k = 2, one can check that C = 2*(A) = (2*a)*G without knowing a, whereas it would be hard to check whether C = (a*a)*G without knowing already a. Also, teh exponentiation is realy just a few multiplications already, if we use fast exponentiations.

[1:24]
that is: successive squarings

theking01 [1:24 AM]
Hmm, true

jollymort [1:24 AM]
the main problem i see is communicate `k` safely without it getting `lost`


One-time BOT [1:25 AM]
k can be public\

theking01 [1:25 AM]
Actually, k can be small.

jollymort [1:25 AM]
thought we could use integrated address but seems i was wrong becasue i forgot pID there is encrypted with a


One-time BOT [1:25 AM]
Oh, you mean the sender not including it?

theking01 [1:25 AM]
Alice still has to remember not to reuse k's though.

[1:26]
Also, instead of a^k, why not H(a,k)?


One-time BOT [1:26 AM]
Why?

jollymort [1:26 AM]
but you can't stop a sender from sending again to the same kCD pair


One-time BOT [1:26 AM]
I mean, sure :)

theking01 [1:26 AM]
If she reuses k, the identities will be linked.


One-time BOT [1:26 AM]
Right, I agree

jollymort [1:27 AM]
ok how about this then

[1:27]
ignore, let me form my thoughts for 5min and i come back :slightly_smiling_face:


One-time BOT [1:27 AM]
But that is the same deal with other implementations of HD wallets

theking01 [1:27 AM]
You could make k small id numbers.

[1:28]
That could efficiently be searched.


One-time BOT [1:29 AM]
That would be an advantage. On the other hand, if you are sending a bunch of txs in short sucession, those sequential values could leak that fact a bit

theking01 [1:29 AM]
And could search the blockchain to see which id numbers have already been used.

[1:30]
But the ids could be hidden. You wouldn't need to store them in tx extra.


One-time BOT [1:30 AM]
JollyMort suggested a Mycelium style pID=hash((A)+k)

theking01 [1:31 AM]
If k is small, it can be bruteforced by the receiver.


One-time BOT [1:32 AM]
I see that now that you mention

jollymort [1:36 AM]
Ok, here goes:

Note: `(A,B)` refers to main address, `(C,D)` to some sub-address. Small caps are private view,spend keys.
1. The `k` will be incremented from 1 to ...
2. `k` is padded to the size of short pIDs with 0s, but the first byte could be "AA" or something.
2. User encrypts `k` with `a`, obtain `K`
3. User generates (C,D)=f(A,B,k)
4. User prepares integrated address consisting of (C,D) + K
5. sender pays to user
6. user decrypts K, and checks for first byte "AA", if yes, decrypt the output with (C,F)=f(A,B,k)

[1:38]
3 & 6 should be small caps (private keys)

[1:42]
think there should be some sender random data + DK exchange added somewhere in the process :smile:

[1:42]
DH


One-time BOT [1:43 AM]
Jollymort: I like the idea of carrying the information that the address was derived using this scheme by having a sufix, because I was just noticing that (A,B) would enjoy a special treatment in the user's wallet compared to any other (C,D) generated from it, in that the wallet always checks if a tx belongs to (A,B), or (A,B) plus the PID, which would be a (C,D), but never for (C,D) plus the PID.

[1:44]
Otherwise we would just revert to regulat HD linear grouth

[1:44]
in number of addresses to check

jollymort [1:44 AM]
this way you have a fallback method to restore all

[1:45]
but i still suspect i misunderstood integrated addresses, again

[1:45]
(looking for the paper describing them)

[1:46]
this: http://pastebin.com/bp5RKXuC
 Pastebin
[JavaScript] Stealth Payment IDs 0.8.5 - Pastebin.com (19KB)



One-time BOT [1:47 AM]
I am not sure I understand how the address and PID are encoded together, but it seems to reversible by playing with the wallet. I haven't tried reversing an integrated address that wasn't created by me though

jollymort [1:47 AM]
it's described in this link ^

[1:47]
reading it now

[1:48]
also, check out http://xmrtests.llcoins.net/addresstests.html

[1:48]
theres a nice explanation at the bottom of the page

jollymort [1:54 AM]
ah it can't work with integrated addresses in the current form

[1:55]
at least not in the way i imagined it


One-time BOT [1:55 AM]
What problem did you see? I am still trying to understand

jollymort [1:56 AM]
encryption key = H(sharedSecret + 0x8d)


One-time BOT [1:57 AM]
Is sharedSecret the r value?

jollymort [1:57 AM]
i think so


luigi1111w BOT [1:57 AM]
sharedSecret is rA or aR


smooth BOT [1:58 AM]
which one?


luigi1111w BOT [1:58 AM]
the one that encryption key =

jollymort [1:58 AM]
but if you give out (C,D) you need to know which (c,d) to use to decrypt it


luigi1111w BOT [1:58 AM]
indeed

jollymort [1:59 AM]
so that's why.. idea was to be able to use (a,b) to find these (C,D,k) transactions


luigi1111w BOT [1:59 AM]
I'm still catching up on backlog, feel free to ignore me


One-time BOT [2:04 AM]
Sorry, I have to be afk for a moment

jollymort [2:13 AM]
pero BOT [1:39 AM]  some hoppers in #monero-dev are solving P=NP
[1:39]  moon soon

[2:13]
lol


luigi1111w BOT [2:14 AM]
rofl

[2:14]
pretty sure that wouldn't be moon

jollymort [2:15 AM]
quite the opposite


One-time BOT [2:20 AM]
I am back

[2:20]
But still reading

[2:20]
Will have to leave in 20 min again though...

theking01 [2:29 AM]
aR=rA

[2:29]
That's the point.

jollymort [2:29 AM]
so One-time, the problem of my proposal before is in step 6., because you're decypting the pID with `c`, but you can't know which `c` to use because you don't know the `k` which is hidden inside..


luigi1111w BOT [2:30 AM]
you can't encrypt k, right

jollymort [2:30 AM]
so, bugger

[2:30]
if using ordinary pID

[2:30]
then you could give out a `k` encrypted with your a, just to obfucsate what's it for

[2:31]
but if sender uses the same pID few times, the transactions can be linked

theking01 [2:31 AM]
Can you generate random k in such a way that chance of collisions is negligible but can still be bruteforced?

[2:31]
@luigi1111

jollymort [2:31 AM]
all belonging to the same address (C,D)


luigi1111w BOT [2:31 AM]
yes @jollymort that is the concern

[2:32]
you negate the advantage of stealth addresses if you reuse these "HD" ones

[2:32]
unless k is small

jollymort [2:32 AM]
yeah

theking01 [2:32 AM]
Like would 64-bits work?


luigi1111w BOT [2:32 AM]
that's not small enough to negate the linkability thing

theking01 [2:33 AM]
I think 128 would be too big.

jollymort [2:33 AM]
16 bits


luigi1111w BOT [2:33 AM]
"any" is fine if you don't reuse

theking01 [2:33 AM]
Couldn't bruteforce k


luigi1111w BOT [2:33 AM]
if you do reuse you have to be really small

[2:33]
so there's lots of collisions

[2:33]
but then you have to check them

[2:34]
most won't be for you

[2:34]
but that's less than checking all outputs now

jollymort [2:34 AM]
so again, plain HD would work better

theking01 [2:34 AM]
Yeah, I guess doing 64-bit bruteforce for every output would be a bit much.


luigi1111w BOT [2:35 AM]
yes way too much :)

jollymort [2:35 AM]
16bits gives you 65535 sub-addresses

[2:35]
more than enough for normal people

[2:35]
179 years of tx/day

theking01 [2:35 AM]
32 bits is way too many k-collisions


luigi1111w BOT [2:35 AM]
why do we need to bruteforce k?

theking01 [2:35 AM]
So we don't need the put it in tx extra.

[2:36]
Or remember it.

jollymort [2:36 AM]
but if small enough you could put it in txextra, as it would collide with other users


luigi1111w BOT [2:36 AM]
then there's nothing to identify it...

theking01 [2:36 AM]
(you could be using two wallets, for example)

jollymort [2:36 AM]
so you lose some linkability

[2:36]
anonymity set would be all the users who're using the scheme

theking01 [2:36 AM]
(and you don't want them to generate the same k if they aren't synced)

[2:38]
If you have memory, it's easier.

[2:39]
To make a new address, do A'=H(k,a)G+A, B'=H(k,a)G+B

[2:39]
And remember k

jollymort [2:39 AM]
what's G?


luigi1111w BOT [2:40 AM]
the basepoint

jollymort [2:40 AM]
ah yes


luigi1111w BOT [2:40 AM]
but how do you remember k?


One-time BOT [2:40 AM]
Jollymort: I see. It just started to sink in for me that k can't go out in the clear, otherwise the trasactions that reuse it can be linked... Feeling a bit stupid right now, hahaha

theking01 [2:40 AM]
Computer memory

jollymort [2:40 AM]
nah, it was interesting


luigi1111w BOT [2:40 AM]
One-time are you the reddit user?

[2:40]
@theking01 what about restoring the wallet?

jollymort [2:40 AM]
i learned something more, and i think you did too :slightly_smiling_face:

theking01 [2:40 AM]
I'm saying if you can save k to a file, for example.

jollymort [2:40 AM]
but if you lose it?


luigi1111w BOT [2:40 AM]
yes but your computer crashes

jollymort [2:40 AM]
bruteforce

theking01 [2:41 AM]
And you could make them small.


One-time BOT [2:41 AM]
No

theking01 [2:41 AM]
You need to remember them to prevent reuse though.


luigi1111w BOT [2:41 AM]
who is user141?

theking01 [2:41 AM]
If your computer crashes, you need to salt the hash.

new messages
[2:41]
For future hd addresses.

[2:42]
Or generate a new base address.


luigi1111w BOT [2:42 AM]
you need to find old outputs with the restore..

[2:42]
you can't do that unless you can bruteforce the ks

theking01 [2:42 AM]
If k is small, that should be fine.


luigi1111w BOT [2:42 AM]
or have them be deterministic

theking01 [2:42 AM]
Like sequential I'd numbers.


One-time BOT [2:42 AM]
I have to go now. Catch up with you guys later

theking01 [2:42 AM]
*id

jollymort [2:43 AM]
the point of the idea was to avoid to have to try out each derived address, like you would in a HD scheme

[2:44]
maybe it's one of the "impossible" problems


luigi1111w BOT [2:44 AM]
which is basically attaching k

jollymort [2:44 AM]
which could be proven impossible

[2:44]
yeah


luigi1111w BOT [2:44 AM]
which isn't really different than a plaintext id

jollymort [2:44 AM]
exactly


luigi1111w BOT [2:44 AM]
but yes I've given this some thought

[2:44]
haven't come up with a reasonable solution yet

[2:45]
(not HD)

theking01 [2:45 AM]
It would only be necessary during crashes.


luigi1111w BOT [2:45 AM]
I mean the scan time vs linkability issue

[2:45]
they seem diametrically opposed

jollymort [2:45 AM]
yeah

theking01 [2:45 AM]
@luigi1111 I think bilinear groups could be a solution


luigi1111w BOT [2:46 AM]
I haven't looked at those

theking01 [2:46 AM]
They essentially allow you to "multiply" group elements.

[2:47]
So you could do R=rG and X=R*C

[2:47]
Or something like that.


luigi1111w BOT [2:47 AM]
interesting

theking01 [2:48 AM]
It might not work with monero's elliptic curve though. I haven't looked into it enough.

jollymort [2:51 AM]
it's an interesting problem, feels like the 5th piece to add to the privacy puzzle (1.unlinkability 2.untraceability 3.rCT 4.Kovri 5.no-address-reuse)