SNICKER to save address reuse?

[nopara73]

Address reuse is a bad privacy practice but it happens either to accept donations or by accident.

@AdamISZ's SNICKER protocol could be integrated to Wasabi without the user even being aware of it.

https://joinmarket.me/blog/blog/snicker/

The integration would go as follows:

In the Settings a "SNICKER" enabled flag could be set. This is opt-in, but in order to participate in SNICKER as the passive party, it would be default enabled, all the user would have to do is to accidentally address reuse.
The passive party would always get snicker filters from the coordinator with the "sync" request.
If the passive party finds a match to any of his enqueued address, then he'd fetch the encrypted message of the active party and make the coinjoin. The passive party can be default because the passive would never pays.

The active party would always look for address reuse (if coins are enqueued) (how? should this be after Core integration and snicker could be only enabled actively if core is also enabled? or maybe the active party could fetch bech32 address reuses from the coordinator?)
And if bech32 address reuse is found the active party would make the encrypted message to all those and post them server (note these encrypted messages has to be cleared often and cannot be let to grow too big.)
The encrypted message would be a signed coinjoin tx from enqueued coins to the reused address pubkey.

[nopara73]

Or just incorporate the active party's part to sendtx instead with a timeout, it'd be more cost-effective and encrypted messages would be managable too.

[AdamISZ]

Obviously I'm not aware of details, but in general it seems reasonable. I remember in that blog post making the amusing observation that SNICKER works best in cases where people have screwed up their privacy by reusing addresses, so this fits into that paradigm.

I'm not so sure that one should automatically assume that the passive party pays nothing. I wondered about this; I can see arguments both sides for who should pay, active, passive or neither (say 50/50 txfee being the 'balance point' in the middle).

[AdamISZ]

Btw this was a rough and ready POC for SNICKER, in case it helps (some notes about ECIES and similar for the mechanics of transferring the tx proposal).

https://github.com/AdamISZ/SNICKER-POC

[MaxHillebrand]

This is a brilliant protocol!!

I think it requires BIP 322 generic message signing format in the encryption manager first.

[AdamISZ]

Not sure we need message signing for this? Basically you use ECIES to encrypt a partially signed transaction to the recipient's pubkey.

Also I never thought about it before but clearly we should use PSBT for the partially signed tx proposal (it didn't exist at the time of the blog post).

Lastly I wonder if I shouldn't write a BIP for SNICKER itself, because standardising on the format of the proposal tx itself would be nice (as well as standardising the destination tweak mechanism) for cross-wallet compatibility. There are bound to be a lot of details people wouldn't immediately agree on but it's worth trying, if there is interest.

[MaxHillebrand]

Oh, yes, you are right - I thought that BIP 322 is also the standard for de/encrypting SegWit addresses, but it seems that in deed it only does the signing and verification.

Yes, PSBT would be a good standard to use for this.

How [if at all] is the Wasabi coordinator / central server used here?

[AdamISZ]

The protocol needs, effectively, a "bulletin board". Something where you can post proposals and have receivers poll and download recent proposals. The receivers can in principle download everything and then check one by one whether decryption works for them.

As I expounded on in that old blog post, there is a significant scaling issue there - if a bunch of proposers make proposals for all reused addresses on the blockchain, and perhaps also make nonsense proposals, you have a big downloading and decrypting workload.

A coordinating server could serve a significant role in controlling how much bandwidth gets used up. See some discussion on this issue in the blog post. Lots of ways to skin this particular cat, it seems.

[nopara73]

Also I never thought about it before but clearly we should use PSBT for the partially signed tx proposal (it didn't exist at the time of the blog post).

Disagree. The largest bottleneck of this scheme is the size of the messages, PSBT worsens that.

As I expounded on in that old blog post, there is a significant scaling issue there - if a bunch of proposers make proposals for all reused addresses on the blockchain, and perhaps also make nonsense proposals, you have a big downloading and decrypting workload.

No need to download the proposals at all. Imagine the proposal has the following format:

{address:"xyz", message:"imencryptedfoobarbuz"}

Then the server could store these in a dictionary like this:

var myDic = new Dictionary<BitcoinAddress, List<string>>();

So if a new message arrives to the same BitcoinAddress then the server would just add it to the corresponding list.

Finally the server would also maintain a (golomb-rice?) filter of the addresses:

filter:asidjiwqjdljqdijwqdjowqjdoiwqjdoijdwqoijq21321321dajiodoisajdoijsad

This filter would be constantly fetched and tested by the passive observers. If a match found, the corresponding values in the dictionary are fetched only. Then decrypt->sign->propagate->happy.

[AdamISZ]

Disagree. The largest bottleneck of this scheme is the size of the messages, PSBT worsens that.

Ah yes, I forgot that aspect. On balance I'd agree with you there but it still seems debatable, it rather depends on how the scalability issue is addressed.

Re the rest of your suggestions:

Part of this is how purist you want to be. I guess you have a very different idea in your head about how to do this, than I did originally.

My original idea (heavily focused on in the discursive first half of the blog) was a huge focus on anonymity and desynchronization. So, Alisa and Bob in the scenario are never online at the same time and know nothing about each other. In this scenario they can avoid even publishing an address or pubkey. Alisa simply publishes encrypted blobs to the (Tor HS) bulletin board, Bob simply retrieves all of them without any idea which applies to him (and by retrieving all of them, he leaks no information to the passive network adversary). Successful decryption of the first (AES-CBC, say) encryption block to the magic bytes would be enough.

This is the perfect scenario from the privacy perspective, but throws all ideas of scalability out of the window.

On the other hand, I remember Greg Maxwell's response to the idea was that maybe it wouldn't be so bad to index by key (or address perhaps), so similar to what I think you're saying. I was never really sure but it doesn't sound unreasonable.

I also wondered about the idea of charging a fee (or could be a fidelity bond) for the right to publish proposals, but I didn't really think it through too much. In the absence of this we have the spam problem.

Your additional idea of using filters sounds smart for dealing with the problem of privacy leaks from fetching proposals. Similar to the Bitcoin client side filtering case, I guess? It might depend on the scale of the system, I remember calculating that an individual tx proposal encrypted would only be slightly bigger than a normal tx, so unless the system is huge, downloading everything may well be entirely feasible.

[AdamISZ]

Oh and I've just recalled that I did write down a serialization proposal in this section of the original gist here: https://gist.github.com/AdamISZ/8dc3bbb00ac33e270029fe1cdb52f3f4#a-protocol-for-the-most-naive-version-in-broad-strokes

[lontivero]

I wonder if I shouldn't write a BIP for SNICKER

It would be good imo. I think we need a place where to discuss it in detail.

unless the system is huge, downloading everything may well be entirely feasible.

Even when this can be true, the UX could be a problem and not only for the size of the file but also for the number of cryptographic operations. I agree with @nopara73 that some kind of index is needed.

---

Comments about SNICKER protocol

• Alice doesn't need to use a random k to generate a new address for Bob because she can use a well-known constant defined in the protocol. This reduces a bit the message size and simplifies the wallet implementation because we don't need to store the k value. There is no reason to use a random number here.

• IMO the magic number is redundant. The article says that "Finding a match occurs where the decryption has the correct initial magic bytes" but I am not sure about it because ECIES produces authenticated messages (HMAC) so, in case the HMAC code verification fails the message is not decrypted.

• A really naive approach to simplify the public key discovery would be to use 1-of-1 multi-signature scripts because then the extraction of the pubkey is trivial and it would be also a mechanism for signaling the willing to participate in a SNICKER cj.

[AdamISZ]

Alice doesn't need to use a random k to generate a new address for Bob because she can use a well-known constant defined in the protocol. This reduces a bit the message size and simplifies the wallet implementation because we don't need to store the k value. There is no reason to use a random number here.

Unfortunately not; if the constant is publically known, then any outside observer could reconstruct the destination address, and thus the privacy effect is lost.

[AdamISZ]

IMO the magic number is redundant. The article says that "Finding a match occurs where the decryption has the correct initial magic bytes" but I am not sure about it because ECIES produces authenticated messages (HMAC) so, in case the HMAC code verification fails the message is not decrypted

That is true. What I had in mind was that in a scenario of doing a lot of decryption, it may be a good idea to create a scenario where failure could be detected in the first AES block to avoid a lot more decryption. In practice this may be irrelevant. I'd tend to agree with you, I guess the symmetric decryption step is never realistically a bottleneck anyway.

[AdamISZ]

A really naive approach to simplify the public key discovery would be to use 1-of-1 multi-signature scripts because then the extraction of the pubkey is trivial and it would be also a mechanism for signaling the willing to participate in a SNICKER cj.

Not sure what you meant, you don't mean native multisig? If you don't, what advantage would it confer to use msig vs p2(w)pkh? In both cases the pubkey is revealed on redemption. I'm reasonably sure I didn't get the point :)

Thanks for taking the time to review.

[lontivero]

Alice doesn't need to use a random k to generate a new address for Bob because she can use a well-known constant defined in the protocol. This reduces a bit the message size and simplifies the wallet implementation because we don't need to store the k value. There is no reason to use a random number here.

Unfortunately not; if the constant is publically known, then any outside observer could reconstruct the destination address, and thus the privacy effect is lost.

I get it. In that case instead of using the k value Alice could use the x-coordinate of the shared key (what nobody can know).

A really naive approach to simplify the public key discovery would be to use 1-of-1 multi-signature scripts because then the extraction of the pubkey is trivial and it would be also a mechanism for signaling the willing to participate in a SNICKER cj.

Not sure what you meant, you don't mean native multisig? If you don't, what advantage would it confer to use msig vs p2(w)pkh? In both cases the pubkey is revealed on redemption. I'm reasonably sure I didn't get the point :)

Forget it, I made a mess in my mind. I think the best will be using the R extracted from the signature as you describe in your article because it is present in both ECDSA and Schnorr. I will continue thinking about this anyway ;)

[AdamISZ]

I get it. In that case instead of using the k value Alice could use the x-coordinate of the shared key (what nobody can know).

Huh, interesting suggestion. Actually now I remember (or think I do - old man syndrome!) that Tim Ruffing ( @real-or-random ping) suggested this to me in London last summer.
I'm a bit suspicious of the idea of reusing the symmetric decryption key for the Bitcoin address tweak, just on a kind of conservatism (don't reuse secrets for other than original purpose), but I don't see an issue. So this could maybe save 10% of the size in a typical case (imagining a 300-400 byte tx, although there may be other metadata), is that your reason for suggesting it, or is there another reason?

I think the best will be using the R extracted from the signature as you describe in your article because it is present in both ECDSA and Schnorr

Yes it ("Keys Encrypted to R") is a more logical/elegant scheme (and btw hat tip @fivepiece for suggesting it as I recall) than address reuse, but I suspect it's a bit more complicated to implement.

[lontivero]

is that your reason for suggesting it, or is there another reason?

Yes. Because If the bulletin board is not indexed then saving space is something desirable.

I'm a bit suspicious of the idea of reusing the symmetric decryption key for the Bitcoin address tweak. (sic) don't reuse secrets for other than original purpose.

I understand and I mostly agree with you however take into account that that is what "Keys Encrypted to R" is suggesting: the wallet will be reusing a secret r originally created for signing a transaction A to derive the private key needed to spend the coinjoin transaction's (B) output.

There is an additional annoyance here, the R point in the signature is generated with lower entropy r because this has to have an inverse r^(-1) and *Alice" knows it. She knows that the resulting private key is (r + k). I don't know how this plays in the whole scheme.

[lontivero]

I was thinking a bit more about using R and I think it is not a good idea. Basically, given the r (what is called k in the article) has an inverse, it means it is a prime number. Using the formula N/ln(N) (where N is the order of the secp256k1) to estimate the number of prime numbers less than N it gives 4.5e74. Also, r has some other restrictions because it is selected only when it results in a slow R (bitcoin/bitcoin#13666) so, it uses only a subset of those prime numbers. I think it could be dangerous to use R.

[AdamISZ]

I was thinking a bit more about using R and I think it is not a good idea. Basically, given the r (what is called k in the article) has an inverse, it means it is a prime number.

No that's not a concern, to explain:

In both Schnorr and ECDSA, R = kG, k must be selected uniformly randomly (well "must" - if you want decent security there'd better not be any bias) from the group of integers modulo N (with the operation of addition, mod N).

Every element has an inverse (that's part of the definition of a group).

[lontivero]

You're right, all k < N are a group and they all have an inverse. Thank you.

[real-or-random]

I skimmed over this. Just two minor comments about ECIES:

• Indeed, ECIES has redundancy built-in via the HMAC, so no need to add it via a magic number in the plaintext. Ciphertexts for different keys will just result in decryption failures.
• It seems perfectly fine to reuse the shared secret if you separate domains in the key derivation function. (If the shared curve point is abG, use H(abG||"ECIES") for the normal ECIES keys and H(abG||"SNICKER_ADDRESS") for deriving the k to create the new address.)