Can you please help me understand how this would be useful in practice? The amount of tolerated leak is linear in the size of the scriptpubkey. Just giving a party random address also achieves that. Using the homomorphic derivation is attractive for cases where the linear size is not acceptable.

This is explicitly called out in the specification, it is not folkore or a revelation.

Very interesting observation!

Though it's arguably more fragile in one sense that you may think you can release a private key securely but really you cannot because if you leak too much you are broken. It's difficult to write software which will only act a small non-zero number of times e.g. it crashes and forgets that it's already performed one disclosure, certainly the user cannot be counted on to remember such things.  So I think it would be an obvious improvement and might well be worth an increase in the resulting master public key size just for additional robustness, I don't know that in practise it would safely permit intentional use of it.

Your security argument rests on 1MDLP, but we actually use these keys in the context of ECDSA. Inability to solve the DLP (or 1MDLP) does not provably result in the security of ECDSA, and ECDSA reveals another (random) linear relationship with the keys in question; it's concealable that it could undermine the security of the scheme. For example, imagine if the nonce were secrete but constant.  Off the cuff, I do not see a reason that this is problematic for the security of your construction. Though in an abundance of caution we specifically constructed BIP32 to avoid constant any linear relationship out of concern for potential interactions with ECDSA which we were unable to prove did not exist.

Absolutely. The implementation with the wrong signing RNG generating recent discussion was absolutely equally exposed for newly created keys as well.  It's just that the ratio of newly created wallets to signatures from existing ones is low (and perhaps the thefts related to new wallet with bad keys more latent).

Do you actually need to embed the hash or do you just need to commit to it?

If you only need to commit to it you are better of using a pay-to-contract (https://github.com/Blockstream/contracthashtool) or potentially the sign-to-contract (an analog with the contract commitment in the nonce), because the result takes less space (lower transaction fees) and is not easily censorable by miners or tracable to third parties that you don't wish to share the information with.

This is somewhat misleading.

256-bit ECC is normally described to have 2^128 security. But this is in the limit against insanely expensive attacks.

It's also interesting to consider what the chances are of success against an attacker that only does a small amount of work: An attacker who only performs a small amount of computation would have a success rate that reflects a security level similar to 2^256.

As the attacker does more work, their probability of success increases faster than linearly, until success becomes very likely at around 2^128.  It's worth mentioning that with only somewhat more than 2^128 work an attacker breaks almost all keys, not just one, so a very high work factor attacker needs basically only operation on average per key they break.

It works like this because the discrete log breaking is effectively a collision search. You build a huge table of points along a path, and when you find that you've looped back to where you've been before, you know that the table passed through the value you started on, and so you can just walk through it to find your discrete log.  When your table is small unlikely to find a loop. As it grows sufficiently big almost any point you start with joins into a loop and can be used to break any key fast.

Some attackers are perfectly happy to try negative expectation attacks with a low probability of success just in case-- if you've ever typed a sentence from atlas shrugged into some brainwallet site and checked the address, then maybe you were one of those attackers too, having additional security against them isn't bad, and using full entropy keys can help.   That said, I'm sure you could not feel bad at all about using 256 bits of 'untrustworthy randomness' from the computer and then rolling dice for another 128 bits and summing them.

There may also be other attacks on ECDSA if we know that the key is confined to a particular subspace. I'm not aware of any that would be interesting, especially with the data fed into a PRNG, but having a full 256 bits of 'some' kind of entropy probably costs you nothing, and also protects you against things like finding out that popular hex-dice dice were biased and only really had 48 bits of entropy. So why not?

Because, it's lunacy:  The allegation being made (which was after I initially removed the posts, FWIW, when I started removing them there wasn't even that much) is that some decades ago some BFL person ran a BBS in one state, and some BCT user ran some BBS(es) in another state, an activity tens of thousands of people engaged in. And somehow this makes them connected. This just seems like a desperate attempt to draw any connection at all; and it makes the forum dumber for it, because some people have no clue what the words mean, and act like its significant (and as a result makes everyone there look like fools).

I administered BBSes (in Florida, in my case) in the mid 90s. Am I suddenly Josh?!

Sbogovac, you've drank water before, haven't you?!?!?  We all know that Sonny Vleisides was seen drinking water in court.  The connection is CLEAR (I suppose I should go full gauge here and use red text?)!!!!

Witches also drink water. Clearly you are both Sonny _and_ a witch!   Everyone, grab the torches!

If your signing RNG is sufficiently bad your funds can be stolen even if you only ever sign once: If your k some value they've got precomputed in a rainbow table of bad rng outputs they can race you in flight. If your key creation RNG is bad, of course you don't ever have to spend to lose your funds.

Reuse makes it worse-- an RNG with only a couple bits of bias (e.g. using RC4 to generate them) will screw you with enough signatures. And this is indeed a reason "paper wallets" aren't great.  I just wanted to comment to correct the impression that reuse is needed for sufficiently poor rng output to matter. The broken RNG's we've seen (so far!) have mostly been pretty much complete breaks.

As you yourself admitted, the posts had nothing to do with BFL other than by virtue of being posted in that thread.  I did also invite any complaints to come here, rather than to continue offtopic on that thread.

Generally when a thread is going offtopic we'll do a cleanup on the last couple pages to push it back onto the rails. There is no use in cleaning up hundreds of pages of past topic transgressions which no one is reading anymore. Many of the points I removed also had no connection to the (also offtopic) doxing posts.

SaltySpitoon, with due respect: Thanks for your support, but you're also confused. The posts in question were not related to BFL except by virtue of having been (_incorrectly_) posted in a BFL thread, and none of the posts themselves claimed to be related to BFL.  By defending my (very much real) non-connection to and non-motivation to help BFL you're just making it sound like I removed something to the betterment of BFL, which I think cannot be sanely alleged. (Quite the contrary: The mass of inscrutable, unprofessional, and irrelevant rubbish on that thread makes BFL's angry customers look bad and separates them from actual information which could be used to improve their situation).

It's quite likely that I deleted plenty of more borderline material (like the posts with nothing but pictures of chickens) that I might not have deleted as single isolated posts. This is the norm for pushing a thread back on topic. I used a similar approach (periodic aggressive removals) with reasonable success in some of the prior KNC threads.

I agree. But this has nothing to do with the discussion at hand. Cryptic pages of picture of chickens doesn't aid people in recovering their losses, ten pages about people who have nothing to do with BFL beyond having posted in that particular thread, do nothing to aid people recover their losses-- in fact, it does precisely (and I think, intentionally) the opposite.

Thanks for confirming.

Nope.

So your argument here is someone that has, as far as anyone can tell or has alleged, absolutely nothing to do with BFL being harassed with ten pages of nonsense posts is ontopic in a BFL thread because Josh-- a third party-- treated you like shit in the past?  Just making sure I'm clear about your line of thinking, because it doesn't make a lot of sense to me.

Because it had, as far as I can tell or anyone alleged, _NOTHING_ to do with BFL.

How so? None of those posts of ten pages of animated chicken gifs and what not, appeared to make any claim to relevance.  "It's relevant because I harassed someone and had a fun time" is not an argument.

As far as I can tell 90% of this is intentional, controlled topic derailment.  Y'all should be more critical about who you believe is on "your" side and who's been paying them to do what, I would be very surprised if some of the "BFL critics" hadn't been paid off by BFL; their constant lack of ability to conduct themselves professionally only makes everyone whos critical of BFL look stupider by association and the constant noise prevents finding any actual information.

Regardless, keep to the freeking topic. I am tired of the bad behaviour and I am tired of people ignoring requests to cut it out.

(Xian01 tells me that this thread was created because of messages I removed in a thread about BFL)

I don't know and don't care about "dox".  I removed a ton of posts that have absolutely nothing, not even any claim, of having to do with BFL, that were basically making it impossible to find the one in ten posts that were actually about BFL.

For the abstract question ... harassing people is not okay, but there are limits to what can be done about it.

Lambda (mod N) has multiplicative order three, the other value is just lambda applied twice. Unfortunately, it appears is no way to use that for additional speedups because the is no small orthogonal basis that cam be formed from a reduction on [n, lambda, lambda^2].

Absolutely not. The changes in 0.10 you're referring to are exclusively related to signing, as the release notes say, and do not change verification.

Verification in libsecp256k1 on x86_64 is now probably closer to ten times faster than OpenSSL's implementation, but the software is very much still under development. This is without batch validation. True batch validation requires additional side information to have any hope of being faster, and even with it the speed increase is not that enormous due to the additional blinding required to preserve security.

Adding to the excellent points DannyHamilton made,  you're completely ignoring the problem of introducing a new node to the network. If the "genesis block" is rewritten and the history forgotten by everyone-- what basis do they have to judge the new system? You haven't provided a security objective/argument at all for that case. (Fortunately, as DannyHamilton points out, the original Bitcoin whitepaper addresses storage and does so in a way that doesn't make it unclear how a new node can be initialized. And Bitcoin core did 99% of the work to implement that storage reduction a couple years ago, in 0.8, it-- as mentioned-- just hasn't been a priority, due to the -- as mentioned-- linear growth maximum).

If you're feeling that the response here is a bit to blunt you should realize that this proposal (and it's ilk) has been repeated here many times since 2011, seemingly by people who missed section 7 of the white paper and seldom proposing something even as good as the design Bitcoin already has. While it's great that you're enthusiastic and have ideas, when you make a public post you're consuming the time of all the readers and people who respond to you. It's helpful if you describe the research you already did when you first propose something in a community that you're new to, since when someone seems to have missed something obvious (like the whole section on the subject in the project's whitepaper) it gives an impression that the poster didn't care for the costs they imposed on others.

I'm not sure that people actually have much to learn from it; or at least the lesson most learn isn't the lesson they need to learn.

The problem is that the security of cryptosystems can't be assured by following a checklist. Do this. Don't do that.  Do this.  No finite set of instructions is necessary or sufficient for security.

The real lesson is the serious hard work, challenge, public review, testing, and residual risk there is with writing cryptographic software.  When you fixate on the list you feel like you have control of the security.

There is far too much adhoc cryptographic code being written in this community (and beyond) by people who are not putting in the serious effort to make sure it's done right. No matter how awesome a coder you are, no matter how many lists of things to avoid, if you're going it alone your code will not be secure, if you're just following instructions from the forum your code is not going to be secure, etc. Maybe it will be _mostly_ secure, but mostly isn't really good enough.

Put another way, if this thread is alerting you to the concern here then it's very likely that you are not yet prepared to be writing cryptographic software for large numbers of people.

BIP32 hardened is perfectly acceptable to release private keys.  They're indistinguishable from random keys to anyone who doesn't know the master secret.  Fore BIP32 _non-hardened_ IT IS ABSOLUTELY NOT ACCEPTABLE TO PUBLISH THE PRIVATE KEYS. PUBLISHING ONE PRIVATE KEY IS EQUIVALENT TO PUBLISHING ALL OF THEM TO ANYONE WHO CAN GENERATE KEYS.

R.x == 0 is not a point on the curve; but R.x congruent to 0 (mod order) _is_ on the curve, and so r can be zero because r is the x value of R mod the curve order.

(And likewise, s can be zero; e.g. I have a test in libsecp256k1 for s==0:
https://github.com/bitcoin/secp256k1/commit/8d11164bc0e03024d38d5694e81f334ea31ec238#diff-4655d106bf03045a3a50beefc800db21R1210)

What risks are you concerned about?

Just incorrect key generation? Attempt signing with all the keys and verify the results. (Bitcoin core does this internally. And I strongly recommend it, it's a little terrifying that nothing else does. It's too easy to have a bitflip cause the creation of an invalid key, and too easy to defend against)

Poor RNG quality?  Thats harder. Vanitygen allows seperated (point addition) key generation, so you could e.g. generate one key another way and generate all additional ones as that key plus some new random value, in order to have a baseline expectation of security.

Concerned about side-channel (timing, emi, etc.) leakage?

Why is speed a concern? I can understand applications for generating some large number and putting them away... but if the keys are going into a safe what do you care if it takes an hour? How fast does it need to be?

It does not.  In RFCs, requirements are usually specified using all-caps (though not strictly required), and special keywords. See RFC 2119.  It does make a suggestion to do so, but there are often good reasons not to do so; e.g. becuase of application layering, code availability, etc. (also RFC6979 is kind of embarrassingly slow already, mandating it be half again slower in our case would just encourage more people to do ill-formed adhoc things). In this case the suggestion doesn't even appear to be SHOULD level.

It's common for found-on-the-internet ECC crypto-implementations to be pedantically incorrect, and in worse ways than this. Caveat emptor. Virtually none of them that I've seen have evidence of strong peer review, or evidence that their authors have an especially detailed understanding of what they're doing. (Turns out you can implement working, or at least mostly working ECC just by aping some tutorials, which were themselves often written by people new to the subject).

I think being correct in this respect is important, not just in case someone manages to find the p=2^-256 inputs that expose misbehaviour, but also because the same code may later be reused for future curves where the field isn't so insanely close to 2^256, and a failure to implement this correctly can turn into a serious security vulnerability. It's also important to do right because it simplifies review: one can mechanically check each step and not resort to time consuming (and risky!) cryptographic reasoning about the implication of any particular change, the bug (or backdoor) that kills you is the one that looked harmless on the surface.