Eliminating finalize step

Currently, grin transactions are created using the following 3 (simplified) steps:

  1. Send - Sender commits to amount, fee, and a public nonce, public excess. It could also commit to tx offset, inputs, change output, and probably others.
  2. Receive - The receiver adds their output & rangeproof, and commits to their public nonce and excess. It then updates the total kernel commitment, and signs for their half of the kernel.
  3. Finalize - The sender adds their half of the signature, aggregates the 2 partial signatures, and builds the final transaction.

The sender can’t just include their part of the signature as part of the send step, because it doesn’t yet know the receiver’s public nonce and public excess. But what if it did?

Grin now has slatepack addresses, which are just encoded ed25519 public keys. If we extended these to include a secp256k1 public key, then we could treat those addresses as BIP32 parent public keys, and the sender could generate the public nonce and public excess for the receiver, and just inform them of which keychain path they used to generate the public keys.

In fact, the sender could generate everything about the transaction except the bulletproof and the receiver’s half of the signature. Then they could just pass that to the receiver, who just adds their half of the signature, and appends a bulletproof to their output. The transaction is complete - no finalize step necessary!

This is a pretty radical change that would require rethinking nearly everything about the wallet: Play & replay attacks, payment proofs, invoices, etc. But I believe these are all solvable, and will propose solutions for these later, if there’s enough interest in this idea.

18 Likes

This idea sounds as a genuine improvement of the current public keys. It is so elegant and simple that it is hard to understand why no one else came up with this. I hope it is technically possible.

2 Likes

I’m probably missing something obvious here, but I don’t understand how this works.
Can you explain in more details how does the receiver derive the nonce and blinding factor that the sender “picked” for him? Or in other words, how does the sender use the secp256k1 public key to produce a subset of private keys for the receiver to use?

Addressing this finalization step would be amazing for Grin. It would really ease transactions for the community. At that point Grin would have the same ideals as cash/checks without any additional steps. Great idea david.
-Makcer

1 Like

Given a public key, you can use bip32 to derive any number of child public keys, without knowing the private key. So if you gave me a pubkey, I could give you a different pubkey that I generate from it, tell you the “path” used to generate it, and only you would be able to figure out the corresponding private key.

This is exactly how “view keys” work in bitcoin, btw.

2 Likes

I agree. Removing the finalize step should make grin usable without sacrificing the few benefits we get from interactive txs.

4 Likes

Interesting idea. I do worry about payment proof feasibility though. Looking forward to your solution…

In the case where the sender needs no change output, this doesn’t seem too different from just sharing the blinding factor with the receiver, in effect creating a 1-of-2 output.

5 Likes

Interesting, I didn’t know that’s possible. I thought you could only derive child private keys from a master private key. In fact it seems kind of odd to me that it can be done on public keys, I don’t quite understand how it works.

If somebody’s interested, CKDpub is indeed mentioned here.

@Paouky The general idea is simple. For elliptic curves, private keys are scalars and pubkey are points generated by multiplying the private key by a common generator point (G).

If I have 2 private keys, s1 and s2, I can generate public key P1=s1G, and public key P2=s2G. It just so happens that if I add P1+P2=P3, that’s the same as if I add s1 and s2=s3 and multiply times the generator (s3*G=P3) . So:

(s1+s2) G = (s1G) +(s2*G) = P1+P2 = P3

child keys are a bit more complex, but just to show you how I can generate a pubkey from your pubkey P=s*G, I can just generate a random secret key s', and add s'*G to your pubkey P to get P'. Then give you s', which you can add to your original secret key s. The result is the private key for P', and only you know that private key.

(Typed on mobile while holding kid - sorry for mistakes)

1 Like

That’s an interesting idea to reduce the extra step of communication.
I think I can see two problems arising from this construction whereby it is the receiver that broadcast the transaction:

  • The usual suspects: the recently-discussed play attacks. Here it is just that the receiver can abort the transaction, and it can be a bit annoying for the sender who would maybe prefer to self spend to protect those outputs, and bloat the blockchain with an extra kernel.
  • Payment proofs (maybe are they possible?)

One thing that could maybe fix both is to do the reverse of your proposal, while using the pivoting idea you provided above.

it’s the receiver that does all the job first, and use the sender’s address.
This fix the problem of breaches of play attacks i think, since it is the sender that controls sending the tx or not, and learning receivers information (his eventual bulletproofs and kernel offsets) does not seem to create problems and falls back to what we currently do when building a Grin transaction (Sender to receiver to Sender communication, as you detailed in OP). For payment proofs, it is probably easy to do them with that variation, since the sender can choose to broadcast, or not, the final transaction, depending if he is happy of the signatures provided by the receiver for the payment proof.

Only question with that is UX. How will people like that it is the receiver that must know the sender’s address. Can also create an interesting framework

5 Likes

@david I think I got it now. I knew about the so called homomorphic properties, but things clicked better with your explanation now. My understanding is as follows:

So if s*G is the receiver’s public key, the sender adds s'*G to it, which is random point on the curve, and the result is point (s+s')*G. The sender will then use this point as the nonce / blinding factor commits (a different one for each of those?) of the receiver. This way he has all he needs to construct his side of the signature.
The sender then shows s' to the receiver, which in turn is able to derive new private key s+s' himself.

Cool.

p.s. try to teach your kid to say ‘paouky’. it’s toddler friendly.

He’s <2 months old. It could be a while :joy:

4 Likes

Kurt,

Maybe the sender could add an expiration to the funds were they would just expire back into their own wallet, kinda like a check from the bank. Or even be able to stop the transaction from the sender’s wallet at any point. (coming from a non-technicall background) The only issue is see with the receiver initiating the job, is it would adds complexity for the user experience. If a sender could create a transaction slate and never have to know or communicate with the receiver that is what i would invision. Send an email, letter, cold slate, usb drive, anything and whoever gets it can deposit it into their account. Done… :sunglasses:

Macker

1 Like

How so? The receiver never learns the blinding factor.

2 Likes

The receiver never learns sender’s blinding factors. But the reciprocal is also true: the sender never learns receiver’s blinding factors :slight_smile: (even if there’s no change output).

But she learns the next best thing. A partial signature for spending it anyway she likes. No need to use the sender-constructed output commitment. Since she knows its blinding factor, she can replace it by any other output, and adjust the kernel offset.

How is that not as good as knowing the sender’s blinding factor?

It seems you were first mentioning that in case of no change output, the tx output becomes a 1-2 output. This one is not true since the sender never learns receiver’s blinding factors with David’s construction, even when there is no change output.

In your post above, you are mentioning something different, which is a play attack vulnerability in case the receiver doesn’t broadcast the tx. This is the same threat model as other play attacks (that can be achieved differently) that were discussed before.

No, you misunderstood. It is the sender’s output that becomes 1-of-2 by providing a partial signature for spending it.

Ok. But the receiver never learns sender’s blinding factors at all, in all cases.

So you were saying that it is vulnerable to a play attack, which is true (mentioned it in my post), and is the same threat as other play attacks. It has nothing to do with change outputs or no change outputs.

1 Like

Am I right in understanding your proposal effectively makes private nonces deterministic, through the sender choosing a derivation path for the public nonce?

My (limited) understanding of Schnorr is that the private nonces must be generated randomly.
It would seem that allowing the sender to “force” the recipient to choose a particular nonce based on the derivation path for the public nonce potentially changes the security model here.

Edit: The catastrophic case would presumably be if the sender somehow forced the recipient to reuse a nonce that had been previously used in a signature. But there may be other more nuanced issues here with deterministic nonce generation.