Latest / Monero Talk / A Holistic Security Analysis of Monero Transactions with Dr. Julian Loss (Monerotopia23)
Transcript
- 1 00:00:01,720 --> 00:00:23,400 [Applause] 2 00:00:07,840 --> 00:00:28,560 [Music] 3 00:00:23,400 --> 00:00:28,560 all right up next we've got Julian 4 00:00:28,960 --> 00:00:33,360 loss 5 00:00:31,039 --> 00:00:37,280 can you see my screen 6 00:00:33,360 --> 00:00:39,320 yep okay well thank you for having me um 7 00:00:37,280 --> 00:00:41,920 so I'm 8 00:00:39,320 --> 00:00:44,480 gonna yeah 9 00:00:41,920 --> 00:00:47,079 so sorry did you want to do an 10 00:00:44,480 --> 00:00:49,199 introduction or should I just begin oh 11 00:00:47,079 --> 00:00:50,920 yeah we we've had people just begin 12 00:00:49,199 --> 00:00:54,160 pretty much 13 00:00:50,920 --> 00:00:57,320 I I'm sorry I'm a volunteer I don't know 14 00:00:54,160 --> 00:00:59,199 too well who is who yeah I'm just I'm 15 00:00:57,320 --> 00:01:00,480 tasked with just like you know trying to 16 00:00:59,199 --> 00:01:02,519 make this go 17 00:01:00,480 --> 00:01:04,879 sorry yeah sure sure before I go off but 18 00:01:02,519 --> 00:01:06,960 but anyway thank you so um I'm going to 19 00:01:04,879 --> 00:01:10,000 be presenting a very recent work of ours 20 00:01:06,960 --> 00:01:11,799 called a holistic security analysis of 21 00:01:10,000 --> 00:01:14,240 Monero transactions and this is Joint 22 00:01:11,799 --> 00:01:16,320 work with uh my colleague Kus kmas and 23 00:01:14,240 --> 00:01:20,000 my student bentic 24 00:01:16,320 --> 00:01:22,320 vagna okay so um obviously I'm going to 25 00:01:20,000 --> 00:01:23,680 be talking about Monero and more 26 00:01:22,320 --> 00:01:27,280 specifically I'm going to be talking 27 00:01:23,680 --> 00:01:28,520 about its um transaction scheme which is 28 00:01:27,280 --> 00:01:31,920 called 29 00:01:28,520 --> 00:01:33,280 ringct and um you know just to give a 30 00:01:31,920 --> 00:01:35,000 broad picture of what I'm going to be 31 00:01:33,280 --> 00:01:37,119 talking about Monero as you probably 32 00:01:35,000 --> 00:01:40,200 know because this is Monero Topia is a 33 00:01:37,119 --> 00:01:43,079 privacy Focus currency it has a market 34 00:01:40,200 --> 00:01:47,840 capitalization of about $2.8 35 00:01:43,079 --> 00:01:50,399 billion um and transactions are uh 36 00:01:47,840 --> 00:01:52,759 secured by a very complex transaction 37 00:01:50,399 --> 00:01:57,360 system called ringct which is the 38 00:01:52,759 --> 00:02:00,360 subject of our work now ringct is made 39 00:01:57,360 --> 00:02:03,600 up of a bunch of components um which 40 00:02:00,360 --> 00:02:05,840 I've listed here uh most notably we have 41 00:02:03,600 --> 00:02:08,080 linkable ring signatures commitments 42 00:02:05,840 --> 00:02:09,759 range proofs and stealth addresses and 43 00:02:08,080 --> 00:02:11,920 I'm going to be going over some of these 44 00:02:09,759 --> 00:02:13,560 components today and I'm going to be 45 00:02:11,920 --> 00:02:16,160 explaining how they work and how they 46 00:02:13,560 --> 00:02:18,920 form together to form 47 00:02:16,160 --> 00:02:20,720 ringct um you know at a very very 48 00:02:18,920 --> 00:02:23,560 abstract 49 00:02:20,720 --> 00:02:26,760 level okay so the central question that 50 00:02:23,560 --> 00:02:29,280 we're trying to answer here is is ringct 51 00:02:26,760 --> 00:02:31,239 secure and uh now if you're not from the 52 00:02:29,280 --> 00:02:35,080 area of provable security then you might 53 00:02:31,239 --> 00:02:37,440 ask why and the answer is well I mean 54 00:02:35,080 --> 00:02:39,879 it's a huge cryptocurrency and it's a 55 00:02:37,440 --> 00:02:42,280 very very complex system and as far as 56 00:02:39,879 --> 00:02:45,239 we're concerned there has been no 57 00:02:42,280 --> 00:02:47,720 security proof of the entire system that 58 00:02:45,239 --> 00:02:51,040 covers all aspects as a whole there have 59 00:02:47,720 --> 00:02:53,120 been groups of partial um you know 60 00:02:51,040 --> 00:02:54,680 components of the system but there has 61 00:02:53,120 --> 00:02:56,720 been no analysis of the whole 62 00:02:54,680 --> 00:02:59,040 transaction system as a whole and for 63 00:02:56,720 --> 00:03:01,519 that reason it's actually not clear 64 00:02:59,040 --> 00:03:05,560 whether it has the provable security 65 00:03:01,519 --> 00:03:08,680 guarantees that it claims um so spoiler 66 00:03:05,560 --> 00:03:10,640 it does we found no bug in the in the in 67 00:03:08,680 --> 00:03:13,599 the transaction protocol and we managed 68 00:03:10,640 --> 00:03:15,360 to prove it secure so that's good I hope 69 00:03:13,599 --> 00:03:18,280 H another thing that I want to add here 70 00:03:15,360 --> 00:03:21,360 is that we only consider the security of 71 00:03:18,280 --> 00:03:22,720 transactions but not their privacy so 72 00:03:21,360 --> 00:03:26,360 okay with those things out of the way 73 00:03:22,720 --> 00:03:28,439 let's Jump Right In now the you know 74 00:03:26,360 --> 00:03:30,280 basically the main result of our work is 75 00:03:28,439 --> 00:03:32,319 that we give an abstraction and a 76 00:03:30,280 --> 00:03:35,000 security model for 77 00:03:32,319 --> 00:03:37,439 ringct and we managed to prove the 78 00:03:35,000 --> 00:03:40,920 security of ringct within this 79 00:03:37,439 --> 00:03:44,159 abstraction and security model um 80 00:03:40,920 --> 00:03:46,519 according to the two following security 81 00:03:44,159 --> 00:03:51,319 goals the first one is that the 82 00:03:46,519 --> 00:03:53,720 adversary cannot steal any coins in mono 83 00:03:51,319 --> 00:03:56,599 and the second one is that the adversary 84 00:03:53,720 --> 00:03:58,360 should not be able to create any coins 85 00:03:56,599 --> 00:04:01,120 and if we can prove those two things 86 00:03:58,360 --> 00:04:03,280 then intuitively one Arrow should be a 87 00:04:01,120 --> 00:04:05,720 secure 88 00:04:03,280 --> 00:04:09,799 cryptocurrency okay 89 00:04:05,720 --> 00:04:13,120 so our security analysis proceeds in two 90 00:04:09,799 --> 00:04:14,599 steps basically so the first thing that 91 00:04:13,120 --> 00:04:18,040 we do and I'm not going to be talking 92 00:04:14,599 --> 00:04:20,479 about this today is that we modularize 93 00:04:18,040 --> 00:04:23,080 this very very complex transaction 94 00:04:20,479 --> 00:04:25,880 system into multiple different 95 00:04:23,080 --> 00:04:28,199 components and then we actually give a 96 00:04:25,880 --> 00:04:31,080 very detailed analysis of each of these 97 00:04:28,199 --> 00:04:33,840 components okay and once we have all of 98 00:04:31,080 --> 00:04:36,639 these uh security definitions for these 99 00:04:33,840 --> 00:04:39,520 components we put them all together and 100 00:04:36,639 --> 00:04:42,240 then we do a system level analysis of 101 00:04:39,520 --> 00:04:44,720 the security of ring CT and it follows 102 00:04:42,240 --> 00:04:46,880 of course from the security of all of 103 00:04:44,720 --> 00:04:48,560 these different cryptographic components 104 00:04:46,880 --> 00:04:50,360 and so what I mean by components here 105 00:04:48,560 --> 00:04:52,520 are you know a lot of these different 106 00:04:50,360 --> 00:04:55,320 things that I had on my on my previous 107 00:04:52,520 --> 00:04:56,919 slide like uh special type of linkable 108 00:04:55,320 --> 00:04:59,120 ring signature which I'll be getting 109 00:04:56,919 --> 00:05:00,320 back to later uh key derivation 110 00:04:59,120 --> 00:05:02,639 components 111 00:05:00,320 --> 00:05:04,199 um commitments and so on but I'll be 112 00:05:02,639 --> 00:05:06,680 talking about that in a 113 00:05:04,199 --> 00:05:09,160 second okay so this talk will cover the 114 00:05:06,680 --> 00:05:11,600 component uh the the system level 115 00:05:09,160 --> 00:05:14,639 analysis but not the component level 116 00:05:11,600 --> 00:05:18,120 analysis okay so now let's have a look 117 00:05:14,639 --> 00:05:22,400 first at how ringct actually 118 00:05:18,120 --> 00:05:25,319 works so to begin let's have a look at 119 00:05:22,400 --> 00:05:27,919 how transactions work in popular 120 00:05:25,319 --> 00:05:30,039 cryptocurrencies so first we have plain 121 00:05:27,919 --> 00:05:33,440 transactions such as you can find in 122 00:05:30,039 --> 00:05:35,759 Bitcoin and in Bitcoin uh a transaction 123 00:05:33,440 --> 00:05:38,280 basically just transfers some amount of 124 00:05:35,759 --> 00:05:40,720 cryptocurrency from the sender public 125 00:05:38,280 --> 00:05:44,440 key say Alice to the recipient's public 126 00:05:40,720 --> 00:05:46,880 key say Bob here okay and then on the 127 00:05:44,440 --> 00:05:49,800 complete other side of the spectrum we 128 00:05:46,880 --> 00:05:50,600 have um encrypted transactions such as 129 00:05:49,800 --> 00:05:53,319 in 130 00:05:50,600 --> 00:05:54,960 zcash where you have a guarantee 131 00:05:53,319 --> 00:05:57,759 actually provable guarantee that you 132 00:05:54,960 --> 00:06:00,800 have complete anonymity within a certain 133 00:05:57,759 --> 00:06:03,360 Set uh anonymity set set of users where 134 00:06:00,800 --> 00:06:05,199 nobody can gain any information about 135 00:06:03,360 --> 00:06:08,039 any of the transactions that are being 136 00:06:05,199 --> 00:06:10,759 transferred so in in zcash this would be 137 00:06:08,039 --> 00:06:12,319 the the shielded pool right and of 138 00:06:10,759 --> 00:06:15,199 course this givs very very strong 139 00:06:12,319 --> 00:06:18,720 privacy guarantees but as you can see in 140 00:06:15,199 --> 00:06:20,840 the in the example of zcash these 141 00:06:18,720 --> 00:06:23,160 transactions are typically a lot slower 142 00:06:20,840 --> 00:06:25,240 and they're more expensive and that's 143 00:06:23,160 --> 00:06:28,440 why they're not being used that much 144 00:06:25,240 --> 00:06:31,000 even though they exist and now Monero I 145 00:06:28,440 --> 00:06:33,960 see it basically as falling in between 146 00:06:31,000 --> 00:06:37,960 these two extremes so Monero gives very 147 00:06:33,960 --> 00:06:40,840 strong privacy guarantees using a uh an 148 00:06:37,960 --> 00:06:43,280 approach called mixing so the idea is to 149 00:06:40,840 --> 00:06:45,720 take a bunch of transactions mix them 150 00:06:43,280 --> 00:06:48,720 all together and shuffle them around so 151 00:06:45,720 --> 00:06:52,080 it's not clear who's paying how much to 152 00:06:48,720 --> 00:06:54,759 you know whom and that the that that 153 00:06:52,080 --> 00:06:56,960 anonymizes the the uh the senders and 154 00:06:54,759 --> 00:06:59,400 the recipients in this very complex 155 00:06:56,960 --> 00:07:01,720 system and it makes it much harder to tr 156 00:06:59,400 --> 00:07:04,440 Trace certain payments filling from A to 157 00:07:01,720 --> 00:07:07,440 B now 158 00:07:04,440 --> 00:07:10,120 okay let's have a closer look at the 159 00:07:07,440 --> 00:07:12,440 anatomy of plain transactions and then 160 00:07:10,120 --> 00:07:13,879 how that would translate into a more 161 00:07:12,440 --> 00:07:17,120 narrow 162 00:07:13,879 --> 00:07:19,919 transaction so going back to this very 163 00:07:17,120 --> 00:07:23,639 very simple and rudimentary example of 164 00:07:19,919 --> 00:07:26,360 of Bitcoin here a transaction would look 165 00:07:23,639 --> 00:07:28,879 as follows so if say Alice wants to 166 00:07:26,360 --> 00:07:29,960 transfer two Bitcoins to Bob then what 167 00:07:28,879 --> 00:07:32,160 she would do 168 00:07:29,960 --> 00:07:34,800 is she creates a transaction where she 169 00:07:32,160 --> 00:07:38,000 identifies her as the sender she 170 00:07:34,800 --> 00:07:40,960 identifies the amount and she also 171 00:07:38,000 --> 00:07:41,919 identifies as the receiver Bob and then 172 00:07:40,960 --> 00:07:45,000 she 173 00:07:41,919 --> 00:07:49,000 signs uh this transaction with her 174 00:07:45,000 --> 00:07:51,800 secret key which can be verified upon 175 00:07:49,000 --> 00:07:53,159 anybody holding her public key okay and 176 00:07:51,800 --> 00:07:57,039 this will 177 00:07:53,159 --> 00:08:00,240 transfer two Bitcoins to Bob and then 178 00:07:57,039 --> 00:08:02,599 Bob can do the same thing to spend those 179 00:08:00,240 --> 00:08:07,080 transactions in term or those Bitcoins 180 00:08:02,599 --> 00:08:10,159 in term okay and uh the the idea is that 181 00:08:07,080 --> 00:08:12,639 uh each transaction that is being 182 00:08:10,159 --> 00:08:16,400 processed here 183 00:08:12,639 --> 00:08:18,919 actually uh contains as an input the 184 00:08:16,400 --> 00:08:21,360 output or the the unspent output of a 185 00:08:18,919 --> 00:08:24,440 previous transaction okay so whenever 186 00:08:21,360 --> 00:08:26,240 you will pay transaction to somebody 187 00:08:24,440 --> 00:08:28,840 then whatever is left over what doesn't 188 00:08:26,240 --> 00:08:31,599 go to their recipient will become a new 189 00:08:28,840 --> 00:08:34,159 unspent output that can be later spent 190 00:08:31,599 --> 00:08:38,839 in the next transaction and we refer to 191 00:08:34,159 --> 00:08:41,839 this as the unspent transaction or utxo 192 00:08:38,839 --> 00:08:45,600 model so now let's get a little bit 193 00:08:41,839 --> 00:08:47,880 closer to what Monero is doing so here 194 00:08:45,600 --> 00:08:50,519 we will actually consider multi-input 195 00:08:47,880 --> 00:08:52,560 transactions so before we only had a 196 00:08:50,519 --> 00:08:55,320 single input from Alice but now let's 197 00:08:52,560 --> 00:08:58,120 say that Alice has two unspent outputs 198 00:08:55,320 --> 00:09:00,560 each corresponding to one Monero or one 199 00:08:58,120 --> 00:09:03,959 Bitcoin and she wants to spend both of 200 00:09:00,560 --> 00:09:05,880 those um unspent outputs so now a 201 00:09:03,959 --> 00:09:08,200 multi-input transaction would allow 202 00:09:05,880 --> 00:09:10,079 Alice to spend both of these unspent 203 00:09:08,200 --> 00:09:13,839 outputs at the same 204 00:09:10,079 --> 00:09:16,000 time okay uh so in my previous example 205 00:09:13,839 --> 00:09:18,320 here I used one Bitcoin for both of 206 00:09:16,000 --> 00:09:21,680 these or One Mono for both of these 207 00:09:18,320 --> 00:09:25,320 unspent uh outputs but now let's see 208 00:09:21,680 --> 00:09:30,279 what happens if Alice would have uh say 209 00:09:25,320 --> 00:09:32,160 two unspent Monero in the first um 210 00:09:30,279 --> 00:09:35,000 in the first unspent output and three in 211 00:09:32,160 --> 00:09:37,839 the second one what would happen then is 212 00:09:35,000 --> 00:09:39,760 that there is one coin remaining that is 213 00:09:37,839 --> 00:09:42,560 not transferred over to Bob because Bob 214 00:09:39,760 --> 00:09:46,120 in this transaction only gets four 215 00:09:42,560 --> 00:09:49,120 moneros and uh whatever remains after 216 00:09:46,120 --> 00:09:51,800 that actually gets transferred into a 217 00:09:49,120 --> 00:09:55,720 new unspin output of 218 00:09:51,800 --> 00:09:59,160 Alis so this is my running example here 219 00:09:55,720 --> 00:10:01,519 uh again here Alice will use the same 220 00:09:59,160 --> 00:10:04,200 amount of currency in both of our inputs 221 00:10:01,519 --> 00:10:06,800 and um in as we will see it's it's 222 00:10:04,200 --> 00:10:08,600 important to add references to each of 223 00:10:06,800 --> 00:10:11,399 these input so that they can be 224 00:10:08,600 --> 00:10:14,160 distinguished when the transaction is 225 00:10:11,399 --> 00:10:17,680 built okay so now let's get to the main 226 00:10:14,160 --> 00:10:20,360 ideas of ringct so the first thing that 227 00:10:17,680 --> 00:10:22,920 we want to do in ringct is we want to 228 00:10:20,360 --> 00:10:26,800 hide the senders we don't want to reveal 229 00:10:22,920 --> 00:10:29,600 who is sending to so for this at a very 230 00:10:26,800 --> 00:10:31,640 very conceptual level we will be using 231 00:10:29,600 --> 00:10:33,480 um cryptographic primitive called ring 232 00:10:31,640 --> 00:10:35,880 signatures which I'm going to explain on 233 00:10:33,480 --> 00:10:37,360 the next couple of slides the second 234 00:10:35,880 --> 00:10:39,639 goal that we want to have is that we 235 00:10:37,360 --> 00:10:41,360 want to hide the amounts of how much 236 00:10:39,639 --> 00:10:44,360 money is being transferred between 237 00:10:41,360 --> 00:10:46,279 senders and recipients for this we will 238 00:10:44,360 --> 00:10:48,279 use cryptographic 239 00:10:46,279 --> 00:10:50,839 commitments and the third thing that we 240 00:10:48,279 --> 00:10:53,639 want to do is we want to hide who is 241 00:10:50,839 --> 00:10:56,959 receiving what amount from whom and for 242 00:10:53,639 --> 00:11:00,000 this we will be using uh stealth 243 00:10:56,959 --> 00:11:02,240 addresses okay so let's actually look at 244 00:11:00,000 --> 00:11:03,959 this uh third component first the 245 00:11:02,240 --> 00:11:06,399 stealth addresses because I believe that 246 00:11:03,959 --> 00:11:08,160 this is really what sets fero apart from 247 00:11:06,399 --> 00:11:11,440 a lot of other 248 00:11:08,160 --> 00:11:13,839 cryptocurrencies so here is how that 249 00:11:11,440 --> 00:11:16,920 works basically Bob who is going to be 250 00:11:13,839 --> 00:11:19,399 the recipient of this Del this stealth 251 00:11:16,920 --> 00:11:22,320 transaction will have two long-term 252 00:11:19,399 --> 00:11:25,920 secret Keys which are just zp elements 253 00:11:22,320 --> 00:11:30,360 KV for the vew key and KS for the 254 00:11:25,920 --> 00:11:32,320 spending key and those correspond to two 255 00:11:30,360 --> 00:11:34,360 points on an elliptic curve and those 256 00:11:32,320 --> 00:11:35,720 are his public view key and his public 257 00:11:34,360 --> 00:11:40,040 spending 258 00:11:35,720 --> 00:11:42,880 key um okay so those are Bob's long-term 259 00:11:40,040 --> 00:11:46,320 Keys now um excuse 260 00:11:42,880 --> 00:11:49,160 me if Alice would like to spend both of 261 00:11:46,320 --> 00:11:52,600 these unspent uh outputs to Bob in this 262 00:11:49,160 --> 00:11:57,240 transaction then what she will do is the 263 00:11:52,600 --> 00:11:59,320 following he will sample a a random R 264 00:11:57,240 --> 00:12:01,760 from that p and p here is the the order 265 00:11:59,320 --> 00:12:03,760 of the elliptic curve that we're using 266 00:12:01,760 --> 00:12:07,160 um and then she will generate this 267 00:12:03,760 --> 00:12:10,240 Randomness as raising um the base point 268 00:12:07,160 --> 00:12:12,639 of this curve to this power VAR then she 269 00:12:10,240 --> 00:12:15,880 will generate an output Key by taking 270 00:12:12,639 --> 00:12:17,560 Bob's U key and raising Bob's U key to 271 00:12:15,880 --> 00:12:20,600 this R which she 272 00:12:17,560 --> 00:12:23,000 just then she will hash the output key 273 00:12:20,600 --> 00:12:25,199 raise the base point to this hash and 274 00:12:23,000 --> 00:12:27,839 multiply it with Bob's spending key and 275 00:12:25,199 --> 00:12:31,839 this is going to be the public key that 276 00:12:27,839 --> 00:12:33,880 her uh outputs are being transferred to 277 00:12:31,839 --> 00:12:37,920 so now Bob can actually check whether 278 00:12:33,880 --> 00:12:40,760 this output is his by Computing the uh 279 00:12:37,920 --> 00:12:43,279 output key on his side um because these 280 00:12:40,760 --> 00:12:44,880 two operations commute in the exponent 281 00:12:43,279 --> 00:12:47,560 that's basically you can think of it as 282 00:12:44,880 --> 00:12:49,160 a mini Diffy Helman key exchange and 283 00:12:47,560 --> 00:12:51,399 then it can check whether this 284 00:12:49,160 --> 00:12:53,079 transaction is actually meant for him 285 00:12:51,399 --> 00:12:55,320 and then if it is indeed meant for him 286 00:12:53,079 --> 00:12:59,360 then he can later spend it by Computing 287 00:12:55,320 --> 00:13:00,760 spending key in this fashion right here 288 00:12:59,360 --> 00:13:03,839 okay 289 00:13:00,760 --> 00:13:06,440 so now actually something else happens 290 00:13:03,839 --> 00:13:10,360 so what Alice now adds to this 291 00:13:06,440 --> 00:13:14,279 transaction is a commitment to the 292 00:13:10,360 --> 00:13:16,720 amount in the transaction so to do this 293 00:13:14,279 --> 00:13:19,720 she will commit to the amount that's in 294 00:13:16,720 --> 00:13:22,040 this transaction and uh she'll do this 295 00:13:19,720 --> 00:13:25,079 by Computing a commitment say Pon 296 00:13:22,040 --> 00:13:26,720 commitment onto with some corresponding 297 00:13:25,079 --> 00:13:27,760 commitment Randomness that I've denoted 298 00:13:26,720 --> 00:13:29,320 here as 299 00:13:27,760 --> 00:13:31,760 CR 300 00:13:29,320 --> 00:13:35,880 okay 301 00:13:31,760 --> 00:13:37,800 so intuitively this uh commitment we 302 00:13:35,880 --> 00:13:39,920 will use it as I said to hide the 303 00:13:37,800 --> 00:13:42,279 amounts of what is being transferred 304 00:13:39,920 --> 00:13:45,560 here but we'll get to that only on the 305 00:13:42,279 --> 00:13:47,639 next slide first let's have a look at 306 00:13:45,560 --> 00:13:50,600 how we can hide the 307 00:13:47,639 --> 00:13:53,480 inputs uh using ring 308 00:13:50,600 --> 00:13:56,160 signatures okay so in a Monaro 309 00:13:53,480 --> 00:13:57,440 Transaction what is going to happen is 310 00:13:56,160 --> 00:14:01,440 that 311 00:13:57,440 --> 00:14:04,959 um each user is going to supply not only 312 00:14:01,440 --> 00:14:08,079 their inputs but also some decoy inputs 313 00:14:04,959 --> 00:14:10,680 and the intuitive reason behind this is 314 00:14:08,079 --> 00:14:13,839 that what we want to do is increase the 315 00:14:10,680 --> 00:14:15,959 anonymity set remember we want to have 316 00:14:13,839 --> 00:14:17,600 we want to make it very difficult for 317 00:14:15,959 --> 00:14:19,519 somebody an East dropper who is 318 00:14:17,600 --> 00:14:21,800 observing these transactions to see how 319 00:14:19,519 --> 00:14:23,800 much money is being sent around between 320 00:14:21,800 --> 00:14:25,279 senders and recipients and for this 321 00:14:23,800 --> 00:14:27,360 reason we're going to increase the 322 00:14:25,279 --> 00:14:29,320 anonymity set by adding some decoy 323 00:14:27,360 --> 00:14:31,440 inputs to every transaction 324 00:14:29,320 --> 00:14:33,920 and these are the light gray uh 325 00:14:31,440 --> 00:14:37,399 transactions here in this 326 00:14:33,920 --> 00:14:38,959 drawing okay so again we're going to 327 00:14:37,399 --> 00:14:40,000 reference all of them so that they can 328 00:14:38,959 --> 00:14:43,320 be 329 00:14:40,000 --> 00:14:45,759 distinguished and now two problems 330 00:14:43,320 --> 00:14:48,399 remain basically so the first thing that 331 00:14:45,759 --> 00:14:50,120 we have to prevent is double spending 332 00:14:48,399 --> 00:14:54,560 and the second thing that we have to 333 00:14:50,120 --> 00:14:56,399 prevent is that the sum of all you know 334 00:14:54,560 --> 00:14:58,160 the amounts that are going into this 335 00:14:56,399 --> 00:15:00,079 transaction being transferred over to 336 00:14:58,160 --> 00:15:01,720 the recipient of this transaction have 337 00:15:00,079 --> 00:15:03,839 to be 338 00:15:01,720 --> 00:15:05,959 preserved through this intermediate 339 00:15:03,839 --> 00:15:09,120 layer where we are actually committing 340 00:15:05,959 --> 00:15:10,959 to the uh inputs and then they're going 341 00:15:09,120 --> 00:15:14,680 to be spend to the 342 00:15:10,959 --> 00:15:16,759 recipients so to prevent double spending 343 00:15:14,680 --> 00:15:19,880 as I already said we're going to use 344 00:15:16,759 --> 00:15:22,360 linkable ring signatures so what is a 345 00:15:19,880 --> 00:15:23,880 linkable ring signature first let's have 346 00:15:22,360 --> 00:15:25,720 a look at what is a ring signature 347 00:15:23,880 --> 00:15:29,160 actually a ring signature very 348 00:15:25,720 --> 00:15:30,600 abstractly spoken is a um 349 00:15:29,160 --> 00:15:33,319 regular signature basically 350 00:15:30,600 --> 00:15:35,399 cryptographic signature but it doesn't 351 00:15:33,319 --> 00:15:38,480 behave syntactically like a regular 352 00:15:35,399 --> 00:15:40,720 signature rather we have group of people 353 00:15:38,480 --> 00:15:42,759 that's called they're called the ring 354 00:15:40,720 --> 00:15:46,160 and they want to jointly generate a 355 00:15:42,759 --> 00:15:48,240 signature on behalf of group so any 356 00:15:46,160 --> 00:15:50,079 member from this ring can actually 357 00:15:48,240 --> 00:15:51,680 generate the signature and then it will 358 00:15:50,079 --> 00:15:54,480 act as a signature on behalf of this 359 00:15:51,680 --> 00:15:56,279 group but nobody can tell who the member 360 00:15:54,480 --> 00:15:58,399 of the Ring was who generated the 361 00:15:56,279 --> 00:16:00,279 signature that's the functionality that 362 00:15:58,399 --> 00:16:02,639 a ring signature provides so it's a 363 00:16:00,279 --> 00:16:04,319 certain degree of anonymity now with a 364 00:16:02,639 --> 00:16:07,600 linkable ring signature we have an 365 00:16:04,319 --> 00:16:11,040 additional feature we can make sure that 366 00:16:07,600 --> 00:16:13,279 if somebody attempts to sign twice so 367 00:16:11,040 --> 00:16:15,519 the same member of the Ring tries to 368 00:16:13,279 --> 00:16:17,480 sign two different things then there is 369 00:16:15,519 --> 00:16:19,680 an algorithm that we can use to 370 00:16:17,480 --> 00:16:20,959 efficiently link this to the same user 371 00:16:19,680 --> 00:16:23,680 and identify 372 00:16:20,959 --> 00:16:26,639 him um and this is one of the key 373 00:16:23,680 --> 00:16:29,880 components in the Monero CT transaction 374 00:16:26,639 --> 00:16:34,079 system okay so here is the first attempt 375 00:16:29,880 --> 00:16:38,000 of um preserving the amounts in such a 376 00:16:34,079 --> 00:16:41,759 uh privacy preserving transaction so the 377 00:16:38,000 --> 00:16:45,079 sender wants to show that the amounts 378 00:16:41,759 --> 00:16:46,680 hidden in these uh two black commitments 379 00:16:45,079 --> 00:16:49,639 here the ones that are in decoy 380 00:16:46,680 --> 00:16:53,319 commitments sums up to whatever is in 381 00:16:49,639 --> 00:16:57,079 the commitment that corresponds to the 382 00:16:53,319 --> 00:16:59,440 output okay so what's the idea here the 383 00:16:57,079 --> 00:17:01,360 idea here is that we're going to use Pon 384 00:16:59,440 --> 00:17:03,759 commitment to do this which has a 385 00:17:01,360 --> 00:17:06,480 homomorphic property and what that means 386 00:17:03,759 --> 00:17:09,000 is that given the two commitments to the 387 00:17:06,480 --> 00:17:11,799 inputs one can efficiently check whether 388 00:17:09,000 --> 00:17:14,919 whatever is being committed to sums up 389 00:17:11,799 --> 00:17:16,720 to um the commitment that should be the 390 00:17:14,919 --> 00:17:19,439 sum of their inputs without actually 391 00:17:16,720 --> 00:17:21,360 knowing what is inside these 392 00:17:19,439 --> 00:17:23,799 commitments um so here is the 393 00:17:21,360 --> 00:17:26,600 verification equation and and that's the 394 00:17:23,799 --> 00:17:29,760 reason why this actually 395 00:17:26,600 --> 00:17:32,799 works now the problem remains here is is 396 00:17:29,760 --> 00:17:35,600 actually privacy problem because if we 397 00:17:32,799 --> 00:17:37,880 give this homomorphic functionality for 398 00:17:35,600 --> 00:17:41,880 the commitments then it is actually 399 00:17:37,880 --> 00:17:45,520 possible to use that to identify which 400 00:17:41,880 --> 00:17:49,360 of these uh inputs are decoy inputs 401 00:17:45,520 --> 00:17:51,559 corresponding to uh basically zero coins 402 00:17:49,360 --> 00:17:54,799 and which are real inputs corresponding 403 00:17:51,559 --> 00:17:56,799 to nonzero coins because if I have a 404 00:17:54,799 --> 00:17:58,960 decoy input then I can just try to add 405 00:17:56,799 --> 00:18:00,480 it to another one of these commitments 406 00:17:58,960 --> 00:18:02,640 homomorphically and then you can see 407 00:18:00,480 --> 00:18:04,440 that the amount will be preserved and 408 00:18:02,640 --> 00:18:06,679 and then it's not private anymore and it 409 00:18:04,440 --> 00:18:08,559 doesn't hide the amounts in these inputs 410 00:18:06,679 --> 00:18:10,760 and that of course is exactly the reason 411 00:18:08,559 --> 00:18:12,200 why we want to have these commitments in 412 00:18:10,760 --> 00:18:15,720 the first 413 00:18:12,200 --> 00:18:17,880 place so how do we get rid of that well 414 00:18:15,720 --> 00:18:19,840 there is a famous quote attributed to 415 00:18:17,880 --> 00:18:21,760 David wheeler which says that all 416 00:18:19,840 --> 00:18:24,799 problems in computer science can be 417 00:18:21,760 --> 00:18:27,640 solved by another level of indirection 418 00:18:24,799 --> 00:18:30,760 so I'm not sure if this is universally 419 00:18:27,640 --> 00:18:33,320 true but in you know the specific case 420 00:18:30,760 --> 00:18:35,600 of Monero it is actually true so what 421 00:18:33,320 --> 00:18:37,880 we're going to do is is ADD exactly such 422 00:18:35,600 --> 00:18:40,400 a layer IND 423 00:18:37,880 --> 00:18:43,640 Direction and and this will correspond 424 00:18:40,400 --> 00:18:45,600 to something called pseudo outputs so 425 00:18:43,640 --> 00:18:50,520 rather than outputting directly we will 426 00:18:45,600 --> 00:18:52,200 have a layer of pseudo outputs and um so 427 00:18:50,520 --> 00:18:54,799 the the commitments in the pseudo 428 00:18:52,200 --> 00:18:57,559 outputs should now have the property 429 00:18:54,799 --> 00:19:00,600 that they uh homomorphically can sum up 430 00:18:57,559 --> 00:19:04,200 to the commitment in the output but to 431 00:19:00,600 --> 00:19:05,640 make sure that these cannot be linked to 432 00:19:04,200 --> 00:19:07,320 uh the amounts in the original 433 00:19:05,640 --> 00:19:09,080 transactions that cannot be used to 434 00:19:07,320 --> 00:19:12,520 distinguish which are decoys and which 435 00:19:09,080 --> 00:19:14,919 are not we will use a ring signature to 436 00:19:12,520 --> 00:19:17,480 spend from the inputs to these 437 00:19:14,919 --> 00:19:20,919 commitments so the the intuitive idea 438 00:19:17,480 --> 00:19:23,679 behind this is is that the set of all of 439 00:19:20,919 --> 00:19:26,320 these commitments is basically uh the 440 00:19:23,679 --> 00:19:27,960 set of users who want to sign and that's 441 00:19:26,320 --> 00:19:30,360 sounds a little bit weird because now 442 00:19:27,960 --> 00:19:32,679 each these commitments also sort of can 443 00:19:30,360 --> 00:19:34,200 be thought of of H as having a public 444 00:19:32,679 --> 00:19:36,080 key namely the public key that 445 00:19:34,200 --> 00:19:39,039 corresponds to this transaction here or 446 00:19:36,080 --> 00:19:42,880 to this input and what we want to do is 447 00:19:39,039 --> 00:19:45,840 we want to show that there was one of 448 00:19:42,880 --> 00:19:49,600 these uh input commitments plus public 449 00:19:45,840 --> 00:19:51,320 Keys who signed uh the corresponding 450 00:19:49,600 --> 00:19:53,240 amount that transferred to this 451 00:19:51,320 --> 00:19:55,679 commitment but we don't want to show 452 00:19:53,240 --> 00:19:58,000 which of them it was because that would 453 00:19:55,679 --> 00:20:00,760 reveal which ones are the decoy inputs 454 00:19:58,000 --> 00:20:03,480 and which or not um so that's the very 455 00:20:00,760 --> 00:20:06,200 very high level idea basically to treat 456 00:20:03,480 --> 00:20:10,919 these uh inputs as users in a ring 457 00:20:06,200 --> 00:20:12,799 signature very abstractly spoken and um 458 00:20:10,919 --> 00:20:16,039 once we once we are able to do that so 459 00:20:12,799 --> 00:20:19,120 to get from inputs to sudo outputs then 460 00:20:16,039 --> 00:20:23,080 we've broken this link that can be used 461 00:20:19,120 --> 00:20:26,400 to uh distinguish um decoy inputs from 462 00:20:23,080 --> 00:20:30,520 real inputs because we basically add 463 00:20:26,400 --> 00:20:30,520 this layer of anonymity using the ring 464 00:20:34,960 --> 00:20:39,600 signature do you love coffee and Monera 465 00:20:37,559 --> 00:20:42,240 as much as we do consider making 466 00:20:39,600 --> 00:20:44,600 gratuitous dorg your daily cup pay with 467 00:20:42,240 --> 00:20:46,640 Monera for premium fresh beans and if 468 00:20:44,600 --> 00:20:48,919 you like what you taste send a digital 469 00:20:46,640 --> 00:20:50,240 cash tip directly to the farmers that 470 00:20:48,919 --> 00:20:52,600 made it 471 00:20:50,240 --> 00:20:55,950 possible proceeds help us grow this 472 00:20:52,600 --> 00:20:57,120 channel gratuitous and 473 00:20:55,950 --> 00:21:00,120 [Music] 474 00:20:57,120 --> 00:21:00,120 Monero 475 00:21:02,919 --> 00:21:08,880 so that only leaves one thing which is 476 00:21:05,799 --> 00:21:11,240 how are ver transactions verified in 477 00:21:08,880 --> 00:21:13,640 this system well basically we're going 478 00:21:11,240 --> 00:21:16,159 to check for the following things first 479 00:21:13,640 --> 00:21:18,840 we're going to check whether all inputs 480 00:21:16,159 --> 00:21:21,080 are previous unspent 481 00:21:18,840 --> 00:21:23,080 outputs then we're going to check for 482 00:21:21,080 --> 00:21:25,000 whether all signatures meaning ring 483 00:21:23,080 --> 00:21:28,520 signatures here are 484 00:21:25,000 --> 00:21:31,679 valid and we're also going to check that 485 00:21:28,520 --> 00:21:33,440 no signature links because uh if a 486 00:21:31,679 --> 00:21:36,080 signature links then basically that 487 00:21:33,440 --> 00:21:39,320 means that somebody tried to spend the 488 00:21:36,080 --> 00:21:41,120 same output twice uh in in two different 489 00:21:39,320 --> 00:21:43,840 transactions and that of course would be 490 00:21:41,120 --> 00:21:46,559 an attempt of double spending and and 491 00:21:43,840 --> 00:21:49,000 and that's something we want to 492 00:21:46,559 --> 00:21:51,360 prevent and and lastly we're going to 493 00:21:49,000 --> 00:21:53,360 check whether um the amount of the 494 00:21:51,360 --> 00:21:55,320 transaction is preserved so the amount 495 00:21:53,360 --> 00:21:57,400 that's being input is preserved in the 496 00:21:55,320 --> 00:21:58,799 output by checking this homomorphic 497 00:21:57,400 --> 00:22:02,600 equality here 498 00:21:58,799 --> 00:22:05,240 here so that was a very brief overview 499 00:22:02,600 --> 00:22:08,080 of how ring CT Works it's uh rather 500 00:22:05,240 --> 00:22:10,159 complicated and I hope now you um can 501 00:22:08,080 --> 00:22:12,799 appreciate why it's so difficult to 502 00:22:10,159 --> 00:22:15,200 prove the scheme secure but now let's 503 00:22:12,799 --> 00:22:19,400 actually turn to our security 504 00:22:15,200 --> 00:22:22,320 model so for the security 505 00:22:19,400 --> 00:22:25,039 model because uh many of you might not 506 00:22:22,320 --> 00:22:28,279 have a background in in uh improvable 507 00:22:25,039 --> 00:22:30,440 security let's actually first explain 508 00:22:28,279 --> 00:22:32,480 what exactly uh the security model 509 00:22:30,440 --> 00:22:36,200 should capture and how it works and how 510 00:22:32,480 --> 00:22:39,880 to think about it so in provable 511 00:22:36,200 --> 00:22:41,480 security the way that we think about um 512 00:22:39,880 --> 00:22:43,640 security and I think I already mentioned 513 00:22:41,480 --> 00:22:46,600 this at the beginning of my talk is we 514 00:22:43,640 --> 00:22:49,640 think of security as being formalized as 515 00:22:46,600 --> 00:22:52,760 a game between a challenger who proposes 516 00:22:49,640 --> 00:22:55,760 a scheme in this case the ring CT scheme 517 00:22:52,760 --> 00:22:58,400 and an adversary that tries to break the 518 00:22:55,760 --> 00:23:00,200 security of that scheme so so the 519 00:22:58,400 --> 00:23:03,000 adversary basically tries to win the 520 00:23:00,200 --> 00:23:07,880 game by breaking whatever security 521 00:23:03,000 --> 00:23:10,679 property we uh we formalize here okay um 522 00:23:07,880 --> 00:23:13,240 and and the goal of you know of our work 523 00:23:10,679 --> 00:23:16,760 of course is to formalize such a 524 00:23:13,240 --> 00:23:18,840 security game which accurately captures 525 00:23:16,760 --> 00:23:21,159 whatever is going on in the real world 526 00:23:18,840 --> 00:23:24,360 and map it to a mathematical model and 527 00:23:21,159 --> 00:23:27,000 that's the intuition here so now that 528 00:23:24,360 --> 00:23:29,120 means that we have to abstract what the 529 00:23:27,000 --> 00:23:31,559 adversary can mean meaningfully do in 530 00:23:29,120 --> 00:23:34,480 the real world into our model so the 531 00:23:31,559 --> 00:23:37,240 adversary could in our model create new 532 00:23:34,480 --> 00:23:40,440 honest users so it can basically tell 533 00:23:37,240 --> 00:23:42,840 somebody to take up Monero start mining 534 00:23:40,440 --> 00:23:44,400 some coins and uh and behave like an 535 00:23:42,840 --> 00:23:46,720 honest user in the 536 00:23:44,400 --> 00:23:48,240 system maybe through the fishing mail 537 00:23:46,720 --> 00:23:51,320 for 538 00:23:48,240 --> 00:23:54,520 example then um the next thing that it 539 00:23:51,320 --> 00:23:57,360 can do is it can submit transactions to 540 00:23:54,520 --> 00:24:00,120 the system uh or it can spend some 541 00:23:57,360 --> 00:24:02,240 transaction to other users participate 542 00:24:00,120 --> 00:24:06,360 in mixed transactions and so on and so 543 00:24:02,240 --> 00:24:09,000 forth it can make honest users submit 544 00:24:06,360 --> 00:24:11,159 transactions by for example conning them 545 00:24:09,000 --> 00:24:14,000 into spending 546 00:24:11,159 --> 00:24:16,760 something so thirdly it can corrupt 547 00:24:14,000 --> 00:24:19,640 users meaning that now it controls that 548 00:24:16,760 --> 00:24:23,760 user and all of their funds and it can 549 00:24:19,640 --> 00:24:27,320 do so um in in our model at any point in 550 00:24:23,760 --> 00:24:30,320 time and finally just to add some money 551 00:24:27,320 --> 00:24:33,440 to the system initially we also allow 552 00:24:30,320 --> 00:24:35,480 the adversary uh to create Source coins 553 00:24:33,440 --> 00:24:39,159 which basically just means that the 554 00:24:35,480 --> 00:24:43,440 system will be populated with some 555 00:24:39,159 --> 00:24:45,520 currency okay so now let's formalize the 556 00:24:43,440 --> 00:24:47,600 winning conditions of the adversary in 557 00:24:45,520 --> 00:24:50,120 this security game between our implicit 558 00:24:47,600 --> 00:24:52,360 Challenger and whatever adversary tries 559 00:24:50,120 --> 00:24:54,399 to break the security of the game so the 560 00:24:52,360 --> 00:24:57,120 first winning condition is that the 561 00:24:54,399 --> 00:24:59,240 adversary can steal coins from honest 562 00:24:57,120 --> 00:25:01,200 users meaning that they can spend the 563 00:24:59,240 --> 00:25:04,279 coins of honest users without of course 564 00:25:01,200 --> 00:25:07,600 knowing their spending Keys the second 565 00:25:04,279 --> 00:25:10,159 condition is that the adversary can 566 00:25:07,600 --> 00:25:12,799 create coins out of thin air which of 567 00:25:10,159 --> 00:25:14,640 course would also undermine the security 568 00:25:12,799 --> 00:25:15,960 of the honest users because then money 569 00:25:14,640 --> 00:25:18,440 is worth 570 00:25:15,960 --> 00:25:20,360 nothing now for the remainder of my talk 571 00:25:18,440 --> 00:25:23,159 I'm going to be focusing on this second 572 00:25:20,360 --> 00:25:25,039 winning condition here uh so the 573 00:25:23,159 --> 00:25:28,480 adversary should not be able to create 574 00:25:25,039 --> 00:25:31,279 coins out of thin air and let's have a 575 00:25:28,480 --> 00:25:34,320 look at how we formalize 576 00:25:31,279 --> 00:25:36,880 this so we'll start with having you know 577 00:25:34,320 --> 00:25:39,240 some invariant called or or or some 578 00:25:36,880 --> 00:25:42,720 variable rather called received and it's 579 00:25:39,240 --> 00:25:44,600 just going to be some natural number and 580 00:25:42,720 --> 00:25:47,559 whenever the 581 00:25:44,600 --> 00:25:51,080 adversary um gets some coins either from 582 00:25:47,559 --> 00:25:54,000 a source or from an honest user then the 583 00:25:51,080 --> 00:25:55,159 amount received will be increased by 584 00:25:54,000 --> 00:25:57,880 that 585 00:25:55,159 --> 00:26:01,320 much second we have a variable called 586 00:25:57,880 --> 00:26:05,760 spent and whenever the adversary spends 587 00:26:01,320 --> 00:26:08,520 any coins to an honest user then the uh 588 00:26:05,760 --> 00:26:12,200 amount spent will be increased by that 589 00:26:08,520 --> 00:26:16,640 much so um the winning condition now can 590 00:26:12,200 --> 00:26:18,559 be phrased as spent being greater than 591 00:26:16,640 --> 00:26:21,159 received because that means that the 592 00:26:18,559 --> 00:26:23,120 aary spend a money which it did not 593 00:26:21,159 --> 00:26:25,919 receive and that would amount to it 594 00:26:23,120 --> 00:26:29,279 creating coins out of thin and in this 595 00:26:25,919 --> 00:26:31,840 case the adversary would win 596 00:26:29,279 --> 00:26:33,240 okay so this is the security model and 597 00:26:31,840 --> 00:26:36,480 the adversaries 598 00:26:33,240 --> 00:26:38,919 goal and now let's actually have a very 599 00:26:36,480 --> 00:26:41,720 very brief look at how we would attempt 600 00:26:38,919 --> 00:26:41,720 to prove such a 601 00:26:42,840 --> 00:26:50,279 thing okay so if we have a look at these 602 00:26:47,640 --> 00:26:52,480 transactions again remember that we uh 603 00:26:50,279 --> 00:26:56,840 we have these three layers inputs pseudo 604 00:26:52,480 --> 00:27:00,080 outputs and outputs and um now our idea 605 00:26:56,840 --> 00:27:03,640 is that that you know skipping some 606 00:27:00,080 --> 00:27:06,200 details here that we want to we want to 607 00:27:03,640 --> 00:27:08,679 map all of these transactions which 608 00:27:06,200 --> 00:27:11,279 happen over the lifetime of the entire 609 00:27:08,679 --> 00:27:15,840 system to a 610 00:27:11,279 --> 00:27:18,440 graph and once we have this graph we're 611 00:27:15,840 --> 00:27:21,880 actually going to be able to apply graph 612 00:27:18,440 --> 00:27:25,799 theoretic arguments that show that the 613 00:27:21,880 --> 00:27:28,000 adversary is not capable of um spending 614 00:27:25,799 --> 00:27:30,679 more coins than it receives and this is 615 00:27:28,000 --> 00:27:34,159 going to come down to a graph theoretic 616 00:27:30,679 --> 00:27:38,720 argument and the key difficulty of the 617 00:27:34,159 --> 00:27:40,760 proof really is to show that each 618 00:27:38,720 --> 00:27:42,880 behavior of the adversary that it can 619 00:27:40,760 --> 00:27:45,640 perform in this abstraction of the 620 00:27:42,880 --> 00:27:49,200 system can actually be mapped to a 621 00:27:45,640 --> 00:27:53,399 unique graph that we can later analyze 622 00:27:49,200 --> 00:27:55,200 so and this is actually where the um the 623 00:27:53,399 --> 00:27:57,919 cryptographic security of all of the 624 00:27:55,200 --> 00:27:59,919 components of the system comes comes in 625 00:27:57,919 --> 00:28:03,200 because if those components were not 626 00:27:59,919 --> 00:28:05,720 secure then we couldn't map each set of 627 00:28:03,200 --> 00:28:08,240 such transactions to a graph in the way 628 00:28:05,720 --> 00:28:10,039 that I'm going to show you next so I'm 629 00:28:08,240 --> 00:28:13,559 not going to show you how exactly we 630 00:28:10,039 --> 00:28:16,039 translate such a transaction um set to 631 00:28:13,559 --> 00:28:17,760 the graph but but this is intuitively 632 00:28:16,039 --> 00:28:20,360 where the cryptographic security of 633 00:28:17,760 --> 00:28:24,399 these components would come 634 00:28:20,360 --> 00:28:26,720 in okay so let's go directly to step 635 00:28:24,399 --> 00:28:28,880 three how to translate this into a 636 00:28:26,720 --> 00:28:31,120 direct graph 637 00:28:28,880 --> 00:28:34,279 so the directed graph is going to look 638 00:28:31,120 --> 00:28:37,399 as follows we're going to have two types 639 00:28:34,279 --> 00:28:39,440 of notes actually four types so there's 640 00:28:37,399 --> 00:28:42,440 going to be a source which is going to 641 00:28:39,440 --> 00:28:45,840 supply an initial amount of coins to the 642 00:28:42,440 --> 00:28:48,559 system and then we have light gray nodes 643 00:28:45,840 --> 00:28:52,279 and they correspond to 644 00:28:48,559 --> 00:28:54,039 unspent uh outputs and now each of these 645 00:28:52,279 --> 00:28:56,919 light gray nodes you see can be 646 00:28:54,039 --> 00:28:59,159 connected to um one of these darker 647 00:28:56,919 --> 00:29:01,960 nodes and the dark nodes are going to be 648 00:28:59,159 --> 00:29:04,080 transactions which spend those unspent 649 00:29:01,960 --> 00:29:06,840 outputs and they're going to spend them 650 00:29:04,080 --> 00:29:09,240 into new uh unspin 651 00:29:06,840 --> 00:29:12,399 outputs and then of course at the at the 652 00:29:09,240 --> 00:29:14,840 very end when the system ends or dies we 653 00:29:12,399 --> 00:29:16,960 going we're going to have a Target node 654 00:29:14,840 --> 00:29:20,799 and and anything that wasn't spend at 655 00:29:16,960 --> 00:29:23,679 that time uh just goes into this target 656 00:29:20,799 --> 00:29:26,120 directly so this is our graph and now we 657 00:29:23,679 --> 00:29:28,080 you see we have these labeled edges here 658 00:29:26,120 --> 00:29:32,039 um and these label 659 00:29:28,080 --> 00:29:34,360 actually correspond to the amount of 660 00:29:32,039 --> 00:29:37,039 this unspent output that is being 661 00:29:34,360 --> 00:29:39,760 transferred into the transaction 662 00:29:37,039 --> 00:29:43,919 corresponding to these dark ray nodes so 663 00:29:39,760 --> 00:29:47,360 each of these um uh arrows here can be 664 00:29:43,919 --> 00:29:51,200 labeled with such an amount and 665 00:29:47,360 --> 00:29:53,679 um that is how we build this graph so 666 00:29:51,200 --> 00:29:55,559 now here is a brief interlude I told you 667 00:29:53,679 --> 00:29:57,880 that we want to apply some graph 668 00:29:55,559 --> 00:30:01,559 theoretic argument to this graph that we 669 00:29:57,880 --> 00:30:03,559 build and um just to give you a rough 670 00:30:01,559 --> 00:30:06,720 idea of how this will 671 00:30:03,559 --> 00:30:09,960 work um what we're going to use here is 672 00:30:06,720 --> 00:30:12,840 the theory of flow networks so that 673 00:30:09,960 --> 00:30:15,000 sounds a little uh you know maybe 674 00:30:12,840 --> 00:30:17,799 abstract but but it's actually quite 675 00:30:15,000 --> 00:30:20,080 simple so a flow Network what it means 676 00:30:17,799 --> 00:30:21,320 is basically you have a graph and and 677 00:30:20,080 --> 00:30:24,440 this 678 00:30:21,320 --> 00:30:26,760 graph corresponds to a network of flows 679 00:30:24,440 --> 00:30:29,480 passing through through a system so each 680 00:30:26,760 --> 00:30:32,960 of these arrows will correspond to some 681 00:30:29,480 --> 00:30:34,480 flow going from one node to another node 682 00:30:32,960 --> 00:30:37,200 and the property that is crucially 683 00:30:34,480 --> 00:30:40,360 exploited in a flow network is that for 684 00:30:37,200 --> 00:30:43,519 every node in the flow Network whatever 685 00:30:40,360 --> 00:30:47,200 goes in has to go out okay so for 686 00:30:43,519 --> 00:30:51,360 example you can see that um the node 687 00:30:47,200 --> 00:30:54,480 just above the source uh it gets as an 688 00:30:51,360 --> 00:30:57,519 input two flows one one and what comes 689 00:30:54,480 --> 00:30:59,679 out is two and if we have such a flow 690 00:30:57,519 --> 00:31:03,120 Network then we can consider something 691 00:30:59,679 --> 00:31:06,559 called an st cut which is defined as 692 00:31:03,120 --> 00:31:09,320 follows so basically we can partition 693 00:31:06,559 --> 00:31:13,240 all of these nodes in the graph into two 694 00:31:09,320 --> 00:31:16,159 disjoined subsets s and t where s 695 00:31:13,240 --> 00:31:18,000 contains the source and T contains T but 696 00:31:16,159 --> 00:31:20,000 otherwise there is no restriction on 697 00:31:18,000 --> 00:31:23,120 them and now there is a very simple 698 00:31:20,000 --> 00:31:25,600 Lemma that says that any cut in this 699 00:31:23,120 --> 00:31:27,840 network will have the same value so what 700 00:31:25,600 --> 00:31:30,360 is a cut basically a cut is just the 701 00:31:27,840 --> 00:31:33,960 partition as I said of these nodes into 702 00:31:30,360 --> 00:31:35,360 two distinct sets uh which where one of 703 00:31:33,960 --> 00:31:37,720 them contains the source and the other 704 00:31:35,360 --> 00:31:41,760 the Target and now we just see how much 705 00:31:37,720 --> 00:31:44,760 flow goes over this cut so as an example 706 00:31:41,760 --> 00:31:47,559 I could have a cut where the target is 707 00:31:44,760 --> 00:31:49,880 just one node uh in T and and everything 708 00:31:47,559 --> 00:31:52,480 else is in s then we can see that the 709 00:31:49,880 --> 00:31:55,519 value of the cut is three because what 710 00:31:52,480 --> 00:31:57,320 comes out of the left partition is and 711 00:31:55,519 --> 00:32:00,720 and goes into the target is exactly 712 00:31:57,320 --> 00:32:02,799 three but if I look at a cut where these 713 00:32:00,720 --> 00:32:06,279 blue nodes are in s and the black nodes 714 00:32:02,799 --> 00:32:09,360 are in t then what is going out of s 715 00:32:06,279 --> 00:32:12,080 will be four but what goes back into s 716 00:32:09,360 --> 00:32:15,720 from T is one so the overall flow that 717 00:32:12,080 --> 00:32:17,440 goes out of s into T is still three uh 718 00:32:15,720 --> 00:32:21,440 and and for this example it's the same 719 00:32:17,440 --> 00:32:22,880 thing okay so any cut yields the same uh 720 00:32:21,440 --> 00:32:26,919 the same 721 00:32:22,880 --> 00:32:29,200 value okay so we use this now in our in 722 00:32:26,919 --> 00:32:30,039 our security argument after defining 723 00:32:29,200 --> 00:32:32,360 this 724 00:32:30,039 --> 00:32:34,159 graph so first we have to argue that it 725 00:32:32,360 --> 00:32:36,200 is a flow Network that also comes into 726 00:32:34,159 --> 00:32:37,960 our security analysis but once we do 727 00:32:36,200 --> 00:32:41,320 that then we can actually Define a very 728 00:32:37,960 --> 00:32:44,919 simple St cut as follows well basically 729 00:32:41,320 --> 00:32:48,080 we're just going to let uh you know uh 730 00:32:44,919 --> 00:32:50,880 the the the left half of this cut be the 731 00:32:48,080 --> 00:32:52,679 honest uh unspent transaction outputs 732 00:32:50,880 --> 00:32:54,720 for responding to non-corrupted nodes 733 00:32:52,679 --> 00:32:57,200 that don't belong to the adversary and 734 00:32:54,720 --> 00:32:59,799 the rest of these nodes are going to to 735 00:32:57,200 --> 00:33:02,360 belong to the adversary so those are the 736 00:32:59,799 --> 00:33:06,639 ones that it controls and now we're 737 00:33:02,360 --> 00:33:09,799 asking how much flows from the honest 738 00:33:06,639 --> 00:33:11,399 parties uh you know unspent outputs over 739 00:33:09,799 --> 00:33:14,440 to the 740 00:33:11,399 --> 00:33:19,440 adversary and we Analyze This 741 00:33:14,440 --> 00:33:21,440 value and then through a series of um of 742 00:33:19,440 --> 00:33:23,200 inequalities which which are I'm not 743 00:33:21,440 --> 00:33:24,639 going to explain here in detail because 744 00:33:23,200 --> 00:33:27,480 I think I'm running out of time a little 745 00:33:24,639 --> 00:33:30,720 bit uh we are able to show 746 00:33:27,480 --> 00:33:32,960 that the amount of receip coins is 747 00:33:30,720 --> 00:33:35,679 greater or equal to the amount of spend 748 00:33:32,960 --> 00:33:38,639 coins so the intuition of course behind 749 00:33:35,679 --> 00:33:40,919 this is that you know basically the the 750 00:33:38,639 --> 00:33:43,679 flow should always be preserved so it 751 00:33:40,919 --> 00:33:45,399 should not be possible to to spend more 752 00:33:43,679 --> 00:33:48,519 coins than you receive because this 753 00:33:45,399 --> 00:33:50,760 would amount to to violating the 754 00:33:48,519 --> 00:33:52,440 condition of a flow Network in one of 755 00:33:50,760 --> 00:33:54,799 these nodes and this is basically what 756 00:33:52,440 --> 00:33:56,679 the theories of inequality shows here so 757 00:33:54,799 --> 00:33:59,000 it's just a nice way of abstracting this 758 00:33:56,679 --> 00:34:00,399 problem and being able to mathematically 759 00:33:59,000 --> 00:34:03,120 analyze 760 00:34:00,399 --> 00:34:06,200 it okay so let me summarize what I 761 00:34:03,120 --> 00:34:09,000 talked about today so what did we see 762 00:34:06,200 --> 00:34:11,679 what did we find out so we had Mono and 763 00:34:09,000 --> 00:34:15,399 ring CT and we had a new security model 764 00:34:11,679 --> 00:34:18,159 that we saw and we proved the uh 765 00:34:15,399 --> 00:34:20,960 security of Monero and ring CT in a in a 766 00:34:18,159 --> 00:34:22,159 in a formal sense using the theory of 767 00:34:20,960 --> 00:34:25,200 flow 768 00:34:22,159 --> 00:34:27,040 networks so that concludes my talk um 769 00:34:25,200 --> 00:34:32,200 but I'm happy to to take in any 770 00:34:27,040 --> 00:34:32,200 questions um and uh thank you for 771 00:34:38,200 --> 00:34:45,079 listening all right that was great thank 772 00:34:41,599 --> 00:34:47,720 you thank you if anything if anything 773 00:34:45,079 --> 00:34:51,720 comes through in the chat I 774 00:34:47,720 --> 00:34:53,480 will I will read it out loud but so far 775 00:34:51,720 --> 00:34:58,879 I do not see 776 00:34:53,480 --> 00:34:58,879 anything pertains exactly to this 777 00:35:02,520 --> 00:35:06,200 maybe I'll give it a couple minutes just 778 00:35:04,400 --> 00:35:08,680 in case you know someone's already 779 00:35:06,200 --> 00:35:08,680 something 780 00:35:19,040 --> 00:35:24,760 long here on you said that security was 781 00:35:22,280 --> 00:35:28,800 proven but anonymity not what are the 782 00:35:24,760 --> 00:35:28,800 plans for proving the latter 783 00:35:29,320 --> 00:35:32,880 wait I'm I'm not sure I understand the 784 00:35:30,680 --> 00:35:34,119 question can you so so what is what is 785 00:35:32,880 --> 00:35:37,119 not 786 00:35:34,119 --> 00:35:37,119 proen 787 00:35:38,079 --> 00:35:44,839 uh could could you repeat the question 788 00:35:40,200 --> 00:35:46,640 I'm sorry oh uh yeah um I think this 789 00:35:44,839 --> 00:35:48,680 person may have been speaking to someone 790 00:35:46,640 --> 00:35:52,480 else in chat not 791 00:35:48,680 --> 00:35:54,839 sure um no no that was you uh sorry you 792 00:35:52,480 --> 00:35:57,240 said that security was proven but 793 00:35:54,839 --> 00:36:00,920 anonymity not what are the pl for 794 00:35:57,240 --> 00:36:04,960 proving the latter oh oh I see okay okay 795 00:36:00,920 --> 00:36:06,720 so that's a good question so the yeah 796 00:36:04,960 --> 00:36:09,480 that's that's a good 797 00:36:06,720 --> 00:36:12,040 question now now the the issue is with 798 00:36:09,480 --> 00:36:15,800 that first of all it requires very 799 00:36:12,040 --> 00:36:18,560 different set of arguments um because 800 00:36:15,800 --> 00:36:20,240 the the anonymity guarantees so we we 801 00:36:18,560 --> 00:36:21,839 actually know that that some of the 802 00:36:20,240 --> 00:36:24,720 anonymity 803 00:36:21,839 --> 00:36:27,599 guarantees are are difficult to prove in 804 00:36:24,720 --> 00:36:30,520 the narrow because there are these um 805 00:36:27,599 --> 00:36:32,599 these graph-based attacks on anonymity 806 00:36:30,520 --> 00:36:35,280 and it's it's very difficult to formally 807 00:36:32,599 --> 00:36:37,440 capture them and um we were thinking 808 00:36:35,280 --> 00:36:39,880 about this but then we were actually 809 00:36:37,440 --> 00:36:43,160 speaking to some Monero developers and 810 00:36:39,880 --> 00:36:45,560 they told us that there was a plan to 811 00:36:43,160 --> 00:36:48,880 migrate to a uh to a new transaction 812 00:36:45,560 --> 00:36:52,319 system in the near future called I think 813 00:36:48,880 --> 00:36:55,280 sfus and um it's it's unclear to us 814 00:36:52,319 --> 00:36:57,200 whether it would make sense to analyze 815 00:36:55,280 --> 00:37:00,680 the anonymity property 816 00:36:57,200 --> 00:37:02,560 of of Monero as currently is um you know 817 00:37:00,680 --> 00:37:05,599 when there is a new transaction system 818 00:37:02,560 --> 00:37:08,680 on the horizon which might be easier to 819 00:37:05,599 --> 00:37:11,280 analyze or or guarantee better anonymity 820 00:37:08,680 --> 00:37:13,599 um so at this point we're not sure if if 821 00:37:11,280 --> 00:37:17,160 we should you know wait for another year 822 00:37:13,599 --> 00:37:19,599 or go for whatever is currently online 823 00:37:17,160 --> 00:37:23,359 and and I guess we we would appreciate 824 00:37:19,599 --> 00:37:23,359 feedback from the community actually on 825 00:37:25,599 --> 00:37:28,599 that 826 00:37:31,599 --> 00:37:36,920 oh man it happened again someone uh 827 00:37:34,640 --> 00:37:40,920 tried to send a message longer than 280 828 00:37:36,920 --> 00:37:43,400 characters and the uh streamyard just 829 00:37:40,920 --> 00:37:45,960 ate it up um but it looks like they got 830 00:37:43,400 --> 00:37:48,280 it through in a technical sense do you 831 00:37:45,960 --> 00:37:50,440 think some cryptocurrency protocols or 832 00:37:48,280 --> 00:37:52,760 private communication Protocols are too 833 00:37:50,440 --> 00:37:54,960 close to the bleeding edge putting users 834 00:37:52,760 --> 00:37:58,119 at risk due to missing security proofs 835 00:37:54,960 --> 00:38:02,839 or insufficiently reviewed security 836 00:37:58,119 --> 00:38:02,839 proofs um yeah that's a good question I 837 00:38:05,480 --> 00:38:09,640 mean so so it's it's an interesting 838 00:38:07,720 --> 00:38:12,680 question because I think there's so much 839 00:38:09,640 --> 00:38:14,280 Innovation coming out of this space uh 840 00:38:12,680 --> 00:38:16,200 it's it's really amazing right there 841 00:38:14,280 --> 00:38:18,839 there are so many smart people in the 842 00:38:16,200 --> 00:38:21,520 space um but a lot of them of course you 843 00:38:18,839 --> 00:38:24,599 know so many nice ideas but of course 844 00:38:21,520 --> 00:38:27,560 inevitably a lot of these ideas um there 845 00:38:24,599 --> 00:38:30,720 may be not 100% thought through 846 00:38:27,560 --> 00:38:32,000 sometimes they're like Minor Details 847 00:38:30,720 --> 00:38:34,839 very difficult to see and you really 848 00:38:32,000 --> 00:38:36,440 need a kind of a formal training and 849 00:38:34,839 --> 00:38:39,200 have worked a couple of years in the 850 00:38:36,440 --> 00:38:40,760 space to be able to to detect them right 851 00:38:39,200 --> 00:38:42,480 so so often you know like these these 852 00:38:40,760 --> 00:38:44,160 Crypt analytic techniques they can be 853 00:38:42,480 --> 00:38:47,079 very very subtle to 854 00:38:44,160 --> 00:38:48,839 apply and um and there's obviously a lot 855 00:38:47,079 --> 00:38:50,599 of lature on the stuff so it's not 856 00:38:48,839 --> 00:38:52,480 always easy to see where the 857 00:38:50,599 --> 00:38:56,839 vulnerabilities 858 00:38:52,480 --> 00:38:58,359 lie um but but I think it's yeah so I 859 00:38:56,839 --> 00:39:00,359 think I think it's a double-edged sword 860 00:38:58,359 --> 00:39:02,079 right on the one hand we have all of 861 00:39:00,359 --> 00:39:04,040 these amazing new applications coming 862 00:39:02,079 --> 00:39:06,160 out and it's it's been great you know um 863 00:39:04,040 --> 00:39:09,480 I think the the space has seen so much 864 00:39:06,160 --> 00:39:11,839 progress over the past one and a half 865 00:39:09,480 --> 00:39:14,400 decades and but but I think with that 866 00:39:11,839 --> 00:39:16,760 there is always a risk of there being 867 00:39:14,400 --> 00:39:20,000 something deployed that is um that is 868 00:39:16,760 --> 00:39:22,440 not fully secure yet and 869 00:39:20,000 --> 00:39:24,160 um I'm I'm actually not sure what to do 870 00:39:22,440 --> 00:39:26,640 about that I think I think we're we're 871 00:39:24,160 --> 00:39:29,079 slowly moving toward a scenario where 872 00:39:26,640 --> 00:39:31,000 where people are becoming more aware of 873 00:39:29,079 --> 00:39:32,960 this and trying to to give formal 874 00:39:31,000 --> 00:39:35,480 security proves before 875 00:39:32,960 --> 00:39:38,280 deployment um but I think we're not 876 00:39:35,480 --> 00:39:38,280 completely there 877 00:39:40,480 --> 00:39:46,440 yet all right um it doesn't look like we 878 00:39:43,079 --> 00:39:49,440 have anything else and Seth uh our last 879 00:39:46,440 --> 00:39:53,880 speaker is ready to go so thanks so much 880 00:39:49,440 --> 00:39:53,880 Julian thank you okay see you 881 00:39:55,400 --> 00:40:07,089 byebye 882 00:39:57,310 --> 00:40:07,089 [Music] 883 00:40:13,600 --> 00:40:17,550 [Music]