Increasing Anonymity in Bitcoin ... (possible alternative to Zerocoin?)

[Horas Yuan Mouton]

A paper for your review:
Scribd
pdf

The work attempts to increase anonymity in bitcoin transactions.
Any feedback is welcome.

Title: Increasing Anonymity in Bitcoin
Abstract:
Bitcoin is a peer-to-peer cryptocurrency that prevents double spending using a distributed public ledger (known as the blockchain). Due to this, true anonymity is not present in Bitcoin because funds can be traced as they pass via different addresses. It is sometimes possible to link various addresses and obtain information not apparent in the beginning (such as loops). We present a method to enhance the anonymity of Bitcoin-type cryptocurrencies. Our method uses a new primitive known as
one-way aggregate signature (OWAS). The anonymity in our scheme is based on the hardness of the computation Diffie-Hellman assumption in bilinear maps. At a high level, the idea is based on ‘mixing’ funds and can be summarized as follows. In the blockchain, each individual block holds a list of transactions that cryptographically link the sending and receiving addresses. We modify the protocol so that transactions (and blocks) do not contain any links between sending and receiving address. Using this, we obtain a far higher degree of anonymity than what is currently offered. We use two techniques to unlink the input and output addresses of a transaction - using OWAS and applying the knapsack problem to further obfuscate the funds going in and out

[1713541042]

1713541042

[1713541042]

1713541042

[1713541042]

1713541042

[gmaxwell]

I'm glad to see someone with an aggregate signatures proposal.  From an anonymity perspective, I believe a cryptographic approach is unnecessary, and they are very difficulty to deploy, but still may useful in the future.

There are certain malleability problems that arise when using aggregate signatures that would need to be carefully engineered out. For example: I believe If the user has received multiple coins using the same public key (something that is discouraged and which harms privacy today, but is commonly done in practice due to user (and wallet software author) ignorance, as well as convenience) then I could take an OWAS spend of a coin with a certain public key and make it instead be spending a different coin with the same public key.  

Your proposal to use OWAS may offer additional benefits beyond anonymity however.  I'd like to better understand why you write:

"Furthermore, for our application, an even weaker form of security - the non-adaptive case - should be
sucient. This requires the adversary to output a forgery after making only one sign query."

The notion of compressing all the signatures in a block into a constant size output is very attractive, even if it retains a linear validation cost. The improvement of anonymity could be viewed as a side benefit.

[gmaxwell]

Ah. I see. I skimmed too quickly.  I see why the multiple spend problem does not exist: you use the blockhash in your reference when spending from OWAS keys.

After skimming "Aggregate and Veriably Encrypted Signatures from Bilinear Maps" I also now understand your security comment. In this model a sign query is getting the redeemer of a masked coin the sign some message. I agree that its reasonable that a forging aggregation does not have repeated access to a signing oracle.

Your proposal also results in a desirable anti-censorship and participation incentive improvements. Because aggregated spends cannot be deaggregated if a miner learns of a "desirable" spend  only after it is aggregated with censored spends, it must take all or none.  The prospect of open aggregates would also allow relaying nodes to participate in collecting transaction fees.

One problem I see is that waiting on a OWAS output to be confirmed is not sufficient protection before spending it. The network consensus is only eventual a confirmed block may be reorganized out.  Our coinbase transactions have similar exposure and the network will not allow the spend of one before 100 blocks have past.  100 may be excessive however, especially since the signer can sign again with the new signature, assuming the output eventually makes it back into the chain.

[socrates1024]

First of all, thank you for working on this problem and posting it here!

My main criticism: I'm concerned that this paper conflates two senses of anonymity (information leaking, and deniability) and switches between them. The motivation is based on the following statements about anonymity (the information leaking kind) in current Bitcoin:

1. Each output is linked to the inputs via the signatures.
2. Each input is also linked to the previous output via the ref.
3. The inputs themselves are linked together (they belong to the same wallet).

Sure, papers like Reid&Harrigan rely on these links to learn that two inputs are possibly/probably related, either because they're the same user or because they interacted (like a client and merchant). For example, it is typically the case, in ordinary usage of the client, that all the inputs belong to the same wallet.

However Bitcoin already provides deniability, in the sense that none of these links *necessarily* exist. You can already use the rawtransaction API to add one signature at a time to a transaction, so not all inputs in a tx are necessarily signed by a single entity. Nor do the outputs necessarily link to the inputs - you can receive bitcoins from arbitrary strangers, you can also send bitcoins to random addresses you find scribbled on a wall somewhere. The recent thread about CoinJoin https://bitcointalk.org/index.php?topic=279249.0 basically proposes using some out-of-band matching mechanism to find other people to do this kind of signing with.

So it seems like the most that could be said is that OWAS may reduce the costs or DoS vulnerability of something like CoinJoin, by allowing the transaction to be constructed incrementally, rather than in two full phases (which is a real reason CoinJoin may be impractical). It would be easier to understand the contribution if the distinction between deniability (which Bitcoin already has) and inferred-links is clarified.

[gmaxwell]

Seems really simple to implement using the PBC library:

E.g. with the little BC tool: (using random points to replace the hashed messages)

g := rnd(G1);     //generator

x1 := rnd(Zr);    //signer 1 secret
px1 := g^x1;     //signer 1 pubkey
m1 := rnd(G1);  //signer 1 message
s1 := m1^x1;    //sign

x2 := rnd(Zr);
px2 := g^x2;  
m2 := rnd(G1);
s2 := m2^x2;

x3 := rnd(Zr);
px3 := g^x3;  
m3 := rnd(G1);
s3 := m3^x3;

ag := s1*s2*s3;  //aggregate

pairing(m1,px1)*pairing(m2,px2)*pairing(m3,px3) == pairing(ag,g);  //validate the aggregate
1


I got hung up reading about it with some confusion about how it could be unlinked when the verification works on message_n,publickey_n tuples. In case other people hit the same point of confusion:

There are two kinds of message signed for in a group  INs, messages which say they're spending a particular coin, and OUTs, messages which say they are paying to a particular coin.  Making a single one-in-one-out transactions involves creating _two_ signatures and then aggregating them.  Because the aggregation is one way someone can't steal your coins.. and once more are added the correspondence is obscured.

[gmaxwell]

The easiest way to add this to the Bitcoin protocol would be to:

add a  OP_SIGINVERIFY  that pops a public key and a sighash flag byte off the stack and hashes the transaction according to the flag.  The public key and hash are queued for validation.

Define additional data appended to free (non-block) transactions with version=2.  This data contains a list of zero or more additional pubkey,TXOUTs pairs. the TXOUTs are hashed, and the pubkey and hash are queued for validation.  The additional data also contains an aggregate signature. When a transaction is added to a block this additional information is stripped off.

A transaction is valid if the aggregate signature passes and if the sum of all outputs (normal and in the additional data) is less than or equal to the sum of all inputs.

Add an additional hash to the coinbase, which is a hash over an aggregate signature and a list of pubkey, index values which index into the list of coinbase outputs. Tack this additional data to the end of the block.

to validate a block, validate the non-aggregate parts, and accumulate the aggregate keys and message hashes,  then accumulate the keys from the coinbase along with their hashed txouts.  Finally check it against the aggregate for the block.

Because this utilizes the unspent-funds-become-fees functionality this would simply be a soft forking change.

[Horas Yuan Mouton]

Thanks for the comments. I will respond incrementally.

However Bitcoin already provides deniability, in the sense that none of these links *necessarily* exist. You can already use the rawtransaction API to add one signature at a time to a transaction, so not all inputs in a tx are necessarily signed by a single entity.

The current protocol does not provide the deniability in the following sense.
The signatures are still created on the entire transaction, linking the outputs. If the outputs are not linked, then anyone could potentially steal funds by removing the original output and adding his own. OWAS do not allow "removing the original output".

One problem I see is that waiting on a OWAS output to be confirmed is not sufficient protection before spending it. The network consensus is only eventual a confirmed block may be reorganized out.  Our coinbase transactions have similar exposure and the network will not allow the spend of one before 100 blocks have past.  100 may be excessive however, especially since the signer can sign again with the new signature, assuming the output eventually makes it back into the chain.

I agree that fresh coins should not be allowed to be spent until several new blocks are added (example 100). In this aspect, the new protocol should behave exactly as the old one. This might need to be clarified in the paper. Thanks also for mentioning the "anti-censorship" property. In fact this was the original motivation for OWAS, though in an entirely different context.

[gmaxwell]

The current protocol does not provide the deniability in the following sense.
The signatures are still created on the entire transaction, linking the outputs. If the outputs are not linked, then anyone could potentially steal funds by removing the original output and adding his own. OWAS do not allow "removing the original output".

Sort of.  With the current protoco a set of otherwise independent parties can collaborate over an anonymous communications channel to safely produce a single transaction.  E.g. I can author a transaction which spends one of your coins and one of my coins and pays to a new address of yours and to a new address of mine. The transaction is not valid until we both sign it, which we can do in parallel and merge our half signed transactions after the fact.

Third parties who didn't witness our negotiations cannot discern if we are one person or multiple, or which of the outputs belong to which of the input owners. If there are more than two parties there are way to conduct the negotiation externally to the Bitcoin protocol itself so that none of the parties learn the input/output correspondence for the other parties.

You can perform these transactions using the raw transactions commands in the reference bitcoin software.

So while the inputs as a set and outputs as a set are linked, the collections could involve multiple parties like you achieve for a whole block with OWAS.   The OWAS removes the need for any bidirectional interaction or cooperation of the signing parties. A clear improvement for privacy, but perhaps not quite as much as you believed.

[royalfestus]

the use of peeling chains and layering in sending fund to new address and different chain; Are they new method of masking transaction in bitcoin?
Are they expensive in adoption?
Can the process not be handled to reduce the bitcoin crime rate in coin transfer and tracking?

[Pik2]

I recall when anonymity was one of bitcoin's most talked-about features; it's amazing what happens when something becomes popular. Sure, there are still ways to use bitcoins to remain anonymous, but it is becoming increasingly difficult.

[pooya87]

I recall when anonymity was one of bitcoin's most talked-about features; it's amazing what happens when something becomes popular. Sure, there are still ways to use bitcoins to remain anonymous, but it is becoming increasingly difficult.

You are confused. The way this "bitcoin anonymity" you mentioned was talked about for a couple of years starting around 2013 was never an actual "feature" of bitcoin. It was only a misinformation that got big where people thought their transactions on bitcoin are 100% anonymous.
Otherwise from day one, nobody made such a promise ever to change it later.

[BlackHatCoiner]

I recall when anonymity was one of bitcoin's most talked-about features; it's amazing what happens when something becomes popular.

Let's see what happens when something like Bitcoin becomes popular:

• CoinJoin: Bitcoin privacy for the real world
• Lightning Network: Scalable, Instant Bitcoin/Blockchain Transactions
• Taproot proposal
• 2022 List Bitcoin Mixers Bitcoin Tumblers Websites

As for what was talked-about most back then, I currently observe a lot of talk about privacy; https://ninjastic.space/search?board=6&title=privacy

Sure, there are still ways to use bitcoins to remain anonymous, but it is becoming increasingly difficult.

You mean to trade them for fiat in a centralized exchange? Sure, but if that's not the case, my lightning deposits are quite private; they stay between me and the merchant.