Cryptographic coin flipping, now in Keybase • Hacker News Board

Re: Cryptographic coin flipping, now in Keybase

#71

Post by oh_sigh » Tue, Mar 12, 2019, 3:35 AM UTC

leetbulb wrote: post #68

oh_sigh wrote: post #46

Is this a problem with commitment schemes? I want a heads to come up. I add a couple of hacked members to the group, so there are 3 honest members, and lets say 3 coordinated dishonest members. Everyone shares their commitment hash, and the dishonest members share their actual commitments amongst themselves. Once everyone has the commitment hashes, the 3 honest members broadcast their commitment. The three dishonest…

1. All members generate a random value (high entropy). 2. All members submit a hashed value of that random value (the commitment). 3. All commitments are distributed to all members. At this point, no more commitments may be submitted. 4. All members reveal their random values to each other and validate each value against its hash. 5. All values are then used to deterministically calculate the coin flip. A dishonest m…

Sorry, I think I may have used the wrong terminology in my post above. I was referring to the random value as the 'commitment' and the hash of that as the 'commitment hash'.

But what I proposed doesn't require anyone to change their random value. It relies on the fact that step #4 does not happen instantaneously, and honest clients will send their random values as soon as they transition into step #4.

So from my above example, the process reaches step #4 as normal - all honest clients send out their random values, and all dishonest clients wait. Once the dishonest clients have all of the honest random values, they can now determine what the result for #5 will be(because they know all other dishonest client random values because they are colluding, along with all honest client random values), whereas the honest clients cannot do so, because they don't know the random values from the dishonest clients.

So at that point(half way through step #4), dishonest clients can then determine if they want that value to be the end result, or if some of them should drop out(never broadcast their random value), in order to modify what everyone determines to be the final value from step #5.

Re: Cryptographic coin flipping, now in Keybase

#72

Post by patcon » Tue, Mar 12, 2019, 4:00 AM UTC

malgorithms wrote: post #27

I'd be curious if people on HN would want a zero knowledge survey and voting system inside Keybase, and if so, what would it look like? The background: we talk about it sometimes as a solution to a real problem: in certain teams and workplaces, people can be afraid to give honest feedback (who dares to submit an "anonymous" survey to HR?), but Keybase may be in a unique position to let people in a group give written…

imho the more interesting cryptopgraphic proof would be proof of address or bounding box. I feel that if you allowed third-parties to pay you for supporting a validation of locality via cryptographic features sent in postcard, then the rails would come off what was possible with digital systems. Knowing location will be increasingly powerful imho. Our opinions count most in a local spaces, at least with city-building. And I feel that third parties would be willing to fund the main cost of postage, if it allowed them to be assured of certain geographic bounds of users.

In order to cheat that system, people would need to engage in mail fraud or buy a PO box.

Happy to discuss, chris. Sidewalk Labs is setting up camp in Toronto, and I was speaking about the above at a local event, and they were really interested in the concept. I had a call with their head of identity, but was disappointed that he couldn't say anything of substance on _why_ it was relevant to SL efforts, at least not without my signing an NDA. As a community organizer in the civic tech scene, I had no interest in that. More secrecy in the smart city / open gov sector :/ blech

Re: Cryptographic coin flipping, now in Keybase

#73

Post by wildmanx » Tue, Mar 12, 2019, 4:18 AM UTC

>> Who invented commitment schemes?

> ~My wife~ Not sure.

Seriously? You work professionally in the crypto space and don't know where this is from? Or don't feel it's important to attribute such fundamental ideas to the appropriate people? If you really don't know, a quick google would have educated you. But what I fear to be more likely is that you apparently just don't give a damn.

For anybody remotely interested, look up Manuel Blum's work, e.g. "Coin flipping by telephone" presented at CRYPTO 1981. ACM Turing Award.

Or Rivest, Shamir, Adleman, "Mental Poker". Oh, those guys also got the ACM Turing Award.

Re: Cryptographic coin flipping, now in Keybase

#74

Post by Sophistifunk » Tue, Mar 12, 2019, 4:34 AM UTC

rodrigosetti wrote: post #60

I like the UI, but I find the blog post example - flip a coin to see who will donate a kidney - a little distasteful.

Cool story bro.

Re: Cryptographic coin flipping, now in Keybase

#75

Post by leetbulb » Tue, Mar 12, 2019, 4:44 AM UTC

oh_sigh wrote: post #71

leetbulb wrote: post #68

Earlier quoted context omitted.

1. All members generate a random value (high entropy). 2. All members submit a hashed value of that random value (the commitment). 3. All commitments are distributed to all members. At this point, no more commitments may be submitted. 4. All members reveal their random values to each other and validate each value against its hash. 5. All values are then used to deterministically calculate the coin flip. A dishonest m…

Sorry, I think I may have used the wrong terminology in my post above. I was referring to the random value as the 'commitment' and the hash of that as the 'commitment hash'. But what I proposed doesn't require anyone to change their random value. It relies on the fact that step #4 does not happen instantaneously, and honest clients will send their random values as soon as they transition into step #4. So from my abov…

I have implemented an extremely similar protocol for a side project game.

In my implementation, step 4 happens in two phases:

4a. All members submit their secret values to the server.

4b. Once all secret values are submitted, they are all sent to each member at once.

This ensures that members cannot determine the outcome before anyone else.

What you are describing could actually be an issue if there is no server involved, however something like commitment encryption (rather than hashing) utilizing secret sharing could help resolve this issue in a p2p environment.

Another option would be that all possible outcomes are randomly shuffled with their positions encrypted and distributed to all members prior to the game beginning.

My protocol implements the latter... all possible outcomes are encrypted and publicly available on IPFS to members before and after the game.

Re: Cryptographic coin flipping, now in Keybase

#76

Post by techntoke » Tue, Mar 12, 2019, 4:47 AM UTC

dmitriid wrote: post #35

tosh wrote: post #32

Earlier quoted context omitted.

In a sense keybase is one of the most important projects built right now (that I can think of). It covers aspects (think pareto principle) of email, linkedin, slack, github, dropbox, whatsapp, online banking and probably more core use cases that I don’t have on top of my mind. That is now, today. With a decent user experience that keeps getting better (see recent improvements @ user profiles). => all of that end-to-e…

> It covers aspects (think pareto principle) of email, linkedin, slack, github, dropbox, whatsapp, online banking and probably more core use cases that I don’t have on top of my mind. Soooo... A centralized solution for everything? ;)

Exactly... unless the work is open source, they are just another centralized solution. Reminds me of Telegram.

Re: Cryptographic coin flipping, now in Keybase

#77

Post by wildmanx » Tue, Mar 12, 2019, 4:51 AM UTC

oh_sigh wrote: post #71

leetbulb wrote: post #68

Earlier quoted context omitted.

1. All members generate a random value (high entropy). 2. All members submit a hashed value of that random value (the commitment). 3. All commitments are distributed to all members. At this point, no more commitments may be submitted. 4. All members reveal their random values to each other and validate each value against its hash. 5. All values are then used to deterministically calculate the coin flip. A dishonest m…

Sorry, I think I may have used the wrong terminology in my post above. I was referring to the random value as the 'commitment' and the hash of that as the 'commitment hash'. But what I proposed doesn't require anyone to change their random value. It relies on the fact that step #4 does not happen instantaneously, and honest clients will send their random values as soon as they transition into step #4. So from my abov…

Only after step #5 is the value valid, i.e., after everybody has broadcasted their value. This includes everybody who broadcasted anything in previous stages. As long as the dishonest clients have not all broadcasted theirs, the procedure is not done and there is simply no consensus yet.

One could argue that the dishonest clients could use this to basically abort the procedure before the value is determined (by not broadcasting their values). But once the procedure is complete, being dishonest does not mean anything.

Re: Cryptographic coin flipping, now in Keybase

#78

Post by latchkey » Tue, Mar 12, 2019, 5:57 AM UTC

How is this different from provably fair? https://dicesites.com/provably-fair

Re: Cryptographic coin flipping, now in Keybase

#79

Post by jlrubin » Tue, Mar 12, 2019, 6:19 AM UTC

wildmanx wrote: post #73

>> Who invented commitment schemes? > ~My wife~ Not sure. Seriously? You work professionally in the crypto space and don't know where this is from? Or don't feel it's important to attribute such fundamental ideas to the appropriate people? If you really don't know, a quick google would have educated you. But what I fear to be more likely is that you apparently just don't give a damn. For anybody remotely interested,…

I think you're unfairly punishing him for not knowing; it's a bit tough to find. I'll give you that the joke -- pinning it on his wife -- is unfunny.

None of the folks you mentioned, I believe, invented commitment schemes. Whit Diffie has a good history here: https://ee.stanford.edu/~hellman/publications/24.pdf. So these innovations would have been ~1 academic generation prior.

Of course, the GCHQ probably invented them even earlier ;)

Re: Cryptographic coin flipping, now in Keybase

#80

Post by leetbulb » Tue, Mar 12, 2019, 6:19 AM UTC

DuskStar wrote: post #57

stackzero wrote: post #40

How does this address the last revealer problem?

Assuming you mean the attack where one person can wait to be the last to reveal their secret and then influence the game by dropping out, it doesn't appear to. > What if someone loses network before the secret stage? > A bad actor can't change the outcome of a flip but could prevent it from resolving. > The Keybase app will highlight this scenario. Odds are it was just a network issue, but if you have such a person d…

One way to solve this issue is to shuffle the possible outcomes and encrypt or hash their positions along with a nonce. This info would be distributed to clients during the game initialization. At reveal time, the server presents these outcome positions to the clients along with the other client secrets.

Also see my other comment in this thread where in a client/server architectured version of this protocol, the reveal step is split up in to two stages:

> 4a. All members submit their secret values to the server.

> 4b. Once all secret values are submitted, they are all sent to each member at once.

> This ensures that members cannot determine the outcome before anyone else.