I guess it was kinda pointless to not bother talking about it, a lot of people realized the same thing and amusingly also decided to not brag about it.

Llike the stuff I was proposing in the covenants thread: it feels like it has a lot of danger to be used in powerfully stupid ways that hurt fungibility.

That said...  Say there was change to core blockchain functionality that  51% of the bitcoin owners (however you want to measure it) really wanted... and 49% thoroughly opposed.  I think it would be immoral for the majority to force that onto the minority (if you make the minority small enough, I think this argument fails at some point— but for 49% it holds fine).   And yet, I think it's also wrong (if not immoral— after all, they adopted foo by their own free choice as it was—, just unoptimal and probably not stable) to not give the _majority_ what they want.

I think I've thought situations would be resolved through things like altcoins and gradual market forces. ... if you have foo and you want bar.. you don't _force_ with your majority-clique-power all the foo users to become bar users, you sell your foo and buy bar.  And if both foo and bar are good local design-space minima which are distinct from each other (e.g. I don't think ~any of the altcoins existing have this property) perhaps they'll both happily coexist without one forcing the other out of the market through network effect.

The point being, that it may be ultimately better for foo users if bar exists as part of foo but in a way which minimally disrupts foo, instead of as something wholly distinct. Degrading fungibility is sad, but I don't think its more sad than coercive action by the majority through protocol changes, or more sad than an even greater fungibilty loss switching to an entirely separate system.

So while I certainly wouldn't rush out to create such a thing, I think there is room for us to entertain ideas in this space without feeling that it is abhorrent to the idea of Bitcoin.

::sigh::  If adding the secret to the input were problematic the entire signing function would very likely be insecure: Computing a collision is easier than recovering an unknown pre-image, doubly so because the next thing you do is multiply K by G to get R, which both reduces the space of the output, and makes K unrecoverable from unless you can solve a discrete log problem.

The cost of this is that you produce a device whos correct behavior is not measurable. It could have backdoors inserted in several forms which would be very difficult to discover, or it could have flawed operation.

e.g. if it gets hot there are random bitflips in the multiply used to derive R from K, because the twist of secp256k1 is a smooth field where solving the DLP is relatively easy a single bit-flip in the multiply can result in a R value from which K can be recovered in about 2^51 work.

[Edit: Actually this is incorrect secp256k1 is twist secure, the error there resulted from an apparently transcription error copying down the order of the twist for factoring.  Of course the potential for backdoors in DSA nonce generation are universal and apply to all curves, and to edDSA as well]

Essentially I view this as increasing weakness to these specific but "kind of boring" threats which I can articulate and even show you demonstrations of (e.g. the backdoored signers) in favor or speculatively increasing security against vague cryptographic boogymen, which— if they exist at all— will probably kill us all regardless (by allowing collisions on the data being signed, and thus allowing signature rebinding).


So this doesn't really quite reflect the "defense model" I'm going for. Realistically— whos going to go and do those things?  Even of those people with a million dollars to protect?  Very few.

But not zero, a few geeks are reasonably likely to go splunking around— and I'd think that really any one attempting to be a vendor in this space should even set aside some budget to pay for third party auditing to make _sure_ some external eyes dig in deep.

What I think what would be beneficial for the Bitcoin-using economy is if these few rare instances of crazy, curious, or otherwise motivated adventure seekers somehow protected all of us from badness.   This is what happens with open code: When I review code thoroughly, I'm not just protecting myself: I'm protecting everyone I can communicate with.

The problem with (2) there is that I can't tell if the device was unfaithful to begin with. So if I'm the guy who doesn't trust my device the result is that I get a safe device, but I don't get the ability to sound an alarm to warn anyone else.  In particular, if the device is deterministic, someone who goes in with the logic analyzers can certify the device and document the behavior, then other people can randomly check that their devices measure the documented behavior with far less work.

A compromise in the middle if the device has a display: when signing, show the extra "bonus" randomness on the display. The behavior could still then be completely deterministic (assuming you capture the bonus randomness).. but since the protocol should still be secure against anything by cryptographic boogymen even if the "bonus randomness" is just a constant it should be harmless to display it, you could even send it over USB to the host.  Unless you're worried about boogmen who can invert sha256 and own a camcorder (or, in the latter, and who've hacked your computer).

I hope you don't think I'm ranting at you too much. My replies here are all in the spirit of talking through building the best and most practically secure systems possible— a goal I think we all share.

Mars can have its own altcoin. Politics will likely make having a single blockchain across planets very advisable for a long time to come. Good fences make good neighbors.

And unlike the messy topology of geopolitics on earth, inter-planetary security on the basis of time of flight is pretty trivial.  Earth will never have to fear a blockchain attack by mars or vice versa, if they choose to preclude it.

Each could still transact on the others blockchain, they just couldn't participate in the consensus.

Hm. Why are such weak KDFs supported?  Considering that you can now obtain specialized crackers for bc.i wallets that do ~10m passwords per second on a gpu, I'm a little more concerned about the systemic risk of weak KDFs than I was before.

Which has nothing to do with them working in blocks.  >1 was already non-standard, the other values not being was an omission. Discouraging the casual use of these fields is important for having them be viable upgrade mechanisms: E.g. if in the future the community wants to do a soft-fork to enforce some kind of coin-value-in-scriptsig, say, we'd use a version=2 to trigger making sure the inputs values matched after some height... but we couldn't do that if some implementations were putting random numbers in the version field just for fun.

Always bet on more bugs. I suspect we'll ultimately make the version field unsigned, but I can't say for sure until I've actually gone and done it and seen how disruptive it'll be to the codebase.

The primary reason for the inclusion of the private derivation is that the public one has a weakness which is somewhat surprising to users, and so it's easy for them to screw themselves.  And thats if I give you a watching wallet of mine, and then I later "export" a single private key from that wallet you can go zipping around deriving all the other private keys. (likewise, to anyone who has the extended public key, breaking one private key is like compromising the whole chain)

I think our vague plans are in Bitcoin-QT to primarily use the private derivation, while supporting "reoccurring payment" subchains, and never allowing the export of single private keys inside a "reoccurring payment" subchain (except maybe via a debugging interface with pictures of dragons posted on it).

No. While I prefer people behave in privacy maximizing ways, I think mandating it is unrealistic or at least too risky to be worth the benefit. Fortunately we don't have to.

What you can do is construct N lamport keys, where N is some reasonable number like say 1024 or 8192 (this is super fast, of course, since it's just hashes)... and then your public key is a hashtree over those lamport public keys. And in your signature you just provide the log2(N) additional hashes to connect the particular key you are using.  Alternatively the hashtree could be some other binary tree than a fully populated one, to give you different tradeoffs between reuse amount and signature size.  (google: merkle signature scheme)

The usage is still finite, but it's not just one use.  (and Lamport doesn't become completely insecure if you reuse it, it just starts losing its security... so if you had some extra unsolicited payments past your keys lifetime, it isn't the end of the world.)

Of course, the fact that privacy in Bitcoin calls for minimizing address reuse makes the finite lifetime even less of an issue then it would be in some other cases.

"The system that".

The concept of _deterministic_ wallets is general and works for just about any cryptographic system.  Are you talking specifically about derivation using the "public" type-2 homorphism? That works only with cryptosystems based on trapdoor permutation that have certain properties (the permutation must support composition), and obviously a single derivation chain only works with a single cryptosystem.

If you're asking about BIP32,  BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem.

You are really going to use a system database library for Bitcoin software?  I wish you luck!

Why are you using snappy?  It hurt performance and increased size when it was tested with Bitcoin.

Huh? What do you mean by determinstic wallets there?

I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday.

I'd like to go even further with a new checksig and totally replace the sighash type with the ability to include operators inside the pubkey and/or signature which instruct the node to PUSH various values from the transaction to be signed onto a tagged stack, and then the stack is signed instead of the masked transaction.  This would allow you to do things like "I sign any transaction that pays >=3 BTC to XYZ -- love, pubkey Q", or even just the equal of SIGHASH_SINGLE_AND_ALSO_OUTPUT_N...  but everyone has a pet design, I guess.

Why do you ignore P2SH?  It is the only practical way to actually _deploy_ another cryptosystem... without it you couldn't start using your fooknapsack key until everyone you might want to send you funds updated, and why would they update when you're not using fooknapsack?  P2SH removes the script-type catch22.

Integer F_p systems with acceptable security have pubkey+signature sizes which make merkle/lamport keys look more attractive than by comparison with ECC.

More importantly, you don't mention the validation speed: My laptop can do 7000 RSA verifies per second vs twice that with secp256k1.

They're all based on the effectively the same underlying security assumptions. If we were to support something else out of prudence and paranoia, something orthogonal to the hidden subgroup problem would be good, which is why I would prefer we implement merkle/lamport keys.  They are QC hard, have security assumptions unrelated to those of the DLP/factoring asymmetric crypto, and very fast implementations are trivial (unlike DSA/RSA/ElGamal/Ecc).

By curve25519 I assume Mike means Ed25519 (curve25519 is for ECDH only).  I'm not a big fan of the idea of using it for us (though I'm a big fan of Ed25519 generally): Another fast ECC implementation means another pile of orthogonal highly complicated (probably assembly) ECC validation code that all full nodes will need to have to validate and keep up with the chain.  If we accept the idea that there exists mathematical weaknesses unknown to the public which could be found with enough searching in randomly selected curves, which is the reason for wanting an alternative here, then what reason do we have to believe that Ed25519 doesn't suffer from the same or worse?  Arguably NSA could have known about such weaknesses and _strengthened_ their choices based on that. Reasoning under uncertainty stinks.  The Curve25519 curve also, like our SECP256K1, has some special structure which yields fast implementations... which could ultimately turn out to be a source of weakness.

I would go further to suggest this transaction structure optimization:

OP_CHECKSIG2

If stack.size() < 2: fail

The "public key" is popped.
The "signature" is popped.

If the size of  "public key" <1: fail

mode = publickey[0]&63;

Modes:
0    SECP256k1
1    COMPRESSED LAMPORT
2-63 NOP

If mode is 2-63: return PASS the signature is accepted for forwards compatibility.

hashtype = pubkey[0]>>6;

Hashtypes:
0: HASH160(pubkey)+SHA256
1: SHA256
2: (Some non-nist cryptographic hashfunction)
3: SHA3-512-256

The remainder of the "public key" [1..n] and the signature value are taken to be hashtype hashes of the mode-relevant public key and signature.

The actual public key and signature are not included in the transaction (thus making future proofs over transactions which don't care about the signatures compact) but the data is instead appended to the end of the transaction externally and only included in the transaction hash through the embedded hash. When the public key or signature data is being stored or transmitted, the opcodes in the script could be replaced with placeholder references, so there would be no storage/bandwidth overhead of the indirection, just as there is no overhead from using hashtrees in our blocks.

This would also permit, if we were to choose the degrade the Bitcoin security model slightly, us to declare that once a transaction is "XXX deep" in a chain no node will need verify its signature, and so _no_ node would need to store the signatures older than that point. (XXX perhaps being sum POW equal to two months of the highest difficulty ever seen in that chain). Though this security model reduction does have some moral hazard, as it potentially increases the economic benefits of an enormous rewrite attack. Realistically, I think, XXX can be set high enough that such a rewrite attack would be simply infeasible as manual consensus could resolve it.

The overhead of longer signature schemes would be pure bandwidth, and not long term storage.

Even if we didn't go the full route of drooping old signature data we could use the hash of a block committing to a transaction as the virtual counterparty in a non-interactive cut and choose.  E.g. The block hash randomly tells you which 1/2 of the lamport signature data you can drop... the weaking of the signature offset by the huge computational work of producing a block committing to the whole thing.

Even vs our current compressed EC signatures this CHECKSIG2 operator could halve long term storage signature size.

Old news and fpgaminer is not talking about Dual_EC_DRBG. He's implemented the DRBG based on SHA256.

No, I am not kidding you.  If k==11 then r==11*g, which is even _more_ obvious than r==Q (it's a static comparison instead of a variable one!). Or, if you're into dynamic comparisons... what if k were one of your other private keys?

The distinction with the comparison with zero is that 0 is not a valid point on the curve, so no correct signature can ever have that value. Vs k happening to take on the value of one of your private keys which is just as likely as any other point. If you go around disallowing a bunch of K values then you're decreasing security not increasing it... Though I would agree that this specific test is perhaps mildly useful as a "RNG fatally broken, do not pass go" check.

The procedure described to the public would not discard very many.

The seed is a very large number... so wherever they started from, it wasn't 0.  

It could be that they discarded many while making the curve stronger, not weaker, using unknown criteria. ... or that they hardly discarded any any at all and just used a secure RNG to pick their next seed instead of incrementing, a left over from a less deterministic procedure. It seems that there is no way to tell, and unless it turns out that the values are really just hashed newspaper headlines, it seems unlikely that they could convince the public any which way on the matter.

I knew that that there was heavy NSA influence, at least in the public standards, but after all— NSA has a dual mission, the strengthening security / spying on people... and they likely are the single largest employer of cryptographic mathematicians, so it wouldn't be surprising or unusually concerning.

Ultimately if these curves can be weak based on unknown-to-the-world math, thats bad regardless of tinkering with the parameter selection— and another (actually) random curve could be worse against that kind of threat. But I suppose that there is nothing like postulating a specific attacker to help crystallize the attacks that perhaps we should have worried about all along.

The "protocol specification" page is just some page on the wiki. It has some useful things, but I wouldn't be shocked if it had some flaming errors. (The 'protocol rules' page certainly has some humming omissions).  Right now the version is meaningless: all values should work in blocks.  The issue here is not really uint32 vs int32.

Sure it does. For example, with OpenSSL it would force you to add your own K generation conversion to R and Rinv. In that code you get a free chance to make many mistakes or insert many backdoors.

Assuming your RNG isn't broken you're describing something that will happen at a rate in once in the number of points on the curve... which is true for all K values. You might as well just deny K=11, since if they used 11 (or any other specific value) and you know it you could recover the private key too.

[Edit: Ah, I see iddo pointed this out too]

Once you are already stuck waiting won't help.  Add the -checklevel=2  command-line parameter  or checklevel=2 to bitcoin.conf.

No. The wallet encryption is relatively boring symmetric cryptography. We've intentionally designed it to be slow to inhibit brute-forcing. The fast stuff I'm discussing in this thread is primarily ECDSA signature validation, which must be very fast because all full nodes validate all the transactions.   

After it finishes you should be working, but if you restart again it will fail again until you do the workaround described (or until the triggering transactions are far enough back that they are no longer subject to the startup time double checking).

Please see: https://bitcointalk.org/index.php?topic=290922.0