The current known sources of mutability:

OpenSSL will tolerate many different invalid forms of the DER encoding for the signatures. E.g. ones with extra bytes just stuff into the end, or where the values are coded as negative numbers. These are now not relayed or mined by current node versions, but they're still permitted in blocks.

S value can be flipped and still result in a valid signature. This is permitted everwhere with no inhibition and transactions are randomly in one form or another. The next version of Bitcoin-QT will always use the smaller value... but it will likely be years before this is fixed, especially because some client developers may refuse to adopt the canonical behavior.

ScriptSigs can have extra opcodes stuffed into them that do nothing. These are mostly not relayed or mind but they're still permitted in blocks.

ScriptSig pushes can be in non-canonical form. E.g. using a push type that allows larger values than was strictly needed.

We may be able to hasten fixing these things by defining a TX version 2 that has them all enforced and perform a soft fork fairly rapidly.  At least then legacy stuff wouldn't be broken by the fixes.

Please spend some time reviewing and understanding the protocol listed here before commenting on it. If you don't understand what a particular step means, ask about that.

Otherwise you're just a redneck standing on the launch pad saying "This moon launch thing can't work— every rock I've seen thrown comes back down, even if bubba throws it, and bubba is super strong".

The whole idea of this thread is that it resolves the extortion risk you're commenting about. Thats the point. Maybe it fails to actually do that because of some really subtle detail, but people who are not new at this think otherwise.

blah blah. Please read and understand the darn thread first!

Yes. I can't find any evidence of usage which would be imperiled by pointing it out— so:


Bob writes a transaction that pays into some kind of escrow (TxA). Before announcing the transaction (or taking some other irreversible action, like a reveal) Bob asks Alice to sign a locked refund of that transaction (TxB). Alice signs the locked refund, and then Bob announces the escrow payment (or begins the non-reversible action).

Before the escrow payment confirms, however, Alice announces a mutant version of TxA,  TxA' which is TxA but it has the S value in the ECDSA signature replaced by S - secp256k1_order (or one of the many other permissible mutations).  This changes the TXID.  Alice may also have some helpful miners that have agreed to mine the mutant, though this isn't essential.

If TxA' gets mined instead of TxA then TxB will be invalid and so no refund exists.

In the protocol here, you could refuse to reveal until TxA is confirmed. But if Bob broadcasts TxA without a refund already existing, Alice can just walk away and leave bob stuck at that point. "HaHa"

Basically until all forums of mutability in transactions are fixed by blockchain rule no protocol which requires a refund exist before a transaction which can be confirmed is completely safe, because _anyone_ can change the txid of a transaction until its buried in the chain, and child transactions reference parents by TXID.  There are many kinds of mutability, we've been slowly chewing away at some of them by making them non-standard but we're still a long way away from the soft-forks which would start making mutability vulnerable protocols safe.

The video is quite accurate on this point, and note that it does show that there are fees. It then distinguishes the merchant case.

Unfortunately no protocol which requires a blind refund transaction can be completely secure in the Bitcoin network as it exists today.

(The reason may be obvious to you if you think about it for a bit.  I'll gladly describe it, however, if no one else is aware of anyone currently using blind refund transactions right now.)

Luke wasn't the bet moderator, and afaik he was always accurate and factual. The information was available, and the bet moderator could factor it into his decision however he saw fit. So your issue, I think, is with the bet moderator not luke. The emotional "anything that isn't opposed to the communists^wBFL is a communist!^wBFL shill" does more to discredit the complaints about BFL than it does to further them.

Though in the moderator's defense, if it were mean and I called it differently it may well have been in BFL-ships favor. The terms of the bet really did stink, as— I recall— many people pointed out before it closed.

Sure, and you can equally do that balance (making blocks happen below some time a greater portion of the time) just by lowering the time between blocks— without out the cumulative work advantage that creates an expected return increase for larger miners or increasing the proof size.

I always find it gratifying to see all these armchair experts with their "very easy" "improvements" which would hose the security.

We actually need the variation in order to have a decisive consensus. Even ignoring the bandwidth and dos vulnerability that would arise from cumulative work proofs, and the consolidation risks from turning mining into a race... the problem with incremental work POW is that it's not much of a lottery, which means that you'd constantly be losing hash power to orphaning as miners find solutions at very close to the same time.

If this isn't obvious to you after it's pointed out, imagine if instead every miner found a block _exactly_ ten minutes after the last block: Exach miner would have their own chain, none longer than any others... the network split into a zillion separate universes.

Who says they're at the front? Other than thats where the rack ears are mounted it looks like could go either way.  In a lot of facilities its now preferable to have all the cabling on one side in any case.

You need a six dimensions math library.

For curves of particular structure there are simple formulas, but the general case is hard. Fancy math packages just have functions to implement fancy techniques.

There is an overview of techniques in section 5 here: http://cdn.intechopen.com/pdfs/29703/InTech-Elliptic_curve_cryptography_and_point_counting_algorithms.pdf

The optimality testing we can do has exponential confidence with additional testing... so you can be arbitrarily confident. 2^256 is also small enough that you can try factoring numbers to increase your confidence (though you may need to take care to defeat initial primality testing in your factoring software).

(E.g. I successfully factored the order of secp256k1's twist just using the factor command on my Fedora system:
$ time factor 1286578769603068245382716924545379906921918859152521322839515520912848165551
1286578769603068245382716924545379906921918859152521322839515520912848165551: 3 3 3 197 1511 1559 96769 146849 2587814237219 375925338294461779 7427691663837602734654241
real    6m35.889s)


I've seen this paper before.

It's "quite efficient", at least relative to recovering the key the exponential time way by computing the discrete log of the public key, under their assumptions that you've signed messages with either a pair of very small (or large) K values, or a single message with a permitted combination large and small K and signature. The definition of small/large depends which of their cases you're concerned with, but picking one at random, requires (K1 * K2) < (order^(1/2))/6^(3/4).  So e.g. <2^61. The probability of picking a single 256 bit K less than 2^61 is 1e-59. So the probability is negligible even if you sign many times (and I think there were additional constraints as well— it certainly would have been nice if the authors had given concrete figures rather than requiring the readers to fuddle through the math themselves…). (Though I suppose if you want to be extra paranoid you can use this kind of thing as yet another argument for not reusing keys, at if we didn't already have enough). (And even in this case, it's not clear to me that the solution is actually tractable, just exponentially better than the DLP solving way)

You need to set your pesudoshare difficulty to 1 with +1 on the username. This is documented upthread.  ASICminer blades are flawed and works only on difficulty 1 work even when directed otherwise.

Not really, the reasons here are well understood by anyone working on this stuff in detail.

The number is a generalized mersenne prime. The reason for this is that our we are doing calculations in this field so when we multiply we must take the result mod p where p is the size of the field. If p is a freely chosen prime to compute the mod we must divide which is hideously complex. Instead, if P has special form, we can break the larger value at the word level into small fragments and compute the mod p as some sum of them with negations. The performance impact is enormous.

This is just an extension of how it's easier to compute x%16, which can be computed as x&15, then it is to compute x%13.

The reason to use largest prime is just to have the largest field size for one admitting the optimization.

The same reasonable sounding criteria has been used to select primes for many different curves, so it's unlikely that a bad prime was selected and then a complicated explanation was found. The explanation gives a real performance improvement, makes sense, and then was used many times to pick many numbers.

Likewise the efficient endomorphism selection of the a and curve formula permits using the GLV method to speed up point multiplies. This optimization is used by Pieter's libsecp256k1 to make ECDSA verification on x86_64 something like 6x faster than OpenSSL for our curve.

Maybe it turns out that these selections for performance also turn out to select for some weakness. No one knows what unknown math will bring. But the performance benefits are not small, so you don't have to hypothize some rigged process to explain this stuff. (And certainly ECDSA performance is very important to our applications.)  As a side effect, this eliminates all random parameters, save the generator. So thats a great relief for anyone concerned that our parameters were mysterious and could have been rigged via non-public selection.

I have no blinking idea where the generator comes from, but also can't come up with _any_ way it could be an attack even if I assume that our curve has a weakness of every form which I've heard of for discrete log on an abelian variety. The generator is generally irrelevant. You might be able to pick one which permits faster multiplication under some specific multiplication scheme, but I asked Pieter about that and he seemed to believe that it would take a exponentially hard search, so was unlikely to be very useful... I've only bothered expending time thinking about it because I can't figure out why, due to the irrelevance of its specific value, they didn't pick one with a more compact binary representation, and because its the only parameter thats unexplained though it is the only one which there is no real reason to care about.

This isn't to say that the curve selection couldn't be better: Ed25519 is still somewhat faster than Pieter's code. Our parameters pick a curve who's quadratic twist is not of prime order, which means that some optimizations (e.g. the ones used in Ed25519) are not available, and it also means that a single bit error during a multiply (e.g. for doing ECDH) could basically leak the private key. (Basically an off by one in the x coordinate instead gives a value on the twist, and because the twist's order is factorable, the discrete log problem can be solved on it with complexity related to its largest factor, which is only about 2^50). But the ideas behind making curves for high performance which are better in these respects all came after these parameters were selected.

Yep. The reference software (which is to the best of my knoweldge what basically everyone is using) orders w/ fee (e.g. above some minimum threshold) transactions by fee per byte.

Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.

2013-09-16 06:36:03 SetBestChain: new best=0000000000000000004bb6e7e2661661ba9809062d90c3121933d6d02c8bd763  height=258283  log2_work=71.955296  tx=23869863  date=2013-09-16 06:35:37 progress=0.999997

We're pretty lucky now with a 73.75 bit solution on 71.95 in effort.

$100k? Even there, I'd prefer to use procedures to triple check the new outputs in any transactions and attempt to write spends of any resulting change before announcing.

In general it doesn't make sense to make TXouts which are much larger than the transactions you expect to make with them.

The only real arguments against having more txouts are some marginal increase in transaction fees which are irrelevant before you've even reached 100 BTC, and an indirect cap maximum transaction value (in that the 100k relay limit limits you to something on the order of 400 inputs).

It's unclear if you've also forbidden the oracle to have access to some secret data. If so, it's trivial.

If not, then what you really was is a zero-knowledge signature-of-knowledge directly in Bitcoin. We may have one of those someday, but we don't today.

Absent that, if you're able to trust the oracle to continue to exist while you solve the problem, then a zero-knowledge contingent payment might achieve what you're looking for.  (I'm looking for a fun example to use to actually perform one of these transactions, FWIW).

It would be helpful if you'd sketch out what you're trying to achieve without mention of how you think you can achieve it (e.g. no 'oracles'. Just a "Alice wants to send a secret message to bob, but doesn't trust carol." level description).

List of top100 madmen.

One bitflip while making a transaction with these fat txouts and its $10 million in paper value down the drain.

It's really not. When compiled for windows it's a windows program, just one that doesn't use the GUI.
Only if they're not portable. This miner software was primarily developed on x86_64 and most software from the gnu/linux and related ecosystems is highly portable.

uh. You realize you can't have what you want here without building a PKI, right?  I mean, you can make them push a button, but all signatures will pass (except where the attacker is incompetent).

The way signmessage was designed in Bitcoin you have to provide both the message you expect to be signed and the address you expect to have signed it... so that the validation passing isn't just tautological— a ritual that just fulfills itself and always returns true—, but actually means indicates that the user's inputs were consistent.

It helps if you actually understand the use-case for signmessage in Bitcoin-QT:  It's used as an authentication mechanism for services which are address based, e.g. for changing configurations settings on the eligius pool, and it was informed by a number of security exploits against openpgp based systems (e.g. some of the ripe address record databases) which allowed any user to impersonate any other user because gpg --validate would pass on all of them, but there was no way to tell it what user was actually required, so any in your keyring would pass.