mimblewimble team mailing list archive

[Tim Ruffing <crypto@xxxxxxxxxxxxx>]

Hello,

I'm one of the authors of ValueShuffle. It's great to see this being
discussed here. There are a few general things I'd like to mention.

I'll definitively work on an implementation of CoinShuffle++ or
ValueShuffle over the summer. It's not yet clear what currency is the 
target but the goal is obviously to make reusable parts of it (e.g., as
a library) that could be used Mimblewimble as well. We should certainly
coordinate as soon as I have clear picture (which is in about two
weeks).

ValueShuffle requires a few modifications for Mimblewimble. I wrote
down some notes on a plane once and I'm not sure if I can find them...
but it's certainly doable.

If you have any problems understanding the paper or the pseudocode,
just ask here. In particular the pseudocode uses a weird "programming
style" with a lot of arrays, so it's very difficult to parse. (We
should have changed to object-orientied pseudocode at some point I
think...)

If you ask me, the challenge that requires most thought is that
ValueShuffle requires a bulletin board (e.g., a central server
broadcasting messages) to have reasonable performance and to set up
mixings. Even though this bulletin board is not trusted for anonymity
during the protocol, it is trusted for availability. So you need to
rely on it for 
   1. being up and broadcasting correctly in the first place
   2. not kicking out honest users by claiming they're offline
   3. (temporarily) ban users who disrupt the protocol by sending wrong
      messages or just refusing to send messages

The nice thing is that basically everybody can run such a bulletin
board, and so there should be many of them. If one bulletin board does
not work for you or you don't trust it, use another one. Additionally,
if you don't trust that a single bulletin board does not censor you,
you can replicate them (and users accept messages if just one bulletin
board sends them).

> Low liquidity
Yes, that's certain a thing that must be considered but not a large
issue. (And it's kind of natural in an anonymous system: You can't have
anonymity if you're the only one doing transactions.)

> Users should be encouraged to do multiple
> rounds of ValueShuffle to provide liquidity for other users in future
> blocks, decreasing ValueShuffle wait times for everyone in the
> network. 
This seems contradictory to transaction/anti-DoS fees. (I think this is
what Andrew hinted at.) The problem is that we want to incentivize
honest users to participate and we want to disincentivize malicious
users to participate. But we cannot distinguish honest from malicious
users. So this seems impossible (but maybe there is a nice way...)


> Some users may want to do multiple rounds of ValueShuffle
> over several blocks for additional untraceability
One must be careful here. These users may end up being less anonymous
if they stand out of the crowd (if the attacker can observe that they
do multiple rounds).


> If there is
> even a single other honest participant in a round where a sybil
> attack is
> present then an attacker has a 1/N chance of guessing the
> corresponding inputs
> and outputs among N honest participants in a round.
That's unfortunately too nice to be true. The anonymity set in
ValueShuffle is the set of honest participants. So if there are only 2
honest guys in a mixing of N, the chance of guessing is 1/2.
This is not particular to ValueShuffle but actually true in every
anonymous system: The malicious guys know their N-2 messages (recipient
public keys in our case), so they know the 2 other messages are from
honest users.

> I am interested in what this mailing list thinks of integrating 
> ValueShuffle into the base layer of Mimblewimble
One nice thing about ValueShuffle (or any solution based on CoinJoin)
is that integration in _the base layer_ is not necessary because it
runs indepedently on top of the currency. This is great because it
simplifies the design a lot and keeps the core of the currency simple.
For example, even if an implementation of ValueShuffle failed terribly,
the currency itself would not affected.

By the way, I wasn't aware that someone is writing up that Schnorr-
multisig idea formally. It's not a big deal in the end, this
cancellation attack has been known since the 1994 and we know how to
avoid it. What Pieter Wuille  [2] proposed as a solution is pretty
similar to what Mihir Bellare and Gregory Neven [3] proposed in 2006.
Bellare and Neven give a formal security proof for their scheme.
(Pieter's idea is a slightly simpler, and it will be nice to see a
formal proof for it.)

Best,
Tim

[1] Patrick Horster, Markus Michels, Holger Petersen. Meta-
Multisignature schemes based on the discrete logarithm problem (1994) 
http://citeseerx.ist.psu.edu/images/pdf_icon.png;jsessionid=DFAF065D5B8
00B5B41302BD99448CA46
[2] https://github.com/sipa/secp256k1/blob/968e2f415a5e764d159ee03e9581
5ea11460854e/src/modules/schnorr/schnorr.md 
[3] https://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf




On Mon, 2017-05-29 at 01:36 -0400, Luna Lovegood wrote:
> > You found yourself a very nice name, congratulations and welcome.
> 
> Thanks. I am surprised it wasn't already taken by someone, heh.
> 
> > As Andrew predicted (he's starting to know me well), I'll first say
> there's
> > still a lot we need to work on and figure out but if you're willing
> to work on
> > ValueShuffle in Grin, I'd be very happy to help. The first thing to
> clear may
> > be a good Schnorr signature implementation, which would be
> generally very
> > beneficial (hint).
> 
> I would be happy to eventually get a start on ValueShuffle and all
> things
> Schnorr. I have little experience with Rust, so I better start off
> with        
> becoming more familiar with the language first.
> 
> The holdup on Schnorr, as far as I am aware, is the 'cancellation'
> problem
> mentioned in [1]. There is a paper supposedly being written to prove
> the        
> security of 'de-linearization' to address the problem. Maybe Andrew
> knows a bit
> more about this? Anyways it is probably best to wait on a Schnorr
> implementation
> in Grin until the fix is reviewed and merged upstream in
> libsecp256k1.
> 
> For the meantime I will scavenge the codebase for smaller things to
> do and
> familiarize myself with Grin.
> 
> ~Luna Lovegood
> 
> [1] https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregati
> on/