Why we use addition instead of multiplication in public key tweaking

[dr-orlovsky]

This is standard way the public key tweak procedure works, including the code in the rust-bitcoin library written by A. Poelstra.

However it is known that public and private key multiplication is more secure procedure, giving less predictable result, and preventing malicious agents from collecting the information from multiple sources and assuming the actual tweak factor.

We decided to ask Leo and Andrew on this design choice...

[dr-orlovsky]

Alekos answer:

I talked with Leo about the EC multiplication thing and his answer was that even though it should be safe to do multiplications, sums are faster and more "standardized" because other schemes use it (Taproot, opentimestamps)

[dr-orlovsky]

Follow-up of the discussion we had online regarding this issue: in RGB, we tweak public keys in order to commit to the proof — the same way it works in OpenTimeStamps protocol. The tweaked public key looks like any other public key, and it is not a security issue that we need to hide the tweaking factor (proof hash) or the original public key from some chainanalysis tools: they still would not be able to guess which key is tweaked, and even if they know, they have no clue what could be both original pk and the tx hash... So using multiplication will significantly increase CPU load for RGB proof verification (especially in cases of large proof DAGs, which may be the case for some assets like USDTs), but will not add to the security.

@emilbayes pls let me know what do you think on this argument

[emilbayes]

I wasn't concerned about the privacy of the original PK. I was just asking if this is known to be a safe operation, ie. can I recover any knowledge about the private key if I can make you use multiple tweaked private keys. With the "multiplication" it's the DH assumption, but with addition I don't know that security problem this is. Wrt the performance argument; you already have to do multiplications anyway here as you need to hash the commitment and the multiply by the base point and then add to the PK. I don't know if there are some clever tricks that can be utilised here, but with addition you have a base point multiplication and then a point addition. With the multiplication method you only have to multiply with the PK

[dr-orlovsky]

I am definitely not a cryptography expert to make a decision here, so I will probably summon @petertodd who designed OpenTimeStamps and ask his opinion, looks like we have common practice vs more secure option.

But I will also propose to assign this issue to the second version of the protocol: it is fine if we will start with less secure addition and later migrate to multiplication.

[dr-orlovsky]

My opinion, that in order to reconstruct a private key from multiple transactions, first you need to know which of them are RGB txes, then — which of them spends to the same owner, and then to be sure that the owner uses is the same pk and not HD. The possibility of such analysis looks really unlikely...

[dr-orlovsky]

It seems that according to https://crypto.stackexchange.com/questions/11316/subtracting-a-point-in-elliptic-curve-cryptography we can reverse addition of two public keys. This provides a security breach for chain analysis tools, since I can index all existing public keys, subtract all known contract ids and proof ids and see is there any repeated occurrences of the same key withing the set before and after subtraction. This will allow to build a graph of transactions spending assets and reconstruct which assets they spend.

So it is clear that of the referenced article is correct we need to use multiplication instead of addition. However I am not a cryptographer, so it will be nice to have more experienced opinion

[petertodd]

@dr-orlovsky I think you're analysis is correct.

Basically, what you need to guarantee is that the original public key for each distinct type of contract is itself distinctly derived, so that two different uses for different contracts don't use the same original key. IIUC you can do that by deriving a distinct "key chain" for each distinct contract type.

This does potentially pose a backup issue, as you'd additionally need to know what contracts you had to recover your wallet.

[dr-orlovsky]

@emilbayes, now I can summarize the answer to the question:

1. Public keys can only be added; multiplication on EC is possible only for a scalars (like n) multiplied by public key, which is an equivalent of the public key being added to itself n times. So there is no dilemma "multiplication vs addition" at all; when we do apply a tweak to the public key, we multiply the tweak to the generator (which is a public key) and add that to the original public key, i.e. both multiplication and addition are used, and this provides the same guarantees as just multiplication of the original public key to some scalar.

2. The addition of the public keys is reversible: you just need to add a negative of the public key, i.e. if A+B=C, then A=C+(-B), which is simply done by reversing the x-value, i.e. for a compressed bitcoin public key the change of the first byte from 2 to 3 - or vice verse.

Nevertheless, the prevention of the double spend follows from the different fact: we do commit to the original public key P, so the tweaked public key T is derived as T=P+t*G, where t is committed to the P value itself: T=P + t(P, msg) * G. Thus, even if we know P, T and msg, it is impossible to construct another P' != P and msg' != msg, such as T=P' + t(P', msg') * G, since it will be impossible to find out such P' = t(P', msg) * G - T due to hash function guarantees (so we do not rely on the discrete log problem here at all).

[emilbayes]

1. Your commitment, which is essentially as hash of the information, is a scalar
2. I thought that being one-way was a feature

Nevertheless, my concern was in using these "point added" keys for signatures

[dr-orlovsky]

1. It is a scalar and we multiply on it: we multiply generator on scalar commitment, which results in point which is added to the original public key
2. No, it happens that it is not