There are two ways to have a duplicate sending key:
Finding a hash collision.
Reusing the same tuple (P, v, n, ts, dc).
If Bob is a bit paranoid and wants to be safe from hash collisions, the only solution is to permanently store a list of all received sending keys. That’s obviously not compatible with restoring the wallet from the seed.
Protecting from the second attack is much easier. Bob just needs to make sure that at least one of the parameters must change. This can be done for example by validating that the timestamp value is not older than 24 hours and the same sending key has not been received in the last 24 hours. After restoring the wallet, not accepting new payments for 24 hours is sufficient to ensure uniqueness.
It should be noted that if both payments have the same value, Mallory cannot actually steal anything even if Bob accepts the duplicate payment. She can only swap one output for the other. If Bob is fine with this, he might choose to skip the uniqueness check altogether.
If Bob is using both desktop and mobile versions with the same seed then he must have shared “list” between devices right?
Also regarding payment proofs, what if Alice gives her tuple to Carol? If i understand correctly then with this version of payment proofs Carol can claim that she’s the one who paid Bob?
Yes, but I think it should be possible to embed the sending key into the output range proof, so it can be accessed on both devices (unless the other device doesn’t come online before the output is pruned).
This is not an unusual property. Many protocols have transferable payment proofs, e.g. Monero, but it always requires sharing a secret value (here the nonce n). But if the payment description said for example “Alice is buying some flowers from Bob”, then this proof would not be easy to transfer to Carol.
What if both Alice and Bob are evil, create a transaction with description “Carol is buying some guns from Bob” and then Bob provides the tuple and claims it was Carol who paid? I mean i wouldn’t count it as a valid evidence, but Carol would probably prefer if her signature had to be a part of her transaction in this case.
A signature can be included in the description field, which is for arbitrary data. But I don’t recommend it as it makes the payment undeniable for the sender. A plain text description accusing Carol would not be admissible in court, but a signature could likely be considered a hard proof against her. That’s one of the reasons why Monero has payment proofs that are completely detached from the sending wallet. You can’t get a subpoena to produce evidence that does not exist.
I see, don’t know how payment proofs work on other chains so it’s fun to hear that. I think the best payment proofs are the ones where the sender can undoubtedly prove that he’s the sender while receiver can only prove that someone paid to him (at least that’s my current view, it might change though if i invest more time in thinking about them). My first view was that both sender and receiver should have undeniable proofs containing the sender’s information, but that’s too problematic because if receiver is amazon they can share provable data and that’s not really a good thing.
You know this is an unattainable property, right? If Alice pays Bob, she can always share her private key with Charlie, and then Charlie can submit a convincing proof that he paid Bob.
Maybe Alice pays Bob for services. She pays Bob from a dummy account with no left over funds, and then shares the keys to this account with all of her friends, so that they can steal services from Bob. There is no cryptographic scheme that can undeniably prove who signed a message, because anyone can share their private keys at will.
Such a payment proof can only hurt Alice in the event an adversary coerces her to reveal evidence of her participation in a transaction. And Bob can never assume her proof is undeniable anyways. So what good is it? Its a lose-lose.
Agree, when talking about digital identities we should think of private keys. However in theory you could include national identity public keys in the current payment proofs. Now sure someone can share that, but i think people won’t have many incentives to do that imo and it will be harder to share it with time i think.
I don’t see how a permissionless protocol can interoperate with central issuing organization, without the protocol ceding issuance authority to that organization… which in turn makes it no longer a permissionless protocol.
But that’s a whole other rabbit hole, lol
Not to mention, you could impose a similar constraint on the 2-step protocol, so I’m not sure it has merit in this conversation about 2-step vs 3-step.
What i meant is that when you get the national identity certificate you get a key pair and you could use these as part of payment proof. I also think it’s possible to generate similar proof with some 2-step variant. But that’s a bit off-topic.
By eliminating xb from the two equations, Mallory is able to calculate the value of s2*cb1-s1*cb2, where s1 and s2 are the two sending keys (§ 3.4.1 step 3). This is not useful for any attack unless s1 is equal to s2, in which case Mallory can learn cb1-cb2, which allows her to steal the difference between the values of the two Bob’s outputs. Bob must therefore make sure that all payments he accepts have a unique value of s (§ 3.4.2 step 7).
I’m don’t think avoiding duplicate sending keys suffices.
Once Mallory has made a few hundred payments to Bob, she can use a variant of Wagner’s algorithm to find two disjoint subsets with equal summed sending key. This still allows her to steal the difference in sum value between the two payment sets.
We can leave Wagner’s attack out of it for now and look at the simplest case that goes beyond duplicate send keys.
Let’s say Mallory made 3 payments to Bob with send keys s1, s2, and s3, which happen to satisfy s3 = s1 + s2. Mallory can then determine r3 - (r1 + r2), where r1, r2, r3 are the three blinding factors that Bob chose. This lets her steal the difference between the sum of the first payments, and the third payment.
Thanks. Wagner’s attack indeed applies here and would allow Mallory to steal funds from Bob.
I updated the protocol with a mitigation that ensures that Mallory can only steal a zero amount from Bob. I also removed the uniqueness check for the sending key as it’s not actually useful.
At this point it’s too late to set the amounts; since amounts are hashed the send keys that Mallory already ran Wagner’s attack on. Mallory should just make all amounts the same to simplify the attack.
Are you sure?
Once Bob spends one set of outputs to pay Carol, then Mallory can collude with Carol to steal the other set.
A better mitigation would try to prevent the use of Wagner’s attack altogether, by changing step 3.4.1.4 to multiply Q_b not with the value, but instead some pseudo-random scalar such as H_q(T_{stopWagner}, k_s).
Are you sure this stops the Wagner attack? This would effectively increase the hash size from 256 bits to 512 bits, which makes the attack more expensive but I don’t think it prevents it.
What would definitely prevent the attack is hashing all previous k_s values, which is impractical. Another way to prevent the attack is always doing a payjoin with a self-sent output.
