I think since each block already hashes the prev block we already have that property without doing it explicitly!

There is an argument that it should be using toeplitz hashing with as much data as possible as an input as the entropy extraction, but there is a tradeoff that more "unusual crypto" in the scheme makes it harder to trust.

Yep. The idea is that you lay out all the "influence" parts up front, then use the blockchain to 'cut the deck' in a hard to rig way.

Even if someone didn't personally witness the process they still have the blockchain POW as evidence for a minimum computational cost in retrying. E.g. doing 2^70 blockchain work multiple times to rig it might be conceivable, but not the 2^128 work required to do 2^58 retries.

The next annoying property is that you want to have curve-acceptability tests but too many tests and perhaps you are actually testing for weakness-included. E.g. DJB would perhaps have you test that there exists a specific mapping to nearly uniform scalars (e.g. elegator), but perhaps that guarantees a vulnerability. Or in our case secp256k1 is selected with the efficient endomorphism to permit the GLV method for faster operations.

Well, it is different— say there is a class of weak curves known to the NSA but the weakness requires you to select a one in 2^128 set of parameters... without a pre-image attack on the hash function you couldn't use one of these 'random' procedures to pick such a curve.

If the weakness was a 2^32 one— you could, thus the bada55 curves.

The scheme you suggest has a weakness in that there are potentially too many plausible schemes.  For example, an attacker might use their ability to choose a hash function and value serializations to choose insecure parameters.

What I would prefer is a scheme that worked like this:

(1) Take a scheme like yours, but give it an initialization seed as an input. The scheme should be designed such that all acceptable parameters are equally likely to be selected (assuming good properties of some cryptographic hash).
(2) Publish the scheme, and ask various mutual distrusting parties to compute random values R_0, R_1 ... and each of them publishes X_n = H(R_n).
(3) Take the H(scheme) and X_n and commit to them in a bitcoin transaction, publicly announce this commitment.
(4) 100s blocks after the commitment, take the block hash 100 blocks after the comment and have the parties release their R_x numbers. H(scheme||R_n...||block hash)

The idea here is that up to the preimage resistance of the hash function, to influence the selection you must both compromise all the distrusting parties AND do a huge amount of sha256 computation.

But thats all for where a random selection can't be avoided... the "fixed by security/performance considerations" approach is probably best.  An interesting question how reasonable it would be to formalize all those considerations in order to combine the approaches... since DJB's claims notwithstanding, there really is many degrees of freedom in within that (otherwise secp256k1 _and_ ed25519 wouldn't both exist).

As mentioned in my prior response— if you did this then your proposal is completely ineffective. First you double spend, and then you spend your double-spent coins to yourself.  If you do not also unwind the child transaction then the doublespender walks free for nothing but the cost of an extra transaction. If you do unwind the children then everyone is at constant risk.

Please read the thread. We explain in detail how choice of G is not relevant for our own applications. If you don't believe that, DJB also argues why choice of G is usually irrelevant on safe-curves (SafeCurves does not place restrictions on the choice of this base point. If there is a "weak" base point W allowing easy computations of discrete logarithms, then ECDLP is weak for every base point)— an argument he added after I emailed him and suggested he add an explanation of his own G choice, which he did not previously provide... it took me inventing a novel attack against a contrived hypothetical protocol (not Bitcoin) where choice of G actually mattered to convince him to say anything at all.

I don't believe your post contained a "proposed solution" when I initially responded, if it did— I missed it.

But it's not a solution, alas. Ignoring other issues, at best it still leaves it at a simple piece of extortion "return most of the funds to me or I will reliably destroy your payment". It that sense pretty much isomorphic to "replace by fee scorched earth". The ongoing effort has other problems— a txout can be spent again immediately in the same block. Imagine it takes months to get the fraud notice out (heck, imagine a malicious miner creating one and intentionally withholding it).  By that time perhaps virtually all coins in active circulation are deprived from the conflicted coins. Now they finally get the notice out (/finally stop hiding it). What do you do?  Nothing? Invalidate _everyone's_ coins? Partially invalidate everyone's coins?  Each option is horrible. Do nothing makes the 'fix' ineffective in all cases: the attacker just always sends the coins to themselves in the same block, the others make the failure propagate— potentially forever, and don't just hit the unlucky merchant with the potentially unwise policy.

(It should be noted that already systems reject from their mempool discard later double-spend transactions from their local perspective, because— duh)

Many places, I'll pick an example from myself— (note the log I reference there 12:37 < gmaxwell> pirateat40: you can have 10% of the hash power and attack.)

The bada55 curves were created to show the worthlessness "verifyably random" (at least as done by NIST), they are "random"— but the authors (ab)used the process to make sure the parameters had "bada55" in them. You are supposed to imagine an attacker armed with a mathematical breakthrough who could compromise 1/2^24 random curves doing the same kind of seed grinding.

I didn't believe the post I was responding to was at all talking about the bada55 curves, the subject had drifted and the post was talking about the curves recommended by the site. Presumably if I failed to answer the authors question he could respond.

Huh, the fact that someone with <<50% hashpower can successfully double spend has been repeated many many times on this forum, by dozens of people (including myself), along with comments that mining pools or (especially) vertically integrated closed mining operations with double digit percentages of the hashrate are all concerning, even if its not near 50%. The original Bitcoin whitepaper gives the formal for calculating the success rates.

Unlike the NIST curves the Bitcoin curve is not "random": There is no parameter question there. The comments on the safer curves page addresses a whole host of analysis points, so with the randomness off the table I was speaking to some of the other things where there are meaningful engineering differences between Bitcoin and curve25519.

It most certantly does not.

In any case, many (most?) miners do "regard" fees below some threshold as zero in order to prevent people from jumping the queue just by paying an infinitesimal fee... but they still collect it all the same, they just treat it as zero when prioritizing.

Sure it will. If mining centralization undermines the usefulness and values of Bitcoin people will take action— it's not even a question about bitcoin-core developers (though we're bitcoin users too!), since anyone can offer a modified version... The users of bitcoin are not going to just sit back when something moots the system.

No. Not at all.

Can you review my post again with this in mind. Communication is hard and I take full responsibility for being unclear... but I think I'm going to just repeat myself at this point.  I'll gladly retry if you reread with the assumption that the users do not reuse the session key.

No.

You can send a single message, the concern has nothing to do with _you_ potentially reusing your nonce.

I can intercept your single message, modify it, send it to the receiver. I can take advantage of the receivers misbehavior on receipt of the corrupted message— either doing new things from bitflips (e.g. I guessed what part of your message likely was and twiddled bits), or if garbage messages will make the receiver echo back in plaintext I can use that to recover your one-time pad.

Another way to look at it is that without authentication an attacker can cause multiple messages with the same nonce to exist. It doesn't matter that you didn't create them, the additional messages with the same nonce are potentially problematic none the less.

Not at all. It's actually so easy to implement turing-completeness that we implemented it accidentally in the first OP_EVAL patch and took it out (the recursion limits didn't actually work). The implementation in their demo code on github is (or was, I haven't looked in a while) just basically a replication of bitcoin script with a single JUMP opcode added. It's not uncommon for things to be accidentally turing-complete (using the non-pedantic definition which permits bounded memory or computation time as turing complete (otherwise what ethereum has proposed is not either)).

Now, making a system that won't magically implode into insecurity because almost no one validates it anymore takes more work than this, but it's unclear that anyone knows at all how to solve this if validation is made expensive. None of the things ethereum people have discussed there would be particularly difficult to implement in Bitcoin— and many of the ideas like prefixing scripts with an operation count and weighing fees against them were proposed for Bitcoin long before ethereum existed.

All that said, Turing completeness doesn't actually increase the expressive power of cryptocurrency much— the examples usually given for ethereum can also be accomplished with finite state machines. The primary advantage an actually turing complete machine has appears to be that some problems can have much smaller encodings for them, the primary disadvantage is that someone can give you a script and determining exactly what it can do (e.g. if you'd like to agree to it as a contract) can potentially be much harder than a reduced computation model.

Danger! Will Robinson, Danger!

Say someone were to deploy the simple scheme you described just as you described it—  they they used it to secure queries sent to a simple web server.

I capture a message sent to them that I want to intercept, and I take the nonce out of it— but replace it with a message of my own (perhaps all zeros).

The server responds to me "INVALID REQUEST:  20iE⊥∩θ⊂∏↔θ⊂dlkvc25πδjdk⊕κ×σκk8κσ×3th7hξκδι2λσ∃ΚΣ‡"  ... now I xor with my 'message' and have the session keystream and can decode the message I intercepted.

Even if there isn't some handy error response I can invoke, I can still freely flip bits. "Wait, but if its in a transaction, thats signed right?"— no, I can rebind your message without knowing its content either with or without bitflips into another transaction but reuse the ephemeral key and exploit whatever interesting behavior I can squeeze out of that.

This kind of cryptosystem is often trivially insecure without strong authentication tied strongly to the ephemeral key.

Behold the kind of fun that happens when you don't get every detail just right (start reading at the second message): http://sourceforge.net/p/bitcoin/mailman/bitcoin-development/thread/5325B5BC.3030501@gmx.de/  (A cryptographic disaster (near miss) which started with a thread on this forum very much like this one, but one where more experienced folks happened to not notice it…)

Some people have said this— but the history doesn't really support it. With how fast (and, often, recklessly) various players have moved in the larger economy technical development may seem slow by comparison… but while a stream does not carve a canyon over night, it does so all the same. Someone looking to create a speculative asset boom by copying a bit of other people's code and hopping out weeks later before it busts might honestly say that within the time frames they care about Bitcoin won't adapt... But some are in this for the much longer term possibilities.

All of the curves most preferred on there are ones that DJB made. Some of them have no implementation in software, only the curve25519/ed25519 stuff has any non-trivial deployment at all.

While the analysis there is generally good and thoughtful, I believe that the page crosses the line into being a bit ... uh .. marketing motivated. This has been discussed before several times— e.g. it cites several points which are irrelevant to us (e.g. the elegator encoding), are 'one time costs' completeness making a correct implementation take some more work, and other points which are compensated by increased security of secp256k1 in other respects.  (E.g. the efficient endomorphism for secp256k1 that yields very fast verification for our curve reduces security by a couple bits, which is pretty comparable to the cofactor of 8 in ed25519 that reduces their security by a couple bits (actually slightly more).

Whats implemented in openssl has more or less nothing to do with what bitcoin uses, and getting rid of openssl wouldn't change it.

Hm. Adopting script changes is _trivial_— in fact we've done it before. From a technical perspective P2SH replaced the script system with a copy of itself nested inside a hash.

Really the stuff that is not integrable is things that make economic changes (e.g. freicoin), have very negative scaling impact, or involve very different security assumptions (e.g. trusting a centeralized party).  The biggest barrier so far as been the lack of actual innovation or at least it not being clear if the changes that they make are useful and not totally broken.

There aren't any current alerts for fraud.  The original idea in the paper was a bit immature— the problem is that a DOS attacker could cheaply force SPV nodes into the very expensive operation of fetching the whole blocks.

Subsequently we've come up with some more refined versions of the idea where, with a few additions to the data blocks contain we'd be able to extract compact proofs that a block is invalid, preventing that DOS attack, but they've not been implemented yet.

There are hosted wallets, but the true mobile wallets like "android wallet" use SPV mode see section 8 of the bitcoin whitepaper.  SPV wallets do not trust the nodes they query except for some denial of service/privacy issues, and have basically no storage requirements and very low bandwidth (far below your keyframes), and they do not use a centralized server (they use the bitcoin p2p network). SPV nodes security involves additional assumptions about miner honesty.

What you're describing is a pretty radical change in the security model. In Bitcoin we do not trust the data we are given at all, we verify it. The 'keyframes' you'd send there would need to be trusted, if one bogusly claimed to reassign ownership of a bunch of coin— no one relying on that data could tell (at least not mechanically). Assuming they are mined it would basically be the SPV security assumption set, but less efficient for a mobile wallet (since they'd have to transfer a full 'keyframe').

It's perfectly reasonable to relax the security assumptions for some applications, mobile wallets— for example— but thats why we have SPV mode already.

What it does is removes a differential advantage you'd get from using more complex miner designs that queue and pipeline work better and have more communications bandwidth to minimize latency.