I would add my two papers. Although they are not strictly about Bitcoin as it is today, they bring many comparisons between Bitcoin and a proposed system and suggest many Bitcoin improvements.

Author: Sergio Demian Lerner
Topic: MAVE, NEW LIGHTWEIGHT DIGITAL SIGNATURE PROTOCOLS FOR MASSIVE VERIFICATIONS
Year: 2012
Link: bitslog.files.wordpress.com/2012/04/mave1.pdf

Author: Sergio Demian Lerner
Topic: MAVEPAY, A NEW LIGHTWEIGHT PAYMENT SCHEME FOR PEER TO PEER CURRENCY NETWORKS
Year: 2012
Link: bitslog.files.wordpress.com/2012/04/mavepay1.pdf

Thank you for the links you posted, there were many papers I didn't know they existed!

Best regards, Sergio.

When I analyzed and found the DoS vulnerabilities in 0.6.2, I remember having also found potential DoS vectors that were prevented by the IsStandard() check. The attack surface is a lot greater if the check is absent, so I think the check is completely necessary right now.

Honestly I haven't thought how to implement it on Bitcoin as the system to support these contracts (the first payment). I'm testing it on an alternate cryptocoin which does not use "prevouts" but "account numbers" and allows contracts to become effective conditionally. Then I can trade against Bitcoin in the way described. To implement this kind of contracts in Bitcoin some rules would have to change...

That's why I said this could be an advantage for ALTERNATE cryptocurrencies, and only indirectly, for Bitcoin.

No extortion is possible.

First let's assume a system where transactions/contracts have a timeout field if the proof is not published in a block.
(I'm using here my P2PTradeX terminology of what a contract and a proof is)

Since the contract specifies the length of the branch, it should specify a length whose time is much shorter than the timeout for the contract.

For example, a Alice publishes the following contract:

This contract will pay 100 XC from the prevout X to Bob's address if and only if a "proof" is published before 20 blocks from the publication of this contract.
The contract is this:
- The proof consist of a Bitcoin block branch containing a special tx.
- The block branch must be of length 6 after the block where tx is found,.
- Tx must be a Bitcoin transaction sending 100 BTX to address 37muSN5ZrukVTvyVh3mT5Zc5ew9L9CBare (Alice's address)
- The Root of the branch must be 00000000000000ca853e8e3faa30451909ec22db537717653b8bb6949fbe175c (this is the hash of a block 30 minutes in the past)
- The maximum length of the branch should be 10 blocks


Because there is NO SYMMETRY between Alice and Bob, the timeout on XC is setup to be 20 blocks, and the timeout in Bitcoin is setup to be only 10 blocks. If Bob manages to create the tx in Bitcoin in the time specified by the contract, then there is plenty of time (10 blocks) to publish the corresponding proof in the XC system.

As far as I can see, there is no way of extortion.

Best regards, Sergio.

Dear Mike,
As I posted before, that kind of P2P trading (GMAX/luxgladius) does not work well because of the need for timeouts.

My proposal is not based on Example 5. Please read carefully. The only thing in common is that both use the word "Contract".

P2P exchange for fiat is another interesting problem, but it has already been discussed in some other threads. This thread is about P2P cryptocoin exchange.

I think Bitcoin would benefit from any new possible P2P exchange (for example SecondLife linden dollars).

Let's talk about GMAX protocol. The protocol is almost perfect. But as you say, a timeouts would be necessary to prevent the coins getting blocked if one party refuses to reveal the secret.

I see two problems:

1) Suppose the payment A->B is done on cryptocoin X and the B->A payment on cryptocoin Y. If Alice refuses to tell the secret "x" after Bob has told the secret "y", Alice can wait until the last moment when the timeout in Y will elapse and send a transaction that grabs the payment B->A, leaving no time for Bob to send the corresponding transaction in the cryptocoin X. The A->B transaction will timeout, and the money will return to A. Obviously adding a third party would prevent this, but the protocol must be TTF-free.

2) With the scripting system, Alice could encrypt the value x so that it's difficult for Bob to manually find x from the transaction scriptSig. For example the scriptSig reference to x could be "r t + ~" so that x=~(r+t). Then the transaction would need special treatment to extract "x" and "y" in cleartext.

These problem are not present in P2PTradeX. I know it's a bit more complex, but it works and has no drawback.

Best regards,
S.

Could you clarify this:


Is "ABob_pub + H(x)==Ah + H(y)==Bh " the scriptPub ?

Are the values x and y provided by a scriptSig ?

It could in theory be done if banks emitted some kind of digitally signed document when they sent money to an account (which they don't)

Take into account that since bitcoins can be traded against USD or any other fiat money relatively easy now, trading against Bitcoin is "almost" like trading against fiat money.

Sergio.

I want to describe a new P2P protocol I´m implementing for an alternate cryptocoin as a proof of concept.

The protocol allows cross-coin p2p trading without a central point. It seems to me that it is the "holly grail" of alternate crypto coins. And this is an idea that can change the cryptocoin ecosystem for good, where all coins trade against each other. The benefit for alternate chains is enormous: they don´t need to provide an exchange site, they can trade automatically against Bitcoin. It also means that alternate cryptocoins will rely on Bitcoin and will support Bitcoin because they need  it to enter the cryptocurrency game.


This is short explanation:

Suppose that there are two crypto-coins, XC and BTC. Each coin XC and BTC has its own blockchain and client. The user A has some XC and want to buy some BTC in return. User B wants the opposite. First both parties find each other (in a central directory or by a P2P protocol) and fix the trade price (A pays "a" XC and B pays "b" BTC back). There are two payments A->B (in XC) and B->A (in BTC). We well call these payments first and second payment, respectively. Both users have an address in the XC system and an address in the Bitcoin system.

The protocol works as follows:

1. User A commits to the first payment of "a" XC to the address of user B in the system XC. This is a special payment with a "contract" that is automatically allowed if a certain "proof" is published as a special transaction in a limited interval after the publication.

2. User B sends b BTC to A via Bitcoin in a standard way. This is the second payment.

The contract specifies that a piece of the Bitcoin blockchain (a branch) should be copied into a special transaction called "proof" into the XC blockchain to prove the second payment has actually taken place.

The contract also specifies:

• The chain branch size (N). This is how much effort in terms of confirmations (PoW) must be added after the block where the second payment is published.
• The hash of the block where the branch should start (root block). The root block should be chosen to be some blocks in the past to avoid choosing a block that will be discarded by a competing branch. For example, if current block is BLK and the previous block of BLK is Prev(BLK), parties can choose a root in Prev^3(BLK) with a length of at least 9 blocks (6 confirmations after current block)
• The maximum number of blocks after the root block where the second payment can appear. This is to prevent the payment being done just after the XC contract interval has expired, thus making the trade one-way only.

3. When the proof transaction (that matches the contract) is published in an XC block, clients automatically accept the first payment (that specifies the contract), thus paying "a" XC from A to B.

Notes:

1) Not the full Bitcoin blockchain branch needs to be included in the XC blockchain. Only the headers of the N blocks, the Merkel branch that proves the existence of the second payment and the transaction of the second payment. Generally less than 800 bytes are required for the full  "proof".

2) All this protocol works transparently. The user only setups maximum/minimum trade prices and trade quantities.

3) Generally B is the most interested that the "proof" is published, but if B doesn´t do it  (and the second payment was done) then A itself can publish the proof.

4) The "proof" is included in a block as a normal transaction and can pay a fee to the miner, but the minimum fee is specified in the contract. Both parties should take care of specifying fees that allow the transactions to be selected by the miners to be included in a block. If the fee is not enough, a higher fee can be specified when the proof is sent. It is recommended that the fee for the miner of the "proof" be much higher than normal fees to give a strong incentive to miners to include this transaction in all competing blocks.

5) The security of the system is relies on the premise that no party can build a blockchain branch longer and faster than the "global" branch in a limited interval (e.g. 20 blocks). Also the proof cannot be constructed in advance, since the root block (which is almost the current block) is specified in the contract.

6) If the trade fails because the interval has elapsed and the second payment was not done, the first payment is canceled.

7) The coins committed in the first payment cannot be used until the contract is canceled or it is accepted.

I have a proof of concept of this protocol working. I will release the code when it's ready. The system is implemented in a way to understand contracts for all other alternate currencies and unknown ones. The user specifies a "template"  for the second payment message, with placeholders for the fields that are unknown (the transaction signature) and fixed values for the remaining fields (amount of money, public key of recipient,etc.). And also a template for the block format (field of linkage, hash algorithm, etc.).

Best regards,
 Sergio.

PS: I named the protocol P2PTradeX, because there was no result when I googled that word.

libertaad: I know you´re doing your best effort to prove the game is fair, but using math.Random() you are proving nothing. I would be the same as skipping the client_seed stuff and telling the users to trust you because you´re good person or had no complains in the past. Either you provide a secure system or your efforts are worthless. If you want to convince your users there are plenty of companies that audit the PRNGs like iTech Labs. , eCOGRA, etc.

It seems that with little additional effort (providing client-side user programmed scripts to choose the client_seed) you could still take advantage of current developed system and secure it.

best regards, Sergio

                                                                                                                                                                                                                                                                                                                                                                                                                                                               

I've not researched the subject myself, but reading other peoples research it's clearly stated that Math.Random can be predicted with high accuracy: it is seeded with the system time each time a new page or new tab is open.

From http://ifsec.blogspot.com.ar/2012/05/cross-domain-mathrandom-prediction.html:

"In Firefox, each page will have its own PRNG while in IE 8 and below each tab will have its own PRNG and the PRNG will *not* be reseeded if the page in the tab changes, even though the new page might be in another domain."

In Windows, Firefox javaScript engine calls QueryPerformanceCounter(), which provides some a few more bits of entropy (see http://mxr.mozilla.org/seamonkey/source/js/src/jsmath.c#366)

So in IE8 a single javaScript method that is executed before the user starts playing can detect the current seed before the page https://bitzino.com/blackjack loads and afterwards, the client_seed is completely useless as an entropy source. The user will never notice the fact the seed is known by the sever.

But the simplest attack in IE8 is to take some Random() values and solve the modular equations to obtain the seed. Since the PRNG (in Firefox and IE8) is a simple linear Congruential Generator (LCG) [ (state*a+b)%(2^48) ] the seed can be recovered by only knowing only two outputs !! No hidden code has to be sent to the user. Only the first two games would be "fair".
The client script itself is providing enough information for the server to cheat the user in the following games!


So, either you allow the user to supply the random via a greasemonkey script or fairness will never be guaranteed.

On the contrary, claiming fairness by using Math.Random() can be taken by the user as a a sign of hidden malicious intentions.

Best regards,
 Sergio.

There are (possibly) two other problems with your protocol:

1) The origin of the code that choses the client_seed:

I haven´t seen the page, but I doubt the user can provide the random seed manually in an edit box.
If not, then the server-sended client-side javaScript code could choose the number in a predictable way, and the user has no way to find it.

A "fake" webpage could be sent with a probability of 1/10, so the user chances of finding it while reviewing the source code is low.

2) The way the client_seed random is chosen:

Again, I haven´t seen the source code of the webpage where the client_seed is chosen. (I haven´t played in your site) but I guess it has some javaScript code that calls Math.random(), which is not cryptographically secure and so it´s predictable.

How do you compute the client_seed ? You should use a CSPRNG, such as the one provided by SJCL namespace sjcl.random (I haven´t tested it myself)

Could you post the source code of the webpage where the client_seed is chosen ?

Best regards,
 Sergio.

Hi Libertaad, nice to meet you!


What you say is only partially true: since Mersenne Twister is not a Cryptographically-Strong Pseudorandom number generator (CSPRNG) there is the possibility that the possible pre-images could be computed to maximize some statistical properties of the Mersenne Twister output. The advantage might be subtle, but it could be done, in theory.
My suggestion is to use a client_seed much longer (say 80 bits) and a CSPRNG.


You are right. But you should tell the user not to accept reloads with changing hashes.


Great! But the problem is that the user has to manually check the shuffles every time. There should be a way to automate the checks, but in a way the the checking code is not sent by the server, but given by the user. An interfase between the web page and a local application.

It was my pleasure.

The protocol was improved since the thesis.. performance is 10x faster now. These improvements are described in a US patent ...

My implementation is not ready to go open source, and must be cleaned up. Also there is the patent issue, so I must find a license compatible with the patent. I will publish the code soon.

The supposed "Provably Fair Shuffling Through Cryptography" https://techblog.bitzino.com/2012-06-30-provably-fair-shuffling-through-cryptography.html leaves much to be desired to be called "Provably fair".

These are only a few reasons:

(1) Client_seed is not big enough (32 bits) to assure a fair statistical distribution. The server can try each possibility in advance...

(2) The server knows the shuffled deck (every card) BEFORE the user, so the server can abort the game (showing any strange error message) if the deck is too good for the user.

(3) Last but not least, the site is HTML5 only (no open source client application), so there is no way to know if the client-side javaScript code is actually verifying anything !!!

(4) Where is the "proof" for the "Provably Fair" algorithm?

The only way to implement secure card games on the Internet is by using Mental Poker protocols (crypto newbies, check it on Wikipedia). And it happens that I designed the fastest MP protocol so far... humbly 


Best regards,
 Sergio.

Let's use sounds (scream, shout, whisper ) or maybe odors....

Good starting point.

We have to add to the levels the required resources needed for the attack. Sometimes it requires very few, some times it requires massive amounts. Also taking down the entire Bitcoin network at once is far worse than remote code execution.

My list would be:

Level 1:
- Take the whole Bitcoin network offline (DoS)
- Steal coins from all or a subset of users at once

Level 2:
- Remote code execution (of single nodes)
- Steal coins from single users

Level 3:
- Slow down or temporally disrupt the Bitcoin network
- Crash a node without further code execution
- DoS single nodes

Level 4:
- Lost of privacy / pseudo-anonymity of single nodes.

DoS single nodes seems equivalent to disrupt the Bitcoin network, since you can prevent users from connecting by taken down each node that accepts connections.
What do you think?

Dear gmaxwell, Graet, and all,
 
 The fact that we do not have a standard to describe how severe a vuln is, is the source of the problem. I consider the vulnerability SERIUS (as any other vulnerability) as Gavin posted. But SERIUS is not the same as SEVERE. I don't consider the vuln severe.

I don't remember having pressed anyone to say the vuln had to be called in any way. I just asked for akwnoledgement!

I tried to establish a severity standard in https://bitcointalk.org/index.php?topic=79830.0
But consensus was not reached.
I think I will formalize it to help the next time a vuln is found.

Nevertheless the page https://en.bitcoin.it/wiki/CVEs describes the vuln perfectly: "Attacker can disable some functionality, for example by crashing clients".

No more, no less.


Best regards!
And thanks Gavin and the dev team for fixing the vuln for the good of all of us.

EXCELENT post etotheipi! At least there is some self-criticism in the community!

This is what I've been saying in so many posts: we are not prepared.

If just one single entity made such a mess, then think about 10 more satoshidices beginning to operate tomorrow.

That's why I designed MAVEPAY. I'n not saying that MAVEPAY is the only solution, but people should start accepting there is a scalability problem.

The first part of this message is not a constructive critic:

Many people (like me) anticipated it: It need just one disruptive use of Bitcoin (like satoshidice) to break the "all nodes are equal premise".

Now the constructive part: four possible solutions exists:

1- SPV nodes / full nodes distinction and related ideas.
2- Balance sheets (breaks compatibility)
3- Add a new transaction format of much sorter length (e.g.: no scripts, use of firstbits) (breaks compatibility)
4- Add a new (less CPU-demanding) signature standard (e.g. MAVEPAY or Merkle-Wintenitz) (breaks compatibility)

Check out the info at https://en.bitcoin.it/wiki/Hardfork_Wishlist (this page is not well cross-linked).

Best regards!