QPriv = k*Bpriv

B learns Qpriv when A sends k to B.

One of the uses of DAA (Destination Address Anonymization) is to create an p2p escrow without the need for third parties.

Suppose A wants to send X coins to B, and B in return must send Y virtual goods of some kind. B public address is Bpub

First A commits to sending X coins by choosing a random k and sending the money to the address Q=k*Bpub.
Then A creates a simple ZNP (zero knowledge proof) that Q is indeed the encryption of Bpub under a known k.
This can be done with the cut-and-choose method and the Fiat-Shamir heuristic to create a non-interactive proof.
(if you want more information of this method please ask me, it's very simple and a standard practice)

Then B knows that A has committed to the payment (A cannot get the money back and B cannot take it, so the money is blocked).
B sends the virtual goods to A. A releases the money by sending the value k to B.

I know this is not the only way to do an escrow in Bitcoin (and maybe not the best way), but is a new useful way.

Best regards, Sergio.

No they don't. Only if you are accepting 0/unconfirmed transactions you need it.

I understand your point. DAA can only be really useful if it's implemented in all clients. But it brings no backward-compatibility problems so it can be implemented now, and begin to be used in 6 months, when more than 80% of the network will be using the new version.

Also you can provide both methods, so users using the DAA-enabled versions will benefit from a single address per merchant in the address book.

Best regards TangibleCryptography and thank you for opinion!

(copied from another thread)

A standard merchant practice is to give each client an unique address to track transactions and provide anonymity. With Destination Address Anonymization you don't need to. You can give each client an unique number k. This has the additional benefit that your address is always the same and the user can save it in his address book, as normal. (the client application automatically must multiply the pubkey with k while building the tx).

Another advantage is that merchants just need to securely backup one private key (k values can be stored with much less security)

With Destination Address Anonymization (https://bitcointalk.org/index.php?topic=98737.0) you don't need to. You can give each client an unique number k. This has the additional benefit that your address is always the same and the user can save it in his address book, as normal.

This is one of the ideas of APPECoin that can be directly applied to Bitcoin.

When you send a payment to the public address of a merchant, hackers can detect that one of your coins are being sent to that merchant. This is because Bitcoin is not truly anonymous (please do not discuss this fact here, as it has been already debated many times!). For example, your IP can be traced to your one of your Bitcoin addresses, and payments can also be traced with some confidence.

But if you want to cryptographically hide this information then you can do one of the following things:

1 - Contact the merchant privately, ask for a new public address specially generated for you, and send the payment to that address.
(a previous private contact is needed, and the communication must be authenticated or an active attacker may steal your coins, in a man-in-the-middle attack)

2 - Generate a new key pair, send the coins to the public address generated, send the keypair privately to the merchant, wait for the merchant to re-transfer the coins to a new private address.  (two transactions are needed, and the communication must be authenticated or a passive attacker may steal your coins)

There are different ways of doing that, with a method I called Destination Address Anonymization (DAA):

3- Take the merchant public key and "encrypt" it using a special encryption method. Send the coins to that encrypted public address. Send the encryption key privately to the merchant (no authentication is needed, since a passive attacker may only trace you but NOT steal your coins)

4- The merchant has, apart from the signing keys, an keypair suitable for encryption (ECIES or ElGamal), and publishes the encryption public key.  The method is similar to 3 but instead of sending the key in a private communication, you encrypt it using the encryption public key and put it in the script as a message to ignore ("<message> OP_DROP"). The merchant must scan all transactions for the ones that go to himself, trying to decrypt each message.

As previously said, both new methods require an EC public key "encryption", and this is very simple. Suppose the merchant has a key pair suitable for elliptic curve cryptography, consisting of a private key dA and a public key QA (where QA = dA * G). Then for a randomly selected integer in k the interval [1, n-1]). A new keypair can be generated by multiplying both keys by k (k*QA is the public key of the private key k*dA). k is the anonymization key.

So the main different between DAA method 3 and method 1 is that DAA m3 requires user-merchant communication after the payment without authentication, and method 1 requires authenticated communication before the payment is done.

DAA method 4 requires no private communication, but requires a bit more computations in the receiver application.

Best regards,
 Sergio.

- CON. Users are less anonymous since miners can see the IP of users from where transactions are coming. This can be solved by users using Tor.

I´ve thought about multi-level chains before, or even chains with fixed transaction/difficulty ratio for any chosen difficulty. The problem I see is that it´s difficult to predict which will be "Nash equilibrium" of the system or even if an equilibrium exists. Will all miners start making only the lowest difficulty blocks ? Or will they ignore and them always mine the ones with higher rewards?

One possible solution may be to fix the number of low difficulty blocks before a high difficulty block must appear (say in 10:1 ratio). Bit then you will have some (predictable) time intervals where there are no fast confirmations.


Best regard, Sergio.

I've been thinking about the benefits or drawbacks of users connecting directly to miners.
Casascius Instant Partial Confirmation proposes a method where users can locate miners by addresses published on blocks.
These addresses could be normal IP, Tor addresses or whatever system each miner chooses to be located.

Currently the P2P network serves two purposes:

1. Send transactions from users to miners
2. Send blocks from miners to users.

These two transports are coupled together now but this may not be the best idea. One can imagine that users could connect directly to miners to send the transactions and the P2P network is only used to broadcasts blocks. Users willing to send a tx would choose a random sample of K miners of the last X blocks, possibly weighed by network hash power percentage. Then send the tx only to those miners.

The benefits/drawbacks would be:

- PRO. Less than half the network bandwidth usage (also users never see txs that never got into a block because of low fees)
- PRO. Less than half the CPU usage in clients (not true on v0.6.3+)
- PRO. P2P network less susceptible to DoS by spamming.
- PRO. Less memory usage for client application (no need for Tx cache, Sig chache, Orphan Tx cache, etc.)
- PRO. Huge simplification in client application

- CON. No 0-confirmations for transactions (at least not in the way it's done today)
- CON. Miners have to find there own methods to prevent DoS attacks to their servers.
- CON. Miners are less anonymous (but they are not completely anonymous in Bitcoin anyway)
- CON. New miners must publish empty blocks until they are known by the network.


Migrating from the current system gradually would be very easy by:

- adding the possibility to connect directly to miners
- reducing the incentive of users to broadcast the tx using the P2P network by reducing the bandwidth available for tx exchange.

What do you think?

Best regards,  Sergio.

Two problems with your proposal to punish rough miners:

1. You can ask miners not to follow certain longer block branch, but the have the opposite incentive.

2. You can't tell nodes or miners to invalidate transactions even if you have a proof of dishonest behavior, because that will give you a tool to invalidate blocks in the past. And that would give you a tool to revert millions of other (unrelated) transactions!

Now you have created a new type of double-spend attack by a rough miner that includes a (previously rejected) transaction on purpose.

It's very interesting, though I have several questions:

Issue 1:

In your BIP you say: "CONFIRMED: The miner considers the transaction valid and commits to include it in the next block. "

How miners are forced to include such transaction? What happens if they don't ?

Issue 2:

What happens in this situation:

- A transaction has two receivers (outpoints) user1 and user2.
- Two transaction (a double-spend) are publishes t1 and t2 (both with very high fees)
- User1 asks the miners to sign the pre-confirmation or t1. All miners send confirmation of t1.
- User2 asks the miners to sign the pre-confirmation or t2. All miners send confirmation of t2, thus violating the commitment on t1.

Miners will always win, since they can choose t1 or t2, an always get a high fee, so they have no incentive to help either User1 or User2.

To avoid this situation, the protocol could me modified in this way:

- User B wants partial confirmations on transaction t1 (from A to B). The first output (B.output[0]) is the one that goes to himself.

- The user B creates a new transaction tn with a single input t1.outpoint[0] that pays a high fee and sends the change to a B back again (one input, two outputs).

- B sends this transaction to all miners directly by UDP. This transaction will ONLY be valid if t1 is published, since t1.outpoint[0] is only available in that scenario. Transaction tn cannot be send via the p2p network since it has an unconfirmed input.

Now miners do have an incentive to include t1. If they do so, they also receive the fees for transaction tn.

Was the explanation clear?

Issue 3:

In your BIP you say: "...The message shall contain the entire transaction to be partially confirmed, a return path (IP and UDP port) for the response, and proof that the requester is a party to the transaction. ".

But this way you could specify a IP/Port different than yours. It would be preferable to send the response to the same IP where the UDP packet has came.


Good work casascius and best regards,
 Sergio.

As far as I'm concern, the Bitcoin developers have been very responsive to fixing vulnerabilities (in relation to their available resources). 

I agree with GMaxwell.

With some other vulnerabilities found, the Bitcoin developers have establish a 77% upgrade threshold to disclose the details of the vulnerability. See https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures

To reach a 77% upgrade ratio you may have to wait up to 3 months after private disclosure.

I clearly said "two different signature schemes". That means two different public keys, two private keys, two algorithms, read forum messages twice 

Mekle-Winternitz signatures are Quantum-computer proof.

To achieve composed security form signatures is very easy, you just sign the transaction with two different signature schemes and only allow it if both are valid.

Both methods can be added to Bitcoin, but both require a hardfork.

Best regards.

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


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.


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.

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


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.

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.

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!