Skip to content
Quilibrium

About Quilibrium and Components

Level 2: Storage and Compute

Let's say you want to ask Stacy to prom, but you're scared she might say no. She's part of your group chat, and knows how to send messages, but she could totally reveal your question and make fun of you and the embarrassment would be too much to handle! Sally's no quitter when it comes to cool math tricks, so she devised a plan: rather than just let people live in social purgatory, why not use some simple arithmetic to make it so everyone says who they'd ask out, but only if that person also says yes!


Algebra class has come in clutch again, and we've learned the concept of prime numbers, exponents, and modulo arithmetic (a.k.a. clock math), so we all have the right tools in the toolbox to pull off Sally's latest stunt. Here's how it works:


Sally comes up with two prime numbers (p, q), one much smaller than the other (In cryptographic terms, this mathematical trick would require a 256 bit prime and a 3072 bit prime) and the larger, subtracted by 1 (p-1), must be a multiple of the smaller (q). Then, a value (g) is calculated from the formula g = 2^((p-1)/q) modulo p. Sally shares p, q, and g with everyone in the group.


Now, everyone has to come up with their own random value (a) for each person, and use exponentiation and modular arithmetic to calculate a value they share (A):


A = g^a modulo p


Between all participants, they each send a message to the group with their A values for each person. Then, once everyone has sent their A values, each person calculates a new random value (b) and responds to each individual with a yes or no, but in a special way (B):

  • if no, B = g^b modulo p

  • if yes, B = A * g^b modulo p


Receiving this B, the original sender of A must encrypt their answer with the following key

  • encrypt the response to B saying "no" with key = B^a modulo p

  • encrypt the response to B saying "yes" with key = (B/A)^a modulo p

and send both values.


Receiving these encrypted messages, the sender of B must calculate a key = A^b modulo p, and attempt to decrypt both with the key (only one will work), and then they will have their answer. The sender of A remains blind to which choice B made, and B remains blind to whatever the other message said. A perfect way to avoid any embarrassment, except personally feeling let down in the worst case. (Oblivious Transfer and Lookup)


Now everyone in the group is super chill about properly deleting messages, but what if there was something that folks needed to hang onto for a certain period of time, and prove they still had it? That encrypted message may be super long, like another embarrassing TMI outburst from a former member of the group. We might want to hang onto that for old time's sake. How do we prove we still have it, and kept it this whole time?


Sally once again had a math approach for us all: turns out, squaring a special kind of number you'd see in that quadratic formula, that we all had a terrible sing song trick to remember, can't be done quickly. It is, as it turns out, very slow to do, slow enough, that you can use it to measure the progress of time, and with no shortcuts. Only once that value has been calculated, can you quickly verify it is correct. This trick only required a few more clock math moves plus the notion of imaginary numbers (numbers with a square root of a negative value), and it was to calculate what is called an imaginary quadratic integer. Using a formula to square these special kinds of numbers, we can just keep squaring, forever. The output values at given times allows us to produce two values, the output squared value for a given number of iterations (squarings), and an intermediate value produced over the series of squarings to quickly verify the output value and duration taken.


All we need is an input, and boy is that TMI outburst some input. Running this through the squaring function, we can prove how long it's been around by just taking an output sample of this math trick. (Verifiable Delay Function).


But maybe we have a lot of these that we're hanging onto, and proving all of that is simple, but it takes a lot of info to verify, because you need not only the proof output, but you need the whole TMI outburst being proven over. What if you want to prove you've held onto it, only show a small portion of it, yet still prove you still have the full message?


"Sally is burying us in math, maybe that's the next outburst", you think to yourself. But right on cue, Sally does have an answer: That trick we used earlier to create group keys has a similar trick for proving sections of a message. If you take equal, small chunks of the message, and treat it like a number, you can use that as a y value, it's chunk number as an x value, and produce a formula that lets you specify the chunk number to get the chunk of the message you want. Now you can take that formula, and prove time over those values (coefficients) instead, and use the output number to select a random chunk to reveal (KZG Proof) – you have both proof you've held onto the data for a given amount of time, and you can exclusively reveal any section of data you need or whether it's changed (Proof of Meaningful Work).

"I swear to god if she says 'Polynomial' again..."

(Important note: KZG Proofs rely on an additional computational hardness component that is omitted from this ELIHS)

Reference