Integrated Payment Proofs and Round Minimization

Development and Technical Discussion
1

Building on recent ideas for tying nonces to identity, and not committing to the public key in the kernel hash challenge, here’s a proposal for Integrated Payment Proofs to replace the existing ed25519 based proofs.

UPDATE 20200910: not committing to the public key is shown to be insecure in Eliminating finalize step

Suppose party A wants to pay party B. Their wallets have associated fixed public nonces RA = kA*G and RB = kB*G.
Suppose they agree on payment details and compute a hash
h = H(RA | RB | timestamp | amount | memo)
From this they can both compute a public nonce R = RA + RB + h*G, and hash challenge e = H(R | m) for kernel features m.

UPDATE 20200912: Using a permanent public nonce for both sender and receiver is shown to be insecure in Integrated Payment Proofs and Round Minimization

NOTE: Since m includes the fees, the parties need to have agreed already on the (maximum) number of inputs and outputs that each party will later contribute.

Up to here, no slatepacks need to be exchanged yet, just nonce addresses and payment details.

Now wallet A picks excess xA and computes partial sig (sA,RA+(h/2)*G), where sA = kA + h/2 + e*xA,
while wallet B picks excess xB and computes partial sig (sB,RB+(h/2)*G), where sB = kB + h/2 + e*xB.

Now either party sends a slatepack with their public excess, signature, inputs, outputs, and offset to the other party, who can then finalize the transaction.
Which will have signature (s,R) on excess P and offset o where
s = sA+sB
R = RA + RB + h*G
P = (xA+xB-o)*G
satisfying s*G = R + H(R | m) * P.

The hash h is committed to and signed for by both parties.
Assuming that a signature with nonce R requires knowledge of kB, this constitutes agreement by party B to accept such a signature as proof of payment.
EDIT: Kurt pointed out that this is subject to a rogue key attack, and must therefore be accompanied by a proof of knowledge of kA or either of the partial signatures.

There remains an issue of relating the nonce address to the TOR address, where perhaps one should sign for the other.

2 Likes
2

Does this scheme still suffer from malleability where P and o can be “tweaked” arbitrarily?
i.e. We could no longer rely on P for kernel/transaction “identity” (but could use R as discussed elsewhere).

We use kernel “identity” during tx relay between peers for example.
Another example of kernel “identity” is between pairs of NRD kernels where current proposal is to reference them by their shared public excess P.

3

As described it is certainly malleable. To fix that, without adding extra communication rounds, would require the finalizing party’s public excess to be computable by the other party. I’m not sure if that’s feasible at all…

4

How many rounds is this? In this comment https://github.com/mimblewimble/grin-rfcs/pull/59#issuecomment-675991756, I proposed a solution that just involved:

  1. Receiver gives sender “address”, which contains ed25519 key, pubnonce, and perhaps a signature to pubnonce
  2. Sender gives receiver slatepack with partial signature.

That’s all the receiver needs to finalize and broadcast. It’s not clear to me what your proposal is doing to improve on that.

1 Like
5

Same number of rounds as yours. Just trying to simplify payment proofs using public nonces as addresses.

1 Like
6

Combine this with a payjoin 2-2 transaction structure - the direction of the transaction is hidden, during tx building.
Sender and receiver are interchangeable, A->B would look identical to B->A.

2 Likes
7

The assumption is wrong. Yoopa, another attack.

Let’s say I am party A, and I want to fake a payment to party B, with fixed nonce RB.

I generate a random scalar r, and set my RA as RA = r.G - RB.

I set some random scalar x as well. The magic happens (rogue-nonce attack) when you see that
s = r + h + e.x is a valid signature for X = x.G and for total nonce RA + RB + h.G. And me, party A, actually don’t know neither of the private keys to RA or RB !

Using this kernel, I can prove that I paid B without him participating at all : /

That sounds magic. This (almost 1 month old) can go either way as well: Eliminating finalize step - #22 by Kurt. People can choose!

Anyways, not sure why you happened to get rid of the Diffie-Hellman @tromp. It’s not like I haven’t insisted on the need of Diffie-Hellman in several posts of the other thread. In particular note the step 3. at the end of the post on the payment proof…

Indeed, the trick if one doesn’t like rogue-nonce attacks and prefers sound payment proofs is… Diffie-Hellman, and following exactly this, both sound in security and in payment proof:
Eliminating finalize step - #77 by Kurt.
It is a pretty good exercise to read and understand the steps in both links.

3 Likes
8

Thanks for linking to your earlier posts, Kurt.
My proposal is indeed not that different from yours.
It can be considered a slight reformulation of the ideas of David and you in that thread, trying to make the two parties’ behaviour symmetrical.

I edited the OP to indicate the possibility of rogue attack when the payment proof lacks the additional signature on RA.

c is the Diffie-Hellman secret, useful to make x not recoverable by others, plus to be sure the recipient is the intended recipient, and the sender the expected sender

Doesn’t validity of the partial signatures ensure that both sender and receiver are as intended?
A DH secret does make the hash non-guessable, but so does any reasonably sized salt.
Once a payment proof is shown to a 3rd party, that DH secret won’t be that secret any more.

1 Like
9

You’re welcome, my pleasure.

Yes, with a signature that would work.

Indeed, the only differene that I can see in your proposal of this thread is that you propose that the sender uses a permanent address. I proposed an ephemeral address.

The contribution for h has to be alpha.h on one side, and (1 - alpha).h on the other. I chose alpha = 0, you choose alpha = 1/2. Despite the more symetrical aspect with 1/2 it does not change much in practice at all since at some point the two parties have to decide who broadcasts the tx. You also may choose alpha = 13/36. I prefer just alpha = 0.

All true, but it is necessary I put the Diffie-Hellman with my scheme. And adding other salts would be less scalable. Otherwise I could have chosen a signature like you propose to fix the rogue-nonce attack I described.

To sum up all this:

  • if sender uses ephemeral addresses: more scalable to use Diffie-Hellman (32 bytes to keep rather than 100 bytes for a sig).
  • If sender uses permanent address like you propose: better to use signatures.
1 Like
10

My understanding is this signature for proof of knowledge of kA need only be included in the slatepack during tx construction? It would not need to be involved in the final transaction itself?

11

No need to make the signature involved in the tx itself. Just keep it with you. Depending on what you want to prove for payment proof it is even not necessary to send this signature in the slatepack to the other party.
Proving that RA is a legit address with the signature proves at the same time that you havent done a rogue-nonce attack, and thus it proves that party B indeed received money from you when you show the payment proof with your signature that you kept with you in your records.

12

Wallet A picks excess xA and computes partial sig (sA,RA+(h/3)*G), where sA = kA + h/3 + e*xA,
Wallet B picks excess xB and computes partial sig (sB,RB+(h/3)*G), where sB = kB + h/3 + e*xB.
Wallet C picks excess xC and computes partial sig (sC,RC+(h/3)*G), where sC = kC + h/3 + e*xC.

Signature (s,R) on excess P and offset o where
s = sA+sB+sC
R = RA + RB + RC + h*G
P = (xA+xB+xC-o)*G
satisfying s*G = R + H(R | m) * P

So this would appear to scale to n participants splitting h between participants as necessary.
Everything would still be symmetric.
And a single participant would be able to collect all the slatepacks and “finalize” the transaction.

21

As I said, the decision of “who is broadcasting the tx” has to be taken at some point:
So you make the broadcaster contributing the full h. It is completely systematic.

32

For the record, I agree that how to distribute h over the participants is a rather minor concern and I could go either way, symmetric or not.

33

I fear my h/3 comment was entirely misconstrued.

My point was that the overall approach works for >2 participants. Not that h must be distributed equally across participants.

The current approach would involve a lot of communication for >2 participants due to the need to share public excesses before the partial signatures can be constructed.
This approach appears to simplify this considerably.

36

guys you are so wierdo all of you :slight_smile:

11 Likes
37

As I said before, I think you have done this new thread just for proposing a permanent nonce address instead of an ephemeral sender’s nonce, because otherwise I do not see any difference with what was proposed. I would have loved that this variation would work. Unfortunately it is unsecure as is.

Bob receives some coins from Alice, using partial signature s1_b = z + b + e_1.x_1 (1)
Bob builds an unique output for this transaction with blinding factor r. We have r = offset_1 + x_1 (2).

Bob then uses this output to send it back (with no change output) to Alice or a party colliding with Alice. Using his permanent address B = b.B. His partial signature for this second transaction is s2_b = b + e_2.x_2 (3).
We also have -r = offset_2 + x_2 (4).

"e_1.(2) - e_2.(4)" gives: r.(e_1 + e_2) = e_1.offset_1 - e_2.offset_2 + (e_1.x_1 - e_2.x_2) (5).

(1) - (3) gives: s1_b - s2_b = z + b + e_1.x_1 - (b + e_2.x_2) = z + (e_1.x_1 - e_2.x_2) ie: (e_1.x_1 - e_2.x_2) = s1_b - s2_b - z (6).

Substituting (6) in (5) yields:
r.(e_1 + e_2) = e_1.offset_1 - e_2.offset_2 + s1_b - s2_b - z, i.e
r = (e_1.offset_1 - e_2.offset_2 + s1_b - s2_b - z).(e_1 + e_2)^(-1).

That’s the kind of funny thing you can get with permanent nonces. I strongly refrain from trying to use a permenant receiving-only nonce and a permanent sending-only nonce as well. Just use an ephemeral sender’s nonce as I suggested first long time ago. The same is true for my new scheme [1] (this attack would still apply).

[1]Eliminating finalize step ReLoAdEd

1 Like
38

Thanks, Kurt. Good catch! Updating OP…

2 Likes