Little RIDDLE

AdamISZ

— 12 min read


Contents

Introduction

If you want the TLDR for this post, probably just read this section and then the final one on Practical usage.

Previous blogs in this mini-series:

This (last) post represents the culmination of the research into, how best can we do what is described in the third above post RIDDLE.

As was mentioned there, we want to create privacy based on the anonymity set of the decoy members in the ring that we sign over; and if the size of the ring signature is proportional to the anonymity set, then the size becomes impractical. Hence we need something like what is described in the last two posts (i.e. at least logarithmic scaling - O(log(N)) - , though constant size - O(1) - would be even better). Hence "little riddle".

But as we left off at the end of of "Bragging with Brevity", we still need to turn the ring signature into a linkable ring signature, to append a usage token (without that, the ring signature is infinitely reusable).

The Zerocoin generalization - a false trail

GK14 has a final section that talks about how the '1 out of many proof' construct, which we already discussed in detail, can also be used to make an instantiation of the basic "zerocoin" primitive (this idea was new at the time; Green et al. published the original Zerocoin paper in 2013 to some fanfare - though it was originally a very inefficient construction, the demonstration of principle that one could use a fully zero knowledge system to allow transfer of cryptocurrency coins captured, understandably, many's imaginations. However it's a complicated picture of course, because the idea of a private digital cash using blinded signatures was already very old, but that is not quite the same thing.).

In GK14 they write a kind of generalization of this concept in abstract. A coin can be minted, a list of coins can be maintained, and in spending, a serial number can be revealed (along with a proof), which prevents future double spend without revealing the link to the original minting event, for that coin.

The one out of many proof (specifically, the proof that one of N commitments commits to zero) in GK14 allows this construction to be instantiated naturally. Effectively, the serial number S is just a blinding factor applied to all the commitments.

Superficially, it looks like this already gives what you need for something like RIDDLE - because you get a spendable-once-only token for a given commitment (which as we discussed, can indeed just be a public key; a commitment to zero with randomness corresponding to the private key).

But it does not; the construction requires that the key be created fresh for each coin minting. If you use a public key for your taproot utxo for example (private key is 'r'):

\(P = rG\)

and then apply S, the serial number, as a blinding factor to this commitment at index 'l':

\(C_l = SH + rG\)

(to fill out details: all commitments from other parties have their own S values; so subtracting only your S value from each of them results in a list of commitments only one of which commits to 0, that's exactly what the paper shows how to prove), then when the verifier checks the validity, they will remove the blinding that you applied (your spending event precisely consists of revealing this blinding factor S), and will then see the exact value 'P' as per the above equation, which means that they see the exact public key which they can easily then look up on the blockchain.

So in other words, this kind of system cannot be used privately with pre-existing public keys, only with freshly created keys in minting.

The line of reasoning, "oh well; in that case, I will delegate to a fresh key for minting, with my pre-existing key" is actually circular: you need to be able to sign, privately, over the group of starting keys, to make the delegation!

So we'll go back to the idea of creating a "tag" or "key image", as used in the LSAG designs we have discussed before (and concretely used in RIDDLE).

Intuitions behind GK14

Before we continue with the more efficient construction, let's step back and ask ourselves what was the insight that allowed these logarithmic sized ring signatures at all.

The most important thing a ring sig is doing is hiding the choice of 1 from a group. This can be thought of as hiding the position of an item in a list of items. This is really just hiding a choice out a list of (very small) integers (i.e. not the same as hiding a private key, which is an enormously large integer). So the insight is that, if you completely ignore the other aspect of digital signatures (that the private key must be known to the signer (soundness) and must not be revealed (zero knowledgeness)), and just focus on that first point, it's almost trivial that logarithmic scaling can be achieved - you can refer to numbers in logarithmic scaling - that's exactly what digit systems do! (In case you never thought about it - when I write 1,000,000 I do not need a million times more characters than to write 1).

The tricky part is to "glue together" that logarithmic representation, with the digital signature aspect mentioned above. That's where the Kronecker delta trick was so crucial, though it looks a bit strange - it lets the verifier check every commitment/pubkey and only know that behind the 'encryption' provided by blinding, one of the polynomials created matches up, and all the other terms in the polynomials are nullified out by the cancellation/cleanup commitments.

More efficient 1 out of many proofs

In 2015 Bootle et al. (basically, the UCL cryptographers of whom Groth was the lead) wrote a paper on Short Accountable ring signatures based on DDH (henceforth Bootle15), which has two main parts: the second is using El Gamal to create an accountable ring signature (where a coordinator/trusted party can open the signer after the event; we're not interested in that here), but the first part focused on optimisation and generalization of the "proof of 1 out of many commitments is to 0" trick that was originally in GK14.

n-ary instead of binary

The main optimisations are, first, that the construction allows you to express the size of the ring as:

\(N = n^m\)

, that is, to use any base n, not only 2 (in GK14, we expressed the index of the real commitment as a set of bits, and then committed to the bits).

And second, more important, but related: instead of sending a list of commitments, per bit, you send a matrix Pedersen commitment to a matrix of Kronecker delta function values (so each matrix value is 1 or 0, but we'll shortly explain below how those values are calculated).

(What is a matrix Pedersen commitment? We've previously discussed on this blog how a vector Pedersen commitment works, and a matrix is no different: we have a NUMS base per matrix position (row, column) and a single additional randomness term. The homomorphic property still applies, for reasons that will be obvious if you understood the vector case).

So, in GK14, we had a very simple concept: we will just prove that all of a list of values are bits (that is, all the commitments are to a value 1 or 0). But Bootle15 has to make a slightly more sophisticated sigma protocol. It has to prove:

In this list of values, all of the values are 0 or 1, AND only one of them is 1

To do this algebraically, you convert it into a requirement that:

\(b_i(1-b_i) = 0 \ \forall i \ \land \sum_{i} b_i = 1\)

The algebraic reasoning for how to ensure this via the blinded responses in the sigma protocol, is very similar to that seen in our Commit to a bit blog. We will multiply blinded responses \(f\) by \(x - f\) and preload commitments to the terms of the quadratic polynomial that must be cancelled. For details, see Fig 4 in Bootle15.

You might ask: why is it required to prove that exactly one item in the list is 1, while the others are zero?

The reason is that we want to use the above-mentioned \(\delta\)-functions to represent the matching of digits between the real (hidden) index and all the other indices; this will allow us to repeat GK14's trick.

For example, suppose we start with a ring of \(N=81\) items and set \(n=3\) and \(m=4\), and we set the real index to \(l=17\). We would write that index in base 3: 0122.

Next, we form commitments to lists of 3 delta values for each of the 4 digits:

\(\left( \begin{smallmatrix} \delta(l_0, 0)&\delta(l_0, 1)&\delta(l_0, 2)\\ \delta(l_1, 0)&\delta(l_1, 1)&\delta(l_1, 2)\\ \delta(l_2, 0)&\delta(l_2, 1)&\delta(l_2, 2)\\ \delta(l_3, 0)&\delta(l_3, 1)&\delta(l_3, 2) \end{smallmatrix} \right)\)

Notice that in each of these 4 lists of three, exactly one must be 1 and the rest 0, as mentioned.

Concretely, \(l_0=2\), \(l_1=2\), \(l_2 = 1\) and \(l_3 = 0\) as per the above base 3 representation of 17. So only the entries which match those, are 1:

\(\left( \begin{smallmatrix} 0&0&1\\ 0&0&1\\ 0&1&0\\ 1&0&0 \end{smallmatrix} \right)\)

These 12 values are committed to in 1 Pedersen matrix commitment, and the responses, after receiving the chanllenge \(x\) are:

\(\delta_{l_j, i}x + a_{j, i}\ i=1 \ldots n-1, j=0 \ldots m-1\)

The \(a_{j,i}\) terms in this are additional blinding factors that are committed to in another matrix Pedersen commitment (this follows the 'Commit to a bit' pattern, notice). They are random, but the rows of the matrix (corresponding to each digit) add up to zero, to allow the verification to work.

Notice that this is no longer one group element, but \(m(n-1)\) scalars, so here, 8 scalars. (The reason it's 8 not 12 (we don't send the i=0 values) is omitted for brevity).

With this in place, the remaining step to get from that, to "prove 1 of out of N commitments is to zero" is basically as GK14. In Bootle15, they are instead proving "1 out of N El Gamal ciphertexts is an encryption of 1" but logically it's almost exactly the same; we construct polynomials, as before, like:

\(p_i(x) = (\delta_{l_0, i_0}x + a_{l_0, i_0})(\delta_{l_1, i_1}x + a_{l_1, i_1}) \ldots (\delta_{l_{m-1}, i_{m-1}}x + a_{l_{m-1}, i_{m-1}})\)

(think of \(l_j\) as meaning the jth digit of the n-ary representation of the integer \(l\)).

There is one such polynomial for every member of the ring, so in our case, 81 such polynomials. Of these, only the correct index 17 will be "complete", it will be a quartic polynomial since all 4 of those delta functions will be 1, because all 4 of the digits in the 3-ary representation of that specific index, will match. All the other 80 polynomials, corresponding to other indices, will be of smaller degree, from 3 down to 0, depending on how many digits match.

While this is complex, I am deliberately skipping a fair amount of detail - because it is essentially the same logic as GK14; it's just a kind of "souped up" version.

Scaling of Bootle15

On ring signature size: GK14 has size \(7l+1\), where I use short hand \(l\) for logarithm base 2 of the ring size \(N\), and also where I assume (as is true in the secp256k1 context), that field elements require the same space usage as group elements.

I won't go into detail of calculating Bootle15's size, mainly because it's not creating the same kind of object as we discuss in the next section (a linkable ring signature). But it's worth observing at a high level that the size (I still assume that field and group elements have the same size, here) depends mostly on a factor \(nm\) as per \(N = n^m\), which can be rewritten as \(n \textrm{log}_n N\)or changing base,

\(\frac{n}{\textrm{log}_2 n}l\). So for fixed ring size \(N\), the most efficient option is the one that minimizes the function \(\frac{x}{\textrm{log}x}\)which for continuous variables is always \(e\) (as can be seen with high school calculus) - no matter the base of the logarithm. In practice this means values like 2, 3 or 4 will be the best choice, and not much larger (simple example: if we want ring size 64, choose 2^6, not 8^2; the latter has nm=16, the former has nm=12).

On computation and verification cost: since we iterate over the above polynomials, we are always going to need, crudely, around O(N) processing. This can be offset both by batching and multiexponentiation, however.

Both space-efficient and linkable - Triptych

The MRL guys - Goodall and Noether, in Triptych extend the above ideas further, to add extra terms into the sigma protocol so that we can make such a logarithmically-scaled ring signature also have the property of linkability. Basically they take the starting point of Bootle15 (Fig 4 in that paper), and add an extra commitment, so that the verifier can verify a linking tag.

Some "under the hood" mathematics for Triptych

The additional terms for the key image

Here we define some alternative NUMS generator, as usual, in this case \(J\), and calculate the "key image" \(U=rJ\) where \(P = rG\) is the corresponding "real" public key for secret signing key \(r\).

As well as providing, as part of the commitment step, the commitment to all the non-leading polynomial terms, blinded with values \(\rho\):

\(X_j = \sum_{i=0}^{N-1} p_{i, j}M_i + \rho_j G\)

... we also send commitments to the same blinding factors for the shifted base point:

\(Y_j = \rho_j J\)

This means we get to do an additional verification step for the shifted base point, in the following nice trick:

\(\left(\sum_{i=0}^{N-1} \prod_{j=0}^{m-1} f_{j, k_j}\right)U - \sum_{j=0}^{m-1} x^j Y_j - zJ = 0\)

Whilst there are a few algebraic steps I'm omitting (see the paper), the most important point is that that term \(\sum_{k=0}^{N-1}\left(\prod_{j=0}^{m-1} f_{j, k_j} \right)\) will actually always evaluate to exactly \(x^m\). The next aside discusses that, for the curious.

Why is the linking tag coefficient x^m?

It seems likely there's a more insightful explanation, but note that:

There are \(N\) polynomials; each take the form:

\((x-a_{p,q})(x-a_{r,s})..(a_t)(a_u)..\)

(the indices are arbitrary).

There are any number from 0 to m terms of the type that include \(x\), and the same for the constant ones (where the \(x\) term is zero-ed out, because the delta function was zero). So the degree of the polynomial is anything from 0 to m. It's m if and only if every digit of i matches every digit of l, the secret index. And it's 0 if none of the digits match (but remember - a degree zero polynomial is not zero, it's a constant).

Since the list is complete (\(N=n^m\)), we include every possible combination of digits.

Next, note the general fact about polynomials: the sum of the roots of the sum of several polynomials is equal to the sum of the sum of the roots of each polynomial (sorry.. English makes this hard :)).

Now, since the list of polynomials spans all possibilities, it's easy to see that the correct digit match will occur \(n\) times, for each digit. So the total sum of the roots will span all values. But as was noted above, the sum of each of the rows of the \(a_{j,i}\) matrix is zero. Hence the sum of the roots of the sum polynomial is zero.

Next, consider the constant term in these polynomials. Each one will be a product of \(m\) terms and there are \(n^m\) of these m-wise products, each one travelling "down" the matrix, so to speak. Thus we can factor out any of the rows from the sum of all these terms, meaning the total sum of all these products is zero.

If a polynomial of degree \(m\) has the sum of its roots zero, and the product of its roots zero, it follows that all the roots are zero, and the polynomial is identically \(x^m\).

Summary of technical procedure

This aside complete, we can talk at a higher level: the basic story is that we send all these polynomial factors (evaluated at \(x\)), each of which is \(f_{j,i}\), a random number because it is calculated as \(\sigma_{j, i} x + a_{j, i}\), i.e. blinded the same way a standard Schnorr signature is. Then the verifier reconstructs the *total* polynomials, one per ring element, by multiplying those together, and then scalar multiplying them by that ring element.

Then he appends the "cancellation" terms \(X_j\) that reduce it to just \(x^m\) for the secret signing index \(l\), and reduce it to zero for all the other ring members, and compare it with the blinded response \(z\).

In Triptych this process is just repeated for the linking tag (basically!).

Practical usage (scaling)

Using a base of 3, we can list sizes of ring signatures for possible values of \(N\).

exponent N size of signature
3 27 618
4 81 748
5 243 878
6 729 1008
7 2187 1138
8 6561 1268

(technical note: add 32 bytes to each value, for the key image).

You could try it out using the toy Python code in my gist. See the help at the top of the file, but it lets you create ring sigs with random keysets. Also, notice: the algorithm itself only takes up maybe a couple of hundred lines of code.

As you can see, the log scaling gives a powerful result here (and it's also a bit smaller than GK14, as discussed, especially with an optimal base of 3).

You might naturally think, "cool, let's do 100K keys or even more; it should still be pretty small". That's true. But the computation and verification costs, as discussed above w.r.t. Bootle15, are approximately linear in (N) and that means this will become impractical somewhere, depending on your coding efficiency. My guess from playing with the code in the gist above, is that with properly optimised code/algos, we can stay sub 1-3 seconds for these operations as long as we're in the 10K region or perhaps a little larger. But that's already a huge practical achievement, in my opinion (and .. I'm guessing).

Batching verification is discussed in the Triptych paper, which can be powerful here, but it will not be relevant for a use case like RIDDLE, I suspect.

Finally, to complete the story, here is a base64 encoded signature over 6561 keys, taking only 1268 bytes, in which I used a taproot key that I own from signet, somewhere between block 65376 and block 69450:

A1o7rjCKHp+SskFhdPxrb/y0ThBb31QZ5h+HfME0RI06A3gJJEgEGQz1r9e7ExKvLB9Md
9cvWzdnfMeUdbEWrjhuAnVEkOUd1Kh23VMft8qIyJozWUGzi31r1Nf+bostBM94AwCtPB
NpKS/A8P9uDRswYj68oodjt4h7z7FD8yKKnePwAm1KreAaMu4LpGkTNPc8YWp6HalEloo
9EK26PrbFLbMxA3orj96BSgfXnBB2m4II9ENa+taEtNkno0I9GukS1a6dA2403BAC/w4I
A2NbLJufCilpSAluIow9b+kxHlq5kqe/A5j35Y+HBANs1B4YaKxeDczae9bthibo1dvtm
KsRdZ9DAuhz5YUY2priqCHYFQL0/heDN6E4bOWlN5/fgGO6HMpQAtdhnzIFiZEhBJ/bAC
mU+rxmdw7GO4VX7JvPAxEb5dR6Aq9KZxexxmmi0BVguwyx6bD0uHxD7U7GEpkFQ0eRGoi
VA3d78myUJDA74ZWCX5lvgEaF8eNY7L2nqByAj0GiEW2tAmbQnnGo8P1Abo9WmGJPzgEe
XILcqKWMCXcZuRMOjkzRAuBamBH73Hf0F6w8E/YhilcnTccKYb2mWp+p06U16JkQAyNju
vTxC6vloS5TV0WPMy/bIjUw9FwoBFdIAua5pk6/A7E9UpoKfg97kQXt707qfP5jOwj9+G
puKQoT5e6Kq7JzA9b5h00UO3RRxrU+x/dp58ZTESqf0lgZOUv6++pIr7qgAujxddeheGN
UVWVZi5U2Brsn5tyjcc0eMHkgeYbTS5YwAryTlI0RJVGIkJQm5Ngv8vQinTWs0N0fA3J2
I5rT0yycAjVvLQkuoHO/qQqVYS37CFOfaE0ng+AWqXECNZaS70lpN6v9VClqNAysjSTOY
mWXjNWUhOaqeDB8XPnK2rySOFLnrTeGDBpvZPGUYQTV06XUMI15JP/AfNifdN8sP504h7
n8rh+PRsKbfAgb9WDTTfW5NOc6cOoMGol5PKO76j4XrNL/uWwcnPNVBTrE8jkDmNeDHll
kyHZFos2YsYycHAZCjbTgdlJVCvImCcz2eQdaYY2nWujrF4wuK5QEyVK2RXwI8eqC8ZgX
q4Fgt65Q/42+3tUY6dwZZ9hrFOR5LwHnaI0NM+GStqwSD80Jl+17xel7crQo15H8WRnAj
NZiATBGM90dwq+lMYxI6v8qtu9ZNKlWQUaIU5cu5plYuKTHz+h8QVpJnG3TEsMJcj5bbQ
H4dQocmSrOa3q7plgYLLFzbdPhGrMrZigBPh6f0ZJlkCFSy6t38tGbw1AiqCrn64ByUv2
E4t7y+V0ewvZLACshiOacgCXor3GMpg3f7tRq8pQwciq0iqltqi0Z06mIXLKhsCwRW+q3
TNulNwe485cNYBhiWl8FwyT2CxDYVTWVmZ7exMdYFggBuV7OPly3K8Od8Z0AF2OiZLFP1
uz5VY3DgAsZ9VSdfMbnAOnZx2Btzfq9/LEnY0fWxsaOUgWWV4BnUYaLtWdMmJAiO2bB92
liKe5G2hmAgyibci7jebR7WksehkKV3O9j2HJ6ddET8w+5eEYjqOFQeWLKvfL78OqdKCJ
hiPuu5VCrxw1oqGTAdHjRQrEKIG0zZWZqfyyEvm1ZHIu2yKSiVlSu2bG7fKoAvJyg1pP+
XaeYiQzE+KJavWiboEMjsPyoKdhVd4nl8ck=

with key image:

02b2500336c92b3ad3b32c922da8d46b79e021c58f107c3039b9434248d6f4458f

, and I can't make another signature over this set of keys, or any other set of keys, without reusing that key image.

Read more