kernel combination step that voldie missed

[antiochp]

https://gitter.im/grin_community/dev?at=5a71e52098927d57455df4a9

tl;dr If a valid tx consists of -

• inputs
• output
• kernel(s)

And they sum to zero to be a valid tx. Then it is possible to simply try all permutations of inputs and outputs for a given kernel to find a set that sum to zero (particularly given that most txs only have a few inputs and outputs).

From @tromp on gitter -

i just realized that making each block look like one huge tx doesn't help privacy much the kernels still reveal the corresponding inputs and outputs

you can still find inputs and outputs since they have to add up to 0 with the kernel?!

i guess i'm having issues with this paragraph of the MW whitepaper: Now, creating transactions in this manner supports OWAS already. To show this, suppose we have two transactions that have a surplus k1G and k2G, and the attached signatures with these. Then you can combine the lists of inputs and outputs of the two transactions, with both k1G and k2G to the mix, and voilá! is again a valid transaction. From the combination, it is impossible to say which outputs or inputs are from which original transaction.

it seems there's only one way to split inputs and outputs so that these form valid txs with their kernel

most tx have very few ins and outs, so a polytime algorithm could recover them e.g. suppose all tx have 2 in & 2 out. then just try all (n choose 4) subsets

Resolved by #681.

[antiochp]

One thing we discussed -

Mitigate this via "kernel bloat" - build txs with many kernels. A large number of kernels would make the search space significantly larger, making recovery of individual txs harder.

Wallet could be configured to build txs with variable numbers of kernels based on level of anonymity desired. Maybe you pay more in fees for more kernels?

[antiochp]

@apoelstra got paged about this and posted this link to earlier comment - https://www.reddit.com/r/Bitcoin/comments/4vub3y/mimblewimble_noninteractive_coinjoin_and_better/d61n41v/

<andytoshi> re mimblewimble, it's not quite OWAS because it's possible to separate out the transaction .. you have these kG values which represent the excess, so you just need to find subsets of inputs and outputs that sum to each one
<andytoshi> this is the subset-sum problem which is NP-hard in general, but might not be for many specific cases
<andytoshi> having said that, the knowers of specific kG values can interact to combine their transactions, which would make this much harder. an implementation of mimblewimble should maybe have network messages for doing this
<andytoshi> err, not combine transactions, just combine their kG values. the actual transactions don't need to be involved at all
<andytoshi> ah, there's a simple fix, publish k1G and k2, sign with k1G but make the transaction excess be (k1 + k2)G
<andytoshi> and when combining transactions all the k2's just get added together

[antiochp]

From @apoelstra in gitter -

if you publish a kernel kG as (k1G, k2) where k1 + k2 = k, and a signature with k1G, that's as good as publishing kG and a signature w kG as far as proving knowledge of the discrete log goes but in the form (k1G, k2) you can partially combine kernels. like (k1G, k2) + (l1G, l2) becomes (k1G, l1G, (l2 + k2))

@tromp -

yes, a block will have a single aggregate kernel offset i guess this will be processed much like the fee

[antiochp]

cc @ignopeverell

[ignopeverell]

Right, I actually wanted to implement that fix way back when and completely forgot about it. Glad you 2 ran back into it!

[antiochp]

(still like our idea of generating 20 kernels per tx) Edit: /jk

[ignopeverell]

What would multiple kernel give you assuming the offset is done? Btw if we do this, I was thinking we should also sum fees up, save a few bytes in kernels.

[antiochp]

Nothing... but it would have made it "harder" to identify inputs/outputs if we couldn't offset the kernels. At the cost of thousands and thousands of extra kernels...

[antiochp]

Agreed on summing the fees up as well. Right now the fees leak some info about the txs in the block (relative numbers of inputs/outputs, complexity of tx).

So a block would contain an "aggregate kernel" of some kind, containing a single offset, a single fee, and several excess + excess_sig pairs?

We also have lock_heights in there right now so we'd need to decide if we want to leave them in or get rid of them (lock_heights at the tx level).

Oh and features (so we can identify coinbase kernels).

[antiochp]

Digging through the secp code and it looks like we can add two secret keys together -

https://github.com/mimblewimble/secp256k1-zkp/blob/960034ca957ac630dcefdf5a285c92ca830ea7ab/src/eckey_impl.h#L55

static int secp256k1_eckey_privkey_tweak_add(secp256k1_scalar *key, const secp256k1_scalar *tweak) {
    secp256k1_scalar_add(key, key, tweak);
    if (secp256k1_scalar_is_zero(key)) {
        return 0;
    }
    return 1;
}

Which calls the low level -

https://github.com/mimblewimble/secp256k1-zkp/blob/960034ca957ac630dcefdf5a285c92ca830ea7ab/src/scalar_low_impl.h#L35

static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
    *r = (*a + *b) % EXHAUSTIVE_TEST_ORDER;
    return *r < *b;
}

Does splitting a key (so we can do k = k1 + k2) involve creating a new secret key k2 and subtracting it from k to give k1 = k - k2?

Can we subtract secret keys?

I see we can do what appears to be low level subtraction of secp256k1_scalar values -

https://github.com/mimblewimble/secp256k1-zkp/blob/960034ca957ac630dcefdf5a285c92ca830ea7ab/src/scalar_low_impl.h#L40

static void secp256k1_scalar_numsub(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
    *r = *a - *b;
}

[antiochp]

681 for some initial work around splitting the key (work in progress).