Unique Ring Signatures using secp256k1 keys

[tacotime]

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.

[1714194992]

1714194992

[1714194992]

1714194992

[andytoshi]

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]

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]

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

[tacotime]

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

[tacotime]

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.

[gmaxwell]

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.

[andytoshi]

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

[tacotime]

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

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

[andytoshi]

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.

[Crowex]

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.

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]

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.

[gmaxwell]

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.

[dillpicklechips]

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

[drawingthesun]

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?

[gmaxwell]

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]

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?

[andytoshi]

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.

[btchris]

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?

[tacotime]

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.