A question on ECDSA signing (more efficient tx signing)?

[DeathAndTaxes]

Bitcoin signs each of the inputs for tx with a separate signature.  This adds significant size to the overall transaction size. The size of the most common Bitcoin tx can be computed as the following:

Size (in bytes) = 10+147*NumIn+34*NumOut

This applies to tx with standard outputs, scripts of less than 256 bytes each, and all inputs use compressed public keys.  If the public key for the input is uncompressed the size is 32 bytes larger.

The largest portion of a balanced (number of inputs and outputs are equal) comes from the input portion and the largest component of the input is the signature which is 72 bytes with encoding.  If we assume the average tx consists of two inputs and two outputs that makes the average tx size 368 bytes.  Roughly 39% of that or 144 bytes is from the two signatures for the two inputs.  However a tx is only valid if all the signatures are valid.

Is it necessary to store each signature separately?
Is there some ECDSA operation which could allow verification that data was signed by multiple private keys with a single signature and multiple public keys?

Given:
private keys a & b
Public keys A & B
Data to be signed d

Is it possible to create a signature S such that it can be verified given only A, B, and d?

[etotheipi]

Even if there is, a different piece of data is being signed for each input/key.  i.e. "Data to be signed, d" in your question above is not consistent.  Look up OP_CHECKSIG for details.

[DeathAndTaxes]

Even if there is, a different piece of data is being signed for each input/key.  i.e. "Data to be signed, d" in your question above is not consistent.  Look up OP_CHECKSIG for details.

This would be an incompatible break, and I harbor no illusions it would ever be used for Bitcoin.  Lets consider this mostly theoretical possibly for some future altcoin.  The transaction structure would not necessarily need or be the same.  You can assume the d is the same for all inputs.  One method would be that the entire tx is signed (all inputs, all outputs) but the exact structure is not that important.

Doing a little more research I believe it is possible to use elliptic-curve arithmetic to add the private keys together to create a "master" private key for signing and this master private key can be verified by adding the public keys together to form a master public key.

I was going to do some testing with OpenSSL but I need some sleep.

[gmaxwell]

Some ECC signing systems can do grouping operations where you can compose all the keys and all the data being signed and validate the whole thing with negligible probability of accepting if any were invalid and zero possibility of rejecting if all were valid.  But AFAIK ECDSA is not such a scheme, and the ones I know of have larger signatures. (uh, though if you were to use it to always merge all the signatures in a block— that might be interesting).

Maybe you were already suggesting it but its certainly possible to— in a single transaction— expose a bunch of public keys, compose them, and sign with the composition. This is what you get with type-2 deterministic wallets, or vanitypooling, effectively.  But the space reduction is reduced by the need to expose the public keys... and it would make taint analysis more potent because you multiple parties cannot securely sign in that model. It's also incompatible with sighash single. If you wanted an incompatible ECC specific change— you could instead add public key recovery. This would get similar space savings, but also save on transactions with a single input while not breaking the ability to confuse taint analysis with joint transactions, or breaking alternative sighashes.

More philosophically, privileging a particular asymmetric cryptosystem in Bitcoin is probably not a grand idea.   We have this fantastic flexible signature system where signing criteria are programs not just a fixed asymmetric operator. It's worth taking some extra cost in order to keep that flexibility on equal footing.  It also may well be the case that we become concerned about the security of ECDSA in the future (e.g. practical very large QCs make ECDSA unacceptably weak).  The obvious alternatives do not obviously support such mathmatical fun.

One thing that I do sometimes wish is that transactions were themselves hash trees internally.  It would be very nice to be able to give to someone all the data they need to build a current UTXO securely (and thus also verify that there is no permitted inflation in the chain) without sending them a bunch of deeply burred signature data which isn't personally interesting to them and which they believe has adequate hashpower security to only do randomized spot checks.

[Etlase2]

Aggregate and Verifiably Encrypted Signatures from Bilinear Maps - Boneh et al

An aggregate signature scheme is a digital signature that supports aggregation: Given n
signatures on n distinct messages from n distinct users, it is possible to aggregate all these
signatures into a single short signature. This single signature (and the n original messages)
will convince the verifier that the n users did indeed sign the n original messages (i.e., user i
signed message Mi for i = 1; : : : ; n).


Don't know about ECDSA, but bilinear map-based signature schemes are all the rage these days...

[grich]

bilinear map-based signature schemes are all the rage these days...

Only in academic papers

[Atruk]

bilinear map-based signature schemes are all the rage these days...

Only in academic papers

Pretty much. Give them roughly a decade for a trusted implementation to emerge.

[DeathAndTaxes]

Some ECC signing systems can do grouping operations where you can compose all the keys and all the data being signed and validate the whole thing with negligible probability of accepting if any were invalid and zero possibility of rejecting if all were valid.  But AFAIK ECDSA is not such a scheme, and the ones I know of have larger signatures. (uh, though if you were to use it to always merge all the signatures in a block— that might be interesting).

Maybe we are speaking of different things but doesn't ECDSA allow creating a composite key by simply adding the two private keys together.   The signature (which would be the same size as the individual keys) can be verified by completing the same ECC arithmetic on the public keys.  For example say a hypothetical transaction (not in Bitcoin network and not necessarily in the same format) has the following information in the transaction.  At this point the format/structure isn't really important.

Transaction Body:
Version
NumInputs
ArrayOfInputs[]
NumOutputs
ArrayOfOutputs[]

Each Input is in the following format:
PrevTxHash
PrevTxIndex
PubKey

So far this is very similar to Bitcoin however there are no scripts in the tx inputs.  Each input simply consists of the information necessary to identify and authenticate it (tx id, index, and public key).  At this point lets ignore the format of the outputs as it isn't particularly important for this discussion.  Now unlike Bitcoin where each input has a signature (the simplified tx is signed w/ private key corresponding to the pubkey listed for the input) could we instead have a single signature for the entire transaction.  Also lets ignore coinbase/generation tx for the moment.

So for a transaction with more than one public key in the inputs we first create a composite key by performing ECC arithmetic.  Lets call the composite key the tx key.  We would take a list of the inputs, remove the duplicate private keys and create the tx key by adding the private keys together.

tx.privkey = privkey[0] + privkey[1] + ... privkey[2]

Then we sign the entire tx once with the tx key.    The single tx signature would be appended to the tx.

Version
NumInputs
ArrayOfInputs[]
NumOutputs
ArrayOfOutputs[]
Signature


To validate we would take the list of inputs, remove duplicate pubkeys, and create a composite in the same manner as the privkeys.

tx.pubkey = pubkey[0] + pubkey[1] + ... pubkey[2]

The tx (composite) pubkey will validate the signature created by the tx (composite) privkey.

This method would be more limiting than the Bitcoin script system however it would (with a few other changes) result in an up to 50% savings in terms of bandwidth and storage requirements.  The computing power requirements should be roughly the same.  Given that over 99%+ of the transactions to date on the Bitcoin network are "standard" pay to pubkeyhash we are sizable savings.  With the use of versioning other more advanced tx would still be possible so it would be possible for an alternative crypto-currency to have the best of both worlds.  For "simple" transactions a significant reduction in resource requirements while still having the ability to create more complex transactions.

Is there any security risk to a format like this?  Any reduction in key strength?  I can't seem to find anything that would indicate it is the case but this really isn't my area of expertise.

... its certainly possible to— in a single transaction— expose a bunch of public keys, compose them, and sign with the composition. But the space reduction is reduced by the need to expose the public keys... and it would make taint analysis more potent because you multiple parties cannot securely sign in that model. It's also incompatible with sighash single. If you wanted an incompatible ECC specific change— you could instead add public key recovery. This would get similar space savings, but also save on transactions with a single input while not breaking the ability to confuse taint analysis with joint transactions, or breaking alternative sighashes.

I assume by "compose" you mean ECC addition of the private keys (as well as a separate ECC addition of the pubkeys). Right?  I agree there is a need for public key for each input to validate the signature however the signature is significantly larger.  For Bitcoin the pubkey is 34 bytes for compressed pubkey (66 bytes for uncompressed pubkeys).  An alternative CC could simply mandate the use of compressed public keys in the protocol.  The signature is 72 bytes.

Bitcoin Tx Input Format
TxOutHash - 32 bytes
TxOutIndex - 4 bytes
ScriptLength - variable (1-9 bytes, 1 most common)
Signature - 72 bytes (including encoding)
PubKey - 34 bytes (compressed keys)
Sequence - 4 bytes
Total: 147 bytes (Signature is 48% of Input size)

and it would make taint analysis more potent because you multiple parties cannot securely sign in that model. It's also incompatible with sighash single.

Agreed.

If you wanted an incompatible ECC specific change— you could instead add public key recovery. This would get similar space savings, but also save on transactions with a single input ...

Interesting.  Can you provide information or reference on public key recovery?

One thing that I do sometimes wish is that transactions were themselves hash trees internally.  It would be very nice to be able to give to someone all the data they need to build a current UTXO securely (and thus also verify that there is no permitted inflation in the chain) without sending them a bunch of deeply burred signature data which isn't personally interesting to them and which they believe has adequate hashpower security to only do randomized spot checks.

I read this a couple of times and still couldn't conceptualize how hash tree in transaction would add security.  I bookmarked it though.

[poiuytr4]

Given:
private keys a & b
Public keys A & B
Data to be signed d

Is it possible to create a signature S such that it can be verified given only A, B, and d?

Why not sign the data d with private key a and then sign the result with private key b to give you S.
Use public key B then public key A on S to result in data d.

Would this solve the original problem?
Even though, as pointed out, there are distinct items of data so it wouldn't work in practice anyway.

[DeathAndTaxes]

Given:
private keys a & b
Public keys A & B
Data to be signed d

Is it possible to create a signature S such that it can be verified given only A, B, and d?

Why not sign the data d with private key a and then sign the result with private key b to give you S.
Use public key B then public key A on S to result in data d.

Would this solve the original problem?
Even though, as pointed out, there are distinct items of data so it wouldn't work in practice anyway.

This would be for a new (incompatible) transaction format.  There would be no distinct items.  Transactions would simply be signed at the tx level.  At this point it is merely academic, I just want to know if it CAN be done and if doing so results in a reduction of security.

I don't believe it is possible to verify a double signature the way you described.  Remember is verification the entity with the public key isn't recreating the signature and comparing it to the original (if they could do that they could counterfeit the signature on any data).  They entity doing the verification can only validate if the signature is valid or not (i.e. true or false).  

I may be wrong on this one.

[poiuytr4]

Given:
private keys a & b
Public keys A & B
Data to be signed d

Is it possible to create a signature S such that it can be verified given only A, B, and d?

Why not sign the data d with private key a and then sign the result with private key b to give you S.
Use public key B then public key A on S to result in data d.

Would this solve the original problem?
Even though, as pointed out, there are distinct items of data so it wouldn't work in practice anyway.

This would be for a new (incompatible) transaction format.  There would be no distinct items.  Transactions would simply ONLY be signed at the tx level.

I don't believe it is possible to verify a double signature the way you described.  Remember is verification the entity with the public key isn't recreating the signature and comparing it to the original (if they could do that they could counterfeit the signature on any data).  They entity doing the verification can only validate if the signature is valid or not (i.e. true or false). 

I'm pretty sure that this would work to do what you originally described. Basically a private key is used with a random number to encrypt (sign) some data and the public key is used to decrypt (check signature). All I was suggesting was sign (encrypt) the data with private key A then sign (encrypt) the result with private key B.
 To check just decrypt with public key B then decrypt with public key A. They are really just one way functions.
I'm not sure that you can do what you described above. i.e. you can't just add a lot of private keys, sign a message and then add up the corresponding public keys and use this to check the signature (if that is what you meant) even if you are using EC point addition. I'll have to have a look when I'm more awake (sober) 
 

[DeathAndTaxes]

I'm not sure that you can do what you described above. i.e. you can't just add a lot of private keys, sign a message and then add up the corresponding public keys and use this to check the signature (if that is what you meant) even if you are using EC point addition. I'll have to have a look when I'm more awake (sober) 

No problem. I am sure it can be done.  It is used for deterministic wallets for example and it for verifiable secure vanity address generation.  It is an interesting property of ECC keys.  I just wanted to know if any crypto experts saw any potential reduction in security as I have limited knowledge in the field of ECC.  Unless I was drunk I don't recall it even being covered in college.

You may be right about signing and verifying in the method you described.  I will try some experiments with OpenSSL.  My assumption would be that if both are possible that given n keys that n key additions plus one signature (or verification) would be faster than n signings (or verification).

[blueadept]

One thing that I do sometimes wish is that transactions were themselves hash trees internally.  It would be very nice to be able to give to someone all the data they need to build a current UTXO securely (and thus also verify that there is no permitted inflation in the chain) without sending them a bunch of deeply burred signature data which isn't personally interesting to them and which they believe has adequate hashpower security to only do randomized spot checks.

I read this a couple of times and still couldn't conceptualize how hash tree in transaction would add security.  I bookmarked it though.

I've been wishing this myself; it would permit a specific use case in which I'm interested: contract setup.  As an example, in BitcoinJ's payment channels, the setup method doesn't provide for a risk deposit from the sender.  With the current method of generating a txid, one party has to have the entire setup transaction in order to generate the TXID in order to reference it in the refund transaction.  This means that if the server put up a risk deposit, it would be at risk of losing that money permanently (at an expense to the client, to be sure, but it would permit DDoS against a server by multiple parties attempting to put it out of business by collectively throwing away their own money).

With input scripts signing a hash tree, both sides could have the hash used for the TXID prior to signing the setup transaction, so they could collaboratively sign the refund transaction before even signing, much less sharing the signatures of, the setup transaction.  This would also alleviate the issue with TXID malleability, where nodes or miners can add things to the input scripts and change the TXID without changing the validity of the transaction.

In addition, it would permit the replacement of the SIGHASH flags with an array of hashes that must be in the transaction's hash tree.  This would allow inputs to sign any parts of the transaction that are important to them, and ignore the rest.  For example, assume that there are two hash trees that are subtrees - hashes of inputs in one hash subtree and hashes of outputs in the other hash subtree.

SIGHASH_ALL = root hash of full hash tree
SIGHASH_ALL | SIGHASH_ANYONECANPAY = hash of own input, root hash of outputs subtree
SIGHASH_SINGLE | SIGHASH_ANYONECANPAY = hash of own input, hash of output you care about (but more flexible because you can ensure ALL the outputs you care about are in there)
SIGHASH_NONE = root hash of inputs subtree
SIGHASH_NONE | SIGHASH_ANYONECANPAY = empty list

The bad part is there's no direct analog for SIGHASH_SINGLE (EDIT: due to the blanking of the sequence numbers in the inputs) but I imagine for most (EDIT: or at least some) use cases, it's not any more useful without SIGHASH_ANYONECANPAY than it is with that flag.  The better part is, the replacement for SIGHASH_SINGLE | SIGHASH_ANYONECANPAY permits you to sign a contract output and a change output at the same time from all of your inputs.  This permits use for situations where you have a different number of inputs from your number of outputs, or you want to avoid having some of your outputs stolen when using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY.  It would definitely make things easier for micropayment channel contracts with more than two parties.

EDIT: The lack of pure SIGHASH_SINGLE support could be alleviated by making each input's hash actually a hash tree of its own:  a hash of the input exclusive of sequence number, and the sequence number itself.  That way, you could list the hash of the input inclusive of OR exclusive of the sequence number depending on what you care about.

[poiuytr4]

No problem. I am sure it can be done.  It is used for deterministic wallets for example and it for verifiable secure vanity address generation.  It is an interesting property of ECC keys.  I just wanted to know if any crypto experts saw any potential reduction in security as I have limited knowledge in the field of ECC.  Unless I was drunk I don't recall it even being covered in college.

Yes, you are right. But the private keys are scalar quantities so you just use add these using normal addition and, technically you should reduce mod n, where n is the order.
 The public keys are EC points so you add these using point addition.
 I think the vanity address programs often do the same sort of thing but multiply all of the private addresses, which in this case are partial keys (so that the vanity address calculator doesn't end up knowing your private key). This is computationally more efficient.
 The result is just as secure.

[gmaxwell]

Maybe we are speaking of different things but doesn't ECDSA allow creating a composite key by simply adding the two private keys together.

Yes, I was speaking of something different there. Batch verification.  I went on to talk about creating a third key from two other though, which can be done but suffers some of the limitations I mentioned.

Is there any security risk to a format like this?  Any reduction in key strength?  I can't seem to find anything that would indicate it is the case but this really isn't my area of expertise.

I'm not aware of any security harm from doing it.

Interesting.  Can you provide information or reference on public key recovery?

If you have a signature and the message it signed and two disambiguation bits you can recover public key used. This saves you from having to transmit the public keys.  We use this today for bitcoin signmessage.

I read this a couple of times and still couldn't conceptualize how hash tree in transaction would add security.  I bookmarked it though.

It would not _add_ security, what it would permit is more flexible security / computation / bandwidth tradeoffs without compromising security.

A simple example:  Say you are an SPV node. A full node tells you about a transaction paying you which is in a block.  You really don't give a @#$@@ about the _whole_ transaction, what you really want is proof that a particular txout is in that block.  Today the full node must send you the full transaction— along with all of its potentially bloated scriptsigs which you can't verify (lacking the inputs) and don't care about and all the other outputs that don't pay you.  If the transaction was internally tree structured you could request only the data of interest and still receive proof that that data was committed in the block in question.

[DeathAndTaxes]

Is there any security risk to a format like this?  Any reduction in key strength?  I can't seem to find anything that would indicate it is the case but this really isn't my area of expertise.

I'm not aware of any security harm from doing it.

Thank you.

Interesting.  Can you provide information or reference on public key recovery?

If you have a signature and the message it signed and two disambiguation bits you can recover public key used. This saves you from having to transmit the public keys.  We use this today for bitcoin signmessage.

Interesting.  I need to look into that.   So when the original message & signature are known once can reconstruct the public key.  So why does Bitcoin include the public key in the tx input?  Is there a good reason or was it simply due to lack of understanding on how key recovery could be used.  If I understand you correctly like in current Bitcoin tx each input would need to be signed the public key could be recovered.  This would mean the same 72 bytes per input but the eliminate of 34 pubkey bytes per input.  Makes smaller 1 input tx but larger multi-input tx compared to composite key but is still always smaller than "Bitcoin today".

Code:

Comparison of of the size of required pubkeys & signature(s) in bytes, where n = number of inputs.
Bitcoin Today = (72 + 34)*n
Tx Key = 34*n + 72
PubKey Recovery (bytes) = 72*n

One question: What do you mean by "two disambiguation bits"?

It would not _add_ security, what it would permit is more flexible security / computation / bandwidth tradeoffs without compromising security. A simple example:  Say you are an SPV node.  ... If the transaction was internally tree structured you could request only the data of interest and still receive proof that that data was committed in the block in question.

Interesting.  Thanks again for your detailed knowledge.  Got me thinking of a lot of alternatives.

[gmaxwell]

Interesting.  I need to look into that.   So when the original message & signature are known once can reconstruct the public key.  So why does Bitcoin include the public key in the tx input?

Because when Bitcoin was written Satoshi didn't know this. It's also somewhat slower to do it that way, though the space saving is great enough that I believe it's a pretty clear win.  Also, your composed key stuff requires accumulation of the ECC points, so it's not entirely free either.

Makes smaller 1 input tx but larger multi-input tx compared to composite key but is still always smaller than "Bitcoin today".
One question: What do you mean by "two disambiguation bits"?

Quite literally: two bits to disambiguate the multiple possible public keys. The validator could perform the recovery multiple times but that would be quite slow. It's needed for the same reason a compressed public key needs an extra bit to encode the 'sign' of the y coordinate.

Right, it wouldn't be as small as the composed keys but it also wouldn't have the other downsides: privileging ECDSA, making common ownership deanonymization attacks more powerful, goofing up sighash single, breaking the independence of inputs.

If you were willing to do the composed-key signing— you could instead have just used one address, or some address type that used a common ecdsa public key plus a sequence number (e.g. to disambiguate payments).  Then you'd just have an optimization that could aggregate multiple signings under the same key in a transaction into a single one.  ... though I'm also not keen on privileging address reuse.

[Ari]

So the question is...  Is it possible to have a single signature that requires two public keys to create it?

ECDSA is based on ElGamal signatures.  There are several variants, but let's just consider the basic signature scheme:

Given:

Generator g
Private key x
Public key y=g^x
Message m

A signature (r,s) on message m is valid if g^m = y^r * r^s

As gmaxwell points out, it is possible to compute y (public key) from the signature and message as y=(g^m/r^s)^(1/r).  To validate the signature, you would of course have to check that this public key is the one you expected.

It seems possible to make a signature from two public keys A and B, such that g^m = (A*B)^r * r^s

Obviously this would be incompatible with the current bitcoin protocol, but it does seem possible in theory.  I'm not entirely sure of the security implications of such signatures.  I'd have to think about it some more.

[Ari]

So actually this won't work.  An attacker can just add an input with a public key that is the multiplicative inverse of your public key.

So if A = y and B = (1/y) the signature is verified as:

g^m = (A*B)^r * r^s
g^m = (y/y)^r * r^s    
g^m = 1^r * r^s    
g^m = r^s

which is trivially forged.

Doing a little more research I believe it is possible to use elliptic-curve arithmetic to add the private keys together to create a "master" private key for signing and this master private key can be verified by adding the public keys together to form a master public key.

And in elliptic curve arithmetic, you add the inverse, yielding the identity element.  An attacker can then add their own public key to avoid the point at infinity.  The combined "master" public key is insecure.  So this doesn't work.          

[Sergio_Demian_Lerner]

If you were willing to do the composed-key signing— you could instead have just used one address, or some address type that used a common ecdsa public key plus a sequence number (e.g. to disambiguate payments).  Then you'd just have an optimization that could aggregate multiple signings under the same key in a transaction into a single one.  ... though I'm also not keen on privileging address reuse.

If you're willing yo sacrifice privacy, then adding an extra OP_CODESEPARATOR to the previous outputs scriptpubs will allow you to re-use the same signature over and over withing a transaction that uses many inputs sent for the same address. Clients will not verify the same signature many times due to the cache, so both the signer and the verifiers have a performance gain.

To make it work in the standard client you have two options:
1. Sender adds a trailing OP_CODESEPARATOR  to the script (this is non-standard tx) and must be sent directly to the miner.
2. You create a P2SH address of the script containing the trailing OP_CODESEPARATOR. To redeem the funds you will require to send the transaction directly to a miner, since it will be non-standard.

This is obviously an unintended use of OP_CODESEPARATOR, and I discourage to use this of method, but I think it works.