Topic: Why is ECDSA needed at all? (Read 3585 times)

I think we should give this guy a chance and proof him wrong.


You are saying that you would wait for 6 confirmations and then send the private key. However, anyone could just pretend to own the private key while the network cannot verify that you own the private key. This means that it did not matter how many confirmations you have waited as your transactions only becomes worthy once it can be verified (in your case once your private key is revealed).
As such, problems arise which others have described.

Scenario 1:
Mallory sends 1 BTC from Alice address. Mallory is an attacker and actually do not control Alice address (private key) but I can still make the transaction as the pub key is visible e.g. base64decode address. After 6 confirmations Mallory is doing nothing. I suppose in your example you would probably state that the transaction becomes invalid after e.g. 12 transactions without revealing the pubkey, which is fine - no funds are lost for Alice in this example, but way lay the groundwork for the next.

Scenario 2:
Alice sends 1 BTC to Bob (Transaction 1). Transaction 2: Mallory impersonates Alice (can be easily done as per Scenario 1) and send 1 BTC to himself. After 6 confirmations Alice reveals her private key. Meanwhile Mallory established a Man-In-The-Middle between Alice and himself. Mallory does not forward the private key to the network for Transaction 1, instead Mallory will forward the private key of Alice to the network for Transaction 2. Since there is no signing in you scheme this can easily be done. Mallory will continue to block Alice until e.g. 12 transactions as per Scenario 1. After this point all funds are forever lost for Alice.

This sounds really interesting.  Looking forward to see   good luck! 

Use 384-bit hashing, a QC will need 2^192 operations to crack it (subject to P=NP problem).

1) keys are larger but no need to do bunch of one way hashes, just work on the pubkeys and publish those pubkeys. Bloat may be an issue because bandwidth cost is higher but you do get faster signing, so overall you may sync faster.. 20x more per sig for storage and bandwidth costs which sucks, but you don't have the need for change addresses(1 less vout) and other tradeoffs that make end user and integrations much nicer and easier to use. You don't even need to fully spend an input.

2) The Merkle Signature Scheme, which I was advocating for, combines the one-time signature scheme (either Lamport or Winternitz) with a Merkle tree. This allows us to use one public key to sign many messages without worrying about compromising security.  No need for one way hashing scheme to create 160 or even 58 addresses, unless there is analysis to show that the bandwidth cost savings is higher than the cpu and ram usage to do those calculations per tx, based on some metrics.
Ill respond to anonymity later when I have some more time away from coding.

Bitcoin as is is already quantum resistant, its just that its not as nice as it could be with a different signing algo, although at the cost of bandwidth (these are value added tradeoffs in my mind), and since I can see Bitcoin is already going to switch one way or another when NSA does break ECDSA then for me I've already started coding around that assumption in my project by discarding the convention of using one-time addresses only and allowing me to create a fully functional multisig identity system with balances.

Since you bring it up, and folks have been considering, lets look at some of the troubles. 

1)  Keys much larger.  As in 10x or more.  Blockchain bloat will be an issue if the thing becomes popular. 
2)  Lamport signatures are really use-once, because after using it once - the key is basically revealed.  So, what if you want to publish an address for donations?  Is there a way to do this?  Perhaps you could set up a way to sign a group of transactions all at once, consolidating them.  Making sure to change the address that you have published for donations first, of course.  It seems an unsolved problem still. 

Those are the big problems.  A couple of other points:

1) I'm not concerned with quantum computers, Lamport sigs is still an improved security even without that threat.  This is because they are provably as hard to crack as it is to generate a collision in the hash function being used.  ECDSA is not provably as hard as anything, always something that concerns some folks. 

2) Quantum computers allegedly could still provide a route to quicker collision finding in hash functions anyway.  Perhaps not as much of a difference as for Shor' s algo or for ECDSA, but still worth pointing out.       

It is not just bandwidth, but also storage and cache coherency issues for performance. Also the performance advantage declines (is it exponentially?) as bit security increases. So eventually elliptic curves will have no (at least theoretical) resource cost disadvantages. Perhaps the one big advantage right now is (at least hypothetically although I don't know if anyone tried it) servers can employ SHA-256 ASICs for orders-of-magnitude hardware acceleration, and afaik ASICs for elliptic curve cryptography (ECC) are not mass produced.

Winternitz can compress the signatures in exchange for more computation. If the validation server-side it with SHA-256 ASICs (re-purposed Bitcoin mining hardware), it might still be much faster than unaccelerated ECC and with commensurate size at current recommended bit security levels.

However, it might limit compatible hosting for full (validating) nodes of such a design if Bitcoin mining hardware is not a standard offering.

Looking out the future 10 years when bit security levels must increase, perhaps ECC isogenies are ready for real-world usage.


The hash of public key (to create a BTC address) to mitigate any crack on ECC seems reasonably effective, unless it can be cracked in the period of time it takes for your spend transaction to be confirmed. Combined with a Finney attack it might be theoretically vulnerable.


Good point about why discarding public-keys on each spend are important for ECC. I had always thought (without really studying it carefully) it was for recommended for pseudo-anonymity (and perhaps some optimization of representing UXTO?), but your point is also valid.

A speculative counter-argument could posited that given widespread open-source and research sharing in today's Internet world, breakage of ECC is likely to come about in stages and so thus the improvements to ECC, so the risk of actual catastrophy is quite astronomically improbable. In other words, with so many public eyeballs looking at the issues, it is unlikely we will be publicly surprised.

So are you arguing for a persistent public-key or for not employing Merkle, so that each public-key is only (securely) one-time use?


Ah I see you want the persistent public-key for a balances design to avoid the complications of a DAG-like UXTO.

But isn't there another way to make one-time spends more user-friendly wherein the published payto identity remains constant, while the current address is allowed to change. So the spending client needs to access the blockchain before signing to grab the current address for the payto identity. I guess that has a race condition though and thus I am doubting your contention that Bitcoin is aiming for one-time spend address. Rather I think they recommend retiring old publickeys for maximum security, but it is optional right? Perhaps my idea could be combined with Bitcoin's principle for a user friendly automatically secure design. On further contemplation, in an appropriate balances design the payer perhaps doesn't need to reference the current address only the payto identity. The payee can spend from the balance that exists using the current address in the blockchain for that identity. This probably has holistic interactions and ramifications, so needs to be studied carefully. Note this is roughly the design I was implementing when I paused my work to work on a new programming language.


Interesting point that I was not aware of. I don't understand why publishing the hashes of the pub-keys is not sufficient? Are you referring to some cryptographic scheme such as where we blind who signed with a M-of-N ring signature? I haven't studied multi-sig.


Perhaps you could rephrase that summary because I didn't grok it. But i didn't read the linked blog post yet.

Yes.  It looks like OP is suggesting a Lamport Signature coin.  Go and build it please  

There are many reasons why this makes sense... the generation time to create new signatures using Lamport + Merkle is negligent as that is amortized by the client which can afford the extra time for improved security. The signing is up to 10x faster but at the cost of higher bandwidth requirements like Anonymint says. However the upside is favorable as it creates a quantum resistant system that doesn't need a bunch of one way hashing to "work-around" the problem of ECDSA.

Another benefit you get from this is that Bitcoin requires one-time use addresses because those public keys once seen on the network can be used to steal balances by NSA once ECDSA is compromised so all spends with change are sent to new addresses with pubkeys not published yet. Because of this there is lack of usability on services that build upon the transaction creation process. For example in Syscoin I wanted to have an identity system (aliases) that would keep balances like accounts. To avoid mangled code to detect which addresses belong to an alias as change I simply removed the need to create new pubkeys for change and send change back to the alias pubkey which are public on the network. The multisig feature of bitcoin lacks clarity and usability because of the design of bitcoin because pubkeys cannot be published and thus redeemscripts need to be saved and sent across potentially unsafe communication lines...(read my multisig post here: http://syscoin.org/multisignature-identity-system-syscoin-2-1-technical-update/) with aliases I also save a redeem script for multisig alias identities so that any spending can be done without the need to transmit this information to each other (increases usability exponentially). The reasoning behind these changes were that if ECDSA were to be compromised Bitcoin would have a situation where they would probably fork it in as quickly as possible and choose the best implementation... leaving the need for one-time use addresses null and void which would mean my implementation which is one of simplicity actually is the optimal solution. Since I am not a cryptographer I'm not going to bother trying to change the implmentation although it shouldn't be too hard to figure out, just for lack of time to do other work but it makes total sense for long run that either Bitcoin through their new soft-fork voting mechanism or a potential coin supplanting Bitcoin would use something like this to overcome quantum computing.

The rapefugees had a knife to my throat. Sorry.

Or you could use Winternitz (Lamport signatures) with Merkel trees for a more robust solution that doesn't reveal the private key and has roughly 1/20th the resource overhead (not including hardware acceleration of SHA256) of the most efficient (curve25519) elliptic curve cryptography (not factoring in batch mode). But the major downside is the size of signatures increase exponentially with increasing bit security level, which is also the problem with RSA. The theoretical gain is future quantum computing resistance, but research is proceeding on elliptic curve (isogenies) variants which are quantum computing secure.

https://www.imperialviolet.org/2013/07/18/hashsig.html

Pepe thinks you have to make yourself familiar with the difference between

cryptography used for signatures
and
cryptography used for hashes

Those two are very different beasts and not interchangeable.

Something similar to what you proposed can actually work.

It's called MAVEPAY (https://bitslog.wordpress.com/2012/04/16/mavepay-a-new-lightweight-payment-scheme-for-peer-to-peer-currency-networks/), and the signature protocol is called MAVE (https://bitslog.wordpress.com/2012/04/09/mave-digital-signature-protocol-for-massive-bulk-verifications/)

A weaker and later alternative was called FawkesCoin.

I already have an Internet of Things that need internet. Turns out there aren't that many and those that do have lots of processing power because they need to defend themselves from the internet.

Can't recall the name.



It's not needed, you already have a cryptographic hash function and publish SHA3(txData+secret) on the 1st step and reveal the secret on the 2nd when the network verifies that SHA3(secret) matches the spending address.



Probably, depends on an implementation.



Can you imagine, IoT requires a more lightweight algorithms base.

This is a flaw in your assumptions. It is not one directional. The private and public keys are two parts of a puzzle. The puzzle is easy to make but so hard to solve that it is effectively impossible. However there is one exception. There is a shortcut that makes the solving very fast and easy. There is a secret "trap door" that enables bypassing of the impossibly hard route and to open it you need  the right [private] key.

So one gives the public key to anyone that wishes to make a puzzle. Once created only the person that knows the key to the "trap door" can solve it. This is why they are termed "key pairs" since a private and public key are related by the "trap door".

This is the premise behind most cryptography that is based on a "trap door function" and includes Elliptic Curve, RSA and DSA to name the more common ones.

Hopefully you can see that to tell everyone how to open the secret trap door is, in general, not a good idea.

Out of curiosity, which altcoins?

What about the added requirement of a good CSPRNG source for every tx (not required by ECDSA), something which is more difficult to obtain in an isolated IoT environment w/o added (and unauditable) hardware support?

There's also extra non-volatile state which much be maintained to commit the tx, another weak suit of IoT devices in general, correct?

ECDSA isn't that hard, otherwise hardware wallets wouldn't exist....

Yep, with waiting like X confirms, for security (could be specifed by author of transaction), and removing the transaction data if private key is not revealed after X+Y confirmations, where X=Y.

Nodes could block clients that do malicious things (banlist already avalaible in bitcoin too), while the blockchain would remove unconfirmed transaction.

The TX would just be a 2 step process instead of one.

I'd imagine a private blockchain would use something like this, especially if only trusted nodes exist.

Your idea is not worthless and is already used in one of the altcoins. It's actually a nice solution for IoT-friendly cryptography for which ECDSA is too "heavy". The only requirements are to wait long enough between beginning and committing a transaction and to not reuse addresses (private keys).

Just chill out man, no need to be rude.

If my idea is worthless, then it strengthens the point why ECDSA is needed, and people will apreciate ECDSA more.

If my idea has some worth then it could give ideas for developers to create a system like I described, perhaps as a side-chain.

Either case, it is worth discussing this in my opinion, discussing things is never wrong, no matter what is the outcome, people will come out as winners because knowledge will be shared.