Bitcoin Forum

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

 :)

I think you made an error in the following:

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

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

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.

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 (https://bitcointalk.org/index.php?topic=321228) 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.

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.

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?

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. 😊

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

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/ (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.

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.

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?

 

 


 

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

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

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

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.

Looks like the original document is not available anymore. 

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

Thanx for your help.

sorry, I've updated the link in the original post so it should work now.
I'll change it from a dropbox link sometime soon so hopefully it won't disappear again.

Ok, thanx.

Sometimes people want the ability to tell which k of n signed (for accountability purposes, if k < n) and there a multisig has additional functionality that schnorr (or other) mulitparty sigs dont.

I did also mention on twitter another idea to use schnorr to make a compact multisg.  The idea is  to have enough different keys per signer to make it unambiguous which k signed, and commit the public key sums for the needed permutations in a merkle tree.  Then to sign reveal the path to the public key sum used and a multiparty sig with that (via the usual schnorr method).

It seems that Micali et al thought of this idea before see http://www.cs.bu.edu/~reyzin/multisig.html (http://www.cs.bu.edu/~reyzin/multisig.html) though the numbers sound better for them as they're assuming prime fields not EC where a hash of a public key is a smaller ratio than in EC.

I expect it wouldnt be too useful to use the bootstap method I mentioned earlier because the subset doing the bootstrapping know everyone elses keys and so could impersonate them for accountability purposes.  So you do need an enrollment process which does not involve third parties knowing parties private keys!

Adam

There seem to be a few possible different approaches to using threshold schemes with bitcoin.

1) Multiparty threshold signatures which are built in to the bitcoin protocol such as P2SH.

2) Threshold signature schemes based on the signature algorithms such as the Schnorr scheme (if Schnorr, hopefully, becomes a part of the bitcoin protocol) and the ECDSA scheme (link in post #8).

3) Secret sharing schemes - the private key is the shared secret.

 (this is just the way I prefer to categorise them)

 The first two methods enable signers above a certain threshold to produce a signature for a transaction.
 
 The secret sharing schemes allow participants above a certain threshold to create the private key.

 In most secret sharing schemes such as the original Shamir scheme there is a dealer who knows the secret and deals out the shares to the participants but there are methods that have no dealer (nobody knows the secret until it is actually reconstructed by enough participants). Clearly having a dealer who knows the ‘secret’ private key is not a good method for bitcoin but if it is a type of no dealer scheme then I think there are situations where there might be reasons for this approach.

 I believe it is very difficult to perform most secure multi-party computations without the participants having direct communication with each other which makes it much more difficult as more participants are introduced.

 As adam3us pointed out the bitcoin multi-sig may have additional functionality in cases where we want to identify signers. However another multi party signature scheme based around the signature algorithm might be more desirable for some other application. Say, for example, if you wanted to design some type of linkable ring signature.
 I suppose that each method must be considered according to it’s application.
 
 In reality nearly all current applications will use the the bitcoin P2SH threshold (multi-sig) method but we have, incidentally, just built a django web app for negotiating the terms of a 2 of 3 escrow type contracts and incorporated a different threshold scheme. For various reasons particular to the simple (2 of 3 escrow) web application we are trying to implement we don’t currently use the signature schemes but use a type of 'shared secret' private key.
 I’ll post the protocol in a separate thread for comments/questions.

I could not find OP's original PDF document.

(All links expired, not found on web archive either)
https://www.dropbox.com/s/zaxkh0uy7zgavm1/2%20of%202%20ECDSA.pdf
https://www.dropbox.com/s/jbvj4awssn5k59n/2%20of%202%20ECDSA.pdf

Does anyone still have the original PDF for upload?
I just want to know contents of the document, so summary is also welcome.
Thanks in advance.

I am studying ECDSA 2 over RSA and run into this topic it seems the link provided is not found anymore