Yes I know. I apologize for that comment.

I was just trying to make my point for vuln research

Thank you mandros for taking the time to research on this.

I don't understand why you underestimate the task of researching and reporting DoS vulnerabilities or bugs.
It's as useful as any other community activity.
It has been proven useful to protect the network. The only DoS bug I didn't spot (the last one) was exploited in the wild, so I must assume that ones I did foresee could have been exploited too. I even helped you with the BountyCastle vulnerability some time ago.

And don't forget that "There's an unclaimed $1.1bn dollar bounty to hack bitcoin"  (AndreasMAntonopoulos)

Each one must collaborate with what he can do best, and what he has time for.
If you like programming, and Bitcoin needs lots of programmers, then go programming. I really appreciate you work on Bitcoinj, and the microchannel implementation.
I won't tell you to stop programming and start researching vulns.

I invent and I research and I'll do this foreeeeveeeeeeeeeer......

Best regards, Sergio.

Note that with Luke-Jr patch https://github.com/samr7/vanitygen/pull/10 of the vanitygen miner, a few lines of extra code and a few changes, and you can implement the P2SH/M miner in 5 minutes.

I have a hundred ideas of marvelous futuristic things that could be done with a rich script system, that can read the transaction inputs and the transaction outputs.

This is my wish list:
 PUSH_INPUT_AMOUNT / PUSH_INPUT_SCRIPT / PUSH_INPUT_COUNT (to control how money is used)
 PUSH_FEES / PUSH_OUTPUT_AMOUNT / PUSH_TOTAL_OUTPUT / PUSH_OUTPUT_COUNT (to control how money is spent)
 PUSH_BLOCK_DATE / PUSH_BLOCK_NUMBER / PUSH_BLOCK_HASH  (to control time, and random values)
 PARSE_SCRIPT_TOKEN (for previn/prevout parsing right in the script)
 PUSH_PREVTX_OUTPUT (for tx compression)

All these opcodes (maybe with the exception of PARSE_SCRIPT_TOKEN) are completely secure and it's impossible to mess things up implementing them.

You could do things like persistent transaction-sequences (inputs that are virally copied to outputs).

And once you have persistence, you can have autonomous transaction behavior, such as paying fees every month, limiting the spent amounts, etc.
These are like contracts that persist over time and over transactions.

I'm sure that if I tell you each one of my ideas you will be delighted to use them and you'll find ten more use cases that I didn't think of.

But there is this chicken-and-egg problem: because opcodes are not enabled (and probably won't be) nobody wants to research about them.

Best regards,
 Sergio.

I was researching how to improve the speed of generating vanity addresses and I came up with two ideas:

The first was using a non-standard encoding of the public key. For example, if you use uncompressed public keys and you pad the x and y values with between 1 and 10 prefix zeros, you can create 100 different addresses which, when hashed by SHA256/RIPEMD160 will give you 100 different Base58 strings. The overhead of every pubkey will upto 20 bytes. To enumerate these addresses you only need to execute the hash functions and you don't need to compute elliptic curve operations (just one every 100 double-hashes).

But the problem with this approach is that, to redeem the funds of a previous output, you have to put in the script the non-standard encoding of the pubkey. This in turns presents two problems. First is that you need a patch for the client to do it, or do it manually with the RPC interface. The second problem is that beginning with version 0.8.3 of the Satoshi client, public keys are checked for canonical encoding. So the redeem transaction won't be relayed by the network anymore. You can still send it directly to a miner, but that's a huge limitation.

I wanted to do it in a way that could be as standard as possible. Then I came up with this idea:

Instead of generating normal vanity address, generate a P2SH vanity address for a script containing a 1-in-2 multisig transaction. The first public key is the user's "non-vanitized" pubkey key (that will be "vanitized") . The second pubkey is a nonce, in compressed public key format.
I call these addresses "P2SH/M", to differentiate from all other formats. P2SH/M addresses, as P2SH addresses, begin with the base58 digit "3".

This is how the address actually works in the scripts:

scriptpub: OP_HASH160 [20-byte-hash-value] OP_EQUAL
scriptsig:  OP_0 [non-vanitized-privkey-signature] {1 [non-vanitized-pubkey1] [nonce-key] 2 OP_CHECKMULTISIG}

Here [20-byte-hash-value] is equal to RIPEMD-160(SHA({1 [pubkey1] [nonce-key] 2 OP_CHECKMULTISIG}))


If a third party is generating vanity addresses, he can do on of two things to prove he doesn't have the private key associated with the nonce-pubkey:

1. The vanity-miner chooses the nonce to be higher than field p value.

He can use a nonce between FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F and 2^256.
So the X coordinate will be an invalid value of the field.
This nonces when interpreted as pubkeys will not be accepted by OpenSSL pubkey checker. Nevertheless they will be accepted as standard by Bitcoin client 0.8.3 and before. This is because IsCanonicalPubKey() does not check this.
Then the vanity-miner cannot create a valid private key of this invalid pubkey.
He will have 2^32 tries before the need to multiply the non-vanitized pubkey in order to be able to scan another 2^32 elements.

I really didn't like this idea, since maybe in the future the Core dev team may decide to add this check to  IsCanonicalPubKey()

2. The vanity-miner uses a 32-byte nonce that is a hash digest of a known sequence number.

Now the vanity-miner can prove that he didn't choose a specific nonce pubkey by showing the hash preimage. To find a private key a malicuius vanity-miner would need to break the pre-image resistance of the hash function or break ECDSA.

nonce-key = HASH(sequential-number)

After finding a nonce that hashes the script into a P2SH/M vanity address, the vanity-miner checks that the compressed nonce/point lies on the elliptic curve. If it does not, then keeps trying. If it does, then stops. The probability of not being in the elliptic curve is 1/2.

This method generates 100% standard valid and forever usable P2SH vanity addresses. We only need that clients evolve a little bit more to automatically handle paying/receiving from P2SH/multisig addresses.

Currently it can be done with the Satoshi client and the RPC interfase using validateaddress/addmultisigaddress/sendtoaddress/getrawtransaction/createrawtransaction/signrawtransaction.

Also the existence of the nonce does not degrade the performance of the Satoshi client when checking signatures, since the scriptsig signature will always match the first pubkey, so a check against the second nonce-pubkey won't be required.
The overhead in the transaction is of course very low, of about 35 bytes.

I think the current speedup using a GPU to mine P2SH/M is 20X if you're mining your own P2SH/M addresses or 10X if a third party mines them for you (maybe more, but this is an estimation).

This last idea is interesting since it can scan a 32-byte key space with only RIPEMD/SHA hash operations, so it can be performed efficiently in FPGA or ASIC, without the need for EC operations. So maybe we could mine vanity addresses with 2 more chosen prefix chars.

Best regards, Sergio.

I'm reading Satoshi client code and Bitcoinj code. It seems to me that Satoshi supports given a P2SH address as destination, while Bitcoinj does not. On the other side, Satoshi client does not seems to provide multisig in its user interface.

Armory seems to support multisigs natively, but I cannot find support for P2SH (maybe is there somewhere).

Does anybody have a support matrix for each feature and each client ?

That would be awesome.

Thanks! Sergio.

Thanks!


The process involves using both a hardware random generator and a firmware random pool. But most important, the process is a two-party computation where the hardware cannot force a certain key-pair, not generate key-pairs with any probability distribution other than uniform random.
Regarding saving the keys somewhere, there is no problem with saving these keys. Whenever you decide to extract the funds from a Firmcoin, you should also transfer the funds to another Bitcoin address.
Nevertheless, the Firmcoin will wipe the keys from memory and it can prove (yes it can) that the keys have been erased.
The way it is proved is by a method I created that is called "practical compressibility".  Basically the device will fill its memory with some incompressible data and then send you a hash of this data in reverse order, proving that there is no free memory left that can hold a private key.


Yes, I've already discussed this setting somewhere in the bitcointalk forum (here https://bitcointalk.org/index.php?topic=232787.msg2463058#msg2463058)


First you don't create the key: the Firmcoin creates the key.

To fund the Firmcoin you either give it a block-chain-branch which proves that the funds were transferred to the Firmcoin or you get a certificate from one or more Certificate "authorities" that prove that the address is funded. If many people trust you, you can become your own CA for Firmcoin funds.
Both methods can even coexist, because the Firmcoin remembers the certifications it has.

So why didn't you write this line BEFORE the questions so didn't have to answered all your questions!! :-)


I owe you an more technical answer to this question, but there are many usage factors we still don't know.
The product durability is affected by both physical and usage patterns (that affects the number of FLASH/EPROM write cycles).
The physical properties are very good, since there are no holes, nor connectors and all the prints are inside the package.

My rough estimation is that a Firmcoin can last more than 10 years funded and more than 50 years if the Firmcoin is empty or you don't care if the funds are lost afterwards. We could add the Firmcoin a procedure to "refresh" the memory, so if you execute this function every 5 years, you could have the same funds stored for 50 years. But I'm almost sure that the Bitcoin protocol will change in the following 50 years so you will probably need to do something with your wallet and coins (probably change the signing scheme) before the Firmcoin will wear out.
If the Firmcoin is reloaded every day, it will reach the maximum write-cycles in 270 years.


Best regards,
 Sergio.

I hope next week I will publish my two years late AppeCoin paper. Appecoin is even more anonymous than Zerocoin since it hides the amounts (it doesn't require denominations).

The problem I see with Zerocoin and Appecoin when implemented on Bitcoin is that people trust Bitcoin because it relies in a very simple cryptographic scheme (ECDSA) that is well studied. Any other cryptographic protocol will only weaken the trust on the system.

Do people trust AppeCoin/ZeroCoin source code as much as they trust OpenSSL code ?
I don't think so.

For example, if you break AppeCoin you can create money from thin air, which you cannot do in Bitcoin.

AppeCoin and ZeroCoin are complex protocols, and require much more complex implementations. Trust on complex crypto protocol requires time and review for many years.

Best regards, Sergio
 

They are similar in many things, specially in tamper-proof measures.

Yes but a Smartcard will sign anything you ask it for, for example, a transaction, so it will happily loose its funds.
A Fiirmcoin will also sign anything you want, but it will immediately enter the "empty" state.
A Firmcoin will sign special messages that cannot be transactions, to prove the possession of the private key.

Yes.

Sergio.

We have two models: one (the cheapest) has fixed denominations. The other has a display that shows the Firmcoin balance.

Also check this 4 solutions for the same problem:


1- [PROPOSAL] Untrackable addresses: https://bitcointalk.org/index.php?topic=131243.msg1405288#msg1405288

2- Untraceable transactions which can contain a secure message are inevitable: https://bitcointalk.org/index.php?topic=5965.msg87757#msg87757

3- Mine: http://bitslog.wordpress.com/2012/08/06/destination-address-anonymization-in-bitcoin/

4- Gavin's: Bitcoin Payment Messages https://gist.github.com/gavinandresen/4120476

Best regard, Sergio.

Last week I read in a thread about how mini-blocks (blocks with less PoW generated during mining and no list of transactions included) could be used to switch faster between best chains and reduce orphan block rate.
The idea of min-blocks is particularly interesting to me, since it could also help detecting if the network is split. More precisely if the user has been disconnected from a set of miners with a high percentage of the network hashing power. This method won't detect colluding malicious miners, just an accidental split of the network or an split attack performed by a party controlling the links of a node.

So the idea is...

When the miner finds a solution to the block with PoW >= 1/20 of the target , but still not high as the target, the miner publishes the block-header. Now nodes will receive approximately 2 mini-blocks per minute, and they can keep track of the current hash rate. At any time, if the rate of mini-blocks per minute (counted in an average of 1 hour) drops to less than a half, then the client application warns the user he has been disconnected from half of the mining power. The user may check in forums if this disconnection is because an earthquake has happened or anything, and decide if he's under an targeted attack or not.
(Obviously it is required to compute the probability of the node detecting a half-drop when there is none, and adjust the window time and the mini-block rate so this is very uncommon).

Also a modification of the idea could be used to check the number of distinct miners in the network:

Let Kpriv,Kpub a miner's special purpose ECDSA private/public key.

In each block, the miner also includes in the coinbase field a value x computed as x = Sign(KPriv,r),  where r is a random message.

When the miner finds a solution to the block with PoW >= 1/20 of the target , but still not high as the target, the miner publishes the tuple (block-header,KPub,r), and choses another r to continue mining.

Now everybody can verify that the min-block came from the identity that owns Kpub by checking that CheckSig(Kpub,x,r)==true.
(here I'm assuming ECDSA resists a special kind of malleability)

If the miner finds a solution to the target PoW, he does not publish his identity (the values KPub and r). Since x is worthless without knowing r, nobody can know for sure who is the creator of the block.

At any time, the nodes can infer the number of distinct active miners and inform the user about any pattern that matters to the security and stability of the network.

Opinions?

I've changed the post to include gmaxwell explanation about why my solution just doesn't work.

This is my idea of how to change my solution to actually work:

The additional protective measure would be that any chain reorg of n blocks is delayed n seconds.  During that wait period, if another better chain reorg is received, is processed in the same way. After one period expires, the chain reorg is applied, and a new best chain is created. If a block that extends a waiting chain is received, then the waiting lapse is restarted from zero for that chain. If a node receives a 144 length branch in a very short period of time, it will wait 144 seconds to actually apply the reorganization, so if the network is not split, that gives plenty of time to exchange all other chains in existence and choose the best.  If a node receives two 143 block competing branches in a short period of time, then any attempt to extend both chains at the same time will result in both staying in a waiting state for 144 seconds more. A chain of 144 blocks won't accept any additional extension (the max is 144) so the attacker cannot keep playing this game forever.

Any problem with this?

Hey, don't need to get upset. I'm posting the article here. I didn't post it because I thought that the solution was more important that the post itself, which is very speculative ....

The Bitcoin Eternal Choice for the Dark Side Attack (ECDSA)

Warning: This post is a mere speculation. There are many unknowns that may change the ending of this story, but nevertheless, an attack like this, that tries to divide the Bitcoin community, undermining the moral of each user, sounds quite probable to me. But I love Bitcoin, I’m optimistic and I wish Bitcoin a great future.

The 51% attack is probably to costly and to risky to be performed for profit. Currently it requires the attacker to invest (buy) around 5M USD in ASIC mining boxes. This have been widely discussed (e.g. here).. There are nevertheless fewer posts analyzing on the impact of an 51% attack performed to destroy Bitcoin (e.g. here). The most simple idea is to use 51% of the hashing power to paralyze Bitcoin: just creating empty blocks. But it turns out that this attack can be defeated by comparing branches not only using the PoW, but using the age of the coins transacted.

I will describe an attack that could destroy Bitcoin, starting with less resources, such as 15% of the hashing power, with high probability of success, so then the attacker has a chance to increase the resources gradually as the attack proves to be working. I’ve call it the Eternal Choice for the Dark Side Attack (ECDSA), so that it doesn’t clash with some other attack name in the literature. It may work, and may be carried anonymously. The idea is that, with 15% of the hashing power, the attacker has approximately a 1:1000 chance of creating a branch of 8 blocks in a row himself faster than the main branch. So every 7 days, on average, the attacker gets a chance to revert transactions that most people think they are sufficiently confirmed. So far, nothing new.

Now imagine that the attacker never broadcasts the blocks he mines, keeping them private. The attacker includes in his blocks some percentage of the transaction he sees in the network, such as 10%, to thwart a coin-age distinguisher algorithms. Every time he mines 7 blocks in a row faster than the honest chain, he anonymously publishes the block headers (as proof) in some public board such as bitcointalk, but he does not publish the transactions referred by the Merkle root. He also hacks some computer X somewhere and runs a special version of bitcoind that only accepts double-spends (not new transactions, nor previous transactions). Then he advertises a “service” to allow people to double-spend the past transactions, which would only require people to send the double-spend transactions to X, including a fee of 10% of the transaction output value (the 10% fee is just a diversion to let people think it’s some kind of dark business). Since the attacker has 15% of the hashing power, he can succeed creating a new block with the double-spends collected with probability 1/6.6.

What people would do? If they are honest, they will not use the double-spend service. If they are not, they may be tempted to do so. Suppose 10% of the people try double-spending. After the first successful attack , some victims will complain as having been cheated. Rumors will  spread regarding the current insecurity of the network. The price will fluctuate, but will stabilize. Seven days later, the same announce is made, publishing the 6 block header branch. This time the market will react before the attack is even made. Bitcoin price will certainly decrease, even if afterwards the attack is unsuccessful.  In forums, people are advised not to accept 6 confirmations, but 10. Now the attacker increases his resources to 20% of the network hashing power. Seven days later, the announce is made again, showing 10 block headers. This time 20% of the people opt for cheating. More fraud victims appear. Now more fear spreads.  Bitcoin price drops substantially. Miners fail to prevent the attack by including the original transactions in blocks mined after the attacker branch because some of the transactions were actually included in the attackers branch, but which ones is unknown until the attack is performed. Core developers try to implement a patch for the satoshi client to distinguish between the attacker branches and the “honest” branches, by inspecting the maturity of the coins transferred. But since the attacker branch also contains some percentage of valid transactions, the distinction is risky and the patch also introduces the possibility of wrongly switching to a parallel branch with less PoW. The attacker manages to fool the patch. Some honest miners leave Bitcoin mining business temporarily with dubts. The attacker now sees an increase of its hashing share to 30% of network hashing power. He begins to accept double-spends before actually performing the attack, so cheaters can gamble at SatoshiDice and have their bets reversed when they loose, with 1/3 of cheating probability. SatoshiDice closes temporarily. Cheaters find other online sites to abuse. The Core dev team tries to implement a checkpoint system to manually distinguish between branches every week, but there is no consensus on who should take the decision of which is the right branch. There is a warm debate in the forums. Time to decide for the Core dev team is running out. The same eternal choice of cheating or not comes over and over, as attacker announcements are made too often, like Darth Sidious seducing Anakin to go the dark side.  The attacker increases his power to 40%. . The offer is more tempting, so more people try to cheat.  Bitcointalk heros tell people to accept only transactions with 20 confirmations. The usefulness of Bitcoin is in danger. Bitcoin price decreases. The attacker is advertising the reversal of transaction every hour, with a 50% success probability.  Honest people stop transacting using Bitcoin preventively. The price drops, and drops again. Cheaters start to automate cheating using bots, and withdraw funds as fast as they can.  The price collapses.

The attackers laughs, and then an order to dispose 1M USD in custom ASIC chips arrives, not before  100 additional employees are hired and given hammers in order to smash each chip 7 times, in some secret office at a secret headquarters of a secret department of some secretive state.

Solution

(this section has been edited)

At the time I wrote the post I had no clue of how to solve the problem.  My only relief was the hope that there are more honest people in the world than dishonest ones. But after 4 hours of bad sleep I realized that the key is taking pro-active measures. There is little that can be done well under the pressure of an attack. So my idea is to add the Satoshi client a “Safe Mode”. In Safe Mode, transactions are only considered confirmed if they have 144 blocks of confirmation (1 day). Also in Safe Mode, the clients do not accept any chain reorganization of length greater than 144 blocks (this is the key restriction).  One day has been proven to be enough for the core dev team to resolve chain forking situations, and still it is short enough to let people transact almost as normal. Only services that require fast confirmation will have to pause their operations, or accept payments of low value with the implicit risk. Safe Mode could be announced by using the network alert system, either by making clients automatically switch to this mode or by requiring the user confirmation. Safe Mode alerts would have a finalization date, as other alerts. Also Safe Mode would be immediately terminated by the “Alert key compromised” alert.

This solution is very simple to implement (maybe 5 lines of code), and yet provides an incredible increased level of protection against attacks that attempt Bitcoin destruction. I has to be there so it never needs to be used.

The only drawback would be if a 51% powerful attacker colludes with the dev team to activate the Safe Mode and create a 144 length alternate branch to split the network, which is of course a much more sophisticated attack.

Time for breakfast.

I would like to share my post in my blog relating a society-engineering/technical attack on Bitcoin.
The attack is speculative, and there is no certainty that I will succeed as described. Nevertheless the attack idea makes sense for me, and the suggested solution could prevent the network from other unknown market-socio-technical attacks, that play with human emotions like fear or greed.

Here is my post: http://bitslog.wordpress.com/2013/06/26/the-bitcoin-eternal-choice-for-the-dark-side-attack-ecdsa/

Here is a copy of the proposed solution:

Add the Satoshi client a “Safe Mode” (since there is already a Safe Mode that is related to the RPC commands, this could be Safe Mode 2). In Safe Mode, transactions are only considered confirmed if they have 144 blocks of confirmation (1 day). Also in Safe Mode, the clients do not accept any chain reorganization of length greater than 144 blocks (this is the key restriction).  One day has been proven to be enough for the core dev team to resolve chain forking situations, and still it is short enough to let people transact almost as normal. Only services that require fast confirmation will have to pause their operations, or accept payments of low value with the implicit risk. Safe Mode could be announced by using the network alert system, either by making clients automatically switch to this mode or by requiring the user confirmation. Safe Mode alerts would have a finalization date, as other alerts. Also Safe Mode would be immediately terminated by the "Alert key compromised" alert.
 
This solution is very simple to implement (maybe 5 lines of code), and yet provides an incredible increased level of protection against attacks that attempt Bitcoin destruction. I has to be there so it never needs to be used.

The only drawback would be if a 51% powerful attacker colludes with the dev team to activate the Safe Mode and create a 144 length alternate branch to split the network, which is of course a much more sophisticated attack.

Best regards, Sergio.

This is my last post about Firmcoin, regarding how to prevent covert channels while signing Bitcoin transactions and creating Bitcoin keypairs in hardware wallets, where the user may not fully trust the device.

I think this information can also be useful to other hardware wallets manufacturers, such as Trezor.
If you find a vulnerability in any of these protocols, please notify me.

No Subliminal Channel
http://firmcoin.com/?p=52

Best regards, Sergio.

It's true that hackers are always finding new ways to crack crypto, but since we've hired hackers ourselves, and we follow the best security practices, and we follow closely the security research, we think we will be well protected.

Now, if you see the video, they are using two type of attacks:

1. An active attack to measure the power consumption of the device to extract some "master key".

Firmcoin do not have any master key, so there is nothing to extract in one Firmcoin that let you crack another FirmCoin. If you physically break your Firmcoin, nobody will accept it as payment.

2. A passive attack technique "Side Channel Attack" to compromise some information sent by RF (without breaking the device). This kind of attacks are based on the fact that the device performs cryptographic operations using private keys. The attacks presented require repeating the same operation over and over.

If you have a Firmcoin will only send its private key after entering the "no funds" state, so there no advantage on capturing the RF signals.

You could try to attack the function that a Firmcoin can execute a private-key proof of knowledge operation. This would be the weakest point of the Firmcoin security. Currently, to prevent side-channel attacks, we four protective measures:

A. We use a side-channel protected modular exponentiation algorithm
B. We use randomization techniques to make difficult to predict where an operation is taking place.
C. We limit the frequency of proofs the Firmcoin can execute, currently at 1 every 5 seconds (after the power is applied, you must wait 5 seconds before requesting such a proof).
D. We use an industry standard tamper-proof micro-controller, made by a company with more than 10 years of experience in smart cards.

Nevertheless we might remove the private-key proof of knowledge feature if we are not totally satisfied with our power analysis tests we'll perform on the final device we'll use for mass production.

Best regards, Sergio.

See the Q & A section of the Firmcoin page:

Q8. What stops me walking past someone holding one of these and stealing all their money?

A8. The Firmcoin has two capacitive buttons. You have to press only one to redeem the private key. If you press both, then the private key cannot be retrieved for a few seconds.

I believe that trust is not a boolean variable. You may trust me to hold 1 BTC for you but not to hold 1000 BTC.
If we (the manufacturers) make all possible measures to help you identify authentic hardware from counterfeit, authentic firmware from counterfeit, and so on, then you will trust us a little bit more.

We've made every possible effort so that even if we are hacked the next month, and all our private keys are stolen, a hacker cannot create counterfeit Firmcoins that pass all the tests and tools we give you to verify them.

Keep in mind that:

1. If you change the firmware of a device, then the device won't pass an offline verification tests.
2. If you change the hardware of the device, then the device won't pass offline and online verification tests
3. If you change the look of the device, then the device won't pass offline and online verification tests.
4. If you create a perfect counterfeit device, and you handle it to someone else, you're giving him the proof of your criminal act.

Best regards, Sergio.