Using Ethereum for Secure Decentralized Optimization

and for secure decentralized optimum optimization great so if you're debating whether to be in this room or up in the main hall we can cut to the chase the topic of my talk will be discussing how to solve hard math problems off chain how can we actually address problems in machine learning market clearing operation scheduling how can we use smart contracts to be able to bring those problems in consensus on a global optimum and then how can we guarantee security feasibility and optimality of this type of problem the general outline I'm gonna be talking about optimization problems and I don't mean compiler optimization here but a couple of different classes of problems that I work on I'm a PhD student at UC Berkeley and then talk about how we can integrate smart contracts to really improve the application of these types of optimization tools to a wider set of problems I come from a energy background energy markets and the electricity market specifically so I'm gonna be discussing an application of this that I've researched in electricity market formulation for small micro grids so optimization just so that we're all on the same page who here has heard of convex optimization before okay a few hands that's great so in general optimization problems have the goal of minimizing or maximizing some function the dark curved line here subject to some constraints so we can't be in this dark blue area in general these are pretty hard we might end up in the select local minima we'd like to end up in the global minima convex optimization problems make this a lot easier we can prove that a type of problem it basically looks like a bowl as long as we follow the slope of this downwards we'll end up at the right global Optima so there's a lot of tools that we can bring to bear when we know that a problem is convex one of the more interesting components of this is that we can think of it in a decentralized optimization form conventionally we just have one System Operator who has all of the information about all of the data all the constraints in the system so even if these are say individual households who have mobility constraints on their electric vehicles individual participants who have different investment goals for portfolio optimization individual manufactories that have constraints on production one System Operator would have all the knowledge about all those constraints and run the centralized optimization problem this is great if all of those entities are owned by the same person it's hell if you end up with people who don't trust each other and to reach a global optimum you need some sort of way of decentralizing this problem into a trustless cooperative system so decentralized problems break that into a set of local optimization problems these blue dots that then coordinate back and forth with an aggregator until they reach consensus on that global optimum this is really important we're actually able to guarantee that we're going to hit the global optimum even though we start up with these local problems why would we bother with this so one really beautiful part of this is that we can actually take a hard big problem break it into a set of analytically solvable subproblems so you can get a thousand X speed-up in computation time even while running it on the same computing node another part is just breaking a hard problem that has say greater than quadratic compute complexity and break it into a set of small problems even though you're breaking into n smaller problems you've practically reduced your compute time then the other part is that if there's those privacy and trust issues you don't want to share all that information with the global aggregator so the aggregator that person who coordinates between all these nodes has a really easy job fortunately these nodes have hard compute problems subject to local constraints about which they have private information but the aggregator only has a very simple arithmetic update problem in a lot of these formulations so even though this can be something that takes minutes or even hours to compute off chain on a CPU or a server cluster this is just a really simple update problem so this is just adding all those numbers together and broadcasting the update to the rest of the network it's sort of like a market so individuals have a sense of their value functions for a particular good they can propose how much they'd like to sell or buy the market operator aggregates all those together estimates what the market clearing price would be broadcast that price out to everybody people can update their their estimates of their bids or asks for the object and when you iterate back and forth with that you're able to reach consensus and for these comics optimization problems we can prove that that's the global optimum so going from these centralized or sorry decentralized problems to a fully decentralized model one of the challenges with this model of architecture is the aggregator has to have direct lines of communication with every single node so not a problem when you just have three nodes here for the types of electricity market problems that I consider where you're trying to control say 10 million electric vehicles you don't want to have one server that's trying to talk to 10 million electric vehicles all at once you need a more decentralized model so fully decentralized optimization has become a tool that's in vogue in particular for these really large decentralized optimization problems one of the challenges though is that you're only sharing information with your neighbors and those neighbors might be lying to you if they've been compromised so while you might be communicating with your neighbor that neighbor may have had his electric vehicle hacked by somebody and that hacker is attempting to cause a blackout in the electricity grid for instance so we have a question of how do we identify the nodes that have been compromised how do we reach stable operation and then can we guarantee feasibility or optimality of the system when these nodes have been compromised so we have this like bi-directional communication between each neighbor so we just see messages that our neighbor is sending us in this case the Red Nosed has been compromised so rather than the normal operation of the system the red node could distort its private optimization problem so it solves some problem that doesn't actually reflect reality in a machine learning or data science problem this could be that you're throwing in junk data and the network doesn't necessarily know that it just sees some message from you it might not have looked been entirely expecting that message but it can't know whether that's because you're acting strange or whether that's because you're upstream participants have sent you bad data so there's difficulty in identifying where the flaw in the system is also a compromised node can just send a bad signal to its neighbors like unidirectionally and if it knows that there's certain types of problems that this node cannot address her like certain areas where this node would be infeasible it can send a signal that's always going to be infeasible this node basically freaks out is never able to reach consensus it's never able to reach feasibility and the system fails to converge then also a compromised node could just inject noise into the system so that at every update step you have a noisy signal and you're failing to converge because of that so what can we do to prevent these modes of attack what we'd like to do is perhaps bypass any node that might be compromised if you're trying to make your system redundant or resilient to attacks up to end nodes this ultimately would mean that you need a fully connected graph with secure communications channels the other way that we could address this would be have some other centralized database that provides a global information layer on all the state variables now this is starting to look a little bit more like a blockchain so taking that information from a peer-to-peer communication and having that passed trust lessly between all the peers on the network gives us global insight into the state of all the variables in the network this allows us to perform security checks on the signals that we're receiving from our neighbors and thus identify the nodes that have been compromised this is really powerful because it means that we no longer have to trust either an aggregator somebody who's holding the database or just trust our neighbors but we get the benefits of both of those so one of the things that's really interesting about this is we think of block chains as these iterative computations that reach consensus also decentralized optimization also is this same model of iterating between local problems with an aggregator update step or at the rest of the network and reaching eventually consensus on the system the research that I've been doing is highlighting the similarity to be able to create a sort of combined model where these local update steps are coordinating with a smart contract to be able to create or to process a secure verifiable update step ultimately reaching a solution that is auditable you can see how you got to that solution you can prove the optimality of that and know whether or not there were attacks along the way and then that solution can be stored on the blockchain for everybody to access thinking about a couple of the different ways that these different models fail so we first talked about aggregator coordinated decentralized optimization prone to monopolies distortions so anytime that there's a market operator a scheduler who has their own incentives and you may not trust their incentives you wouldn't want to trust some monopolies aggregator they're prone to communication dropouts there if there's a an outage in the electricity grid that monopolies or that centralized aggregator wouldn't be online wouldn't be able to coordinate between these local nodes conversely the fully decentralized models addressed those but had exposed us to these other weaknesses and by using a blockchain to provide a global information layer between all of these we're able to have the benefits of the centralized aggregator problem while also avoiding the pitfalls of the fully decentralized problem so let's take an example this is where my research is in electricity markets and this may be a feel that's unfamiliar to a lot of you but as we look ahead at larger penetrations of electric vehicles and photovoltaic solar systems we'll end up with these big swings and power flows on the local distribution network so going from a model where you can always plan for the power consumption because you know that people just have small loads like toasters and electric light bulbs to a world where you have the Sun might go behind a cloud everybody's photovoltaic generation cuts off at the same time people's electric vehicles are plugging in you have these massive imbalances and generation utilities would like to be able to address these imbalances in a way that minimizes the cost of electricity generation that cost minimization means that we're dealing with an optimization problem here the other challenge though is that the electricity network is constrained we can't just have some generators off a hundred miles away that are going to make up for this we need to be able to respect the local constraints in the system particularly in what I'm modeling the distribution network within a neighborhood one of the challenges though is that the utilities have market power and all of the people who provide your smart devices may be competitors with each other in the marketplace there's a lack of trust not only between perhaps you and the utility who wants to sell you power but also between all of the participants in this marketplace so you might have a household that has a Tesla electric car a Ford electric car both of those are competing with each other to sell regulation services on an energy market you might have different smart thermostats who are competing to be able to provide energy services on a market while also provide these household level services we'd like to be able to reach consensus on the way that most equitably provides compensation for energy services that each of these devices gives so taking that same paradigm that I described earlier we're breaking this big scheduling problem with a bunch of trustless participants into a set of local problems where each household or each node the network as defined by the actual physical constraints of the system resolves a private optimization problem this is harder than you something you would want to run on the blockchain but a lot cheaper than solving it all is one centralized problem those work together through this a smart contract that coordinates the update step to be able to eventually reach consensus on the best schedule for all of these devices so the goal is to minimize the power cost for everybody provide compensation for all of the devices that are participating in this network and do so automatically so we have a model of our network this is the the physical network that actually provides these constraints that gets fed into these smart contracts so we have the optimization problem the smart meter then those the optimization updates get communicated with smart contracts on the blockchain one for actually coordinating the update step once we reach consensus that can be bounced over to a smart contract that does billing and any reconciliation between the expected schedule and the actual realized schedule and so with that we're able to eventually identify when we pick consensus on the global optimum we can guarantee the optimality of the system along the way we're performing security checks to make sure that none of these nodes have been compromised in a way that will push us into an in feasible region caused a blackout and ultimately end up with basically a self scheduling utility free electricity system so just to sort of show some pretty graphs because we have results to share the we can see how we're actually shifting around the behind the meter batteries the shapeable loads in the purple lines deferrable loads like smart washers or smart appliances and moving all of those around to make sure that we're taking advantage of all of the photovoltaic energy that's being pumped into the grid across the whole node we're actually monitoring the physical constraints of the system at every point in the the distribution network we're making sure that the voltage doesn't go out of our acceptable bounds this is the physical constraint that defines the system and we're able to converge on a schedule that is only suboptimal in price by 0.4 percent so really close to what you would get if a utility were solving all of this privately and then we can also guarantee the constraints are satisfied that this isn't going to blow up that our electricity system is still going to stay stable so we've solved a hard optimization problem with physical constraints with an algorithm that respect local privacy and can guarantee the optimality and the feasibility of the solution challenges and opportunities looking ahead so these mirror the the three big areas the Vitalik was talking about yesterday one is privacy so I'm very interested in the sessions tomorrow on zero knowledge proof to be able to identify how can we actually make sure that the information we're sending back and forth is not sensitive so in the model that I just described the actual power consumption for each household ends up getting stored on the blockchain there's concerns about say a thief being able to identify when somebody is away from home and thus could break into the house if they know what everybody's expected power consumption is the other part is there's a potential for data leakage through the iterations back and forth so that even if the information that you're sending is not fundamentally sensitive that the information that is leaking out of the system by how much you're changing your estimate at each of these steps might indicate something about what your private optimization problem is so the security we've been working on like provable guarantees of the feasibility with untrusted nodes one big comment here is that these proofs generally have much weaker conditions than the tea would give so in these constraint systems your ability to guarantee feasibility is going to be dependent on the topology of how faulty nodes are connected and in general though because it's going to be dependent on that we can't guarantee the same one third proof against attack that bft systems generally have scalability so currently looking at converging in about 20 iterations of the system each of those iterations requires update steps or variable updates sent to the aggregator node the aggregator node performing that or the aggregator smart contract performing that update and then broadcasting that back so each of those is at minimum two to three secured box so in net this could be a relatively long slow process it's an area where again like looking at plasma or other ways of speeding this up could improve the system with that I think we have some extra time sure one of the one of the general techniques for dealing with blockchain scalability is only going to the blockchain when necessary are there equivalents here where you could sort of determine that some subset of the network is behaving badly and only go to the blockchain in that case yeah so one area that I'm interested in looking at is state channels to be able to identify basically what are the the portions that we need to update and what which portions of the updates need to be saved to the blockchain which portions can just be done through state channels and not have all of that constantly back and forth on the main blockchain you mentioned there are some nodes that might be untrustworthy but it seems that every node corresponds to a household and every household has you know is it is in their own interest to act you know the trustworthy manner so why is that an issue here so if you think of say the hack against the Ukrainian electricity grid where an outside party was interested in actually just bringing down the whole grid for malicious intent you don't care about the private household reasons for the attack there might be somebody who just wants to cause a blackout so the this is a really unique challenge of this type of work the the private problem of the household is dependent on constraint information fed to them by all the devices so somebody could hack an electric car and pass bad information to the even if it's a secure Enclave that does the actual computation if that's a cure Enclave is getting garbage then it needs to you effectively can't expect that the message is being passed the network or trustworthy one question though there may be one last question any more questions what about offline when the devices are being offline so this is a great question I'm interested in looking into models of sharding and being able to split this up that is one of the big benefits of the fully decentralized - algorithm says that you don't care where there's a break in the system those can still reach local optimality when you have a blockchain being able to bring those to basically forked chains back into consensus is something I haven't yet looked at but want to thanks Eric [Music]