Zero Knowledge Cryptography and Anonymous Engineering
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Subtitle |
| |
| Title of Series | ||
| Number of Parts | ||
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/61792 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
FreewareShared memorySpacetimeSoftwareVolume (thermodynamics)Open setMultiplication signNeuroinformatikComputer animation
02:30
Physical systemArithmetic meanWindowComputer programComponent-based software engineeringTheorySoftware developerComputer architectureSoftwareFreewareAbstractionBasis <Mathematik>Ideal (ethics)CodeComputer animation
04:27
NeuroinformatikBand matrixPeer-to-peerWeb 2.0SoftwareCryptographyComputer fileMachine visionComputer hardwareAlgorithmBasis <Mathematik>CollaborationismPanel painting
05:52
Keilförmige AnordnungDew pointTable (information)State of matterExpressionBoolean algebraFinite-state machineObject (grammar)PolynomialCategory of beingRootRange (statistics)Parameter (computer programming)outputPerformance appraisalFunctional (mathematics)NeuroinformatikRing (mathematics)MappingSet (mathematics)Algebraic closureFunction (mathematics)Database transactionWell-formed formulaCodeMultiplication signResultantComputer animation
11:44
Dew pointPolynomialStatement (computer science)Point (geometry)Multiplication signNP-completeInterpolationCommitment schemeComputer programAlpha (investment)Hash functionLine (geometry)Performance appraisalPhysical systemSet (mathematics)Object (grammar)Category of beingMultiplicationNumberExpressionNichtlineares GleichungssystemLemma (mathematics)Right angleTheory of relativityCommunications protocolAdditionNeuroinformatikRandomizationComputer animation
19:44
RootInclusion mapHomomorphismusNumberHash functionAdditionNetwork topologyPrimitive (album)1 (number)Level (video gaming)Server (computing)BefehlsprozessorSet (mathematics)EncryptionEntire functionLogarithmCartesian coordinate systemPhysical lawRight anglePower (physics)Field (computer science)DiagramAsymmetryElliptic curvePublic-key cryptographyRootMultiplicationStatement (computer science)Inclusion mapFunctional (mathematics)Point (geometry)Invariant (mathematics)Point cloudCodeForm (programming)Object (grammar)AbstractionNeuroinformatikComputer animation
27:43
ModemGamma functionRandom numberColor managementNetwork topologyMaizeExecution unitCodeGame theoryRootCloningoutputInterior (topology)Digital electronicsElectric currentTerm (mathematics)Network topologyStructural loadDigital electronicsCodeFormal verification
28:12
Function (mathematics)Inclusion mapEncryptionDatabase transactionNumberSoftwareMessage passingTelecommunicationFunction (mathematics)Coefficient of determinationNichtlineares GleichungssystemWebsiteSoftware developerCryptographyAtomic numberEndliche ModelltheorieCommunications protocolProgramming paradigmNeuroinformatikBlogOnline chatMobile appKey (cryptography)Beat (acoustics)Computer fileType theoryDifferent (Kate Ryan album)Open sourceoutputCommitment schemeIdentity managementHash functionDeterminismSign (mathematics)Interface (computing)BEEPNumbering schemeNetwork topologyMereologyVotingLattice (order)Sheaf (mathematics)Food energyInclusion mapComputer animation
36:12
Error messageInclusion mapFunction (mathematics)Interrupt <Informatik>PasswordComputer networkRootGoogolUsabilityInternetworkingComputer animation
36:42
CodeCryptographySoftware developerBit error rateSynchronizationBit rateVotingGodImplementation
37:21
Discrete groupDemonVotingInterrupt <Informatik>Error messageReliefPasswordInterface (computing)GoogolFingerprintVotingImplementationOnline chatDemon
37:50
MassEmailAdvanced Boolean Expression LanguageEncryptionOpen setConfiguration spaceOnline chatComputer fileSource code
38:20
Program flowchart
Transcript: Englisch(auto-generated)
00:06
I'm gonna talk about the new breakthroughs that are happening in cryptography, the opening doors to unexplored spaces.
00:21
Yeah, let's raise the volume. Yeah, I don't know how to do it. I think the staff, but I will try to speak louder. So the free software movement and Linux
00:42
at one time had power, it had vitality. But then somewhere along the way, we started to play catch up. We started to try and follow the competition.
01:03
Linux on the desktop never happened. The once great browser, Firefox, its market share dwindled to zero. Even this conference, which has the best minds
01:26
in free software community, is funded by surveillance capitalism, Google, Microsoft. In this talk, I want to talk about how we can escape the death trap
01:43
and create the new paradigm of computing. This talk is dedicated to Peter Hintians.
02:42
Peter Hintians was from Brussels and he was a programmer who, well, he wasn't born in Brussels but he lived and he died in Brussels and he really embodied the ideas of what elegant abstraction means.
03:04
Abstraction is something which done poorly creates complexity, done well empowers the software developer. But he was not just a good developer who he made, for example, ZeroMQ,
03:21
which is really interesting conceptualization about how we could build distributed systems. But he was also a theorist on creating free software, the social layer on creating free software communities. He taught us that free software
03:41
is more than just having the code being accessible, but it's an entire philosophy. And when we create the good, elegant abstractions, that enables us to create software that's composable while not contributing complexity.
04:02
This is the basis of how the Linux architecture is created, there's components and rather than like in a Windows system where there's a system 32 filled with hundreds of DLLs, there is a component which people can modify. And in our projects, we try to embody his ideals.
04:23
We try to carry his philosophy. Also, everything that we use today, the concept of the sockets, the processes,
04:41
the file system, was invented in the 70s with Unix. Since then, nothing has fundamentally changed about computing. And when they created Unix, their vision was something that would enable
05:03
deep collaboration between communities. And the infrastructure that they created, the software, ended up becoming the basis of the web. But at the time, they couldn't take their vision to its full conclusion.
05:20
They didn't have the algorithms that we have now, like around peer-to-peer and consensus and cryptography and so on. There wasn't huge network bandwidths. The resources in the hardware weren't as big.
05:41
And since its invention, not much has changed. So, okay. So, what is a zero-knowledge proof?
06:06
So, if I have a simple function, and I call the function on a set of parameters or arguments,
06:21
and I produce a result, the return value of the function, if I want to show to you that this value that I've computed from the function is computed from some parameters that went into the function, then normally, the way that you do that, like logically,
06:44
is I would have to give you those input parameters, and you have the function, and you would compute the function yourself and get that result at the end. And then be able to verify that the result is what it claims it is.
07:00
So, for example, in like a Bitcoin blockchain, you're doing transactions, and everybody verifies the transactions that the computation is to advance the state machine to the next state is correctly done.
07:28
And there are two very interesting properties of ZK proofs. So, first, the ZK proof is succinct. So, what that means is the actual proof object that proves the computation
07:41
that has been run on the values is very small. It's smaller than the input parameters that go into the function. Like, you'd expect that it would be some big proof, but actually, we save computation. When you want to verify that, you save computation compared to
08:03
if you would compute the evaluation of the input values, what we call the witnesses yourself. So, the proof size is small, and the time to verify the proof is very small compared to actually computing it,
08:20
and it can be anonymous. So, there are some values that you put into a function to get a result. You don't know what S, X, and Y are. You know Z, you know food, but you don't know S, X, and Y. And that enable us, they give us a very powerful technique in our arsenal, in our toolkit of anonymous engineering.
08:45
So, this is the general schema of ZK proofing. So, you have a proof function. So, that's how we generate a ZK proof. So, you have some private values,
09:02
the input values to your function, foo, and you have the output of the function, which are your public values, and you create a proof. And then I give to you the proof, and you want to verify the proof, and you have the public values from the evaluation of that function, and you get true or false back.
09:21
Okay, so how does it work? Like, this is obviously greatly simplified, but just observe this property. If I have polynomials, and I add two polynomials, and then I evaluate the polynomial, that is the same as evaluating the polynomials
09:43
and adding them together. This is due to what is called mathematically the homomorphic property of the function that maps from the ring of the polynomials to the ring of the closure.
10:02
And it works as well for multiplication. So, just remember that homomorphic property, and then what we do is that function, foo, we do this step called arithmetization. So, any code that you write,
10:22
we turn that code into a set of polynomials. So, how do we do that? Well, imagine A and B are Boolean values, either one or zero. So, how can we turn those into arithmetic expressions? So, if you notice with those formulas in the top left
10:44
and these tables on the right, if you do the calculation, you will get the same thing. As long as A and B are zero or one, when you perform those formulas, they are the equivalent to those Boolean expressions.
11:02
And if you want to enforce, just as a side note, that a value S is in a certain range of values, for example, zero or one, well, it's just the same as saying S minus zero multiplied by S minus one is equal to zero,
11:21
which is the roots of the polynomial where it would evaluate to zero. And that will be a degree two polynomial. There'll be no other roots of zero there. And so, we have that function foo, which if you remember,
11:42
where was it? It was here, this one. If S return X times Y, else return X plus Y. And how do we arithmetize that? Well, you can see below that we have Z is equal to S X Y plus, open bracket,
12:01
one minus S X plus Y. Both of those are equivalent. So, we've taken piece of code, we've arithmetized it as a mathematical expression. So, then,
12:21
we can use the Schwartz-Zippel lemma, which is, rather than having to give you all of these huge degree polynomials, you know, like, depending on the number of equations that you're checking,
12:42
there is something that we can do where we can just evaluate a polynomial at one point. That relies on the Schwartz-Zippel lemma. So, let's pretend that we have two polynomials that we're trying to check a multiplication of.
13:02
If you remember in the first slide, we had FG evaluated at alpha is equal to F of alpha multiplied by G of alpha. So, these polynomials, if you notice, they're constructed so that they
13:21
intersect through a certain number of points here. So, the red one goes through one. X equals zero, the red one goes through one. X equals one, the red one goes through two. X equals two, it goes through minus one. X equals three, goes through one, et cetera, two, three, two.
13:44
So, that's a Lagrange interpolation of those points. And the yellow one, likewise, does the same, but for zero, two, two, zero, two, one, three. So, you can imagine those are the lines of our kind of proof or program
14:03
that we're trying to enforce. So, the first one might be that we wanna check that zero times one is equal to zero and two times two is equal to four and two times minus one is equal to minus two. So, how do we construct that proof?
14:20
Well, if we multiply the points together, like so, we get a new set of points. And then, because these polynomials are degree six, to create the polynomial that comes from multiplying these two polynomials, we need 12 points which are multiplied
14:44
from both of these, but I've only done six here. So, then we have these points and we interpolate, we draw a polynomial interpolating those. So, this is the new polynomial we get, the pink one.
15:02
And, if you remember this relation from earlier, we now have this polynomial F G. And therefore, if there is a protocol where a random point or a random X value is selected,
15:24
then it's sufficient to prove that this evaluation at this combined polynomial F G of alpha is equal to evaluations
15:41
of the other two polynomials multiplied together. And therefore, you can be sure that that pink one is the multiplication of all the individual points because the random point and the probability of you being able to preempt that is basically nearly zero.
16:02
And so, we can actually see here, if we look at any two points, the top two is the red and the yellow one
16:22
and the white one is actually the multiplication of the two points and the purple one is the purple one. So, we've actually created the polynomial which have this property at all points along it.
16:40
And, because it has this property, it's sufficient just to pick a random point and check that that's true. And, there is another puzzle piece which is the polynomial commitment proof.
17:02
So, essentially, you can create a commitment of a polynomial which is like hashing a polynomial and you don't know what the polynomial is. So, this is where the zero knowledge property come from. And, then there's objects representing a polynomial
17:25
in your system and anytime you can create a proof using the polynomial which has this statement on the right which says that the F is a commitment
17:43
or a hash of this polynomial F and Z is equal to an evaluation of F at S. And so, that's what that open does is it creates this proof on the right and then I can give you this proof
18:05
and I can give you the commitment to the polynomial which is just a hash of the polynomial essentially. And, you can verify that whatever polynomial is inside of F is the Z is equal to F or evaluator S.
18:22
And, the same principle is true for addition. So, we have multiplication and we have addition which means we can construct any NP complete program inside of ZK proof. Also, another technique is multi-party computation.
18:43
So, in NPC, so with a zero knowledge proof
19:06
I can compute a value, I can prove a statement about some values that I hold but maybe sometimes we need to compute
19:20
or other people need to be able to know certain facts about other actors in the system and maybe they don't have the incentive to create a ZK proof or to prove statements about values that they hold. So, that's where we use another technique that's called MPC.
19:41
And, I will show you how we can do addition of values with MPC. So, Alice has some number, some secret number, 110. And, Alice and Bob has some other number, 777.
20:01
And, Alice now splits her number randomly such that those numbers add up to 110. So, if you add them up it would be 110. And then, sends them to each of the servers. So, none of the servers know what Alice's number is
20:21
but they know parts of it. They can reconstruct it if they collude but we're assuming they don't collude. And then, Bob does the same thing. He sends his numbers. And now, when we want to compute an addition of the values, each of the server will add the values together.
20:42
And now, they get these new values. And, if you look, those values added together when they reconstruct it is the answer of adding the two private values together. And, multiplication is similar but slightly more involved.
21:04
But, also it's possible. So, MPC is another powerful technique. Also, we have homomorphic encryption. So, a very simple partial homomorphic encryption is simply this function
21:21
which is elliptic curve multiplication. So, if I have two values and I add them together and I multiply them by the generator of an elliptic curve or just some point on the elliptic curve, that is the same as taking the value multiplying it by G and then adding it to the other value
21:43
multiplied by G. So, homomorphic encryption, the original idea in the 80s was there's a cloud and anybody can put values into this cloud but they're encrypted. And then, other people can compute answers
22:03
encrypted for a certain public key. So, you can use this to make computations on secret values. From a kind of abstract level
22:23
to like, there is this new emerging field of anonymous engineering. So, we can compare it to other forms of engineering. So, for example, when we have software, we write these instructions that run on a CPU and execute.
22:44
And, when we do cryptography, we try to use deep mathematical laws to try and create primitives or schemas but the anonymous engineering is actually using those different techniques like the ones I just showed
23:01
or other ones like VDF or hash function, public key, asymmetric crypto, et cetera, to try and come up with schemas that enable certain forms of applications with invariants to hold. So, let's give a first practical example
23:25
which is I have a set, I have a set of values and this set is just represented by a single hash and I wanna prove that my value is in this set of objects
23:43
so, to do that, we have to construct something called a Merkle tree. So, let's say we have eight values and what we do is we take two values at a time. So, we take the first two values
24:03
and we hash them together. So, we get a hash of that and let's represent that by A and now, let's hash the next two values. We get another node, B and then we hash them together and we get another node.
24:21
So, we get this kind of tree which the root R represents the entire set of values and this is a simplified diagram. Normally, these might be 32 layers so, two to the power of 32 values will be in the tree.
24:41
So, for example, we had V1 and V2 and we hash them together and we get A and likewise, we have V1, V3 and V4. We hash them together and we get B and then we hash those together and we get AB and then, you know, we do the same.
25:05
We do the same on the right hand side and eventually, we get to R. Now, if I have some value, any value, but let's say, I don't know, V5. Which one's V5? This one. And let's say, we also have R.
25:21
How can I prove to you that I have, that V5 is in R? Well, what I need is a pathway to be able to get to R. So, what does that pathway mean? So, for example, if I give you V6,
25:40
then we can take, we can hash those together and we get C and then if I give you D, and we hash those together, then we get CD and then if I give you AB
26:02
and we hash that with CD, then we get R and then I've proved to you that V5 is in R, using, instead of needing to give you all of the items, I just give you a logarithmic number of items. I give you a smaller number of items. So, it's faster, it's used as a technique,
26:21
but it can also be used to create an anonymous inclusion proof. So, we can anonymously prove that there is some value in R and we can even encrypt that value or we can prove other statements on that value. So, I'll show you some code, how that looks like.
26:41
Maybe I can put this mic somehow, like this. Yeah, that would be great.
27:04
All right, I need to speed up, but here is the proof. You see the Merkle root at the top. We're saying, and there's a pathway and we're proving some values in the root and then we're re-encrypting the value
27:21
and we're exporting it and, yeah, hold it, yeah. And to compile it and then I compile the proof like this so it's compiled and then I have, sorry, it's here.
27:42
I have the code which actually computes the Merkle tree with the value, but then also, you see, includes the ZK proof code and then creates the witnesses
28:04
and where is it, and then loads the circuit and then constructs the proof here. So, now we get a proof and then for the verifier we do here, we verify the proof. So, we can just run that like so.
28:30
Ah, okay, no internet, but anyway, let's not worry about that. Haven't got, okay.
28:43
So, then we can use that to create anonymous voting. So, how do we do that? Well, we say, when we create, construct the people who are gonna vote,
29:03
we create something like a coin and there's like, you generate a random serial number that's private and you just create this commitment to it and then when you wanna use up your vote, then you burn the coin and you make that public, that secret value S, which means you can't ever generate
29:23
the same thing again because that value's deterministic and then you just, you prove that there is a C that's a hash of S and that C is in the tree using the previous inclusion proof. And so, how do we change that to do anonymous payments? Well, it's very similar, except now this coin,
29:43
not just being a hash of S, it's also a hash of a value for the coin. So, it's two and four, which are owned by Alice and then when we wanna spend that coin,
30:01
that Alice has, then we reveal those serial numbers and we can compute the partial homomorphic encryption of the two and the four and we create this transaction with two outputs and we create the two new coins
30:22
like we showed before in the previous slide, but we also wanna prove that the value that goes into the transaction is the same as the value that goes out and we do that using homomorphic encryption like we showed earlier and you see here, we've got the two plus the four is equal to the three
30:41
plus the three. So, there we go. Then we can do atomic swaps with different types of assets. So, Alice constructs her input and one output sending to Bob. Bob takes a transaction, adds his input
31:00
and one output sending to Alice. Bob also signs the transaction. Bob signs and sends the finalized transaction. We can also do something where you have a network with anonymous spam protection. So, you have Shamir's secret sharing scheme and normally, so basically with this,
31:27
you have this evaluation. I'm gonna go fast now and when you wanna send a message, you compute the message M, you compute this X and Y and if in one epoch, you again create another message,
31:45
so you're spamming the network, then you get these values which using the equation on the first line, you can compute what A zero is and A zero is actually your secret key
32:00
and so then that means that whenever you try to send another message to the network in any other epoch, now you've lost your account, you can never send but it also means that messages are unlinkable. So, you have unlinkability. We can do anonymous auctions using MPC.
32:22
So, Alice has bids $4, Bob bids $6, they do a computation, they compute who's the winner. We can do anonymous WikiLeaks. So, I have this thing .jpeg and then there's a protocol
32:44
where I've said that this is, I've made some claim about what this file is and it selects a random chunk from the file and then we verify, yep, that file is what it claims it is and then there's an auction on the remaining chunks and the winners of those auctions
33:03
decrypt the remaining parts and then the file is decrypted. So, if you go to DarkFi website and you go to the Docs section,
33:22
we have, where is it? So, go to the website and there's also a blog called Insights. We have our own peer-to-peer anonymous chat. There's like no concept of identities.
33:43
So, if you go to the Doc, there's a section called ILCD and we have a weekly meeting every Monday. Also, there's a crypto section, Zcast section, Testnet guide, you know, we're looking for good devs as well.
34:08
So, conclusion. So, we missed the mobile and the desktop.
34:23
Will we also miss the crypto renaissance? This is like our best chance to capture value for development. Like, this is the biggest problem with creative people is they create value. They don't necessarily have a way to capture some of that value back.
34:40
We now have techniques to do that. We were promised this future of computing in the 90s, you know, the interface is beep, beep, beep. Whatever happened to that? Never got it. Right now, our phones, they're filled with all these dog shit electron apps.
35:06
Like, that's a failed paradigm. Like, we're literally trying to copy Silicon Valley. I'm optimistic that now people are actually going, actually, no, Linux is different. We're like distinct, we have our own energy,
35:21
but we need to rediscover that. We need to create something that's new because their model is about capturing users under surveillance capitalism to extract value from them. Our model is we create infrastructure. We create economic value for our networks to become strong and as a movement, grow powerful.
35:41
It's a different way of thinking. Open source was a mistake, you know? Like, we discarded the beating heart of what gave us energy so we need to conceptualize the computing paradigm. So, you know, like, let's build something new, like, actually, inventive.
36:00
So if I have a couple of minutes, I'm actually just gonna show our website so I can show where to find docs. Sorry.
36:31
Okay, I guess there's no, no internet.
36:45
All right, let's give a tour of El Docsos. So here, there's book. I talked about peer-to-peer distributed IRCD.
37:03
You see there, instructions. Where is it? There's also crypto section, you see here. And also, implementations.
37:22
There's a ZK explainer and also implementations of most of the major ZK algos. And also, probably more interesting for you guys, the Zcast stuff, like how anonymous voting works and also anonymous payments.
37:45
All right, I just showed the distributed chat. You just run a daemon like that. Open my WeChat, bam, here we are. There's like encrypted channels as well.
38:02
You just set in your config file an encrypted channel and then we have a chat. See if I can chat with other people. So, yep, that's it. That's my talk. Thanks very much.
Recommendations
Series of 9 media