I know that it requires some extra hashes but if my math is correct we are talking about 12-13 GHash/s for a 400 PHash/s pool.  And I don't think 12-13 GHash/s cost millions of dollar per year.

This is how I derived the number:

A 400 PHash/s pool grinds through 100 million mid-states per second.  With 4-way asicboost, it needs about 25 million 4-way collisions per second.

If one collects collisions on a central server (the most efficient way to find a lot of collisions in a big pool), one needs about 3 billion hashes to create 25 million 4-way collisions.  If one can live with 5 seconds delay (i.e. blocks miss some high-fee transactions from the last 5 seconds), one can  reduce this to 5 billion hashes in 5 seconds, or a billion hashes per second.

Collecting the hashes and storing them to find the collision is not trivial, but should be possible.  You have to do it for any form of covert asicboost.   

Now, the extra commitment in the UTXO makes computing the hashes more expensive.  Instead of a single hash, you need to compute 12-13 Hashes for the Merkle root (if you still use Merkle grinding to generate the commitment hashes).  But it requires no extra storage.  So the total extra cost is 12-13 GHash/s for a 400 PHash/s pool.  Everything else is unchanged.

Looks like someone put a challenge for breaking weak signatures:

https://blockchain.info/de/tx/695b04afbc477d045d396f062eeff5e950e5e44f91b7e2b273c5a74e27306177

When spending the first three outputs of this transaction, a weak signature was used.

The first output used k=1 when spent.  This was broken immediately by a bot.
The second output used the same k as a previous transaction of  19iAvuzfb8uH2SZLYcbb5wtbBZdn1o3vRm.  The latter is probably a weak brainwallet or something similar.  I didn't break it though.  amaclin, can you explain?
The third output has k=private key.  I solved the challenge and collected.
The fourth output is still unsolved.

The other four outputs are not yet spent.  I guess we still have to wait for the challenge.  Or maybe the address is weak for some other reason.

I noticed that there are a lot of 2 of 3 multisig transactions where one key has the private key 1. This makes them effectively 1 of 2 multisig, although I think the owner isn't aware of this.   Does anyone know, who is creating these?

Here is an example:
https://blockchain.info/tx/9aebe8dedd172d3662d0713ec94dff3ede1efca9b315b52be087872d06a93dc3

There is only a little address reuse.  I count over 1000 different addresses in the last three months.

My script that I still occasionally run has detected repeated nonces (r-value) in signatures again.  Looks like a bad random number generator; the repetitions usually happen some days apart.  The problem seems already to be fixed but the addresses that were compromised are still used.

There were at least 135 keys involved of which at least 82 are compromised now.  Most keys are related to 1BTrViTDX... (in the sense that they are inputs in the same transaction).

I setup a bot to sweep the compromised keys.  If you can prove that it is your address, you can contact me to get the collected funds back.

But don't use the addresses again.  There will probably be other persons setting up bots soon...

EDIT: To prove ownership, you can sign a message with 1HGXq5Spi6NNXFKuQFfDDcYZmzTczKJi4b.  This address doesn't seem to be compromised yet.  Note that this address has also been exposed and should not be used any more.

So far I have collected about 7 BTC.

EDIT2: Fixed the number of addresses.  I accidently counted five unrelated addresses.  Here is a complete list (addresses marked with + can be cracked):
http://johoe.mooo.com/bitcoin/2016-03-compromised.txt

Hello,

I noticed that some miners collect the spam and use a single empty output script with zero satoshi (no OP_RETURN).   For example 6a8b0cd013fd0ed45e93dc9e1a200785fdf54b77f70a5fde2428bcf27ff84c14

I was under the impression that these outputs cannot be pruned since in principle someone may spend them, e.g., use OP_TRUE as input script.  Of course, it doesn't make senses to spend a zero valued coin, but bitcoind must be able handle these according to the consensus rules.  Wouldn't this mean that these transactions still clutter the UTXO space?  Worse, these transaction have only one input, i.e., they do not even reduce the number of UTXOs.

Am I missing something?

The number 00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 is now the most repeated R value on the blockchain (>70000 uses this morning, all other repeated R values are together used about 7000 times).

I saw on the IRC logs that gmaxwell suggested to use this R value for sweeping dust transactions, since it saves 11 bytes of encoding (leading zeros can be omitted) and since the private keys are publicly known, so there is no harm in doing this.  Some time ago, he also posed a challenge to explain this.

The corresponding private key is 1/2  (in modular arithmetic, so its numeric value is (order+1)/2).  It indicates that the generator G of secp256k1 was chosen such that 1/2G has this x coordinate (this cannot be a coincidence, that would be as likely as if the lottery winning numbers would be the same five times in a row).  In principle the generator G could have been chosen such that 1/2G is any valid point (almost every second 256-bit number corresponds to a valid point), so why did the creators of secp256k1 choose this particular number?  What else is so special about this number?

The document describing the SEC elliptic curves seems to avoid this topic altogether.  It doesn't describe how G was generated.

If we want to test how Bitcoin behaves if the blocks are nearly full under realistic conditions, there is an alternative to spamming the Blockchain.  We could try to convince the top miners to decrease their soft limit on the block size.  For example if most miners limit themselves to produce only 300 KB blocks we should see what happens if the blocks get full and the memory pools grow in size.

I'm not sure how easy it is to get most miners to participate in this experiment.  They should not have any disadvantages by doing this (following the logic of some people they should even gain something due to fee pressure) Anyways, the fee is about 2-3% of the block reward and the lower orphan rate should easily make up for the missed transaction fees.  If the transaction congestion has negative effects it is easy for them to revert the block size limitation.  And every miner can choose to participate or not immediately without the need for consensus (of course we only see an effect if most do).

The 300 KB limit is just a suggestion, considering that the current average block size is above 300kb; I expect that many miners are not participating.  Of course, every miner can adjust the limit arbitrarily to add or release some pressure.

I fear there is no way to do this experiment on TestNet since what we really want to test are economic choices.  E.g., it should show if users pay more transaction fees, or if they send fewer transactions.  This experiment may actually have bad effects, e.g. making Bitcoin transactions unreliable and leading to increased 0-confirmation double spends, but at least it is easy to revert the soft block limit if there are serious problems.

I read the zerocoin white paper again and while trying to understand the dynamic accumulator [1] used their I wondered if this can be used to tackle the UTXO problem.  I wonder if anyone has already proposed this idea (probably, it seems obvious to me) and what the problems are.  My idea has nothing to do with Zerocoin, so it isn't a solution to remove the pseudonymity of Bitcoin.

A dynamic accumulator is a way to compactly store a nearly unlimited amount of data, e.g., active UTXOs in a single number, e.g., a 3072 bit number.  In principle the whole blockchain can be stored in this number and a miner can check if a transaction only spends UTXOs using just this single trusted number and some untrusted transaction data that the sender of the transaction could provide.  It sounds a bit like magic but it actually works.

The drawback is that the everyone possessing an UTXO needs to keep track of a witness (another 3072 bit number) that proves that the accumulator contains his UTXO.  The witness can be computed from the list of all transactions that occurred between the UTXO and the transaction that spends it. We probably still need nodes that store the whole blockchain, so that users can find their UTXO and compute the witness from the transactions that follow it.  The witness can be computed incrementally, so if you update your client once a week it can update the witness for all its UTXOs by just reading the list of the transactions that happened this week.

Another drawback is the computation time.  Updating the accumulator is computationally involved, probably much more than checking a ECDSA signature and it has to be done for every input and every output in every transaction to check that a block is valid (in addition to the usual checks that the signatures in the transactions are correct).  Worse this has to be repeated by everyone who wants to update his wallet using a full client.  In fact, updating the witness is a bit more complex than checking the accumulator.  Clients that rely on a server to retrieve their UTXO and corresponding witness are still possible but the work is then just shifted to the service provider.  Basically the service has to update the witness for every user separately.

The security of the dynamic accumulators in [1] relies on the security of RSA (more precisely the strong RSA assumption).  A key of 3072 bits should give us about the security of 256 bit ECDSA.  However, if someone breaks this key he can mint coins.  In principle this can be detected if someone still has the full blockchain since the genesis block, but the purpose of this scheme is to avoid checking the full blockchain.  Another problem is to generate the RSA key in such a way that the inventor is not suspected of keeping the private key to mint his own coins later.  It seems that all published accumulators are based on RSA (or on Merkle Trees, but these requires much larger witnesses).

Of course, something like this requires at least a hard fork, more probably an altcoin.

[1] J. Camenisch and A. Lysyanskaya, Dynamic Accumulators and Applications to Efficient Revocation of Anonymous Credentials, CRYPTO 2002

Hello,

there has been a lot of reused R values in the signatures on the blockchain, recently.  This exposed many private keys.  After googleing the addresses, I think it is related to Counterparty (XCP).  Here is a list of the exposed addresses in alphabetic order.  Most keys were exposed very recently, i.e., in the last week.

If you own one of the following addresses, you should transfer the money to a fresh address (before someone else does it for you).  Also figure out, which client has the bug that revealed the private key by reusing R values.  Then notify the author of that tool.

112KZ24UgNndZqdnu2cXwXStSjtY78ZRUh
12ZXAga2nRxBECsMDjFypWuL9UkKEaS4Z3
12sisxXmNPmFTpekBKEqZCELYXESPYUHCB
139YrtXS2J1KiD8pf2R3RtKRPr8sLwLuiq
13GSuGxtMZyE6SDA8XJyuWsHYpXZyNQTAn
13ikC8398HhciFWkqPCrRHWUBASGxhBY4m
13tRCNGCGuVN4gYyf6CpfYckhM3qrJy9YX
14Bgi1c11HBcj7krN5tRepMdL3SPghEaMM
14kaXa47cUcMpvKnCa8zr38C9v7sVPxSta
14qF25Rg3hJaYFHwE6ST2rr1cnBS3DPYNe
14uS988CkkfTs7Ckre8nkVedSQF9v4CqrM
1599DB5Tb1RWDPYMuU3YJT3jRwyyoPZa1B
15Ew6Sen8hVhTfLmXvAEEqGfX58iYWqEV5
15mcUhVMi3KmoWvP6Y8NpVaXaPVGCWztgL
1681LkMDLNw6CCjUrMojRKC8BaiwQ2LTFt
16LEKMzhabDoTghR2no3a59SJQC6MJp2aM
16NMGWRavnYG5bhWzY8GAXWiTZLytpT4v7
16khUbFwUK6X7U5X919RJeWyfBHSLfJMda
16vHYDZCLZiD97TucWr5Wht9zBA7JJmuF5
17SP6Qc3fP3zUWFkfRrwY3TF3a6eQ3NsZr
17Vxv31VfpFY6tWBBB93tcSgP4SYeqzTTb
17quWZhtGikUcTUpExchL6UdFga6Z8hME9
17xnTfrWYiLMhEQmW55VCa5cVhSZMVUak6
181ErGfBCT7twckweWJgoDMGXNepvb4qnp
185YGf4EoVfgqFBSAAUf1wDte9KVwmdHMy
187TT5PpAKGHRBGjdaKDZsgBH1s8yNCtS4
18RecXQxH8xuqS1zNgrukvPybDtc3Mn4br
18SEPGaZ3xdHiH2hkSdPgkYdnvzPr6PZYS
18U2grD3VwFa626tkTnabXSY2nVQAvmf3U
18W9kV7SqNPnvcbZRzM34aE14m5tFmAuz5
18djF84ZNVURvFUX2ZAVaFqV9MerjJkQtE
18mEp3aKQ9thp3H72rrzHAfW719YmHq2f7
199EPbUzU6mBr7dP61ihWsicuJyeYbJviS
19Ey6feEfARgzcNRmUxBZNQFYSmwgsU9Wc
19usDGaGtwHfMoJKAJEJd3KcfZFWj5zocV
19vokfKSJJMwHAqQ3Kehk8Gq5drXhi7wzU
1AApKu3su7VT9K1hgyxp3pcp2DSNC5V9s3
1AFZ8j6Mm6EphAFJbHyzCxKpKm9si8Vt3v
1AGCK1JM7pEu5r4g5yRiezXhn83TPGaWEh
1AKE18rv9BUPpxciQziTjQzwNQoMSrvQaV
1AX5hvrNXTs8KnDVBSRwHPHg5iQ5fyb8rs
1AjwULXBv9TeVjADC3khcP69USBGRXYUpd
1ArJ9vRaQcoQ29mTWZH768AmRwzb6Zif1z
1AsEhnbniTP4YSA8L1Xa1uQjfSfHbb8tzJ
1AsbDvSw2rzEa39erkCrMW6KTr4tDHGSAH
1Asfz56unNm1c527p3ENavRqecShQyxHeN
1B9FoQWdPift6CUXUs6K82TZxaTyHpTUnC
1BDMV3Yb6Pp2ycB94UsruXgPWAWBJhBuKL
1BYuQ21smrF1hKfmHPsDnJkWZZdEpBFLZo
1Bn1n2N9Z3Xhnxd3b6ViNMstg7oGjh8XAa
1BwrmTmhnp6K6Shbq5zQQqGqnsfXsunsqE
1C4YepY3K1gDrRiQ5E9rgaJuXvrawxXMJG
1CAsRJ5Z9CXdhBwxrCVrf8kJNPBxYQJiH1
1CLfNqGBb949bBbMgefRPkDVgpgyEgWRF
1CPzjQTH5vNADXQGeCfHtRgX8S5xMLGMr4
1Cbw9MZ8Vrfkzv1FxuJS5JBySbypuMARQj
1CgEzXmF7SeNr8rd2AfyN1DQNJpprVxWmW
1CjKefUiRhK5hWf79MoJqccHC1ohye7SWr
1CpV2F9YASreNrBGf1E8QgFgKdqYQopzGH
1CtgapxmS4CRLCNFGTbidAqfk9WNdR2kdn
1D76ha9QoxkUPLxufDoZVEzx6hH3uVJvnZ
1DEsbC42Je7psYeaE2mbWNUpSEFTL9aQUs
1DL21hg5FBLC4h9mXwx9XDbHmUK3BZFCQe
1DkCk3S98BCwPP8wdmxqQKcQoH4WJthvMR
1DpyhFtQs3yVM4gSf3KiD9GBxcPaxuQRDT
1DqXkT8KR25q56sAerfSg875KaJ6o3f3mi
1Dsoi4eggJhipmYZtFGPGBxLX8nguYxiGh
1DxzwX4qC9PsWDSAzuWbJRzEwdGx3n9CJB
1E1rbpZitcZ73JQoLYXB18pDm8BTHVqxtk
1EGok6kAbJRrzryXAGyCHRq5c649rhzwJ3
1EKJUnK4EE83LdGsCnFPZxgkybyFiTdbMk
1EMkFrY86siasW3F9zC2bS1ZcSuTdaiJqj
1EMxjb3667se6LuqkhRsrBaAScGsx5DMFq
1EZtDBBkqkHxRXNSBwTV7HhBbPVvqC8Rte
1EkkAMw1K6HKGiou5vNrLBffDtjVAC5HW3
1EqBqwtfJMZERvyckvexLJLuSrqYewCaE3
1Es37FWCT3xDCrQM2NEJLajRPYNbk7jUaH
1FMhAUpVgU2H3n576vUe7vQp94zCkRPnf6
1FSmh8gSuPkZTqx6LeH6Jic4iZ1A8BsZ2L
1FyQtBr9ub8FhKGDcgW2uAbU6cHYuNmBk3
1GNvTWNZM48QA44QmbVjxXhQ7hmJDicxec
1GvhZ6FewuuyYwZ9cPWd614Gu6UhWacrDY
1HAEJNWN7johTEiooRau7F6NFvHnBDXHzh
1HDGRnafT7ogCaMuHx9csBGvGeYc441tQ4
1HMYjeeZf4qq9L9WZRaBKnNjsP1bSLsuMs
1HSUdtBoNbexP3ordhnSZ2jfHCGVvAbGt
1HW45VWikPEoijyKtguggMEJ5CnsS78ESf
1HfjrpJLP5SaPRFzYUxrzhppw6xv6GXZ6f
1Hu5wfuk9nHuYDpdX6FjQrU1NYvpUS8r6t
1JHL7mbGq64heFnJA8i2QVm18p4TQ1kf9M
1JX7Z9Si6tUQgFa4PLNTtJ8bC9WrfMDvLb
1JmY6KZxoMjMaFKLVSMAr7BdsAAWASMR7d
1K3iZPSqMCxtMd5o5hw4gfpFq3i9zqL61o
1K8fu7jfjuKS28YrA2rSCy7fkZhNvcab5p
1KJERjQwXx8ojrKRSPFKwkCct1aAkyHgnF
1KS7abb8CrqrSizfyPXkcRocYejZQ332xM
1KiAVfFJH9EU29C9H9p2SBnrkfzrgrRRCe
1KojFMcdHzDndhfqPxb5CnXeB1R5u9nnxG
1KpxMLLmEhaqoUXN1hfq8fci4z7p593HsV
1KvvnDBRtHFZdE9ngqGWV5VGznFgXuF1fd
1Kzf3YptWEMwDHF1nmVpMbs3jSvWjWdSbR
1L2Bcohuf1qyHykTdP8rD74K6HQSsTaTE
1LCnNsa2pxbZCsVdRoNqLGFcULbrEFL4i1
1LKVE8ys5rep3LbELC3fhfCRWXQiEi7hpv
1LKumxgbfSycQVaAwagpyZRSy71wXC2zhF
1LWDzisQtETsxk6N8QNa1KuUSiYtmmfa5A
1LhA9wbU4enUCT8EVorxeJegQtkZcyr7m6
1LrUd8tr5TD3UvD4KZaiNcAxmFveCw5h27
1M52izWFApBEuRMqMx4gbr8prABCA9Q9tv
1M7hSnVZniAXrre2SH9qaHvfxgXRAjpMVk
1MLQDQQsaHPSPQwp3TJ5YSbffm2EHneaU9
1MMMpX4AKhf9JTviWuU7fwnZuTdW78G2Mf
1MX1fSzSvTuw3yNgPNE3Ni31kT1DSdeUPC
1MmJk1peLVmycqY8Hq6WyZfrK4u1oTvkER
1NAddQ2XhM96aGn4yK9naRzxTxe7BbNTLG
1NLbWbTczixoA3sCgQg5NLpsExqRPJiA3H
1NMb6g4rQXHmsaHaiy1iV2Wmn4bTGwxyLT
1NR7Bw4XWK3oic9HvgWFProGVzp5jKeqCw
1NWXH2DE5DTfKWAwABAvFesGXKkyKBUoiN
1NeAtszct9Uav81CEr1FGhV4KAaXahdsVF
1NjGEKWWrupvbzvEivnfXJpdNdXK5xzdDb
1NkYPP3Eix9shAvU47xJtnL4Ggd2ScAbcD
1P5anXJVbPeXsw4wExuQ8SCBRevRPe8syQ
1PEAu3bS7t6ZYKGX77ZJsEKSupGzdR5Kpj
1PNa9dZ3P3fVhx1uMCqJ4sEYmyhxnQNy3M
1PQwoVNRCiK2J5GNumfpT3qk7KnhKPJ6Ph
1PVHbRqh1eYsGCVZ7t18UCQ6oPzXFR3HQz
1QBYgXMTqEQNgoVotQN2iP1sPhHRPEoDHb
1QDB2W1VFqinxu5zm4qMGecQTfviBjk3JA
1RfEM5WPtboTNnjHN3HR889FyuUx6T14D
1ZaRiG4qLj336tKFMZCGPpySoRQsReivv
1iuC1ovtbMJQLniEiJtR5obbWvVkmTjiE
1ptDzNsRy3CtGm8bGEfqx58PfGERmXCgs
1sgNrgAnjMVSzyeMDTeVsKN7FuZy34U5t
1vdbVPC6Ts9d5WhRDriPdndvvCwmCbKCj