mimblewimble team mailing list archive

[John Tromp <john.tromp@xxxxxxxxx>]

I believe the following is the general procedure for robustly building
any transaction:
There are m inputs, p transacting parties, and n outputs.
Each input/output can be either single-sig, meaning its blinding factor is known
by a single party, or can be a k-of-k multi-sig, meaning its blinding
factor is the
sum of k parts (2 <=k <= p), each known by a single party,
or (for one particular output) must be a 0-of-0 zero-sig, to model the fee.

Let the i'th input be I_i = q_i * G + v_i * H, and the i'th output be
O_i = r_i * G + w_i * H,
where O_0 = w_0 * H corresponds to the fee, and all other r_i are
initially undetermined.

Here then are the general steps:

1. The parties agree that Sum v_i = Sum w_i is the total amount of
coins to be transferred.

2. Party j picks random blinding factors r_i_j for all the outputs O_i
that it participates in,
    and computes its total blinding excess x_j = Sum_i r_i_j - Sum_i q_i_j,
    where q_i_j is its contribution to the blinding factor q_i for
inputs I_i that it participates in.
    It also picks a random nonce k_j, and shares commitments x_j * G,
k_j * G with all parties.

3. All parties compute Schnorr signature challenge e = H(fee | Sum k_j * G).

4. Party j computes s_j = k_j + e * x_j.

5. The final signature is computed as (Sum s_j, e).

Let's check to see if this works:

(Sum s_j) * G =
/* expand s_j */
Sum (k_j * G + e * x_j) * G =
/* expand x_j */
(Sum k_j * G ) + e * (Sum_j (Sum_i r_i_j - Sum_i q_i_j)) * G =
/* change summation order */
(Sum k_j * G ) + e * ((Sum_i Sum_j r_i_j - Sum_i Sum_j q_i_j)) * G =
/* definition of r_i, q_i */
(Sum k_j * G ) + e * ((Sum_i r_i - Sum_i q_i)) * G =
/* adding in 0 = Sum w_i - Sum v_i */
(Sum k_j * G ) + e * ((Sum_i O_i - Sum_i I_i)) * G.

Yup, checks out...
We leave the construction of the required n-1 rangeproofs an an
exercise for the reader...

-John

> If the sender input is rI*G+a*H, then the receiver output will be
> rR*G+b*H, and the change output will be rS*G+(a-b)*H.
>
>> I'm having trouble not making that depend on rI (which
>> would defeat the purpose) when I factor in that (rO - rI) should be public
>> key validating your signature.
>
> sum of output minus input commitments is
> rR*G+b*H + rS*G+(a-b)*H - (rI*G+a*H) = rR+rS-rI
> which matches
> s = sS + sR = kS+e*(rS-rI) + kR+e*rR = (kS+kR) + e * (rR+rS-rI)
>
>> 1. Sender and recipient agree on amount to be sent. Call this b.
>>
>> 2. Both sender and receiver pick a random blinding factor, rS and
>> rR respectively, and a random nonce, kS and kR respectively,
>> and share their commitments rS*G, rR*G, kS*G and kR*G
>>
>> 3. Both compute the Schnorr signature challenge e=H(kS*G+kR*G).
>>
>> 4. Sender computes sS=kS+e*(rS-rI), where rI is the blinding factor
>> on his input.
>> Receiver computes sR = kR+e*rR.
>> sS and sR are shared and verified against step 2 commitments by
>> multiplication with G.
>>
>> 5. The final signature is computed as (s,e) where s = sS + sR.
>
> -John