
jaesyn
Newbie
Offline
Activity: 10
Merit: 1


March 12, 2014, 06:19:25 AM 

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 (OP)
Member
Offline
Activity: 111
Merit: 10


March 12, 2014, 08:32:06 AM 

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




oleganza
Full Member
Offline
Activity: 200
Merit: 104
Software design and user experience.


March 12, 2014, 11:20:20 AM 

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

Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo



Crowex (OP)
Member
Offline
Activity: 111
Merit: 10


March 12, 2014, 12:53:04 PM 

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 mumbojumbo.
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 altcurrencies 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
Moderator
Legendary
Offline
Activity: 4214
Merit: 8516


March 12, 2014, 03:48:30 PM Last edit: March 12, 2014, 04:02:16 PM by 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 mumbojumbo.
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 2of2 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 2of2 multisig transactions. I'd previously lamented that in schorr signatures single key 2of2 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 2of2 key agreement and signing.





oleganza
Full Member
Offline
Activity: 200
Merit: 104
Software design and user experience.


March 12, 2014, 05:28:51 PM 

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

Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo



oleganza
Full Member
Offline
Activity: 200
Merit: 104
Software design and user experience.


March 12, 2014, 05:30:59 PM 

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 nofm in schnorr scheme?

Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo



Crowex (OP)
Member
Offline
Activity: 111
Merit: 10


March 12, 2014, 10:22:15 PM 

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


March 16, 2014, 01:34:00 PM Last edit: September 28, 2014, 01:53:32 AM by 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 nofm in schnorr scheme? Well starting with nofn 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 ECSalternate: R=kG, [c=H(R,m), s=k+cd], Q=dG, verify: c=?H(sGcQ,m) (because kG=sGcQ) (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 preexisting keys (and without having to do oneuse signatures.) A risk with R=kG being fixed that is a oneshow 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 oneshow signatures, where Q'=(R=kG,Q=dG) so k is precommitted as a doublespend model ie then you cant double spend without giving both spends to the miners has the same problem with accidental doublespend and transactional client storage requirement to avoid). Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



randomwalker
Newbie
Offline
Activity: 2
Merit: 0


March 30, 2014, 02:09:26 AM Last edit: March 30, 2014, 05:29:12 AM by randomwalker 

I'm part of a research group at Princeton who've been independently working on just this problem. https://freedomtotinker.com/blog/stevenag/newresearchbetterwalletsecurityforbitcoin/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 twofactor security for personal wallets (as an alternative to Gavin's proposal of a multisignature twofactor wallet.) BTW, it's actually straightforward to avoid having a separate "dealer" even with the fullfledged threshold signature protocol.




Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129


March 30, 2014, 12:13:16 PM 

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
Newbie
Offline
Activity: 2
Merit: 0


March 30, 2014, 02:27:53 PM 

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 (OP)
Member
Offline
Activity: 111
Merit: 10


March 30, 2014, 03:26:13 PM 

BTW, it's actually straightforward to avoid having a separate "dealer" even with the fullfledged 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 t1?




Crowex (OP)
Member
Offline
Activity: 111
Merit: 10


March 31, 2014, 01:18:24 PM 

In the setup phase of your threshold signature generation does the polynomial need to be of degree t not t1?
Ok, sorry, I see you used t to represent a different value than in the original paper.




adam3us


January 19, 2015, 10:53:58 PM 

Well starting with nofn 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 ECSalternate: R=kG, [c=H(R,m), s=k+cd], Q=dG, verify: c=?H(sGcQ,m) (because kG=sGcQ)
(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 resplit d twice, once by A and once by b: first A: 1. A choses random r and sets a'=ar 2. A sends r to B 3. B sets b'=b+r 4. A sends a' to C (as d=a'+b'=ar+b+r=a+b, so a',b' is a resplit of d) similarly B: 5. B choses random r' and sets b"=br' 6. B sends r' to A 7. A sets a"=a+r' 8. B sends b" to C (as d=a"+b"=ar'+b+r'=a+b, so a",b" is a second resplit 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

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity



Reynaldo
Legendary
Offline
Activity: 1143
Merit: 1000


January 20, 2015, 01:36:56 AM 

http://pointatinfinity.org/ssss/Perhaps Shamir's secret sharing scheme may work to do a mofn 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 mofn 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
Moderator
Legendary
Offline
Activity: 4214
Merit: 8516


January 20, 2015, 01:47:55 AM 

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


January 21, 2015, 01:54:14 PM 

Looks like the original document is not available anymore.
Do you know where I could find it or something similar?
Thanx for your help.




