Monero Village - Bulletproofs deep dive
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 |
| |
| Title of Series | ||
| Number of Parts | 335 | |
| Author | ||
| License | CC Attribution 3.0 Unported: 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/48722 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
DEF CON 27306 / 335
8
9
12
14
32
38
41
58
60
61
72
75
83
87
92
96
108
115
128
132
143
152
158
159
191
193
218
230
268
271
273
276
278
295
310
320
321
335
00:00
CryptographyMultiplication signImplementationException handlingMathematicsBitMusical ensembleExistenceProof theoryCircleSheaf (mathematics)Computer animation
01:47
EmailProof theoryDatabase transactionComa BerenicesBlock (periodic table)ChainLogicPersonal digital assistantFormal verificationSynchronizationScale (map)Digital electronicsStatement (computer science)QuicksortCategory of beingProof theoryDatabase transactionPlastikkarteDifferential (mechanical device)Commitment schemeNegative numberGroup actionNumberOrder (biology)String (computer science)Range (statistics)outputMathematicsContext awarenessPoint (geometry)Cartesian coordinate systemOpen setGoodness of fitSynchronizationSummierbarkeitFormal verificationAsynchronous Transfer ModeBitHybrid computerMultiplicationCase moddingFunction (mathematics)Instance (computer science)Extreme programmingInternet service providerCuboidComplex (psychology)Constraint (mathematics)Content (media)Data storage deviceBinary multiplierMultiplication signStapeldateiLoginPattern languageComputer animation
06:59
CircleLibrary (computing)ImplementationMultiplication sign1 (number)Process (computing)Range (statistics)MultiplicationGodComputer animation
07:41
Range (statistics)Statement (computer science)Product (business)Interior (topology)MultiplicationHypothesisMusical ensembleSlide rulePoint (geometry)InformationComputer animation
08:15
Local area networkVisualization (computer graphics)Link (knot theory)Group actionSkalarproduktraumVector spaceProof theoryInverse elementInterior (topology)Multiplication signLengthSpacetimePrime idealScalar fieldRandomizationMultiplication2 (number)Scaling (geometry)QuicksortInheritance (object-oriented programming)SummierbarkeitGame theoryBulletin board systemProduct (business)Special unitary groupVideo gameMusical ensembleBuildingComputer programmingOpen setWeb applicationPlanningComputer animation
10:59
Term (mathematics)Port scannerRepresentation (politics)SkalarproduktraumMereologyLine (geometry)MathematicsProduct (business)Computer animation
11:46
CASE <Informatik>Scalar fieldOperations researchPotenz <Mathematik>MultiplicationFormal verificationProof theoryMathematicsCryptographyRange (statistics)Product (business)Interior (topology)Binary fileRing (mathematics)Cellular automatonSkalarproduktraumMusical ensembleStatement (computer science)Physical systemCuboidConstraint (mathematics)PlanningRange (statistics)Prime idealRoundness (object)Logical constantState of matterProof theoryNumberSpacetimeMixed realityTerm (mathematics)Point (geometry)LengthLine (geometry)Metropolitan area networkPosition operatorEvent horizonMultiplication signMathematicsScalar fieldBlock (periodic table)Binary codeBuildingLevel (video gaming)LoginTheoryVector spaceCASE <Informatik>Commitment schemeOperator (mathematics)Computer configurationForm (programming)Order (biology)Core dumpParameter (computer programming)Selectivity (electronic)Representation (politics)TrailFormal verificationProcess (computing)Computer animation
18:43
Binary fileVector spaceProof theoryData structureScalar fieldStatement (computer science)Block (periodic table)BuildingMotion blurRandom numberIntrusion detection systemProduct (business)Nichtlineares GleichungssystemTerm (mathematics)BitCategory of beingRange (statistics)SkalarproduktraumStatement (computer science)Multiplication signVector spaceForm (programming)BuildingPower (physics)Proof theoryDifferent (Kate Ryan album)Sampling (statistics)Subject indexingCombinational logicSpacetimeFile formatExponentiationDigitizingParameter (computer programming)Slide ruleCommitment schemeCommunications protocolComputer configurationMathematicsMetropolitan area networkInterpreter (computing)Student's t-testProper mapMultiplicationMusical ensembleMathematical optimizationAbsolute valuePhysical systemCuboidNumberForcing (mathematics)MappingMereologyControl flowParticle systemSoftware developerSoftware testing2 (number)CurveOrder (biology)WordArithmetic meanProduct (business)Computer filePhysical lawState of matterSuite (music)Endliche ModelltheorieDisk read-and-write headCompilation albumComputer animation
25:39
Term (mathematics)Nichtlineares GleichungssystemCommitment schemeStatement (computer science)Product (business)Interior (topology)Programmable read-only memoryBlock (periodic table)BuildingVector spaceScalar fieldHomomorphismusFormal verificationProof theoryFaktorenanalyseRange (statistics)LoginCommitment schemeRange (statistics)Formal verificationStatement (computer science)NumberRight angleMultiplication signSlide ruleMereologyBlack box2 (number)Rule of inferenceSpeech synthesisSkalarproduktraumNichtlineares GleichungssystemCategory of beingProduct (business)Element (mathematics)Group actionParameter (computer programming)DivisorFile formatScaling (geometry)MathematicsQuicksortSquare numberSpacetimeMusical ensembleCircleVideoconferencingKälteerzeugungResultantEstimatorMetropolitan area networkBuildingNeuroinformatikComputer animation
32:36
Proof theoryCryptographyDatabase transactionRange (statistics)Proof theoryStatement (computer science)MereologyComputer animation
33:10
QuicksortCategory of beingSkalarproduktraumComputer animation
34:08
Menu (computing)Range (statistics)Statement (computer science)Interior (topology)MultiplicationMaxima and minimaMusical ensemblePrime idealMathematicsInheritance (object-oriented programming)Library (computing)Right angleComputer networkCommunications protocolCASE <Informatik>Slide ruleTextsystemComputer animation
36:51
Vector graphicsRange (statistics)Interior (topology)Product (business)Scalar fieldRandom numberHash functionCollisionScalar fieldRandomizationRoundness (object)MultiplicationBlack boxMultiplication signInstance (computer science)Vector spaceComputer animation
38:04
Database transactionConstraint (mathematics)MultiplicationVariable (mathematics)WeightLinear mapSystem programmingPhysical systemProof theoryoutputEmailCommunications protocolSlide ruleMusical ensembleCodePhysical systemGroup actionExtension (kinesiology)Complete metric spaceCommunications protocolSpring (hydrology)Constraint (mathematics)Computer programmingVariable (mathematics)Multiplication signDifferent (Kate Ryan album)Representation (politics)SpacetimeInheritance (object-oriented programming)Ferry CorstenCombinational logicDigital electronicsMathematical analysisType theoryoutputDatabase transactionProof theorySummierbarkeitBitQuicksortBackupTheoryComputer animation
40:30
Database transactionState observerComplete metric spaceCodeoutputProof theoryConstraint (mathematics)Physical systemQuicksortType theoryRight angleMultiplication signMultiplicationRandomizationFunction (mathematics)SummierbarkeitCommunications protocolMereologyGroup actionVariable (mathematics)Range (statistics)Database transactionFormal verificationCommitment schemeNegative numberValidity (statistics)Heegaard splittingMaxima and minimaSpacetimeMehrfachzugriffFilm editingEvent horizonPulse (signal processing)NumberConfidence intervalRing (mathematics)WebsiteOpen setReflection (mathematics)Process (computing)Touch typingSound effectSoftware developer1 (number)Game controllerCASE <Informatik>Order (biology)Computer animation
Transcript: English(auto-generated)
00:00
Hello everybody, welcome to the last day in the Marrow Village. If you are just wandering in here, you arrive just in time for a talk by the world famous Taffy Heung, who is going to give us a deep dive into bulletproofs. Now, if you are a swimmer, you may be familiar with diving deep, but diving into mathematics is a lot different,
00:25
and you come out just as exhausted, but it's a different form of exhaustion. So Taffy here is going to very gently, gently take us through bulletproofs, and I hope you all come out the other side smarter, because all of this is going to go online.
00:40
Taffy, please, please be gentle. Hi, I'm Taffy. For some context, the implementation of bulletproofs in Rust, both at Chain and Interstellar, and we have the fastest implementation in existence,
01:02
and so I feel like maybe that makes me qualified to just tell you a little bit about how bulletproofs works. So maybe before I begin, and what I want to hear. So what I submitted to this talk was, let's go really deep into the math of bulletproofs.
01:22
We can do that, we can also do lessons on that, and talk more about the things we've built on top of bulletproofs, what other people can use it for, maybe composals of what Marrow might be able to do. So maybe by a show of hands, how many people are here because they really want to just get into the math? Oh, okay. Afterwards, I'm happy to talk about other exceptions over that.
01:49
So, I guess we should talk about why we care about zero null proof. So for some of you, this might be redundant, but I'll just cover some basic ground first.
02:03
So zero proof is a way to make a proof about, sorry, a proof that a statement is true about some input without revealing what that input is. So that might be a little confusing and abstract. One example of a zero null proof is a range proof. So a range proof is a proof that a certain number is in a range, usually like 0 to 2 to the n,
02:24
and you can show that this proof is true without revealing what your number is. So instead of revealing your number, you're like, that's a secret, you make a commitment to that number, and that commitment is binding, hiding, and you can show that commitment to someone without revealing your secret. So, we'll talk a little bit more about range proofs, actually a lot more about range proofs,
02:44
so don't be too intimidated to get it. So, and then of course, sum to the number that's equal to your outputs. So here you can, you know, usually check 5 plus 4 equals 2 plus 6
03:03
if you're not making any extra money out of an error. And if you wanted to make this confidential, there's many ways to do it. It's just called confidential transaction proposed for Bitcoin, and a broken way to do this would be to use an additively homomorphic commitment,
03:24
and just say, well now we're just going to do a, b, c, and d, which are blinding and hiding for our secret values. And then you just check that a plus b equals c plus d, and this will be true with very high probability if and only if your interior secret values actually sum up to the same value.
03:43
Now, can anyone tell me why this is broken? Anyone? What was that? Yes. Of the way that you have your commitment scheme,
04:01
but that's like such small probabilities that that's actually like not something that we're going to worry about. What about you? Exactly, yeah. A negative number, this also still works,
04:21
a blockchain financial transaction. So we don't want this to be possible, and for those of you who want to understand the math better, it's actually a negative number mod p, and so what this is basically equivalent to is an extremely large number in your Bitcoin order group,
04:43
and so those two statements are equivalent. So you could be allowing someone to spend negative one dollars, or you could be allowing someone to spend like p minus one, where p is very large. So that's just to be technically correct here. So what we want to do is to insert a proof, a range proof, that all of your secret values are in a certain range.
05:03
So from zero to a number that's still smaller than your prime over group p, then this will make sure that you don't add any like negative, weird numbers. So in the blockchain context, obviously,
05:22
there's many other ways to use blockchains too, but you're probably interested in the blockchain applications. And why do we care about bulletproofs? So bulletproofs is a pretty cool paper, came out in 2017 from Stanford, and it gives us a lot of what we really want in a blockchain context.
05:41
So what we really want is a constrained proof size because all the nodes have to receive a proof and verify them, and bulletproofs provides a pretty constrained proof size open. So once again, you have to have all nodes sync up,
06:02
and bulletproofs provides fast verification that also allows you to batch, which means that you can verify multiple proofs in parallel more efficiently, and aggregate, which means you can combine multiple proofs into one proof that they are all correct. And then lastly, this is a really nice property and sort of a big differentiator from ZK smart strings.
06:23
You can have ad hoc logic that doesn't require a trusted setup. So if you wanted to create a custom smart contract, for instance, you don't have to have a trusted reference string that requires a setup string. So that is a big thing that is appealing about bulletproofs, and a big pain point of using ZK snarks.
06:42
And I know a lot of more recent zero-knowledge proof protocols, such as K-sharks, which is great, the H is for hybrid, actually gives you a hybrid mode between bulletproofs not requiring trusted setup, and ZK snarks requiring trusted setup. So that's just a good fun side note. So basically at the time when we were looking to implement zero-knowledge proofs,
07:03
bulletproofs was the thing that definitely made the most sense. So what we wanted to do was, well, first of all, understand the paper, so we don't just blindly implement it. And then second, once we understood, then implement it using really best practices and existing libraries and Rust, and then make it a good performer.
07:21
So you all hear, this is what I use in range. And then it just gives us this massive multiscalar multiplication. So I would like to hopefully give you a path between step one and step two.
07:45
And when we find one or two of just wipesies of how we get from step one to step two, and being like, no, that's wrong. No, that's still wrong.
08:02
So if you listen to this talk, you want more information, or maybe you see this talk and you're confused about some of the points, we actually have... Also, I will post the slides online, too, so don't worry about finding all of yours. And then, oh, the last thing is that
08:21
after we understood all of the math, Oleh Link was this graphic genius and made a cyberpunk visual. And so hopefully you all understand all these transitions. They'll be really great. Well, most of them.
08:42
So this is actually not unique to Bulletproofs. This was introduced by a previous paper out of UCL. And Bulletproofs just made this three times more efficient. So what is an inner product? An inner product, for instance, C is an inner product of A and B. It's the sum of entry-wise multiplications of...
09:10
...represent vectors. So here, C is the inner product of vector A and vector B. So, naively, if you wanted to prove to me that C was equal to the inner product of...
09:24
Like, just shout out some ideas. Like, super naive. How would you do this in, like, O and space? Yeah, you could just send vector A, vector B, and scale it C to me. And then I could do...
09:41
I, as the verifier, could do the multiplication. So obviously this proof would be O and space, because, you know, N is the length of A and B. The thing that Bulletproofs introduced is a way to do this in O and time. Oh, sorry, O and space. So what this looks like is first you start out with vectors A and B and your scalar C.
10:02
Then you split A and B into two halves. Then you take this random scalar, X, and right now you don't have to worry about where X comes from. All you have to know is that it's not zero, because if it's zero, then you're like, excuse me. And it's totally random. Like, you cannot predict it a third of the time. So you take this random scalar, X,
10:22
and you multiply it by the first half of A, and you multiply the inverse by the second half of A. Oh, sorry, the second half of A. And then you get this A prime, and then you do this thing with B prime. And A prime and B prime are now half the length of A and B. And then you then get this big mess for C prime.
10:44
But actually watch this. This is sort of magic. Because of the way that we selected the inverse and not inverse for A prime and B prime for X, we can actually simplify this mess of C prime to be equal to the inner product of A low and B low plus the inner product of A high and B high plus some part.
11:02
And wait for it. This, the inner product of A low and B low plus the inner product of A high and B high is by definition an inner product group, the same thing as C. So do you see what's going on here? That line is actually the same thing as C above. Wow.
11:20
Wait, okay. Can you raise your hand if you understood that? If you don't, I can repeat. Because I feel like this is a really critical part of understanding. Okay, cool.
11:41
So first, we appreciate that the math works here so that you actually have C in your representation and then you have the scarfish. So the scarfish, you have to just commit to it. So let's call the thing underlined in green L and the thing underlined in red R and then we send those two, so there are two points,
12:01
we send those two points to the verifier and you just say C prime is equal to the C from the previous round plus X squared plus times L plus X negative two times R. So, in summary, this is one round and in one round, what we have achieved is that we have half of C
12:23
and committed to two points. That's a constant number of points. So from theory of computation, if you do a half of C every step and every step you do a constant number of commitments, then you have O of N
12:45
Now you can, for very long vectors, A and B, be able to make a proof that C is the inner product of A and B in O of log N space instead of before the only options
13:01
were O of N space or something like on that order of four performance. We have A prime and B prime are just single scalars. You send the single A prime and B prime and the verifier tracks that
13:20
to your base case C prime. Cool. So that's a recap. If you are the prover, now you have received one L and one R point for every one of these steps. And then you've also received the C prime. So you effectively reverse this process
13:40
and you build up what every higher C is using the L and R from that previous step until you get to the top level C. And if your top level C is equal to the C that you expect, then you're like, wow, this all verifies perfectly. So that is our core building block here. Before we move on, any questions about this X
14:28
to all of the things in the previous round so that you only get this random X once you've committed to everything before so you can't actually maliciously choose this X. So that's something that I didn't talk too much about. If you're curious about it, I'll explain more.
14:41
I also didn't talk about how operations are actually over commitments over the plain values. In all of these examples, I just used plain A and B, but we actually are actually homomorphic commitments in the exact same way that in our earlier example for a confidential transaction, we actually offer commitments and we check that they add to the same thing else.
15:03
And then the last one is just a performance thing. We use multi-explanation to have faster verification, but that's not fundamental to the map. It's just like, cool performance, speed us. All right, so we just covered the inner product building block and now we might go with A and B.
15:26
Whatever. By applying math and photography to a statement, we can represent effectively any statement as an inner product.
15:41
If you don't believe me, I'll show you with this range proof and then I can also show you with constraint system proof, which therefore reduces from any statement.
16:01
Zero is less than or equal to B, which is less than two to the N. We want to do some things to it, TBD, until it's in the form of C equals the inner product of A and B, such that if C is equal to the inner product of A and B, then with a very high probability, V is in range.
16:21
Cool. Is everyone on board with this solution? Any questions so far? All right, so now we're just looking at this in between math and photography stuff. All right, so the first thing that we want to observe is really interesting. So if V is in range from zero to two to the N, then V must be a binary number of N.
16:43
So in this example, if V is three, V is definitely in range between zero and two to the N if N is four. So you must be able to represent V as a binary number. Cool. So as the mental exercise, you can try this with any value,
17:03
between zero and two to the four, and you'll see that yes, indeed, it does work. And then if you try to represent something larger, so two to the four plus one, you'll see that you cannot actually fit everything in these boxes. Cool. So I think this is pretty cool, first of all.
17:21
Any questions so far? Anyone, if you don't come along with this, you'll be lost for the rest of this explanation, so I want to make sure everyone's on board. Don't be embarrassed. It took us at least a month to figure this out, so we now have V of three,
17:42
this is our secret value, and we want to prove that it's between zero and two to the four. What we do is we call the binary representation of V, A sub L, and this is like what the paper uses, so it's trying to be consistent. And then we can say that V is the inner product of A sub L and two to the N.
18:01
Remember, inner products can be of any two vectors that are the same length. So here we're actually representing V as an inner product. So maybe some of you are thinking, whoa, this V is an inner product statement. Are we done? I wish. That would be really nice.
18:20
No, we're not done. And it makes me really interested to do something malicious with your A sub L. Does anyone have any guesses as to what you can do with the selection of A sub L that would be malicious, that would allow you to make a value that's outside of the range but for whom this inner product argument is actually true?
18:42
Yes, exactly. A sub L, nothing about the statement V equals the inner product of A sub L and two to the N requires that A sub L is actually just binary. So if we had like last digit or the first digit is 100, then V would be a huge number, but this inner product statement would still be true. So what we want to do,
19:01
oh, whoops, I actually have slides to walk through all of this. There we go. So here's some examples of V. A sub L has to be binary. And the way that we do this is we create an A sub R. A sub R is the bits of A sub L minus one. So if it becomes 0011,
19:21
then A sub R is negative one, negative one, zero, zero. So this has a really like neat property where if you multiply every bit of A sub L with the corresponding bit of A sub R, then if A sub L is only bits, then you'll get a vector of zeros. If A sub L is anything else, for example 100, then you'll get like 100 times 99,
19:42
A sub L is zero. So this is actually a statement that makes sure that A sub L is comprised of bits. So now we have three statements, one being like the vector is actually A sub L times inner product of two to the N, the second one being A sub L times A sub R equals zeros, and the third just being the definition of A sub R.
20:02
Cool. So how's everyone doing? Does this make sense? Why we have to use A sub R? Cool. And obviously you can combine steps two and three into just like one statement without defining A sub R, but we tried to do that and then realized that that breaks the protocol so you have to separately make a commitment to A sub R. So just trust me that you actually need to do
20:22
all three of these things. Cool. So now we have come up with these three statements. With these three statements, if they're true, then your original range statement is true. So before moving on, I need to...
20:42
The same way that... Here let's just pretend we have E equals zero, then you can actually combine these two statements together into one statement using this random challenge
21:01
by saying A plus BX equals zero. And as long as X is random, then with extremely high probability this last statement will be true. Does this make sense? Let's see. And can someone tell me if you do not choose zero?
21:37
And that will also give you maliciously a way to, you know, circumvent this double combination step.
21:45
So we just have to check X is not equal to zero based on the probability that it's equal to A divided by B. It's so small that we don't even worry about it. And in practice we sample X from like two to the two hundred fifty five minus nineteen so like we're fine.
22:00
Don't worry about it. Cool. So we can actually do this multiple times. Don't be scared. This is the same idea. We can do this multiple times by instead of using X once, we can multiply the first one by nothing, the second one by, well here, so on and so forth.
22:23
And the reason that we're allowed to do this is because if Y is random, then taking Y to a certain exponent is also going to give you something that is random in that space. And so the way that we write this combination is the inner product of A and B times
22:40
the vector of Y to the N equals zero. So it's a little bit weird syntax, but that's just how we write it. And so since the proof is like inner product of A and B times Y to the N equals zero, it's true with very high probability. All right, so this is our building block. I'm just showing you how you can use
23:01
random calendars to combine a bunch of statements together. And hopefully you'll also like have a little inkling of like, hmm, this is interesting because this last statement is actually an inner product statement. So like remember a range proof or a range statement and ending up with an inner product, this is actually a tool that we'll use
23:22
to get to that inner product. So the way that we'll use this tool is that the verifier gives us a random form scaling Y. So this comes from somewhere. In practice, it comes from the the option of your mistake. Then we rewrite the second two statements because the first statement is already like in the inner product proof form.
23:42
So we're like already pretty well along there. But the second two statements, is we use this Y to combine the statements together into inner product forms. So once again, originally, the second statement, a sub l times a sub y equals zero, the vector zeros, is actually
24:01
multiple statements. It's n statements, one statement for each index of a sub l and a sub r. And what we have to do is we're combining all of those statements by multiplying each of those statements by a different power of Y. And then we're combining them in one inner product argument. So this is just a format that we write it in once we combine it with Y.
24:22
And then we do the same for the second one. We use this challenge scalar, or we do some crazy stuff and end up putting it into three inner product arguments,
24:49
times the challenge scalar. Zero equals
25:02
v, I'm sorry, zero equals a sub l. And what you do is you just multiply and then you end up with now you have that is one.
25:26
So we're really good at arguments. And then we do some maths that's basically just algebra, you just take some things apart and rearrange them. And then you end up with
25:41
this inner product statement equals this thing on the right. So if you're curious about what that maths is, we wrote it up here. It's really not I promise you it's not actually that interesting. But look here on the right, this is exactly the format that we want. We want an inner product argument where
26:01
the thing on the left, inner product with the thing on the right equals C. So we can essentially represent, we can think of as A, and the thing after the comma is B, and the thing after the equals is C. So to recap, we have, or sorry, LOR, I forgot
26:22
the letters that I used. But to recap, this is our thing. We broke it up into three separate statements that must all be true if this range is actually, if the vowels are in range. And then we apply these like, scalars such that we could rearrange all three of these into
26:40
one inner product argument. And that is why we wanted to use the inner product of LOR. And going all the way back to the beginning, now that it's in this inner product argument, if and only if this inner product is true, then the B is in range. And we have a really efficient way in O of log N to prove that this inner product
27:01
is true. Cool, so comes Pulsar rule. Yeah, and then this is LOR T of inner product. So, before I move on to how this is actually kind of oversimplifying it, I want to make sure that this simplification makes sense to everyone.
27:24
Yes. So the first, this Y, and we took the Y to rewrite each of these. So now we have like, here on the right-hand side,
27:41
here on the left-hand side, we now have three statements and these three statements have to be true. But we want some way to like somehow smush all of these three statements into one statement. So like, if we're not looking at a equals zero, b equals zero, c equals zero, and you want to represent that as just one statement, what you can do
28:00
is you can take like a random number, z in this case, and you can say if a plus b times z plus c times z squared equals zero, then with extremely high probability, we know that all are three individual statements. So that's exactly what we're doing here.
28:21
We're multiplying the second thing by z, multiplying the third three by z to the zero or nothing. And then that gives us the equation on the right. And then we just move the phi to the end. Just because it's figured out. Cool, does that answer your question? Okay, so I'm not wearing a hat, yeah.
28:43
Ooh, let's open it on the next slide. The same way that the previous slide was like.
29:06
So delta is not any, doesn't have anything that's secret in it. The proof and the variable are both what's in delta. And that's how it gets abstracted into this delta nice thing. So it doesn't contain anything too important or too secret.
29:22
Cool, any other questions? Alright, so that's actually a good segue to the next section, which is that as you might notice a sub l minus z on the left hand side of the product, if you were just to send that to the prover, oh sorry if you were to send that to the verifier
29:41
the verifier would just learn what your a sub l is. And then you're like, oh, I know your secret. So that's actually sort of silly. And so what we actually do in practice is we make commitments to what's on the left and the right in our product. And then really nice, and then also this is where time speaks. So like these are things that we
30:02
actually want to make commitments to and we will send over the commitments instead of sending over the plain secrets. What does that look like? Maybe first I should, you know, review what commitments are. So if you have an additive label more of a commitment, like I mentioned way at the beginning of the talk, then if you have some secrets
30:22
a plus b equals c plus d then your commitments will also maintain the additive property of those secrets. So then the commitment of a plus the commitment of b would be equal to the commitment of c plus the commitment of d. And then similarly this also extends to multiplication by scaling. So if you have two times e equals f then two times the commitment of e equals
30:42
the commitment of f. So you don't have to worry about how this works, you can just sort of treat this as a black box. If you do want to learn about how this works, it's really just a Peterson commitment, and it's really straightforward, you're just multiplying by a group element and adding a blank factor times another group element that's orthogonal. It's not that crazy, you also have to dive into that more.
31:00
But if you want to treat this as a black box, then basically all you do is you start out with the thing on the left of the inner product the thing on the right of the inner product, and the thing on the left side, and you just make commitments to them. And if the inner product of those commitments is true, then if they extremely have probability, then the secrets inside those commitments are also true.
31:22
So, that's really nice. That's a perfect commitment scheme. And in practice, so, let's see yeah, so as a recap, we can send
31:40
over the fearing that we're revealing any secrets. So things that I have in this work in detail, once again they're just Peter's commitments, and I also that's part of how the commitments work. So if you want a deeper dive into that,
32:00
I'm also happy to talk about that, but it's okay just reading it as a black box and being like yes, that is how it works. You know, we understood the paper, we implemented it. And then these are I forgot to include that it's less than one millisecond per 64 bit verification.
32:20
And that's even without fetching. So if you were to fetch, you can get multiple verifications in even the last time. And so, yeah, that's our numbers. And I think that's all of the material that I have for today. I'm also happy, you know, how we use this
32:40
and other ways to abstract you know, bullet proofs over arbitrary statements instead of only over range proofs. So maybe let's start with some questions let's see what I'm doing on time. Let's see what other things that we want to hear about.
33:05
Anything that you missed, I'm happy to review. Yes. Yes.
33:33
Here, you actually get the x of the b low to, sorry, the x that is x inverse attached to the b low to cancel out the x
33:42
and a low. So here, let me just like review how this works. So if you have the inner product of this with this, what you're actually doing is you're taking this and that gives you and then here
34:00
that gives you a high inner product of b high. And so that's just a nice sort of reconstruct c from c prime. So good question. That is a really cool trick.
34:25
Question about math.
34:41
Sorry. If you want to just like review the slides it's doc and channel dot dot dot r s slash bulletproofs. If you just go to that you can navigate all the notes. The distinction between
35:00
is that the doc is the API and all the doc. And this is a really nice thing that we have because we made everything in Rust. We have like Rust documentation formatting. In arbitrary
35:36
statements, I'm super excited
35:50
that in the paper, we
36:21
uninteracted. And then as an influencer, you're like and so we're this transcript protocol that enemy made a use case for a library that takes
36:41
care of all of that for you. In practice for papers, when you implement the fiat engineer, the actual things that the pooper gives the verifier, you're like we just pass this and then we take the challenge from it and then we use the challenge such as, sorry, here's an example. If you wanted to take a challenge
37:00
like here, for instance x, like where does this x come from? And a lot of times a lot of the time people just like take for example the vector b and hash it and get the challenge x. But this is sort of easy to misuse or easy to get a little bit
37:20
if you're doing multiple rounds of this. And so that's why it's effectively a black box where you're like, I put my randomness in here, and I get some randomness back that I have guarantees about that it's actually fully random, that's the main sub-rating, you don't have hash collisions, things like that. So that's
37:42
actually, and so that's where we get x from. We actually use the real transcript to get x, to get the y, to get the z for all of these random challenge scalars. Yeah. Anything else? Anyone want to hear about any other things? I can also be done.
38:06
All of this is the cloak protocol. Nice slides for that. Sorry.
38:29
Back up. So bulletproofs is not just a range-proof protocol, where you can take it
38:42
and then make a proof that it is correct over some inputs while keeping those inputs secret. It turns out to be a constraint system. They're really easily translatable from one to the next, but it's a little bit easier to talk about.
39:00
So you have a multiplicative constraint, which is you have three variables, and you have the additional secret variables. And you also have a linear constraint, which is like some linear textbooks. So these are like those constraint systems. You can actually represent anything that is
39:25
officially verifiable. So by this I mean any NP-complete program can be changed into or represented as a constraint system. So that's pretty nice. Final side note is that the extension that lists constraint systems is the things that
39:47
NP-complete to p-space. So if you're a theory nerd, that's pretty fun, but if you're not, it doesn't matter. So I have a constraint system.
40:03
So what we wanted to do was to make a confidential assets protocol. And confidential assets is like a confidential transaction protocol because you want to keep the asset types secret. And so like manually if you're just like
40:21
then you have to specify which assets are the same and that will reveal which assets are which over enough analysis. So you can't just sort of sum together things the same way that I do for confidential transactions with one asset type. So what we came up with was sort of multiple gadgets that we composed together.
40:40
So on the right hand side we have a range gadget, that's what we call it, which is a collection of constraints that basically make sure that the variables in the constraint system are in range. And then we add some new ones. So collection of constraints that make sure that the inputs
41:01
and the outputs are valid reordering of each other. So you can't just introduce a new input, introduce a new output. Then the shuffle gadget will fail. And then there's a merge gadget which either merges two inputs into one or just moves them without altering. Same with splits. So a split either splits one item into two or it
41:20
moves the two inputs to the two outputs without altering it at all. I guess before I jump have some way to prove that your input to this protocol and your output to this protocol are valid
41:40
you want to prove that your inputs have been rearranged in such a way that the asset types are preserved but without creating or destroying value. So this is really tricky because you can't actually reveal what asset groupings you have. So this is like a fine like, it took us a while to
42:01
We first, we grouped these gadgets together such that any you know, transaction output should be able to satisfy this collection if you're why this is the case or like how you actually prove this.
42:29
You would put these together into the same chunks. So you could use the shuffle to reorder this such that your dollar amounts
42:41
are together and your yen is at the very end. Then you will merge your dollar amounts into one lump sum and you'll merge your yen and well you will because you only have one. And then you shuffle it such that your non-zero value is at the very top of the shuffle for each asset type and then this is the part that's like, hopefully the intuition
43:00
is that you then split your lump sum into whatever your target amounts are. So here all the target amounts are 3 yen, 6 dollars and 3 dollars so you'll take your 9 dollars and split it into 6 dollars and 3 dollars and the yen you'll pull down because it's just one output. And then just to preserve the randomness of your output, you'll shuffle it one more time. You'll apply a range
43:21
check to it to make sure that none of these are negative. And then you get your your outputs are valid then you should be able to do this successfully. If your outputs are not well, suppose that one of your outputs you wanted to make it 100 dollars you would not actually be able to correctly satisfy all these gadgets. One of these gadgets would be like, wait, where does this extra money
43:42
come from? This is not a valid constraint satisfaction. So this is the intuition for how it works. And then for a verified a verified actually only receives these commitments and inputs and commitments and outputs and it can't tell what happened within each of the gadgets because all of it is just like commitments to the verifier but all it can do is verify that yes indeed
44:02
this proof succeeded or this proof failed and then you know valid or invalid transaction. So that's the intuition for cloak and I think the important thing to illustrate here is like this is just one of many uses for the Bulletproof Constraint System API that you can come up with. We just sort of make this by hand after figuring out what would make sense
44:21
as a way to build it and anyone else can basically make their own protocols and proofs as well. So that's cool. That's my little add-on. I think I have time Do I have time for questions maybe? Or should I just... Alright.
44:48
And so basically the output of the third and we just want between zero to the nth of some large n. For example if then
45:08
$100 is one of the outputs and then negative another negative number to make sure that we can't make extra money.
45:21
Sorry. You can ask more questions afterwards and then cut off. Thank you for all of your attention.