Bitcoin Forum
August 17, 2022, 03:54:51 AM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Unique Ring Signatures using secp256k1 keys  (Read 6955 times)
tacotime
Legendary
*
Offline Offline

Activity: 1484
Merit: 1005



View Profile
September 03, 2014, 09:12:28 PM
 #1

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.

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
1660708491
Hero Member
*
Offline Offline

Posts: 1660708491

View Profile Personal Message (Offline)

Ignore
1660708491
Reply with quote  #2

1660708491
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1660708491
Hero Member
*
Offline Offline

Posts: 1660708491

View Profile Personal Message (Offline)

Ignore
1660708491
Reply with quote  #2

1660708491
Report to moderator
1660708491
Hero Member
*
Offline Offline

Posts: 1660708491

View Profile Personal Message (Offline)

Ignore
1660708491
Reply with quote  #2

1660708491
Report to moderator
andytoshi
Full Member
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 03, 2014, 11:20:20 PM
Last edit: September 03, 2014, 11:34:12 PM by andytoshi
 #2

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
*
Offline Offline

Activity: 1484
Merit: 1005



View Profile
September 03, 2014, 11:30:01 PM
 #3

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.

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
andytoshi
Full Member
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 03, 2014, 11:35:35 PM
 #4

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

Activity: 1484
Merit: 1005



View Profile
September 03, 2014, 11:43:08 PM
Last edit: September 04, 2014, 12:44:27 AM by tacotime
 #5

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

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
tacotime
Legendary
*
Offline Offline

Activity: 1484
Merit: 1005



View Profile
September 03, 2014, 11:49:09 PM
 #6

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

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3696
Merit: 6463



View Profile
September 04, 2014, 12:31:34 AM
Last edit: September 04, 2014, 12:41:36 AM by gmaxwell
 #7

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
Full Member
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 04, 2014, 12:41:58 AM
 #8

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
tacotime
Legendary
*
Offline Offline

Activity: 1484
Merit: 1005



View Profile
September 04, 2014, 12:44:03 AM
 #9

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

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
andytoshi
Full Member
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 04, 2014, 02:04:54 AM
 #10

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
Member
**
Offline Offline

Activity: 111
Merit: 10


View Profile
September 04, 2014, 04:43:01 PM
 #11

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
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 04, 2014, 06:47:29 PM
 #12

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 3696
Merit: 6463



View Profile
September 04, 2014, 08:51:39 PM
 #13

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.
dillpicklechips
Hero Member
*****
Offline Offline

Activity: 994
Merit: 506


View Profile
September 04, 2014, 11:57:38 PM
 #14

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

Activity: 1176
Merit: 1015


View Profile
September 05, 2014, 05:39:28 PM
 #15

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
Moderator
Legendary
*
expert
Offline Offline

Activity: 3696
Merit: 6463



View Profile
September 05, 2014, 09:15:44 PM
 #16

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
*
Offline Offline

Activity: 1176
Merit: 1015


View Profile
September 06, 2014, 04:25:55 AM
 #17

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
Full Member
***
Offline Offline

Activity: 178
Merit: 148

-


View Profile
September 06, 2014, 01:14:12 PM
 #18

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
Hero Member
*****
Offline Offline

Activity: 672
Merit: 503

a.k.a. gurnec on GitHub


View Profile WWW
September 06, 2014, 03:39:38 PM
 #19

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
Legendary
*
Offline Offline

Activity: 1484
Merit: 1005



View Profile
September 06, 2014, 03:43:32 PM
 #20

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.

Code:
XMR: 44GBHzv6ZyQdJkjqZje6KLZ3xSyN1hBSFAnLP6EAqJtCRVzMzZmeXTC2AHKDS9aEDTRKmo6a6o9r9j86pYfhCWDkKjbtcns
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!