APPECoin, a system with total anonymization - key design points

[Sergio_Demian_Lerner]

passerby, and other users and some people that visited my blog post (http://bitslog.wordpress.com/2011/09/17/total-anonymization-vs-bitcoin-pseudonymous/) have asked me how a peer to peer system with total anonymization may actually work.

Since I have very little time to finish the paper now I will publish the key design points. The system is called APPECoin (Anonymous Peer-to-Peer electronic Coin). Anonymization is based on these premises:

1) Untraceable tokens: When user A sends a token X to user B, he just publish the fact in a signed transaction, as in Bitcoin. The miners, at periodic intervals, shuffle all (or a sub-set of) the existent tokens by re-encryption. The shuffle protocol (and encryption algorithm) has a designed "backdoor" so each owner knows exactly which are the re-encryption tokens of his own original tokens, but not the tokens from the other users. Miners shuffle are proven by Zero knowledge proofs, so no token can be added or removed by the miner. After shuffles, all token identifiers change, but still no cheating can occur. A user can have a high confidence his tokens have been anonymized after several rounds of shuffles (like confirmations) and the shuffling by at least one honest miner.

Suppose that after the shuffle, token X is now token Y. If B sends the token Y (ex-X) to C, then nobody knows that is the same token X that was given by A.

2) Unlikeable user accounts:  Destinations addresses are re-encyrpted in each transaction (a crypto masking) so when A sends a token to B, nobody knows he is using B's public key, but still B can identify he is the destination of the transaction and accept the token.

3) Private transaction amounts: The value hidden in each token in the network is unknown until you receive the token and open it. Only tokens created by coinbase have publicly known value, until they are shuffled for the first time.

4) Private account balances: You cannot group tokens by signature address, nor you can infer how much money or how many tokens a certain user has. Tokens can be divided or combined by a special transaction without disclosing the tokens amounts (division/combination is done using Zero knowledge proofs). You can re-combine tokens securely so you have enough "change".
 
The system uses an accounting system similar to the txout tracing system that Bitcoin use. Also users can shuffle their own tokens securely publishing a ZNP or use a shuffling service, as in Bitcoin. The advantage is that, as amounts are unknown, the shuffling service leaks very few information about the permutation.

Nevertheless there are a few disadvantages of the system:

- In the long term transaction fees will be higher than in Bitcoin, since messages tend to be larger and the system demands more CPU from nodes to verify miners shuffles.

- As a result, the maximum transaction rate could be lower than in Bitcoin. This is not necessary so, because many other factors alter transaction rate, such as the performance of the signature algorithm chosen.

These design key points [not the full design] were also published in my blog (http://bitslog.wordpress.com/2012/07/27/appecoin-anonymous-peer-to-peer-electronic-coin-design/)

Best regards,
 Sergio.

PS: If you like APPECoin and want me to keep on working it, I accept donations or funding, since I don't have much spare time now!

[1713578947]

1713578947

[1713578947]

1713578947

[1713578947]

1713578947

[1713578947]

1713578947

[gmaxwell]

have asked me how a peer to peer system with total anonymization may actually work.

Unfortunately you haven't answered this question here at all.  This is a marketing speak arm-wave, not a design description.

I'm familiar with some of the re-encryption shuffles e.g. described for e-voting. I'm not aware of any way to get quite the properties you need.

Since you haven't described any details, I'm just going to pick the most insecure system which fits the description you've posted, a reasonable conservative assumption, and then I'll show that the strawman burns easily.

So— I say your proposal is that the miners produce N reencryption keys,  and make a random shuffle with each re-encryption key. The user can decrypt their own but not others. The non-interactive ZKP is created by the hash of the next block selecting which of the N published shuffles is the real one, then the miner must publish the N-1 reencryption keys for the other shuffles, and they must be valid shuffles or the prior block was invalid.

But this means that There is p=1/n chance of replacing all the transactions with your own at any block, or p=1 chance if you can mine two consecutive blocks.  This system fails.

Perhaps you didn't mean to propose something so trivially defeated, but I can't tell because you didn't describe it in more detail.

I'm not trying to be rude, but if you want the credit and attention of having disclosed something interesting you have to actually disclose something of interest— even just links to papers on algorithims which provide exactly the right properties and a sentence or two on how composing them gives you what your feature list describes. I'm sure lots of people would be interested in such a system, even if boring issues like space and time complexity make it not-practically-viable. Also, this thread probably belongs in the altcoin subthread.

[Sergio_Demian_Lerner]

Dear gmaxwell, you are not trying to be rude but you are being a bit rude. Try reading your posts before sending them, as you could have just said "Interesting, could you post more info?"

I didn't expect my last post to be the only one describing the system, because, as you said, I'm not describing it but just giving the most important aspects of the design. I said I was working on it, and I would publish more details when I had more time..

I cannot understand your guessing on the shuffle-method because, with so little information given by me, you're just designing your own system.

In APPECoin, basically the miners take a set of tokens or bills, re-encrypts them, permute them, and publish them in the block. The permuted re-encrypted tokens are the new tokens that replace the originals. Each user can know for sure in with blocks his tokens are being shuffled (the token selection algorithm is deterministic and depends only on the block number). Also each user can try to decrypt each shuffled token and detect the new tokens that belong to himself.

The encryption algorithm is a variant of Elgamal I created myself for the sole purpose to satisfy the design requirements.

No, I don't expect anybody to blindly trust my cryptosystem, so I will publish it for public scrutiny. If someone breaks it, that would be great because some other guy will find the appropriate cryptosystem for the task.
The cryptosystem difficulty is based on the difficulty of the Diffie–Hellman problem (DHP).

But as far I as can think, the system cannot be trivially defeated. Please let me find some time to post more info..

Regarding where in the forum this topic should go, fell free to tell the forum admin to move it anywhere you like.

[gmaxwell]

with so little information given by me,

This was basically my point.  You posted a lot of text, which I spent a fair amount of time reading— and I didn't get anything out of it because you didn't say much of anything. I didn't know if it was clear to you that you weren't saying anything concrete, so I used an example to illustrate the point.

In APPECoin,

Can I download APPECoin?

basically the miners take a set of tokens or bills, re-encrypts them, permute them, and publish them in the block. The permuted re-encrypted tokens are the new tokens that replace the originals. Each user can know for sure in with blocks his tokens are being shuffled (the token selection algorithm is deterministic and depends only on the block number). Also each user can try to decrypt each shuffled token and detect the new tokens that belong to himself.

I'm another miner and I have no transactions involved in the prior shuffle. How do I know know that the shuffle was valid?  Or, say I do have some transactions on the input side— and I see those are fine on the output, how do I validate that the shuffle didn't invalidly replace a bunch of transaction which weren't mine?  Is there a reason why I don't need to know?

I assumed you'd have a non-interactive zero-knoweldge proof for this, but I'm not aware of any which would be suitable.

[DeathAndTaxes]

Two points:

1) How can other miners verify a block is valid if the transactions of the block are encrypted such that only the receiver can identify their transaction?

Miners shuffle are proven by Zero knowledge proofs, so no token can be added or removed by the miner.

Ok.  How?  Simply stating it as so doesn't really provide anything useful.  I could do that "BIP 9999 proposes that double spends be eliminated.  Miners can verify that no doublespends exist in a block by Zero knowledge proofs".  Doesn't really mean much.

2) What is to prevent a miner (or simply an listening node) from recording the raw (unshuffled) transactions to break the anonymity?

Maybe these are stupid questions but your post provides no details.  Nobody is expecting a complete whitepaper but you provide nothing and thus there really isn't much to discuss even reading the post I had to make a lot of (likely incorrect) guesses and assumptions.

[Sergio_Demian_Lerner]

Can I download APPECoin?

Not very soon, since I've just implemented a prototype for the crypto part.

I'm another miner and I have no transactions involved in the prior shuffle. How do I know know that the shuffle was valid?  Or, say I do have some transactions on the input side— and I see those are fine on the output, how do I validate that the shuffle didn't invalidly replace a bunch of transaction which weren't mine?  Is there a reason why I don't need to know?

I assumed you'd have a non-interactive zero-knoweldge proof for this, but I'm not aware of any which would be suitable.

Exactly as you say.. The shuffle is published along a non-interactive ZNP that the output tokens are exactly a permutation of the input tokens. Every user MUST check this, whether they have tokens in the input set or not. The ZNP is only computational zero knowledge, meaning that an attacker with unbounded computing power could in theory find the shuffle permutation. But the same holds for any ECC/RSA encryption!

Best regards, Sergio.

[Sergio_Demian_Lerner]

Two points:

1) How can other miners verify a block is valid if the transactions of the block are encrypted such that only the receiver can identify their transaction?

There are plenty of methods to provide ZNP for message shuffles. They are used in Mental Poker protocols and e-voting schemes.

Check out, for example, these papers:

1. A. Barnett and N. Smart. Mental poker revisited. In Proc. Cryptography and Coding, volume 2898 of Lecture Notes in Computer Science, pages 370--383. Springer­Verlag, December 2003.

2. C. Schindelhauer. A toolbox for mental card games, 1998. Medizinische Universitat Lubeck.

3. W.H. Soo, A. Samsudin, and A. Goh. Effiient mental card shuffling via optimised arbitrary ­sized benes permutation network. In Information Security Conference, volume 2433 of Lecture Notes in Computer Science, pages 446--458. Springer­Verlag, 2002.

4. Stephanie Bayer and Jens Groth, Efficient Zero-Knowledge Argument for Correctness of a Shuffle

5. Jens Groth, Sub-linear Zero-Knowledge Argument for Correctness of a Shuffle

Any many more..

You can also search the web for the terms: ElGamal homomorphic re-encryptio and ElGamal re-masking

2) What is to prevent a miner (or simply an listening node) from recording the raw (unshuffled) transactions to break the anonymity?

If a miner wants to make the permutation public, nobody can prevent it.
As in Bitcoin, we suppose miners will have an incentive not to publish the permutations because they earn APPECoins and want the APPECoin to be useful, so the value of each APC increases.

Nevertheless, if there is at least one honest miner, it´s enough. You just have to wait that your tokens get shuffled by that miner. Even if no miner is honest, you can still shuffle your own tokens, or mix your tokens with your friends tokens  in a pool.

Nobody is expecting a complete whitepaper but you provide nothing and thus there really isn't much to discuss even reading the post I had to make a lot of (likely incorrect) guesses and assumptions.

The problem is that there is much cryptographic background behind the scenes. Please read Barnett and N. Smart paper and everything will be much clearer. Please forgive me all if I got hurry to post the design without giving background information.

Best regards, Sergio.