ECDSA 2 of 2 signing

[Crowex]

hi,
 After coming across the blind signature protocol in this forum http://oleganza.com/blind-ecdsa-draft-v2.pdf I've designed a 2 of 2 ECDSA signing protocol. It's only suitable for a one time signature. Any feedback is appreciated (thanks andytoshi for some useful pm feedback prior to post)

 https://www.dropbox.com/s/zaxkh0uy7zgavm1/2%20of%202%20ECDSA.pdf?dl=0

 

[jaesyn]

I think you made an error in the following:

3. Alice signs by calculating s2 = c*s1 + d mod p

Should be s2=a*s1 + b, no?

[Crowex]

yes, thanks, that was a typo
I've corrected it

[oleganza]

Very cool to see someone playing with my approach. Haven't checked your paper throughly, but the principle of packing 2 signatures in one is very useful. I was recently thinking about packing 1000s of signatures in one to help with crowdfunding and possibly a majority vote. Maybe it's possible with some more algebraic mumbo-jumbo.

[Crowex]

Very cool to see someone playing with my approach. Haven't checked your paper throughly, but the principle of packing 2 signatures in one is very useful. I was recently thinking about packing 1000s of signatures in one to help with crowdfunding and possibly a majority vote. Maybe it's possible with some more algebraic mumbo-jumbo.

I think my method is OK but there may be some attack I haven't considered.

It's very similar to your approach but for my method I had to add a step to stop someone cheating by declaring a false value for A.

I think it's interesting using the EC maths rather than the bicoin scripting for this type of thing - less problem with wallet compatibility and it works with most alt-currencies too.

The multiple signatures and crowd funding ideas are interesting. I was going to see if I could adapt it to a 2 of 3 signature when I get time.I think this type of thing could be useful in other distributed systems.

[gmaxwell]

Very cool to see someone playing with my approach. Haven't checked your paper throughly, but the principle of packing 2 signatures in one is very useful. I was recently thinking about packing 1000s of signatures in one to help with crowdfunding and possibly a majority vote. Maybe it's possible with some more algebraic mumbo-jumbo.

It's relatively easy to do with schnorr signatures.  It would be a major advance to be able to do this with ECDSA.

I've not worked through the protocol presented here yet... but if it is indeed secure it will also be a major advance.  In CoinSwap there is shown a method where any two party fancy scripted transaction can be made indistinguishable from a 2-of-2 multisig, assuming the transacting parties are honest (if someone cheats the transaction loses its indistinguishably). So the anonymity set of these transactions is the set of 2-of-2 multisig transactions. I'd previously lamented that in schorr signatures single key 2-of-2 is utterly trivial, and these could have an anonymity set of all transactions.

Though it's too early to deploy, I recommend coming up with a patch for libsecp256k1 to do these 2-of-2 key agreement and signing.

[Mike Hearn]

I was under the impression that n-of-m ecdsa was outlined some time ago by this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.9913&rep=rep1&type=pdf

Perhaps I have missed something? Your technique does however appear a lot simpler for the 2-of-2 case specifically, which is often useful for various contract protocols.

[oleganza]

I was under the impression that n-of-m ecdsa was outlined some time ago by this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.9913&rep=rep1&type=pdf

Perhaps I have missed something? Your technique does however appear a lot simpler for the 2-of-2 case specifically, which is often useful for various contract protocols.

Wow, thanks for the paper. I will definitely check it out.

My goal is to implement this idea:

1. People crowdfund a bunch of money for some company.
2. Unlike usual schemes, company cannot use all that money how they want, but only in some pre-determined portions. E.g. when they start crowdfunding, they need a guarantee of $1M, but they will spend first $100K on a prototype, then $300K for initial batch, then if everything is well, for the rest. Crowdfunding contract will take care of putting all money in such buckets so they are not spendable right away.
3. If founders begin spending money not in a way investors like, investors can unlock the funds and get them back to everyone with a majority vote.

TLDR: "If you start fucking with us, we will automatically get most of the cash back".

Alternatively, every chunk of money could be allowed or denied via a majority vote, but that may be too cumbersome. It's probably more efficient to simply allow spending some smaller portions and rescue the rest in case of a problem.

Alternatively (2), crowdfunding process itself can be broken down in independent stages, but that is also cumbersome for the same reason. It's simpler just to crowdfund the total $1M only once, begin the work and then take it back if needed.

[oleganza]

It's relatively easy to do with schnorr signatures.  It would be a major advance to be able to do this with ECDSA.

I don't know much about schnorr signatures. Could you pls show an example why/how it is trivial to do n-of-m in schnorr scheme?

[Crowex]

I was under the impression that n-of-m ecdsa was outlined some time ago by this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.9913&rep=rep1&type=pdf

Perhaps I have missed something? Your technique does however appear a lot simpler for the 2-of-2 case specifically, which is often useful for various contract protocols.

I haven't come across this, it's really interesting.
It looks really useful and you can do multiple signatures corresponding to one public key and threshold signatures.
As far as I can see (if I understand it correctly) the main problem with this scheme for bitcoin applications is that the dealer who initializes the protocol knows the secret key s.
 The dealer distributes shares of the key using a Shamir type secret sharing scheme and then the players (or enough players to meet the threshold) can create nonces and signatures between themselves independently of the dealer. However the dealer could spend the funds corresponding to the public key whenever he wants. I'm not sure if there's a way round this, but there might be.
 I don't know if the Schnorr and other threshold signature schemes work this way but I suspect they will.
 The advantage of the above 2 of 2 method (if there's no mistakes 😊) is that both parties can be sure that nobody knows the secret key since it has been constructed using their secret values. You can only do one signature per address because the secret values create the nonce too but I suppose that will discourage address reuse. 😊

[adam3us]

It's relatively easy to do with schnorr signatures.  It would be a major advance to be able to do this with ECDSA.

I don't know much about schnorr signatures. Could you pls show an example why/how it is trivial to do n-of-m in schnorr scheme?

Well starting with n-of-n Schnorr, the difference is no k^-1 value complicating the math.  DSA is a complexification of Schnorr, probably as an attempt to avoid Schnorr's now expired patent.  Schnorr is simpler, has better security proofs (possible because its simpler) and makes weaker assumptions about the hash function (ie tolerates a weaker hash, or more slips in hash function properties without breaking the signature, aka DSA stresses the hash function more).

The simplicity makes it easier to do blind signatures, and n of n, k of n etc.

Comparing ECDSA and ECSchnorr (with relabeling to highlight similarities):

ECDSA: R=kG, [r=R.x, s=(H(m)+rd)/k], Q=dG verify: sR=?H(m)G+rQ
ECS:     R=kG, [r=R.x, s=k+H(r,m)d],    Q=dG verify: sG=?R+H(r,m)Q
ECS-alternate: R=kG, [c=H(R,m), s=k+cd], Q=dG, verify: c=?H(sG-cQ,m)
(because kG=sG-cQ)

(And both ECDSA and ECS can use deterministic variant where k=H(m,d)).

so with ECS if you have users with pub keys A=aG and B=bG (priv keys a,b) they can make a sig with  their combined key Q=A+B simply as

R1=k1G, r1=R1.x    ->r1
                              <= r2,s2       R2=k2G, r2=R2.x, s2=k2+H(r1+r2,m)b
s1=k1+H(r1+r2,m)a, r=r1+r2, s=s1+s2

as r1+r2=k1G+k2G=(k1+k2)G, s1+s2=(k1+k2)+H(r1+r2,m)(a+b)

QED.  (That was just figured out from scratch, maybe there are some other nuances).  k of n would have to look up or think harder.

So then unlike with the blind ECDSA method you proposed by choosing a public key relating to k, (and I was thinking ok with that you can 2 of 2 most likely, and sure enough https://bitcointalk.org/index.php?topic=511074.0 the OP put that together), with ECS
you can do it more simply and with normally chosen pre-existing keys (and without having to do one-use signatures.)  

A risk with R=kG being fixed that is a one-show signature, meaning if you accidentally (eg due to non transactional storage on the client) sign two different messages, you leak the private key, and allow miners to take your coin.  (Considering one-show signatures, where Q'=(R=kG,Q=dG) so k is pre-committed as a double-spend model ie then you cant double spend without giving both spends to the miners has the same problem with accidental double-spend and transactional client storage requirement to avoid).

Adam

[randomwalker]

I'm part of a research group at Princeton who've been independently working on just this problem.  https://freedom-to-tinker.com/blog/stevenag/new-research-better-wallet-security-for-bitcoin/

We released our research yesterday, and Mike Hearn pointed us to this thread. Great to see that others have been thinking along these lines as well!

We implemented the technique in the Egypt paper as a bitcoinj fork. We're plan to release our code soon.

In addition, we show how to make a threshold deterministic wallet, which is a major improvement in practicality.

The two major use cases we've been thinking about are a business splitting control of a wallet between employees, and two-factor security for personal wallets (as an alternative to Gavin's proposal of a multi-signature two-factor wallet.)

BTW, it's actually straightforward to avoid having a separate "dealer" even with the full-fledged threshold signature protocol.

[Mike Hearn]

I'm implementing HD wallets in bitcoinj at the moment (on a branch). A threshold HD wallet would be a very nice primitive indeed.

[randomwalker]

I'm implementing HD wallets in bitcoinj at the moment (on a branch). A threshold HD wallet would be a very nice primitive indeed.

Cool. To clarify, our construction is threshold deterministic (Section 3.3), but not hierarchical. Maybe threshold HD is possible, but when we thought about it the math got complex and we didn't see a way to make it work in the time we had.

[Crowex]

BTW, it's actually straightforward to avoid having a separate "dealer" even with the full-fledged threshold signature protocol.

Yes, when I first looked at the paper I wondered why they didn't use a no dealer scheme to distribute the private key too, which is how I thought you would get past the problem of the dealer knowing the key. I thought there might have been some security issue but there wasn't.

In the setup phase of your threshold signature generation does the polynomial need to be of degree t not t-1?

 

 


 

[Crowex]

In the setup phase of your threshold signature generation does the polynomial need to be of degree t not t-1?

Ok, sorry, I see you used t to represent a different value than in the original paper.

[adam3us]

Well starting with n-of-n Schnorr, the difference is no k^-1 value complicating the math.  DSA is a complexification of Schnorr, probably as an attempt to avoid Schnorr's now expired patent.  Schnorr is simpler, has better security proofs (possible because its simpler) and makes weaker assumptions about the hash function (ie tolerates a weaker hash, or more slips in hash function properties without breaking the signature, aka DSA stresses the hash function more).

The simplicity makes it easier to do blind signatures, and n of n, k of n etc.

Comparing ECDSA and ECSchnorr (with relabeling to highlight similarities):

ECDSA: R=kG, [r=R.x, s=(H(m)+rd)/k], Q=dG verify: sR=?H(m)G+rQ
ECS:     R=kG, [r=R.x, s=k+H(r,m)d],    Q=dG verify: sG=?R+H(r,m)Q
ECS-alternate: R=kG, [c=H(R,m), s=k+cd], Q=dG, verify: c=?H(sG-cQ,m)
(because kG=sG-cQ)

(And both ECDSA and ECS can use deterministic variant where k=H(m,d)).

so with ECS if you have users with pub keys A=aG and B=bG (priv keys a,b) they can make a sig with  their combined key Q=A+B simply as

R1=k1G, r1=R1.x    ->r1
                              <= r2,s2       R2=k2G, r2=R2.x, s2=k2+H(r1+r2,m)b
s1=k1+H(r1+r2,m)a, r=r1+r2, s=s1+s2

as r1+r2=k1G+k2G=(k1+k2)G, s1+s2=(k1+k2)+H(r1+r2,m)(a+b)

As there was discussion on this topic on twitter I thought I'd update this with how to bootstrap from 2 of 2 to 2 of 3: introduce new signer C

to recap the combined public key Q=A+B
combined private key d=a+b


we will re-split d twice, once by A and once by b:

first A:
1. A choses random r and sets a'=a-r
2. A sends r to B
3. B sets b'=b+r
4. A sends a' to C

(as d=a'+b'=a-r+b+r=a+b, so a',b' is a re-split of d)

similarly B:
5. B choses random r' and sets b"=b-r'
6. B sends r' to A
7. A sets a"=a+r'
8. B sends b" to C

(as d=a"+b"=a-r'+b+r'=a+b, so a",b" is a second re-split of d)

Now any 2 of A,B or C can sign consider the three cases:

A & B: sign with a,b

A & C sign with a",b" (as B sent b" to C, this prevents A signing by itself)

B & C sign with a',b' (as A sent a' to C, this prevents B signing by itself).

This setup pattern scales to other k of n thresholds.

Adam

[Reynaldo]

http://point-at-infinity.org/ssss/

Perhaps Shamir's secret sharing scheme may work to do a m-of-n where m<n for a transaction where you want majority of votes.

Situation:

someone makes a bitcoin address with priv key K
he then proceeds to use SSSS in m-of-n scheme with the private key;
then since you'll need m keys to get the priv key K to spend any funds sent to the bitcoin address.

Problems that arise from this solution:

any not known vulnerability of SSSS
trust is spread at the agent that generated the priv key K

this would really be like a bruteforce, perhaps anyone can find this ideas useful or the SSSS;

my 0.01 BTC

[gmaxwell]

my 0.01 BTC

Might want to consider putting those views on sale, because that price is a little high.

If you take a moment to search you'll see that sort of thing has been discussed before. Not only does it need a trusted setup, but it needs a single trusted point while signing.  It's not completely worthless to split up a key only while stored, but does defeat most of the point, since it basically removes all immunity to malicious hardware or malicious participants.

As far as secret sharing schemes: If constructed right (e.g. using truly random inputs) the scheme has trivially provable information theoretic security (basically if you have threshold - 1 shares, any possible key output can be reached by some possible missing share input). So there is no realistic possibility of "any not know vulnerability"; but a particular implementation could easily be defective in some way-- so you should cite correctly implemented not the sharing itself;  ... really, the greater risk there is thinking that it does something useful for you at all, since due to the aforementioned issues: it likely doesn't.

[mably]

Looks like the original document is not available anymore. 

Do you know where I could find it or something similar?

Thanx for your help.