A new paper called "Deanonymisation of clients in Bitcoin P2P network" by Biryukov, Khovratovich and Pustogarov from the University of Luxembourg has been published on arxiv.org.
In contrast to the usual offerings, it's actually quite good.

The authors explain how to deny the use of TOR to connect to the bitcoin network by sending enough short messages of a particular form to get all the TOR exit nodes banned.
They analyze a method of discovering the 8 peers to which an average node maintains a connection thereby discovering the network topology.
They outline a DOS attack using ADDR flooding
They outline a method of rapidly lowering the difficulty under certain circumstances by constructing an "Alternate Reality". (A bit less exciting than it sounds!)

There are some other substantial chunks of experiment and analysis as well as some pretty graphs.

Probably the best constructed paper I've seen on Bitcoin.

ByteCoin

Now fixed...

I know Nicolas Courtois and had I not seen the paper linked from his web page I would have assumed that someone had just added his name to this rubbish in order to give it some gravitas.

He should have given his old supervisor a red pen (with plenty of ink left ) and asked him to review the paper first. There are portions which are OK but he's certainly gone a long way down in my estimation.

Bytecoin

Thank you. The intention was also to provide an incentive for miners to make an effort to clear client's memory pools.
I would be wary of allowing fees to change the merit of the block because it's low-risk for a miner to publish a transaction with a large fee immediately before publishing a pre-mined block which has its merit artificially inflated because of the influence of the included transaction's fee. Let's not forget that the purpose of a fee is to pay a fair amount for the time taken to verify the transaction and the space it takes in the block-chain. There are a variety of distorting effects that transactions with large fees have so I suggest that a  transaction's fee for the purpose of calculating transactionfee seconds be capped at a value which is no larger than the transaction with the largest fee that the client saw did not make it into the previous block.

In other words, if a client received a transaction paying 0.01BTC in fees and then received a plausible block which did not include that transaction, then when the client receives a 10BTC fee transaction followed swiftly by a block including that transaction then the transactionfeeseconds of the 10BTC fee transaction should be calculated as if that transaction had a 0.01BTC fee.

The general idea behind this is to start to remove perverse incentives that arise from transactions with large fees while still allowing fees to buy priority service.

I am sensitive to hannesnaude's concerns not to encourage block-bloating but hopefully the existing schemes to calculate transaction priority will cope with that. Am I right in thinking that clients are likely to fail to relay and otherwise drop transactions with very low priority?

I must remark that I am very concerned that we do not introduce further incentives for miners to spam the network with transactions carrying fees in order to increase their own profits at the expense of everyone else. One important metric for the health of the network is the number of zero-fee transactions in blocks.

ByteCoin

I was very pleased to read a recent paper by Eyal and Sirer which put on a rigorous footing something I had investigated in 2010.

I mentioned at the time that there were a number of different strategies which a selfish miner could follow. I found the one that appeared to appeared to become worthwhile at 34% which is the one outlined in section 4.2 of the linked paper. The fact that it pays off at 34% is mentioned in section 4.4 and apparent from Fig.3

Although their paper is substantially correct, I believe the authors neglect the fact that (if I recall correctly) the optimum strategy changes when the percentage of hashpower is between 33% and 50%.

The linked forum topic shows how I was unable to convince Gavin that this mining strategy was viable. I hope that the recent paper and publicity will lead him to reconsider.

My concern at the time was to show how the mining incentives in place encourage the formation of cartels. This is still a problem and I can imagine the bitcoin network reaching a steady state with two mining pools the large one verifiably "honest" and the smaller one "selfish" whereby the presence of the selfish mining pool is tolerated (and even encouraged) by the larger "honest" pool because it suppresses competing smaller "honest" pools. The selfish pool can pay "protection money" to the honest pool either directly out of the coinbase or more covertly by including in the "selfish blocks" double spent transactions which fund new transactions paying a large fee (the success of this scheme depends on the absence of forfeiture of double-spent coins).

As time goes by and fees become large compared to the block reward, miners will of course feel the incentive to build on or orphan blocks based on their share of fees after any block reorganization. It is easy for a miner to appear honest and still participate in cartel activity as it is hard to prove in what order the miner received blocks.

My countermeasure for "Selfish" mining relies on the fact that pre-mined transactions from a selfish miner don't contain as many transactions of non-zero age from the memory pool. So conceptually, when a miner receives a transaction it should start a timer which measures the age of that transaction. When a block arrives it stops all the timers,  sums the total age of all transactions in that block and stores this value against the block. As this is a product of transactions and seconds I propose it should be called "transactionseconds" (similar to bitcoindays) . If another block arrives then the number of transactionseconds for the new block is measured as if it had arrived at the same time as the previous block. The block with the highest number of transactionseconds is used to build the next block.
If another block arrives and the existing block chain rules indicate that a block should be orphaned then the transactionseconds of the longer block chain should be calculated as if all the blocks had arrived at once and the orphaning should not be successful unless the longer chain also destroys a larger number of transactionseconds.

We don't just compare the number of memorypool transactions included in the different blocks as that would give the selfish miner an incentive to stuff their selfish blocks with dummy transactions (which could pay themselves hefty fees to allow themselves to bloat the block).

There's no point for non-miners really to have an opinion about which block is better but if they see blocks destroying large numbers of transactionseconds being orphaned by blocks destroying small numbers of transactionseconds then they can be pretty sure that something fishy is going on!

ByteCoin

PS If I am allowed, I intend to moderate this thread to remove posts which are off topic or do not contribute positively to discussion of cartels, selfish mining, incentives or Eyal and Sirer's paper.

This is the first thing written about Bitcoin that's been worth reading in quite a while.

ByteCoin

Note that this scheme is essentially the one I posted more than a year and a half ago but without the short secure message.
Untraceable transactions which can contain a secure message are inevitable.

ByteCoin

Now that this is well known, I have to point out the following:

If some subset of clients rebroadcast transactions while flipping the sign of s then the transactions have different ids (because currently the signatures are included when hashing to find the transaction ID) and there may be some problems if the flipped version makes it into the block instead of the vanilla version as I believe the originator wouldn't recognise the flipped transaction has spent his coins.

ByteCoin

I've been out of the loop for a while.. Does lockTime work correctly nowadays? If not, when is it scheduled to be implemented?


Well, the worst case scenario (under plausible assumptions) for the exchange signing something arbitrary with some key is to lose control of (or unwittingly commit to) everything associated with that key, so it's important that the key has not been used for anything else.

Now of course if my proposal about transaction id hashes not including signatures were adopted, then the funding transaction could be sent in its unsigned form to the exchange and the exchange could verify that the refund spent the funding transaction because of course the transaction id wouldn't change on signing.

ByteCoin

Why would the other node have to trust you completely to initialize itself under my scheme?
Can you come up with a remotely plausible scheme in which anyone would regret us excluding the signature from the hash that generates the transaction id?

ByteCoin

All known serious algorithms for computing what have become known as "discrete logarithms" on elliptic curve over fields of prime order have a very extensive precomputation step, which, when completed allows arbitrary solutions to be computed quickly.
Please provide a citation for this "fact". There is an attempt underway to calculate discrete logs on a 130-bit elliptic curve over a prime order field. Without some massive algorithmic improvements we're not going to have any chance of attacking 256-bit curves in eight years. I seem to recall that there is some speculation that humankind will never be able to count up to 2^128 let alone perform an attack with such a work factor.

ByteCoin

Whoever holds the private key for P₁ can easily calculate the private key for P₂. I haven't been following your scheme but I presume that's the issuer. If I catch on correctly then the issuer could misrepresent some information about the bond, saying that the issuer public key was actually P₂.

The "modular operations" use the prime p but for the above calculation you should use the group order n which is a somewhat smaller prime.


Yes that's what I meant. The block chain is still entirely self-validating if the transaction hash doesn't include the signature as long as you bother to store the signature. At the moment though you HAVE to store the signatures. Can anyone propose a remotely plausible scenario in which we would regret not hashing the signatures?

ByteCoin

I'm posting in part because I felt my ears burning on #bitcoin-dev.

Does everything that is broadcast have to be incorporated into the block chain? I suggested a long time ago that the signatures not be part of the hash so that the signature data could be pruned out.

There are two issues associated with including OP_DROP data. One is the amount of data stored in the block chain for eternity and the other is the amount of data that has to propagate through the network right now. These issues are not the same and don't suffer the same constraints. I believe the current system smooshes them together to make things 'simpler'. I don't think this is a good idea.

ByteCoin

Nice to see my suggestion being implemented finally.

ByteCoin

Nice work! Implementing this sort of technology is the way forward.

ByteCoin

Ok. Deal with this scenario:
1) Innocent user funds casino account with tiny number of bitcoins and provides convincing ID.
2) Innocent user's laptop is stolen or otherwise hacked by Hacker - the point being that Hacker gains access to innocent user's private key and Innocent user loses access to the private key.
3) Hacker steals lots of bitcoins and sends them to Innocent user's casino funding address.
4) Hacker withdraws the coins from Innocent user's casino account.
5) Police find out that the stolen coins went to the casino.
6) Police ask the casino to tell them who the account belongs to.
7) Police have good reason to accuse Innocent user of theft. Innocent user can't prove he doesn't control the stolen coins and a jury has good reason to believe he can.

ByteCoin

https://blockexplorer.com/address/1QLbz7JHiBTspS962RLKV8GndWFwi5j6Qr

ByteCoin

Since the adoption of Firstbits has demonstrably contributed to useless block-chain bloat and the implementers have "reserved" many of the short addresses before "going public" I suggest that it should not be supported.

ByteCoin

I think this is the wrong approach and will give you problems down the line even if you're dogmatic about sticking to your recommended "solution".

You're essentially asking the unwilling recipient of the funds to participate in laundering them.
Imagine this scenario:
1 ) We have a casino using the kjj/Gavinandresen scheme.
2 ) Hacker says he wishes to deposit bitcoins and supplies them with a return address A.
3 ) Casino generates funding address B and gives it to hacker.
4 ) Hacker steals large amount of bitcoins and sends them to B.
5 ) Casino gets a bit suspicious and to avoid liability as per kjj/Gavin's scheme sends them to agreed return address "A"
6 ) Police investigate theft and want to get their hands on the money (to return it). They catch the hacker but don't get the private key for A. Perhaps the hacker was supplied with A by the person paying him. Anyway, they find out somehow that the bitcoins were sent to the casino.
7 ) Police go to the casino and ask for the stolen bitcoins.
8 ) Casino says "Yes we did have them but we sent them to A".
9 ) Police accuse the casino of helping the hacker launder the coins.

You would also have to address the situation in which step 5 is "Before theft is discovered, Hacker rings up casino and asks for deposited funds to be returned due to 'urgent unforseen expenses'" - a perfectly legitimate sounding reason many legitimate clients would use when asking for funds back from their casino account.

If, instead of sending them to A, the casino hangs on to the funds until the police investigate then the casino can send the bitcoins to the police but then the public might accuse the hacker and the police of working together to steal the coins. Ok the police might eventually generate a transaction which can be seen to return the coins to the rightful owner but that may be years down the line after the case has gone through the courts. Until then, the casino is under suspicion. Also, while the casino has the coins (which might be a lot more than their company is worth) they'd better be sure their internal security is good enough to stop an employee getting their private keys!

The only way the casino can instantly avoid liability or suspicion from an unwanted payment is by returning the coins whence they came. Everyone can see that the situation has been returned to the status quo ante.

If you wish to firefight these cases, I have plenty more awkward situations to discuss. This should be a good thread.

ByteCoin

There are perfectly good reasons for returning unwanted payments. With Bitcoin's lack of fungibility, the only convincing way to untaint your coins is to publish a transaction which the putative owner could use to return the coins whence they came.
In the event that all transactions must have fees to be included in the block chain, there should be a way for the casino to publish some signed message to reverse the unwanted payment without paying a fee.
The signed message should be publicly available from the casino as soon as possible to show that the casino rejects the payment.

The putative owner would then use this signed message to create a transaction to retrieve the coins and would have to pay the fee to get the transaction in the block. They would also be responsible for contacting a bitcoin node to tender the transaction for inclusion in the block chain.

Is it possible for the casino to sign some message to which someone could attach a fee payment which couldn't be stripped off and redirected to another transaction? Is it possible to attach a fee payment to someone else's transaction using the existing Bitcoin System.

There are two interesting cases:
1) Someone has published a transaction without a fee or with an insufficient fee. They're uncontactable or have lost the private keys so they can't issue a new transaction with a higher fee. Is it possible to take their transaction and "wrap" it with a fee payment so that it gets in a block?

2) The case in the quoted article, the casino wants to publish some sort of signed pseudotransaction which can be seen to facilitate returning some bitcoins. Someone else then takes this pseudotransaction and creates a valid fee paying transaction returning the bitcoins where a relay node can't take off the fee payment and use it to pay the fees on some other transaction.

The first case is likely to be more difficult as the cooperation of the sender in constructing some special signed message is not possible.

Can this be done?
 
ByteCoin