# 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 generates a “Sender Generated Ephemeral Receive Key” for Bob, C, for the purposes of this transaction

• Alice generates a “Sender Generated Blinding Factor” for Bob, X, for this transaction

• Alice generates a “Sender Generated Signature” on the transaction sum that proves that the coin values sum to zero

If Alice wants to use a public key from Bob but only has access to well-known Bob public keys, then Alice may want to generate a brand new key-pair that is untraceable to Bob but has the property that only Bob can create the private key. Alice can then use the public side of this new anonymous key for the rest of the protocol.

This is how it’s done. Alice has a private key, a, with public key A = aG. (Where G is the basis point in the ECC system). Let Bob have a well-known public key B known to Alice.

The sender, Alice, generates the public side of a new key pair for 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

C = qB				C is Bob’s ephemeral public key. Alice can use this now.
``````

Note that later Alice can send A and m to Bob, and Bob is the only one able to generate the private part of the new key-pair as follows:

``````q = Hash(m,bA)		Note that b is Bob’s private key and bA = aB,
allowing Bob to create the shared secret

c = q b				This is an integer multiply modulo a large prime (order of ECC)
``````

We can check that C = cG and Alice has use of C, an ephemeral public key for Bob.

Sender Generated Blinding Factor

The sender, Alice, now generates a blinding factor for Bob that only Bob will know. Alice will know the corresponding public point in the group. It basically follows the same idea as above:

``````u = Hash(m,aC)		where C is Bobs ephemeral key and m is unique

X = uC				X is the group point corresponding to Bob’s blinding factor
``````

Again note that later with A and m in hand, Bob is the only one able to generate the actual blinding factor as follows:

``````u = Hash(m,cA)		Note that c is Bob’s ephemeral private key recovered
in the previous section

x = u c				This is an integer multiply modulo a large prime (order of ECC)
(note that X = xG)
``````

At this point Alice can use X in building the transaction and we are left with a verification sum

``````xG + 0H
``````

that needs to be signed using the basis point G to prove that the coins sum to zero. (The signature will only succeed if the multiplier of the basis point H is zero.)

This signature cannot be created by the sender, Alice. She does not know x, Bob’s blinding factor.

Sender Generated Signature

The insight here is that there is another way to prove that the H multiplier is zero. Note the following:

``````xG + 0H  =  X + 0H  =  uC + 0H
``````

Alice happens to know u and C. She can create a signature, using u as the secret and C as the basis point, that proves that the H multiplier is zero. It goes a follows:

``````r = Hash(u,C)
R = rC
s = Hash(X,R)u + r
``````

Now C, (R, s) is the required Schnorr signature. We include the basis point, C, over which the signature is performed.

Verifying the signature given C, (R, s)

Note that X = xG + 0H, so X is available to the verifier. Also, since uC = X, what he needs to confirm is that:

``````sC  ?=  Hash(X,R)X + R
``````

Well, there it is. I hope I understood what is needed to construct Mimblewimble transactions and that this is a valid method of generating non-interactive transactions.

I wanted to add that by careful choice of A and m, Alice and Bob need 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 for the property that they are non-interactive and have signature C, (R, s).

• Bob’s wallet then retrieves A and m and checks that C has the property that

``````  C = Hash(m,bA)B		Again, b is Bob’s private key
``````
• The wallet then calculates Bob’s blinding factor, x, determines the sent balance, and adds the balance to the total Bob has in the wallet.

No interaction between Bob and Alice required!

Regards,
Farid

1 Like

Thanks for your attempt at removing the interactivity requirement from MimbleWimble transacting, Farid.
That is a well written exposition.

The problem I see is with your proof that xG+0H commits to a zero value.

A third party just seeing your alternative C, (R,s) signature cannot verify that C was constructed
If instead C were chosen as a known multiple C=zH of H, then one can easily make such signatures
that commit to nonzero values. E.g. uC + 1H = (uz+1)H + 0H = (uz+1)z’ C + 0H, where z’ is the inverse of z.

Hi Farid,

Thanks for taking to the time to write this up… I think though, you may have overlooked where the Rangeproof fits in here. The output create by Alice cannot be put into the UTXO set as she doesn’t have any way to construct a Rangeproof that proves the amount is non-negative without access to Bob’s private blinding factor. He could add one to the output after the fact (taking an output marked as ‘non-interactive’ as you say,) but that ‘non-interactive output’ can’t be posted into the summed and verified UTXO set without the proof and therefore has to get to Bob first via some other means… even if you added some feature to allow the Grin chain to store ‘unverified’ outputs for claiming later, you’re just creating a separate means for an interactive exchange.

I assumed Farid was planning to do the rangeproof in the same way he proved a zero value in the value excess; with C replacing G.

Thank you tromp and Yeastplume for taking the time to look at my post. I feel bad the proof is faulty, but I enjoyed thinking about it.

I’m sure there’s a discussion somewhere that H and G were select so that there isn’t some secret relationship between them (H = zG), but I didn’t catch it. Maybe I wouldn’t have made the mistake I made if that had been on my mind. I’m curious, how were G and H selected?

https://bitcointalk.org/index.php?topic=553091.0

suggests G’s origin is not publicly known. Of course it’s very important to choose H independent of G, in “nothing-up-my-sleeve” fashion.

https://bitcointalk.org/index.php?topic=1085273.0

suggests picking H = to_point(SHA256(ENCODE(G)))

A Non-Interactive Transaction is easily accomplished if Alice and Bob are ok with the following state of affairs:

Both Bob and Alice can spend the resulting transaction.

No one else can spend it.

When Bob comes online, he must immediately spend the transaction to a secure blinding factor of his own choosing and only then is the transfer between the two of them considered concluded.

This is accomplished by Alice directly generating a blinding factor for Bob that both Alice and Bob can use.

x = Hash(m,aB) where B is Bob’s well known public key and m is unique to this transaction.

Note x is now a shared secret between Alice and Bob since Bob can recover it using bA which is equal to aB. This is used as Bob’s blinding factor.

Let X = xG

Now Alice can directly sign the verification sum, xG + 0H, because she knows the new blinding factor, x. She can also participate in generating the range proof required by the transaction.

The job of Bob’s wallet is a little more complicated unless we add a bit to the protocol to indicate this is a shared transaction.

If A and m are selected as in the original post, then no interaction at all is required between Alice and Bob.

Regards,
Farid

Footnote: Of course there is no way that Alice can prove to anyone else that Bob collected his grin.

This is just like Alice leaving Bob a message saying:

"Hey Bob, I have this output with 100 Grins in it, and just to let you in on a little secret,
the blinding factor is D71207CA61… "

Yes, in that sense divulging your private key is a Non-Interactive Transaction.

Yeah well, I agree it is not the system I was hoping for and it’s pretty obvious. I just wanted to point it out to people.

However there most definitely is a difference between a contact level of none and contact by email. When Bob gets arrested and his laptop confiscated and that email discovered Alice will be hoping the anonymity of the email system matches that of her transaction.

Also, Bob is offline. That was the motive. Who wants to leave a live blinding factor sitting in an email?

If I want to donate to Wikileaks and keep it really anonymous where even Wikileaks can’t tell who sent the donation I would not want to send an email.

I left out the message medium. It could be left on an answering machine, or sent by snail-mail.

But I’ll agree making the blinding factor a shared secret is a step up from there.

The secondary oblivity of the algorithums disjunction flux is obviously a tricky quisitive to address. I hate to say it, but Voldemorts plan is dastardly