2
$\begingroup$

I am looking for some sort of communication or consensus algorithm with the following properties:

  • Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties)
  • Requires each party to initiate some sort of communication to which the other responds (ideally in a binary way)
  • Non-hierarchical
  • Bonus points if it's some sort of consensus, decision-making, or contract signing algorithm

Context: my boyfriend and I are planning on getting engaged soon. For various reasons, we would both like to propose to each other. The challenge is that we don't want whichever proposal is second to feel like it was unnecessary. Since we're both computer scientists, we figure there must be an algorithmic solution to this problem! So we are looking for a communication protocol/consensus algorithm/something else in that vein in which it is necessary for both parties to initiate and respond to a communication. We will be implementing the chosen algorithm verbally, not over an actual internet connection. In case you're having a hard time picturing this, it would be kind of like how a lot of textbooks will have conversational English versions of the messages being sent under various communications protocols, e.g.:

Example of a cartoon communication protocol from https://medium.com/@PrakhashS/concepts-behind-network-scanning-using-nmap-598df2a72ab9

Except we would replace "Hey. Can I talk to you?" with something more like "Will you marry me?".

Before anyone asks, yes, this is entirely symbolic/for fun, but we feel that's true of most aspects of getting engaged/married. And yes, we are nerdy enough that we will happily exchange random numbers with each other in public if that's what the protocol (or its associated cryptography) demands.

Possibilities we've considered so far:

  • TCP: This was our first thought, but it's not a great fit. For connection establishment all the server sends is a SYN-ACK, which isn't really satisfying either as a response to the first proposal or as the question being asked in the second proposal. The connection termination protocol seems like it would be weird to adapt to verbal communication.
  • Dining cryptographers: Would be great (although we'd have to use 0 to mean yes, which is a little gross), except it falls apart with only two parties. So we'd have to include a third person (and give them veto power over our engagement). It would be perfect for a polyamorous engagement, though!
  • Some sort of blockchain consensus algorithm: All the ones I'm aware of seem like they'd collapse to a trivial case with two parties (but I could be wrong about this)
  • Some sort of contract signing algorithm: Probably the best option we've found so far. These are the closest to being designed to solve the actual problem that we have, but all the ones I've seen require some sort of trusted third party (we could make that work but it wouldn't be ideal).

Does anyone know of an algorithm that is a better fit than these? Apologies if this is off-topic (I'm hoping it falls under "we do not hate fun")!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this). The number of steps is very large though! Probably not suitable to carry out by hand.

You could try a simpler protocol:

  1. Alice picks a message $m_A$, computes a commitment $C(m_A)$ to $m_A$, and reveals the commitment $C(m_A)$. For instance, maybe Alice writes down $C(m_A)$ in view of Bob.

  2. Bob picks a message $m_B$, computes a commitment $C(m_B)$ to $m_B$, and reveals the commitment $C(m_B)$ -- say, writing it down too. (Steps 1 and 2 can be done simultaneously or in any order.)

  3. Alice opens her commitment to reveal $m_A$ (e.g., she writes $m_A$ down on the piece of paper). Bob verifies that the message matches her commitment.

  4. Bob opens his commitment to reveal $m_B$. Alice verifies that the message matches his commitment. (Steps 3 and 4 can be done in any order; but they shouldn't be started until both Steps 1 and 2 are complete.)

In your case, Alice could choose as her message "Bob, will you marry me?" or "Bob, let's not get married yet" and Bob could choose as his message "Alice, will you marry me?" or "Alice, let's not get married yet" and then you could compare at the end.

There are various ways to do a cryptographic commitment. One way is with a cryptographic hash function (you could use a web site to compute it for you). A simpler method is to secretly write down the message on a piece of paper, then put the paper in an envelope, seal the envelope, and place the envelope on the table in front of both of you.

See, e.g., https://keybase.io/blog/cryptographic-coin-flipping for a gentle introduction to related ideas.

Another idea is to execute a two-phase commit protocol.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.