mimblewimble team mailing list archive

[Gary YU <gairy.yu@xxxxxxxxx>]

The Mimblewimble transaction is an interactive procedure between payer and
payee, both for the original Mimblewimble whitepaper [1] and for the
enhanced version of transaction designed by John Tromp [2] which is the
current implementation of Grin [3]. Briefly, the transaction need a 2-of-2
multisig from both payer and payee.

The required interactive procedure is the root cause of why Mimblewimble
blockchain doesn’t have Mimblewimble "address", no matter how popular it's
in almost all other blockchains such as Bitcoin, Ethereum, and so on.
Obviously the payer can’t complete the 2-of-2 multisig without payee’s
interaction, just by a static “address”.

I believe supporting a non-interactive transaction procedure will provide
much more usability, in some cases. So I propose a Mimblewimble
"Pay-to-Address" / "Pay-to-Public-Key" solution here.

The basic idea:
- Add 2 new types of Mimblewimble transactions: Payment Transaction and
Deposit Transaction (let’s use PTX and DTX as brief and retained for the
rest of the document to save words.), to differentiate from the
Mimblewimble Interactive Transaction (use ITX as brief for it and retained
for the rest of the document).
- In PTX, payer create an output with a blinding factor which both payer
and payee know it, we name this PTX output as PTXO and retained for the
rest of the document.
- In DTX, we restrict that ONLY PTXO can be used as input, and a DTX’s
public excess MUST be the designated one by the input PTXO (in transaction
kernel) in case of single input, or the aggregated one from all input PTXOs
in case of multiple inputs. And we restrict that PTXO can ONLY be used as
DTX input.

For example, Alice want send some coins to Bob, and Alice know Bob's a
well-known public address P which is a public key in EC.

Here we go. Let’s start from a PTX creation:

0. Alice selects input(s): ri*G + vi*H, and creates a change output: rc*G +
vc*H.
1. Alice creates a PTXO which use q as blinding factor, i.e., PTXO = q*G +
v*H.
2. Alice calculates q = Hash(m || k*P), and m is a unique message for this
transaction (for example: fee || lock height, as in Grin implementation), k
is the private nonce for the signature of this transaction, P is Bob’s
well-known public address (i.e. payee’s public key). We design q in this
form so that payee also know this q, because k*P = k*p*G = p*k*G = p*R, and
p is payee's private key to the public key P, R is the public nonce. (q
here is inspired from [4])
3. Alice calculates the public excess = (q + rc - ri - offset)*G, and
offset is the generated kernel offset.
4. Alice signs for this PTX with excess as public key, sig = (R, s) and R =
k*G, k is the private nonce for this signature.
5. Alice calculates (q*P) and attach it to the transaction kernel as the
restriction to spend its PTXO. ONLY who owns the private key of this public
(q*P) can spend this PTXO.
6. The encrypted value v' is also attached to the transaction kernel so
that the payee know it. For example: v' = v ^ q[0..8] ^ q[8..16] ^
q[16..24] ^ q[24..32], or any defined symmetric encryption algorithm is
acceptable here, with q as the secret.
7. Because the transmitted signature (R.x, s) lose R’s y-coordinate info,
we encode 1 bit for R.y even/odd, and attach to the transaction kernel.

It’s done for a PTX creation procedure.
To show the total sum balance of this PTX:
  change + PTXO + (-offset*G + fee*H) = input + public_excess
=> (rc*G + vc*H) + (q*G + v*H) + (-offset*G + fee*H) = (ri*G + vi*H) + (q +
rc - ri - offset)*G

To summarize the difference of the transaction kernel between ITX and PTX,
PTX has 3 additional fields which ITX doesn’t have:
- (q*P): 33 bytes
- v': 8 bytes
- even/odd of R.y: 1 bit

Now let’s create a DTX for Bob to spend this PTXO:

0. Bob creates a DTX with the input commitment (q*G + v*H) and a new output
commitment (r*G + v"*H). This DTX is a single input single output
transaction, no change-output is needed.
1. Bob calculates q = Hash(m || p*R), p is Bob’s private key to his
well-known public key P, the message m and public nonce R can be acquired
from the transaction kernel of the input PTXO (let’s use PTXO kernel as
brief for this kernel and retained for the rest of the document).
2. In the new output commitment, the blinding factor r = (q*p + q + offset)
mod n, and offset is the generated kernel offset, and v" = v - fee", fee"
is the transaction fee of this DTX. v can be calculated (decrypted) by q
and the v', and v' is acquired from the input PTXO kernel.
3. In this DTX, the public excess use (q*P) which can be acquired from the
input PTXO kernel.
4. Bob signs this DTX with (q*P) as the public key.

It’s done for a DTX creation procedure.
To show the total sum balance of this DTX:
  output + (-offset*G + fee"*H) = input + public_excess
=> ((q*p + q + offset)*G + v”*H) + (-offset*G + fee"*H) = (q*G + v*H) + q*P

Since (q*P) here works quite similar as the public key of
"Pay-to-Public-Key" in Bitcoin, perhaps we can name this (q*P) as
Mimblewimble "Pay-to-Address" / "Pay-to-Public-Key", and name the public
"P" as Mimblewimble "Address".

In case the payee has multiple unspent PTXOs, he/she can create one DTX to
collect all those unspent PTXOs into one normal UTXO, and that’s the
meaning of the name: "deposit transaction". For example in case of a DTX
collecting n PTXOs, payee signs this DTX with (q1+q2+…+qn)*P as the public
key and use it also as public excess of this DTX.

Note: In above example, we don’t give a change output. But actually a
change output is allowed in DTX, even it breaks the meaning of the
"deposit". In practical situation, one or more PTXOs can be spent and
create an output for a 3rd party.

The cost of this non-interactive transaction solution, compared to
interactive transaction:
- The transaction fee will increase up to 25%. For example in Grin, if we
say the fee = MAX(-1 * num_inputs + 4 * num_change_outputs + 1, 1), then an
ITX/PTX with 1 input, 1 change and 1 output need a fee of 4 milli-grin, and
a DTX always need a fee of 1 milli-grin. But in case of multiple PTXOs
collection, the increased fee is trivial, for example a DTX with 100 PTXOs,
the comparable fee to a single ITX will increase only 0.25%.
- Because of the fee of DTX, if payer wants payee to get v coins, he/she
need send (v+0.001) coins to payee in PTX.
- The transaction kernel size of a PTX is 41 bytes bigger than ITX’s
kernel. (ITX’s transaction kernel size is 114 bytes in current Grin
implementation.)

[1] https://github.com/mimblewimble/docs/wiki/MimbleWimble-Origin
[2] https://lists.launchpad.net/mimblewimble/msg00087.html
[3] https://github.com/mimblewimble/grin
[4]
https://www.grin-forum.org/t/mimblewimble-non-interactive-transactions/168

Any comments/feedback welcome.

BTW, I am not a cryptographer, but I do hope to have the non-interactive
feature for Mimblewimble, to gain better usability, so, if people are
willing to help out on proving the proposed solution here is secure, I
would be really grateful.

Cheers,
Gary

--
https://github.com/garyyu