P(o)ODLE

"Here is a purse of monies ... which I am not going to give to you" - Edmund Blackadder

P(o)ODLE, not POODLE

This post, fortunately, has nothing to do with faintly ridiculous SSL 3 downgrade attacks. Irritatingly, our usage here has no made-up need for the parenthetical (o), but on the other hand "podle" is not actually a word.

The problem

You're engaging in a protocol (like Joinmarket) where you're using bitcoin utxos regularly. We want to enforce some scarcity; you can't use the same utxo more than once, let's say. Utxos can be created all the time, but at some cost of time and money; so it can be seen as a kind of rate limiting.

So: you have a bitcoin utxo. You'd like someone else to know that you have it, and that you haven't used it before, with them or anyone else, in this protocol, but you don't want to show it to them. For that second property (hiding), you want to make a commitment to the utxo. Later on in the protocol you will open the commitment and reveal the utxo.

Now, a cryptographic commitment is a standard kind of protocol, usually it works something like:

Alice->Bob: commit: h := hash(secret, nonce)
(do stuff)
Alice->Bob: open: reveal secret, nonce
Bob: verify: h =?= hash(secret, nonce)

Hashing a secret is not enough to keep it secret, at least in general: because the verifier might be able to guess, especially if the data is from a small-ish set (utxos in bitcoin being certainly a small enough set; and that list is public). So usually, this protocol, with a large-enough random nonce, would be enough for the purposes of proving you own a bitcoin utxo without revealing it.

But in our case it doesn't suffice - because of the bolded sentence in the problem description. You could pretend to commit to different utxos at different times, simply by using different nonces. If you tried to do that just with me, well, no big deal - I'll just block your second use. But you could use the same utxos with different counterparties, and they would be none the wiser, unless they all shared all private information with each other. Which we certainly don't want.

Contrariwise, if you ditch the nonce and just use Hash(utxo) every time to every counterparty, you have the failure-to-hide-the-secret problem mentioned above.

In case you didn't get that: Alice wants to prove to Bob and Carol and ... that she owns utxo
\(U\), and she never used it before. Bob and Carol etc. are keeping a public list of all previously used commitments (which shouldn't give away what the utxo is, for privacy). If she just makes a commitment: Hash(\(U +\) nonce) and sends it to Bob and Carol, they will check and see it isn't on the public list of commitments and if not, OK, she can open the commitment later and prove honest action. But her conversations with Bob and Carol are separate, on private messaging channels. How can Bob know she didn't use the same utxo as previously used with Carol, but with a different nonce?

The solution

This is a bit of a headscratcher; after several IRC discussions, Greg Maxwell suggested the idea of proof of discrete logarithm equivalence (hence the title), and pointed me at this crypo.stackexchange thread. It's a cool idea (although note that that description is based on DL rather than ECDL seen here): "shift" the EC point to a new base/generator point, so that nobody else can read (crudely put), then append a Schnorr signature acting as proof that the two points have the same discrete logarithm (= private key) with respect to the two base points. In detail, consider a Bitcoin private, public keypair \((x, P\)\)
for the usual base point/generator \(G\), and consider a NUMS alternative generator \(J\) ( a little more on this later).

\(P = xG\)

\(P_2 = xJ\)

Next, Alice will provide her commitment as \(H(P_2)\) in the handshake initiation stage of the protocol. Then, when it comes time for Alice to request private information from Bob, on their private message channel, she will have to open her commitment with this data:

\(P, U, P_2, s, e\)

Here \(s, e\) are a Schnorr signature proving equivalence of the private key (we called it \(x\) above) with respect to \(G, J\), but of course without revealing that private key. It is constructed, after choosing a random nonce \(k\), like this:

\(K_G = kG\)

\(K_J = kJ\)

\(e = H(K_G||K_J||P||P_2)\)

\(s = k + xe\)

Then Bob, receiving this authorisation information, proceeds to verify the commitment before exchanging private information:

1. Does \(H(P_2\) equal the previously provided commitment? If yes:
   
2. Check that the commitment is not repeated on the public list (or whatever the policy is)
   
3. Verify via the blockchain that \(P\) matches the utxo \(U\)
4. \(K_G\ = sG - eP\)
5. \(K_J = sJ - eP_2\)
6. Schnorr sig verify operation: Does \(H(K_G||K_J||P||P_2) = e\)?

Bob now knows that the utxo \(U\) has not been repeated (the simplest policy) but Alice has not been exposed to a potential public leakage of information about the utxo. (It should be noted of course! Bob knows the utxo from now on, but that's for another discussion about Coinjoin generally...)

Why an alternate generator point \(J\)?

Publishing \(H(P_2\) gives no information about \(P\), the actual Bitcoin pubkey that Alice wants to use; in that sense it's the same as using a nonce in the commitment. But it also gives her no degree of freedom, as a nonce does, to create different public values for the same hidden pubkey. No one not possessing \(x\) can deduce \(P\) from \(P_2\) (or vice versa, for that matter) - unless they have the private key/discrete log of \(J\) with respect to \(G\). If anyone had this number \(x^*\) such that \(J = x^*G\), then it would be easy to make the shift from one to the other:

\(P_2 = xJ = x(x^*G) = x^*(xG) = x^*P\)

and apply a modular inverse if necessary.

This is why the concept of NUMS is critical. The construction of a NUMS alternate generator is discussed in the same CT doc as above, and also in my CT overview, at the end of section 2.2. Note I use \(J\) here in place of \(H\) to avoid confusion with hash functions.

Code and thoughts on implementation

I did an abbreviated write up of the concept of this post in this gist, as one of three possible ways of attacking the problem in Joinmarket: how can we prevent people initiating transactions over and over again to collect information on utxos? This algorithm is not intended as a complete solution to that issue, but it's very interesting in its own right and may have a variety of applications, perhaps.

The algorithm was fairly simple to code, at least in a naive way, and I did it some time ago using Bitcoin's libsecp256k1 with the Python binding by ludbb. An initial version of my Python "podle" module is here.

There are lots of tricky things to think about in implementing this; I think the most obvious issue is how would publishing/maintaining a public list work? If we just want each utxo to be allowed only one use, any kind of broadcast mechanism would be fine; other participants can know as soon as any \(H(P_2)\) is used, or at least to a reasonable approximation. Even in a multi-party protocol like Joinmarket, the utxo would be broadcast as "used" only after its first usage by each party, so it would from then on be on what is effectively a blacklist. But if the policy were more like "only allow re-use 3 times" this doesn't seem to work without some kind of unrealistic honesty assumption.