Another Take on Non Interactive Transactions

[Elwailly]

This is another take on non-interactive transactions.

I had posted a failed attempt in the past here

Mimblewimble Non-Interactive Transactions

I’m new to Grin and am very excited about the technology. I noticed that transaction are interactive and decided to take a cut at making them non-interactive. (I’m not judging the merits of either way but I’m new here and may have missed some discussions, so bear with me.) Assume Alice wants to pay Bob but Bob is not online. Alice has a public key, A, and Bob has well known public key, B, available to Alice. I’ll develop the method following these steps: To preserve Bob’s anonymity, Alice g…

Recently, Gary Yu proposed a scheme that modified current Mimblewimble transactions. "Pay-to-Address" / "Pay-to-Public-Key": Non-Interactive Transaction Solution for Mimblewimble
in an Email To: mimblewimble@lists.launchpad.net

In this writeup I propose allowing non-interactive transactions based on the insight that the Rangeproof and the commitment to zero H multiplier can be separated to allow sending to a pay-to public key.

I’ll develop the method following these steps: Alice is sending to Bob

• Bob publishes a “send-to” key with a signature proving no H-Multipliers in his public key
• Alice generates a transaction on her own to her own blinding factors and with range proofs on her own outputs as well as zero H multiplier signatures
• Each one output in her transaction, now proven to be in range, is forwarded to one recipient cover by re-blinding it for the ultimate recipient. Since we have (single input goes to single output) we can say this step requires no range proof. However, we still require a zero H-multiplier proof. This is done as follows
• To preserve Bob’s anonymity, Alice generates a private shared secret with Bob , q, for the purposes of this transaction
• Alice generates a blinding factor for Bob based on his “send-to” key and the shared secret and applies it to one of the transaction outputs
• Alice generates a “ Sender Generated Signature ” on the transaction output that proves that the output minus the input has no H-multiplier.

The main difference in transactions is that each output has an extra blinding step after the range proofs are done .

Receiver Publishes a Receive Public Key with “Zero H-Multiplier” Signature

Bob publishes a “Send-To” key, “B”, with secret “b”. Where B = bG.
Bob also publishes a signature to prove the H multiplier is zero in his public key:

r = Hash(b)
R = rG
s = Hash(G)b + r

The signature, (R,s) with public key B, proves the H multiplier in B is zero.

Sender-Generated Zero H-Multiplier Signature

The insight here is that Alice can generate another signature for Bob from his published one with the same desirable property. Alice has a private key, a, with public key A = aG. Alice, generates a shared secret with Bob as follows:

q = Hash(m,aB) where B is Bobs public key and m is unique to this transaction

Note q is now a shared secret between Alice and Bob since Bob can generate it with q = Hash(m,bA)

Now notice that multiplying both sides of Bob’s Schnorr signature by the shared secret produces another relationship that still holds the properties we desire.

q (s = Hash(G)b + r) which expands to qs = Hash(G)qb + qr

So, given [(R,s) B], Alice can generate [(qR, qs) qB], renamed [(R’,s’) B’], which is a signature that proves that the H multiplier in B’ is zero. (B’ = qB, if B’ has a non-zero H multiplier then B must have one as well, which is a contradiction.)

Sender Generated Blinding Factor

Alice now uses B’ as the difference of the blinding factor for Bob and her blinding factor (Bob’s public blinding factor can be calculated from the difference) and publishes (R’,s’) as the proof that B’ has a zero H multiplier; verifiable as s’G = Hash(G)B’ + R’ (from qs = Hash(G)qb + qr )

Both Alice and Bob know the shared secret q, but only Bob knows b’, the secret part of B’, since b’ = qb and only bob knows b.

Addendum

By careful choice of A and m, Alice and Bob will never interact.

• A is selected as the curve point corresponding to the blinding factor the sender, Alice, is using on the input coins.
• m is selected as the Hash of unique parts of the input.
• Bob, the recipient, has a wallet that checks all new outputs by retrieving A and m, calculating a q = Hash(m,bA), and checking that B’ has the property that B’ = Hash(m,bA)B
• The wallet then calculates Bob’s blinding factor from B’, determines the sent balance, and adds the balance to the total Bob has in the wallet.

No interaction between Bob and Alice outside the transaction required!

Regards,
Farid

[Elwailly]

Sorry. Doesn’t work. The sig (R’, s’) is not a real signature. It needs a commitment to R’ inside the hash of the massage being signed.

s’ = r’ + Hash(R’, G)b’

Alice can’t produce s’ without b’

[MerlinsBeard]

I get excited whenever I see another attempt of yours. Keep trying, please!

[Elwailly]

Just thought I’d mention in case it’s not obvious.

The difficulty above is in keeping Bob’s identity private. If that is not a requirement, we can use the method as described by using Bob’s public signature directly, as follows:

Bob publishes a “Send-To” key, “B”, with secret “b”. Where B = bG.

Bob also publishes a signature to prove the H multiplier is zero in his public key:

 r = Hash(b)

 R = rG

 s = Hash(R,G)b + r

Note, here “s” does commit to R in the hash

The signature, (R,s) with public key B, proves the H multiplier in B is zero.

Alice now uses B as the difference of the blinding factor for Bob and her blinding factor (Bob’s public blinding factor can be calculated from the difference)

Only Bob knows b, the secret part of B, and only Bob can calculate his private blinding factor if Alice’s private blinding factor is known to him. I don’t know if there is an easier way to do this, but it can be done by including a field created by Alice that only Bob can read with her private blinding factor included. For example

 field = a Hash(m, aB) (Bob calculates a = field / Hash(m, bA))

That’s it.

The takeaway; We don’t need the same secret for the range proof and the final blinding factor…

[tromp]

@Elwailly

if Alice’s private blinding factor is known to him

This appears equivalent to Alice just communicating her output’s blinding factor to Bob to turn it into a 1-of-2 output, that either party can spend. With all the usual problems…

[Elwailly]

Alice can’t spend the output. She doesn’t know b-a, Bob’s cover. ( I think. . I’ve been wrong so many times)

Farid

(People seem to really want pay-to addresses)

[Elwailly]

In more detail:

Bob has published a send-to key B and proven it has a zero H multiplier with a signature he generated from b, the secret part of B.

Assuming Alice owns 5 coins in two inputs.

 (162G + 3H)		public blinding factor 162G and pubic coins 3H 
 (9G + 2H)		    public blinding factor 9G and pubic coins 2H

She wants to send 4 coins to Bob and have 1 coin go back to her in change.

She knows Bob will see the 162G and the 9G. So she uses A = 162G + 9G = 171G. The secret part, a, will be 171 and only Alice knows that. She is considered to have published A = aG.

She picks a temporary blinding factor for Bob’s output as follows. q = Hash(m,aB). Let us assume this is q = 113. What is important is that later Bob will be able to recover this secret because he can calculate q = Hash(m,bA). (aB = bA).

She picks another blinding factor for her change, let us say 54.

She creates outputs.

   (113G + 4H)
   (54G + 1H)

She performs a range proof that shows that the 4 and the 1 are non-negative. She can do that because she knows all the private parts of the outputs.

She now shows that the excess value is

 (162G + 3H) + (9G + 2H) - (113G + 4H) - (54G + 1H) = (4G + 0H)

and she knows the private 4 and uses it to sign the output proving that the H multiplier in the excess value is zero.

Now she re-blinds the output to Bob. It has already been range-proofed.

To repeat, Bob has published a send-to key B and proven it has a zero H multiplier with a signature he generated from b, the secret part of B. Let’s assume b = 10 and B = 10G

Alice forms the new output:

(113G + 4H) + B    =    (113G + 4H) + (10G + 0H)    =    (123G + 4H)

Since we know B has zero coins, we know we haven’t changed the value of the output. Just re-blinded it.

Alice cannot spend this output. She does not know b. She does not know the secret 123.

Bob knows b and can recover the secret 113 (because he can calculate q = Hash(m,bA)). Note that (aB = bA). Now he knows his blinding factor [113+b] = 123 and he can spend the output,

(123G + 4H)

[tromp]

There are two big problems with your reblinding scheme.

@Elwailly

Now she re-blinds the output to Bob. It has already been range-proofed.

reblinding the output invalidates the range-proof. Only Bob, knowing b, can make a range-proof for this output.

@Elwailly

Alice cannot spend this output. She does not know b.

That means she also cannot compute a kernel for the transaction.

[Elwailly]

How can Alice produce a range proof that can be checked to be valid later that is not correct if the validator happens to know B? Notice this proof can be validated by anyone even if they don’t know B.

Only later is B introduced to re blind. The re blinded output is not involved in, and cannot invalidate the proof. The argument to accept the final out is based on B not having any coins and therefore the final out coin is still in range. No range proof required.

The kernel you are thinking of is generated before B is introduced. It is valid. The final re blinding is an additional step added to the protocol.

By the way, on a different error, the description of how Alice generates A = aG above is faulty. At this point she has to generate ‘a’ randomly and publish A for the above to be correct.

[Elwailly]

An intriguing point is that Alice has signed the excess (4G + 0H) above. Only she knows the secret part of 4G. She is essentially publishing her own B and the signature that proves it has no coins. Can this be used later by Carol to send to Alice?

[tromp]

I read your proposal as Alice building a transaction and then tweaking the output for B (reblinding) before publishing it. Are you instead proposing 2 separate transactions? Where the first just produces an output of Alice in the right amount?
For the purpose of this discussion, we should simply assume that Alice already has an output in the amount she wants to pay Bob.

[Elwailly]

Yes.

Although I was thinking of the whole thing as one extended transaction because it can be generated in one step.

[Elwailly]

I think you are right. We can just assume Alice has an output in the right amount. However she may not. I don’t see the need for two separate transactions in this case.

[tromp]

So Alice has aG+4H and wants to pay to Bob’s output of bG+4H.

I think that any solution where Alice doesn’t share a with Bob (which instead just makes aG+4H a 1-of-2 output that either can spend) requires Bob’s involvement.

[Elwailly]

If (aG + 4H) is an intermediate step in a single extended transaction, then it is already spent by Alice when she publishes the extended transaction. There is no opportunity for Bob to spend it.

[tromp]

So how do you propose to sign the kernel (b-a)G, when only Alice knows a and only Bob knows b?

[Elwailly]

I don’t understand.

The kernel is generated and signed by Alice before B is introduced. The re blinded output is accepted based on this Alice signed kernel and the properties of B. No final signature by both Alice and Bob required here to prove things balance.

Maybe I’m breaking other desirable properties of the kernel by having Alice extend her transaction with a re blinding?

[tromp]

@Elwailly

The kernel is generated and signed by Alice

What kernel?
Can you please rephrase your proposal in the simplest setting where Alice has aG+4H and wants to pay to Bob’s output of bG+4H.
Then there is only the kernel (b-a)G, which Alice cannot sign by herself.

[Elwailly]

{ [ (aG+4H) to (xG+4H) ] to (xG+bG+4H) }

[ ] is a transaction as we know it today. Alice knows everything about it and has done rangeproofs and signed it and produced a kernel etc. She does not publish it. She publishes { } as one extended transaction.

{ } is the extended transaction I am discussing today. It is not defined in the protocol today. It re blinds one output to produce another. Bob knows x and and can spend (x+b)G+4H. Bob has no interest in xG+4H or aG+4H. He spends his 4 coins using (x+b)G+4H. Alice does not know x+b but can generate (x+b)G. The final step in { } has nothing requiring a signature based on (a x and b) in a joint operation as you imply.

[tromp]

@Elwailly

Bob knows x

So this x is the Diffie-Helmann shared secret between Alice and Bob?
Then the intermediate output xG+4H is a 1-of-2 output both can spend.

So you propose { [ alice-can-spend to either-can-spend] to Bob-can-spend }
But you realize this cannot be split into separate transactions because either-can-spend outputs are problematic and an invitation for cheating.
So how should these be implemented as a single transaction without Bob’s interaction?