Unique Ring Signatures using secp256k1 keys

Joshuar

hero member

Activity: 504

Merit: 500

eidoo wallet

Quote from: tacotime on March 21, 2015, 02:01:39 PM

Quote from: Joshuar on March 21, 2015, 01:02:45 PM

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

Well, andytoshi and adam3us I know were trying to see if there was a way to compress ring signatures so that they reference the entire utxo set. I'm not sure how far they got. For maximum size of ring signature members, you're mainly limited to the memory of the system you are working on. Both size of the ring signature and time to verify is O(n) with the current signature algorithms.

For those outside Monero, a "mixin" is a ring signature member not the actual signer.

Ok thanks I understand, so limitations is just memory based.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: Joshuar on March 21, 2015, 01:02:45 PM

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

Well, andytoshi and adam3us I know were trying to see if there was a way to compress ring signatures so that they reference the entire utxo set. I'm not sure how far they got. For maximum size of ring signature members, you're mainly limited to the memory of the system you are working on. Both size of the ring signature and time to verify is O(n) with the current signature algorithms.

For those outside Monero, a "mixin" is a ring signature member not the actual signer.

Joshuar

hero member

Activity: 504

Merit: 500

eidoo wallet

I know this thread may be a bit outdated. But, I was wondering, is the mixin number that can be used, truly infinite? I know you can use a mixin of say 100,000 etc, but what about a mixin of truly incredible size, like 1,000,000,000(1billion)?

tacotime

legendary

Activity: 1484

Merit: 1005

Blinding has been added:
https://github.com/monero-project/urs/blob/master/urs.go#L547-L752

Use '-B' to blind your signature in the scheme described by andytoshi and gmaxwell (this is my first time messing with EC ops, hope I implemented it right!).

andytoshi

full member

Activity: 179

Merit: 156

-

Quote from: dillpicklechips on September 07, 2014, 12:35:04 AM

Another interesting use could be a type of ring signature coinjoin? A group gets together and determines the inputs. The ring signatures are used for each person to pick their outputs and can even have multiple outputs of different values. Once the group has enough messages specifying the output addresses the coinjoin transaction is created and signed. If any party of the group cheats the output values will total to be too high and the transaction is discarded.

This is a good idea. In the original coinjoin thread gmaxwell described a blinding scheme wherein users would initially provide their outputs in blinded form, have them blindsigned by the central server (or the "leader" node in a p2p setup) (or all participating parties, which is bandwidth-heavy), then reconnect anonymously to unblind them. For a p2p setup this means that somebody has to produce the blind signatures: either a leader must be selected, which adds complexity to the protocol, or every party signs every output, which leads to O(n^2) scaling.

With a ring signature on the other hand, each party would anonymously sign only their own outputs -- all nodes participate equally, with O(n) signatures. (Of course, the ring signatures are O(n) in size, so you might say this is still O(n^2) scaling. But since every signature uses the same keyring, this doesn't need to be passed around. Just the signature itself plus a blinding factor Q (one per signature, no need to use different ones per key in this case) as described in an earlier post.)

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: Crowex on September 07, 2014, 05:17:52 AM

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

Quote from: gmaxwell on September 05, 2014, 04:15:44 PM

Quote from: drawingthesun on September 05, 2014, 12:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

You need to be careful here because voting and whistleblowing are not the same.
The linkability, or what the authors of this paper describe as uniqueness introduces restricted anonymity, as you described above, because the signer is not completely anonymous and can be exposed by all of the other people in the ring.
A blinding scheme could affect the linkability and increase the anonymity. It might mean that it is difficult for other signers to group together and expose a whistleblower but it also might mean that anybody could vote more than once.

The uniqueness would also seem to be necessary for any simple type of threshold scheme, although there may be other ways of achieving this.

Yes. Voting under this scheme would require signers to sign either a "Yea" or "Nay" message and submit it somehow to an authority who tallies the votes. Users could also vote for both Yea/Nay, which is a little strange but in the end doesn't effect the majority consensus decision one way or the other (hence you can get more than 100% votes, but the end decision will be based on the majority voting direction regardless).

Using gmaxwell's blinding scheme, you will no longer get unique X and Y values per message, so it can no longer be used for such a voting scheme. When I implement it I will just add a new flag that turns on or off this feature, because you may or may not want it. Additionally to simplify my coding I will probably make it sign H(m) instead of H(0) for the niZKP (I don't think it matters really what you sign, just that you can demonstrate you made a signature that proves knowledge of your private key).

Crowex

member

Activity: 111

Merit: 10

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

Quote from: gmaxwell on September 05, 2014, 04:15:44 PM

Quote from: drawingthesun on September 05, 2014, 12:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

You need to be careful here because voting and whistleblowing are not the same.
The linkability, or what the authors of this paper describe as uniqueness introduces restricted anonymity, as you described above, because the signer is not completely anonymous and can be exposed by all of the other people in the ring.
A blinding scheme could affect the linkability and increase the anonymity. It might mean that it is difficult for other signers to group together and expose a whistleblower but it also might mean that anybody could vote more than once.

The uniqueness would also seem to be necessary for any simple type of threshold scheme, although there may be other ways of achieving this.

dillpicklechips

hero member

Activity: 994

Merit: 507

Another interesting use could be a type of ring signature coinjoin? A group gets together and determines the inputs. The ring signatures are used for each person to pick their outputs and can even have multiple outputs of different values. Once the group has enough messages specifying the output addresses the coinjoin transaction is created and signed. If any party of the group cheats the output values will total to be too high and the transaction is discarded.

andytoshi

full member

Activity: 179

Merit: 156

-

I did all of the writing but none of the ideas

So I think it's fair to give gmaxwell all the credit.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: andytoshi on September 06, 2014, 01:05:26 PM

Quote from: btchris on September 06, 2014, 10:39:38 AM

It's even stronger than that, isn't it? If the signer used gmaxwell's blinding scheme, than none of the 1,000,000 (including the actual signer) are capable of proving that they either did or didn't sign it (even if any of them wanted to), correct?

Almost. If the signer actually threw away her q value, then yes. There is no way to enforce this. (But why wouldn't you? I dunno, depends on the context I guess..)

Got it, thanks.

Also, are you a co-author of the paper? I didn't mean to exclude you by calling it exclusively "gmaxwell's blinding scheme"...

andytoshi

full member

Activity: 179

Merit: 156

-

Quote from: btchris on September 06, 2014, 10:39:38 AM

It's even stronger than that, isn't it? If the signer used gmaxwell's blinding scheme, than none of the 1,000,000 (including the actual signer) are capable of proving that they either did or didn't sign it (even if any of them wanted to), correct?

Almost. If the signer actually threw away her q value, then yes. There is no way to enforce this. (But why wouldn't you? I dunno, depends on the context I guess..)

tacotime

legendary

Activity: 1484

Merit: 1005

Quote

It's even stronger than that, isn't it? If the signer used gmaxwell's blinding scheme, than none of the 1,000,000 (including the actual signer) are capable of proving that they either did or didn't sign it (even if any of them wanted to), correct?

Well, unless the computer used to generate the signature was compromised so that the private and ephemeral keys were known.

Haven't gotten around to implementing that yet, still dealing with the recent Monero attack. But hopefully soon.

btchris

hero member

Activity: 672

Merit: 504

a.k.a. gurnec on GitHub

Quote from: andytoshi on September 06, 2014, 08:14:12 AM

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

If you used the blinding scheme gmaxwell described above, all 1,000,000 could "admit" it wasn't them and nobody would be able to prove otherwise.

It's even stronger than that, isn't it? If the signer used gmaxwell's blinding scheme, than none of the 1,000,000 (including the actual signer) are capable of proving that they either did or didn't sign it (even if any of them wanted to), correct?

andytoshi

full member

Activity: 179

Merit: 156

-

Quote from: drawingthesun on September 05, 2014, 11:25:55 PM

Quote from: gmaxwell on September 05, 2014, 04:15:44 PM

Quote from: drawingthesun on September 05, 2014, 12:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

If you used the blinding scheme gmaxwell described above, all 1,000,000 could "admit" it wasn't them and nobody would be able to prove otherwise.

drawingthesun

legendary

Activity: 1176

Merit: 1015

Quote from: gmaxwell on September 05, 2014, 04:15:44 PM

Quote from: drawingthesun on September 05, 2014, 12:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

So if we had 1,000,000 people apart of this signature, you could never find out who voted or released/leaked info unless the other 999,999 admitted it wasn't them?

gmaxwell

staff

Activity: 4326

Merit: 8951

Quote from: drawingthesun on September 05, 2014, 12:39:28 PM

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

Only that it has linear scaling. Such a signature would be many megabytes in size and would take minutes to verify with state of the art ECC code.

drawingthesun

legendary

Activity: 1176

Merit: 1015

Quote from: dillpicklechips on September 04, 2014, 06:57:38 PM

This sounds potentially useful for voting systems. You can see that everyone voted without seeing who voted for who.

Could a ring signature set of several million people be created? Is there a limit to how many people mix together?

dillpicklechips

hero member

Activity: 994

Merit: 507

This sounds potentially useful for voting systems. You can see that everyone voted without seeing who voted for who.

gmaxwell

staff

Activity: 4326

Merit: 8951

Quote from: andytoshi on September 04, 2014, 01:47:29 PM

Quote

I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

Nope. Even with the same q, nobody except the signer is able to prove that they were or weren't the signer, and if the signer forgets her q then she can't either.

The "different q's" thing was just an artifact of my initial misunderstanding when I wrote the article.

You need different Qs if you want multiple signers (in the BRS style) and for them to be mutually anonymous from each other. E.g. to select a group of N out of M trusted parties, where the N don't know who each other are.

andytoshi

full member

Activity: 179

Merit: 156

-

Quote

I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

Nope. Even with the same q, nobody except the signer is able to prove that they were or weren't the signer, and if the signer forgets her q then she can't either.

The "different q's" thing was just an artifact of my initial misunderstanding when I wrote the article.

Crowex

member

Activity: 111

Merit: 10

Quote from: andytoshi on September 03, 2014, 09:04:54 PM

Quote from: gmaxwell on September 03, 2014, 07:31:34 PM

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Tacotime and myself were quite confused by this ... after a long IRC conversation I believe the three of us landed on this description of how exactly the blinding is done.

That's really neat.

Quote

the signer generates q values for all signers. She proves
knowledge of each one of them

Could you simplify the protocol a little by using the same q value for all signers?
I don't really know exactly what the ring signature protocol is (any links?) so maybe there are disadvantages to doing this?

andytoshi

full member

Activity: 179

Merit: 156

-

Quote from: gmaxwell on September 03, 2014, 07:31:34 PM

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Tacotime and myself were quite confused by this ... after a long IRC conversation I believe the three of us landed on this description of how exactly the blinding is done.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 07:41:58 PM

I think you made a typo tacotime, because two keys are repeated. What you mean is

Code:

{
"0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
"1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
"2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

and I can indeed verify your signed message with this ring Cheesy

Ah, yes, correct, I'll fix it up above.

andytoshi

full member

Activity: 179

Merit: 156

-

I think you made a typo tacotime, because two keys are repeated. What you mean is

Code:

{
"0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
"1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
"2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

and I can indeed verify your signed message with this ring Cheesy

gmaxwell

staff

Activity: 4326

Merit: 8951

Something to watch out for here is that it's coercion vulnerable, which I think I'd addressed in my science project work.

E.g. I can go to Satoshi and Andytoshi and demand they give me they publish public keys, and then in doing so prove the message came from tacotime.

To avoid this, you generate a random blinding key Q and sign with gP+gQ instead, proving knoweldge of P, then you forget Q. Later you cannot be coerced because you can honestly claim to have forgotten Q.

Making the threshold scheme e.g. where you have a set of N of M signers where _no_ person knows who all the N (not even the members themselves) is more complicated with this blinding, however, because someone must create the Qs for the involuntary participants.

You currently don't support composing signatures but you totally could doing so results in useful applications.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 06:35:35 PM

Do you know if they are aware of our value blinding scheme described in my writeup?

Yup, the math/crypto guys that have been hired have gone over it a lot. Unfortunately, it's a rather large change in terms of core code that we'd have to make and right now we're still trying to figure out why even basic stuff in the codebase like network propagation/syncing is dysfunctional. Large, likely hardfork changes like that will be a while off to implement, although it is a really cool idea.

tacotime

legendary

Activity: 1484

Merit: 1005

Quote

Edit: Ok, looks like we have to generate the keyring manually? To make a keypair you use the -g command. There is an example keyring that comes with program

Code:

{
   "0":"024627032575180c2773b3eedd3a163dc2f3c6c84f9d0a1fc561a9578a15e6d0e3",
   "1":"02b266b2c32ba5fc8d203c8f3e65e50480dfc10404ed089bad5f9ac5a45ffa4251",
   "2":"031ea759e3401463b82e2132535393076dde89bf2af7fc550f0793126669ffb5cd",
   "3":"03320cd05f3538159693cd253c30ec4972fa06ad10f1812951923a5ea063e9748c",
   "4":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
   "5":"03c81094edb63ba28b1e4d5556d91dc030b725e105be94fb4005bee987f80a38f0",
   "6":"032077679a3f1579acc22308f09b7d5f597cba4ea9f314b8aaf86ab2f052fa0157",
   "7":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
   "8":"02dcdb96d05d6cd36ce7014a69ebce8b48f8d7de46ce3bfa99482af65284697e13",
   "9":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

So I guess we will just copy the format.

My key for this thread is 02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194

Yes, this is correct. Here is a test pubkey from me:

Code:

032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888

I will sign using this keyring:

Code:

{
"0":"02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194"
"1":"032e76a7de5584eee15a23e872c08543fcca5445d844a6ce63d37c5d25ce377888",
"2":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

(The first is andytoshi, the second is me, and the third is Satoshi (from the genesis block).)

This is the message:

Code:

The Times 03/Jan/2009 Chancellor on brink of second bailout for banks

Using the verify text feature, here's the returned signature for you to validate:

Code:

144VfXoJFBzxhFe7c4GXsCpPogkhXkkrQut5r7waHxgUv+FiH39RvZ5LSYEUFR2UXKfgcgzxZ48Dd3f2CdgycnUKHk+FFkDCK438Zdpza9RaAyh5VCMcpe5d1Yj29SP1111vZtL&5dma9x2cspgqM3TZZugDuyjVz5dmJLC9JU4JVb4frTdb&BnJdCj4DAsr6QzK22Qx5n4ts8Rzas4s23Cs5YDDirThA&+HJmdbgEnpXcQ7mDnuywXsy6bdzg5zN1RCdeYN8RLnhnm&78K3TP8PbjrMKWKEHmWM1Cf7nUsnse3EQ6owKoJFi3f3&9duvujESzXaHTKxDEJPESYoSRVYbVxHQej3FEZbysMGc&

This signature is from either me, or andytoshi, or Satoshi.

If you check the key file, you will also see that generated keys include mainnet V1 addresses (although these aren't used by the program itself).

andytoshi

full member

Activity: 179

Merit: 156

-

Do you know if they are aware of our value blinding scheme described in my writeup?

tacotime

legendary

Activity: 1484

Merit: 1005

Quote from: andytoshi on September 03, 2014, 06:20:20 PM

This is great stuff tacotime! I bet we have a lot of fun with this. Maybe I will install Go, generate a key, and post it here for us to play ringsigning games.

Are you involved with Monero?

Thanks! Admittedly I don't follow 100% of the ring signature crypto code that Hein wrote, but the usage and verification is as expected. One thing I did add was sorting to the key ring input based on the public key X and Y values, so that ordering of the keyring did not impact signature generation/verification.

The output for signatures is in Base58, in the format:

Code:

X+Y+[C_0]&[C_1]&...&[C_N]&+[T_0]&[T_1]&...&[T_N]&

I am involved with Monero as a (volunteer) member of the core team, although most of what I do is higher level consulting on how to maintain anonymity using the stock ring signature code. This has been kind of a "rabbit hole" problem of endlessly more things to consider in terms of deanonymization attack vectors, but we should have some publications and proposals out soon that further investigate this that you and gmaxwell will probably be interested in.

andytoshi

full member

Activity: 179

Merit: 156

-

This is great stuff tacotime! I bet we have a lot of fun with this. Maybe I will install Go, generate a key, and post it here for us to play ringsigning games.

Are you involved with Monero?

Edit: Ok, looks like we have to generate the keyring manually? To make a keypair you use the -g command. There is an example keyring that comes with program

Code:

{
"0":"024627032575180c2773b3eedd3a163dc2f3c6c84f9d0a1fc561a9578a15e6d0e3",
"1":"02b266b2c32ba5fc8d203c8f3e65e50480dfc10404ed089bad5f9ac5a45ffa4251",
"2":"031ea759e3401463b82e2132535393076dde89bf2af7fc550f0793126669ffb5cd",
"3":"03320cd05f3538159693cd253c30ec4972fa06ad10f1812951923a5ea063e9748c",
"4":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
"5":"03c81094edb63ba28b1e4d5556d91dc030b725e105be94fb4005bee987f80a38f0",
"6":"032077679a3f1579acc22308f09b7d5f597cba4ea9f314b8aaf86ab2f052fa0157",
"7":"039b9033d0377e3af7fdf4369134f3ec96aa03326fd07f89d60dc3ba70d0a19956",
"8":"02dcdb96d05d6cd36ce7014a69ebce8b48f8d7de46ce3bfa99482af65284697e13",
"9":"04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"
}

So I guess we will just copy the format.

My key for this thread is 02b631fc5e901982a8d130ea65f2966e99a51375030b3c9c64288f4631943ed194

tacotime

legendary

Activity: 1484

Merit: 1005

As part of ongoing efforts of the Monero Project, a small program has been generated that allows you to do 1-of-N ring signatures using a secp256k1 keypair and a keyring of public keys. The program signs both binaries and text files.

https://github.com/monero-project/urs

To build and install, use this command after installation of Go:

Code:

go get -u -v github.com/monero-project/urs/...

According to the paper, unique ring signatures are anonymous except in the case of signing the same message multiple times (in which case X and Y in the signature appear to be the same).

http://csiflabs.cs.ucdavis.edu/~hbzhang/romring.pdf

A potential usage might be to sign gitian asserts from a trusted keyring anonymously that contains well known members of the Bitcoin project. Another usage would be for members of a trusted community of Bitcoin users to anonymously vote for some proposal by signing it separately and publishing their signatures.

Thanks to Hein Meling for the initial URS implementation, Conformal Systems for their immensely useful libraries, and gmaxwell for inspiration.

Topic: Unique Ring Signatures using secp256k1 keys (Read 7047 times)