Quote from: oleganza on March 12, 2014, 05:30:59 PM

Quote from: gmaxwell on March 12, 2014, 03:48:30 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 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