You can do a similar construction using a Diffie Hellman key exchange, and use it similarly to what is done in stealth addresses protocols. This provides “true” randomness for the nonce computation since the sender can generate fully randomnly an ephemeral key (sent to the sender in the slatepack) from which to derive (together with receiver secp256k1 key) the Diffie Hellman secret.
1 Like
How to do Payment proofs following the original proposal (not the “reverse” one, which has easier payment proofs):
Due to the fact that it is the receiver that finally broadcasts the transaction, the traditional payment proof cannot be performed in this proposal. Here is a proposed solition:
Set up:
- Grin users have a base secp256k1 public key that is used when they receive transactions, call it
B. Call the associate private keyb - Grin’s senders of transactions generate an ephemeral secp256k1 key when they send a transaction: call it
S, and letsbe the associated private key.Sis to be sent by the sender in the slatepack for the receiver to gain knowledge of it to finalize the transaction.
Protocol:
Let’s call c the Diffie-Hellman secret, which can be computed by the sender and the receiver only:
c = Hash(s.B) = Hash(b.S).
Now, the receiver’s partial nonce R_b could be derived by the following formula:
R_b = c.G + B. That would work well for building the transaction, but we will modify this a bit in order to enable payment proofs.
Let’s define x = Hash(c||B||tx_amount||timestamp). And we actually define R_b by the following formula instead:
R_b = x.G + B.
Only the receiver knows the private key of R_b since only him knows the private key of B.
Define by R_a being the sender’s partial nonce, and by R being the total nonce: R = R_a + R_b.
R is going to be onchain data. The receiver, in David’s scheme, cannot trick everyone and use a different partial nonce since the sender has committed to R when creating his partial signature already.
How can the sender prove payment?
He can do that by doing the three following things:
- Prove knowledge of the secret key to
R_a - Show that
R - R_a = x.G + B - Provide the preimage to
x(and toc).
The sender has successfully proven that he sent tx_amount coins at time t = timestamp to the owner of the public key B.
7 Likes
This is much better than my idea for payment proofs. Great job @Kurt. And if we generate the sender’s nonce deterministically from the kernel commitment, you can rebuild the proof by knowing only the kernel, tx_amount, and receiver’s address (I’m ignoring timestamp, since that may not actually be necessary). So payment proofs are very lightweight.
3 Likes
What specific form would the receiver’s nonce and excess take?
Sorry, I’m not quite sure what you’re asking. Can you elaborate?
How do you define the receiver’s nonce and excess as a function of receiver public key and sender public keys?
1 Like
I like @Kurt’s idea above for generating the nonce. The excess can be generated in a similar way, or just pure BIP32 (https://en.bitcoin.it/wiki/BIP_0032#Public_parent_key_.E2.86.92_public_child_key) using a keychain path derived from something deterministic, like the has of the inputs.
One cannot have both R_b and P_b linear in B (with coefficients known to sender) though, as the receiver signature would allow solving for their private key.
Right, I guess we would require having 2 public keys - one for nonce and one for excess. Unless you’ve got a better idea?
It is not necessary to derive excess for receiver anyway if you dont put total excess in signature’s message, which doesnt hurt security. Then receiver chooses whatever partial excess he likes when finalizing the tx. If you absolutely want, you can use two addresses as David suggests, yep.
Tromp is only referring to receiver’s excess & nonce - not sender’s
right, typo, i meant receiver. i edited to correct
I suspect that two public keys are necessary.
Note that if you make these the receiver public excess and public nonce, then it’s just the extra round that you were trying to avoid.
Instead you plan for these keys to be used as a base key pair from which to derive many (excess, nonce) key pairs.
The major worry here is that the derivation method somehow leaks information about the base key pair, particularly when the sender has the ability to grind over the derived nonce key and introduce subtle biases there.
1 Like
Actually, can’t you just multiply their pubkey by some factor for nonce, and add some amount to it for excess?
I think it does not solve. The problem is that the sender knows all the data in the signature’s scalar, and he can always solve for b whatever trick you do. The only way would be to be the receiver has two secrets, aka two public keys, i think.
If you do your suggestion:
s_b (the partial signature of the receiver) verifies:
s_b = alpha.b + Hash(m).(beta + b),
which the sender can solve for b since he knows everything but b.
(solution is b = (s_b - Hash(m).beta).(alpha + Hash(m))^(-1))
1 Like
You are correct. My mistake.
Beam’s Valdo pointed out that this also applies across signatures, such as the case where Alice sends to Bob twice. Since the nonce and excess for the 2nd signature would once again just be a linear transformation of the first signature’s excess and nonce, the scheme would be insecure.
So the solution appears to be unique receive addresses, randomly generated (not from seed).
Yes indeed. system of two equations with two unlnown, which is solvable. And the same would be true with n addresses. it would be solvable with n different partial sigs.
1 Like
(n+1) different partial sigs, but yes, I agree.
The good news is we can still get close to a listener-only wallet that doesn’t require bringing keys online. Just pre-generate a few hundred addresses, have a listening wallet collect partial txs, and then finalize them all at once the next time you login.
It’s also very feasible for hardware wallets. They don’t have to remain connected. You just connect once, collect addresses, and then later reconnect when you want to finalize your received txs.
1 Like
No n. My example used one address. B = b.G.
The scheme is perfectly secure if B is reused multiple times, but the partial excess is generated randomly each time by the receiver, using pure randomness independent from sender.
s_1 = (x_1 + b) + Hash(m_1).sk_1
s_2 = (x_2 + b) + Hash(m_2).sk_2
…
s_n = (x_n + b) + Hash(m_n).sk_n.
And so on and so forth. the x_i all known by the sender. This is never solvable for neither b or any of the sk_i as long as the receiver generates his partial excess sk_i randomly each time. In canonical Schnorr use, when key is reused, the nonce must never be two times the same otherwise the secret to the key can be solved. This is similar here: don’t generate two times the same partial excess.
Schnorr nonce reuse with same key X = sk.G:
s_1 = r + Hash(m_1).sk
s_2 = r + Hash(m_2).sk
Implies sk = (s_1 - s_2).(Hash(m_1) - Hash(m_2))^(-1)
Partial nonces generated by sender (x.G + B) and receiver partial excess E = sk.G reuse:
s_1 = x_1 + b + Hash(m_1).sk
s_2 = x_2 + b + Hash(m_2).sk
implies: s_1 - s_2 - (x_1 - x_2) = (Hash(m_1) - Hash(m_2)).sk
And one find: sk = (s_1 - s_2 - (x_1 - x_2)).(Hash(m_1) - Hash(m_2))^(-1).
So it is totally insecure to reuse partial excess, the same way as it is totally insecure to reuse nonce (with same public key) in usual Schnorr use.
Partial nonces generated by sender (x.G + B) and receiver does not reuse partial excess:
As written earlier, it gives:
s_1 = (x_1 + b) + Hash(m_1).sk_1
s_2 = (x_2 + b) + Hash(m_2).sk_2
In this case s_1 - s_2 - (x_1 - x_2) = Hash(m_1).sk_1 - Hash(m_2).sk_2.
The left hand side is known by the sender. Hash(m_1) and Hash(m_2) are also known by him. However there are about 2^256 different combinations of (sk_1,sk_2) that give the same left hand side: one cannot find sk_1 or sk_2. Using more signatures, say n, won’t help to find any of the private keys either. Reason is that there are n+1 independent unknown variables sk_1,...,sk_n and b, with only n equations linking them.
One can also see why using 2 addresses is unsecure:
We assume receiver’s partial excess are generated by sender under the form y.G + C, where C is, similarly to B, a public key owned by the receiver. c its private key.
s_1 = x_1 + b + Hash(m_1).(y_1 + c)
s_2 = x_2 + b + Hash(m_2).(y_2 + c).
s_1 - s_2 - (x_1 - x_2) - (Hash(m_1).y_1 - Hash(m_2).y_2) = (Hash(m_1) - Hash(m_2)).c
implies: c = (s_1 - s_2 - (x_1 - x_2) - (Hash(m_1).y_1 - Hash(m_2).y_2)).(Hash(m_1) - Hash(m_2))^(-1).
And solve for b: b = s_1 - x_1 - Hash(m_1).(y_1 + c).
Conclusion:
“Partial nonces generated by sender (x.G + B) and receiver does not reuse partial excess” is secure. The receiver can generate its partial excess secret key, independently, how he likes. From a path coming from a private seed typically. The same B can be reused indefinitely.
2 Likes