Replies: 6 comments 25 replies
-
|
Great write up! I'll provide more detailed comments later on - but this is very close to how I was thinking about it as well. There is one difference though - I imaged data flow to be somewhat different. Specifically, it could look something like this (for simplicity this is just for the plaintext state case):
The flow is as follows:
Basically, in this approach, the account logic is fully responsible for ensuring that DA has the latest account state. The main advantage of this is that we don't need to add anything to the base protocol to support this. Potential disadvantages are:
There are also probably other advantages and disadvantages - so, we should try to think through them more. Also, dealing with the encrypted state adds a few more complications which I'll go over later. |
Beta Was this translation helpful? Give feedback.
-
A question here is what do you mean by public key? Are you imaging this being a simple multisig / data availability committe? If so, are we comfortable with the additional trust assumption this introduces? I would be strongly opposed to introducing multisig based DA into the protocol. An alternative would be to verify a consensus proof of the DA layer but then we introduce a honest majority assumption and verifying a consensus proof would be a highly complex and expensive task.
By design, DA layers do not compute on the data they make available, they simply commit to the data using some commitment scheme (merkle tree / kzg etc). I guess you are implying we introduce a custom data availability committee for Miden?
The biggest disadvantage in my opinion is the additional trust assumption on the data availability committee. I don't think this trust assumption should be introduced lightly. Another disadvantage is we make the transaction kernel interactive and as such the latency is constrained by the responsiveness of the data availability committee. Additionally, it makes offline transaction execution a bit more awkward. Its also worth crunching some numbers on this. Lets take an "extreme" case in which 2000 slots change across the account vault and storage for an account. In this case the account delta would be 2000 * 2 (key + value) * 256 = 125 kB. This is quite a large data blob to be posting to a DA layer. To put it into context Ethereum will support 1MB per block. |
Beta Was this translation helpful? Give feedback.
-
|
To answer simpler questions first:
It could be anything: a centralized server (e.g., Google cloud, but with ability to sign things), a data availability committee with multisig, or some DA layer with internal consensus mechanism - or some combination thereof. All of these have pros and cons - and it could be up to each account to decide what they want to use.
Totally agree. What I described does not introduce anything at the core protocol level. We basically leverage the fact that all accounts are smart contracts and can have arbitrary logic. Within this logic, they can define how the state can be updated.
I actually think from the "cost" stand point this shouldn't be too bad - could be as simple as verifying a recursive proof (which is comparable to verifying a signature right now). I do think that latency might be a significant challenge for this scenario.
No, Miden still puts all on-chain account data on Ethereum. But off-chain accounts would be free to choose DA solution that works for them. As mention above, in my proposal off-chain account DA is not tied into Miden protocol. Now, to more complex questions:
I agree - we shouldn't introduce any additional trust assumptions (especially ones based on multisig). So, ideally, I'd like to keep the solution to the "problem of off-chain account state" separate from the protocol. The question is to what extent this is possible. Or rather, what minimal changes to the core protocol design do we need to make to support use cases that most people would care about. Let's take a use case of a personal wallet. I think in most cases, a DA committee or even a centralized solution could be perfectly acceptable here. In the extreme case, I could choose to back up my wallet state to Google cloud (assuming they support the right APIs). The likelihood that my key is compromised and Google decides to withhold the data from me at the same time is pretty low in my mind (I could also use Google and Amazon etc. in parallel, to reduce such risks). Two important assumptions I'm making here:
I've used Google just as an example, but I do think that there could be a vibrant ecosystem of different DA solutions which people could opt into on per-account basis. These solutions would provide different tradeoffs on cost, latency, decentralization etc. and users could chose what they are most comfortable with. While I think something like the above could work for most people, there definitely would be people who would not want to introduce any additional parties into the mix. The simplest solution for such people would be to use on-chain accounts (ideally, with encrypted state) as data for these accounts would end up on Ethereum and could be recovered from there. I do expect these accounts to be rather "expensive" because putting data on Ethereum probably will remain a bottleneck. For example, at 1K TPS, even posting account state commitments to Ethereum would require about ~40KB/sec or ~500KB per block. And this doesn't include note commitments, nullifiers etc. So, I guess one question is: why, as I user, I would prefer to use a separate DA layer which still puts data on Ethereum vs. using a Miden on-chain account which also puts data on Ethereum?
I agree with this - but want to say that this shouldn't affect the kernel itself, only the user-provided code. Also, I'm not sure we'll be able to get away from making transaction execution "interactive" at least in some cases. For example, I may store my private key in a secure element or in a cold wallet. In such cases, the kernel would execute the transaction, the transaction would make a request for signature to an external component (i.e., secure element) and then resume execution once the signature is received.
I think this depends on implementation. For example, I may chose a DA layer with 1 second guarantee on returning a signature (or some other proof) attesting that they have my latest update, and this could be good enough in many cases. |
Beta Was this translation helpful? Give feedback.
-
Good point, it does make sense to give the user the freedom to choose a solution that fits their requirements.
This makes sense.
I thin the cost of consensus proof verification is quite expensive inside a zk circuit. Here are some benchmarks from succinct labs for verification of Ethereum sync committee based protocol (not full consensus proof). An actual consensus proof with full validator set security would probably be orders of magnitude more expensive.
I think you made some very strong points about providing options for users which I agree with. I also think we should ensure that off-chain accounts can achieve full L1 security. As you say, encrypted on-chain accounts do in-deed provide a viable option for this. However, this being the only solution to achieve L1 security is not ideal as it is at odds with our goal of minimising state bloat. I would expect there to be some cost for storing account state on-chain (there must be or else it is an attack vector). So from a user perspective it will be cheaper to use L1 only for DA and store the account off-chain. We should also consider implications of this. If the user has encrypted on-chain account then they will have to post the full encrypted state after each transaction as the node operator will not be able to apply an encrypted account state diff (unless we use some form of homomorphic encryption? but this is likely out of scope anyway). Having to post the full encrypted account state every time increases bandwidth requirements on the network. If the account was stored locally then the user would fetch the new encrypted state diff, unencrypt it and apply it to their local plaintext account state.
I thin we can make a distinction between locally interactive and network based interaction. I also think it would be possible to sign messages ahead of time and load them into the advice provider instead of signing as requests are made by the the VM. |
Beta Was this translation helpful? Give feedback.
-
I think we need to clarify the terminology here. Originally, the way I thought about accounts is as follows:
In the off-chain account case, the core protocol is not concerned with how the user chooses to manage their state. But I think we are now discussing another type of an account - I'll call it a "hybrid" account (but probably a better term is needed). These accounts rely on L2 for execution and on L1 for DA. So, now we have 3 types of accounts:
So, the question is really to evaluate pros and cons (e.g., cost, complexity etc.) of these, and maybe the eventual answer is that we should support all 3.
Maybe, but I'd like to think through this a bit more. If for example, L1 DA costs are 99% of the overall cost, the benefit may be marginal.
I actually think that maybe we can do this. We just need to authenticate the encrypted state diff, and based on our offline discussion, this may not be as complicated as I originally thought. |
Beta Was this translation helpful? Give feedback.
-
Yes I think this illustrates the different account types well. Maybe it's worth making the analysis 3 dimensional: execution, storage, DA.
I think there are two components here - the costs to users for storing the account on-chain and also the implications of on-chain accounts (i.e. state bloat). I don't think state bloat is a real concern at this point whilst the protocol is young but once it matures and gains adoption it would be good to address (more of a nice to have).
I had assumed that we would not be able to apply an encrypted state diff to an encrypted on-chain state without introducing additional trust assumptions (i.e. the operator knowing the encryption key). If this is practical then it would massively mitigate the mandate for hybrid accounts. |
Beta Was this translation helpful? Give feedback.
-
I think we should think through a bit more about how encrypted accounts would work (I have done very little on this front). There are several approaches here, each with different tradeoffs. The ideal scenario would be:
I don't know if we can achieve both of these, but would be really cool if we did. I think the approach you are thinking about involves modifications to the transaction kernel where the kernel would be responsible for encrypting either entire account state or state diffs. Then, in addition to outputting account hash, a transaction would also output hash of the encrypted state (or a state diff), and the nodes (as well as L1) would be able to authenticate it. In this scenario, indeed we can authenticate either a full encrypted state or a state diff, but we won't be able to apply the state diff to an encrypted state. There could be another approach though: we break the state into blocks and encrypt them separately. Let me illustrate this on an example of storage (the high level storage with 256 slots - though, I think this can be extended to TSMT-based storage maps as well): Encryption/decryption could be delegated to account code. Specifically, account code would wrap The advantages of this method are:
The disadvantages are:
The last issue is especially troublesome, in my opinion - but maybe there is a solution for it. |
Beta Was this translation helpful? Give feedback.
-
Yes this is what I had in mind.
Ahh interesting approach! I had not considered this. Intuitively I was under the impression that we would not be able to provide any account encryption support without kernel level modifications / extensions.
Yes this does sound challenging, particularly in relation to the invariant we want to uphold for asset creation / destruction but maybe we can find a way. |
Beta Was this translation helpful? Give feedback.
-
|
Some notes on this problem that occurred to me when chatting with @frisitano : The main point from the text below is that:
Protocol notesIn the above scenario we have two nodes sending valid transactions to the network, so we have race conditions that should be handled otherwise recovery is not guaranteed.
Trade-offs
Design spaceAbove I claimed that the protocol alone can not implement state recovery, because of account abstraction and nondeterministic inputs, what is the required state is not know by the VM. In that case, I think we can also leverage account abstraction and consider other design alternatives:
|
Beta Was this translation helpful? Give feedback.
-
|
Ah, my bad, I initially misunderstood @frisitano 's proposal. I assumed it would have required protocol changes, so I thought you were advocating for not doing them. My current interpretation of that idea is that 1. account abstraction can limit the number of transactions per day 2. eventually the attacker will reach the limit, so they can't sustain an starvation of the user 3. meaning that eventually the user will have time to recover the account I think it works, but it is probably interesting to describe it more extensively. For example:
|
Beta Was this translation helpful? Give feedback.
-
I actually don't think we currently have a way to force a transaction to user a recent block. I think this would be very interesting functionality to support and one way to support this is described #36 (this would require a change in protocol).
Ah - very good observation! Indeed, this may enable the attacker to execute more transactions than desired - especially, if the account hasn't been used recently. A potential way may be to rely on the state guardian to rate-limit state updates (see #189 (reply in thread)).
The only downside that I see is extra code complexity (and thus potential for more bugs). Also, maybe users underestimating these limits and being frustrated that they can't execute transactions until the next day or something like that. |
Beta Was this translation helpful? Give feedback.
-
|
Great observation @hackaugusto. I think Bobbin's proposal in #36 should suffice. The account should be able to set some upper bound on the acceptable height delta for a transaction. I think this would address the attack vector you mention. This also begs the question of whether there should be a height delta limit imposed in the block kernel. One reason for this would be to prevent the following potential griefing attack. A malicious user creates many transactions against a block that costs the most to authenticate in the chain MMR. We could mitigate this by implementing some block height delta such that the user would have less flexibility on the number of blocks they could chose to execute against. |
Beta Was this translation helpful? Give feedback.
-
|
Ah, yes #36 would fix the issue if it is determined by the account abstraction. We would also need a way of merging the deltas from all the different places, it seems that should be done with a min of the account's bound, the notes, etc. |
Beta Was this translation helpful? Give feedback.
-
|
Now that I think of it, we need it. Most of these measures we are talking here are defined somewhere, either code or account storage, and we can't allow the attacker to update these right away, so we need a way of enforcing the transaction is executed against a sufficiently recent block hash, otherwise the attacker would be able to use an old one, out of the window to change the settings, and circumvent these measures. IOW, I'm saying that we need a setting |
Beta Was this translation helpful? Give feedback.
-
|
One way we can try to figure out a comprehensive solution is to start with the simplest use case and see if we can expand from there. It seems to me that the simplest use case is:
I'll also narrow down the problem as follows: what changes do we need to make to the protocol to make sure that a user can place the following restriction on their account:
It seems to me that this functionality can be supported without any changes to the protocol. Here's how it would work. First, let's assume that account code has
While the above works, it has a couple of issues:
I'll leave the first issue for a different discussion. But the second issue should be pretty easy to solve: the user sends deltas for individual components (e.g., vault, storage, code) and the guardian applies them to the state they currently have. Then, everything else works as before. Privacy against state guardianNow, let's say the user doesn't want the state guardian to know the contents of their account. Assuming we have a way to efficiently perform encryption within the VM, the user could encrypt the state inside The state guardian has only the encrypted state, and thus, won't be able to tell if/when this state becomes committed. There are probably several ways to solve this problem, but as far as I can tell, all of them require some modifications to the core protocol. Two potential solutions which came to mind (and there probably more) are:
The first solution implies that we'd need to enshrine an encryption scheme in the protocol. It also is also much less flexible. It does however, provide more information to the protocol - and this could be useful in other contexts. But for now, let's say we go with solution 2. Now, the interaction would look as follows:
Encrypted state deltasAnother problem of dealing with the encrypted state is that we are back to sending the entire state to the guardian. The problem is that we cannot apply encrypted state deltas to an encrypted state to get a new state (unless we use homomorphic encryption - but this is probably prohibitively expensive). One potential solution is to encrypt the state in chunks. Let's take account vault as an example. The un-encrypted delta for the vault could look like so: This obviously won't work for encrypted delta. But we may be able to do something like this: Let's say the initial account vault contains two fungible assets:
Now, let's say we execute a transaction which removes 90 MATIC from the vault. We could send the following delta to the guardian Now let's say we execute another transaction which adds 90 MATIC to the vault. The delta we'd send to the guardian is as follows: Note that even though both the first and the third state has |
Beta Was this translation helpful? Give feedback.
-
|
question: how are the changes going to be tracked? Is the plan to have every account abstraction procedure keeping a list of the account changes? I'm asking because we can't rely on tracking outside of the VM + nondeterministic input, otherwise an attacker would just intentionally discard changes. Edit: The idea is to have the VM doing the diff at the tx epilogue, and the change set will be validated against the initial / final hashes by the kernel, so this is a non-issue. question: what is preventing an attacker from doing note: I'm not sure if that was intentionally left out, but it is probably required to add a discriminant to the encrypted data, so that one can distinguish from vault and storage changes. Something like |
Beta Was this translation helpful? Give feedback.
-
This is probably an attack vector. An attacker would send two transactions in quick succession for the same asset, transitioning Another thing that I just realized. This design precludes the usage of watch towers. Meaning there is an implicit requirement the user must be online once a day, to detect rogue changes to the account and react. Ideally we should have the possibility of delegating action to someone else, for example, if I go to vacation for a month, and I don't want to worry about my wallet being stolen, it would be nice to delegate action to a watch tower, were if any transaction is detected into my account, the watch tower sends a transaction to block my account. Once I'm back online I can recover my account. (edit: to clarify, the watch tower would get a pre-signed transaction, the transaction would for the period of 1mo be allowed to block my account if anything changes in it, and pay a fee to the watch tower, after one month it only pays a smaller fee to the watch tower. Another simpler approach is to allow the account to be preemptively blocked for the period of the month, so no need for any watch tower. There is still the requirement the user must be online and monitoring its accounts, but it is not as bad as before) |
Beta Was this translation helpful? Give feedback.
-
|
Not a full response but I wanted to table some questions / comments regarding state deltas.
Should it be What benefit is there in the state guardian reconstructing the current state? This proposal implies that the state guardian has the required business logic to construct the current state given the provided deltas. I.e. the business logic is enshrined into the state guardian. This provides an inherent coupling between the DA layer and the Miden protocol. This could potentially limit the number of viable state guardians that could be used. Would it be practical to convince Ethereum, Celestia, Avail, Google, Microsoft to encode our business logic? Maybe there would be some specialised services that do this but that could introduce some centralising forces. Additionally, orchestration of updates to the state delta logic could be challenging. An alternative solution is to treat the state guardian as a dumb bulletin board / append only log. It's only responsibility is to store and sign the state deltas that have been provided to it indefinitely. It would not be responsible for processing them or reconstructing the current state. To the state guardian, the deltas would look like random bits / data blobs. Lets now explore a potential implementation using this basis. During the |
Beta Was this translation helpful? Give feedback.
-
Yes, correct - this was a typo on my end (fixed now).
It should be possibly to send "decoys" (e.g., empty assets encrypted with a new iv) - but yes, this needs to be analyzed further.
As compared to the approach of storing state diffs, the benefits are:
The drawbacks are as you described:
One unsolved issue with the whole approach is the spamming attacks I mentioned above, and in a way, addressing these may require some level of coupling. Specifically, guardians have no way to verify whether the data they get from the user is "real" (and this is true for both state diff and latest state cases). This means, a malicious user could send a bunch of data to the guardian to overwhelm them with state diffs. In the ideal world, we'd like the state guardian to be able to verify the following:
I don't think that either of these are particularly difficult to solve, but I think they will require some custom logic. For example, to solve the second problem a state guardian may put a limit on the number of diffs per day. Once the number of state diffs has been submitted, only a recovery transaction would be accepted (this could be another way to mitigate the spamming attack we discussed with @hackaugusto above). However, the above requires custom logic in that:
Again, not too difficult to do (could be as simple as using different keys) - but does require some level of customization. Having said the above, I actually think we should strive to make both approaches possible. It just seems to me that the approach of storing state diffs is fairly straight-forward and can be supported with no or minimal modifications to the core protocol. I'm now trying to see if the approach of storing the latest state could be supported with minimal changes as well. |
Beta Was this translation helpful? Give feedback.
-
I'm not sure if the state guardian guardian would care if the data is authentic or not, as long as they are getting payed (in the form of fees) then they are happy. It would then be the responsibility of the user / a higher level entity to follow the canonical Miden chain to identify relevant transactions and associated account state diff hashes such that they can request the correct account state diffs from the state guardian to reconstruct the account state. Relevant reading regarding the "woods attack" linked here.
I do have some concerns about the amount of complexity the proposal would encode in the state guardian. However, with account abstraction the users will be free to chose the solution that best fits their needs and this will allow the market to experiment and find the solution that works best. One other dimension relevant to this conversation is that of censorship. The state guardian has the power to censor transactions at their discretion by not signing on account state diffs. I think a simple solution for this would be to also allow for multiple state guardians. It would be at the discretion of the user to chose. |
Beta Was this translation helpful? Give feedback.
-
I think this is not a problem. There could be a service layer on front of these APIs, which would do the business logic and use these services as data storage layers. We just have to save |
Beta Was this translation helpful? Give feedback.
-
I'm not sure I follow completely - are you suggesting something similar to what I mention here?
|
Beta Was this translation helpful? Give feedback.
-
Maybe, it seems we are using state guardian differently. I'm trying to say that ethereum/google are not a state guardian, just a data layer of a state guardian. And we don't have to worry about convincing them to become a state guardian and implementing our protocol, because we can implement a service that uses their API for storage, and does the validation on top. |
Beta Was this translation helpful? Give feedback.
-
Overview
Polygon Miden has the unique property that node operators do not need to know the full state of an account to validate that a state transition was executed correctly against it. Node operators only need to know an initial commitment to the account state which allows them to verify a proof of a state transition to assert that it has been applied correctly before updating the commitment to reflect the new state of an account. We refer to accounts which only store a commitment to the account on-chain as off-chain accounts. It is the responsibility of the users to store their account data themselves. This is an effective approach at solving the state bloat problem which traditional blockchains struggle with. For more insight into this state model you can read through this blog post: https://polygon.technology/blog/polygon-miden-state-model. Off-chain accounts are also a foundational pillar of the privacy preserving capabilities that Polygon Miden can support. As only a commitment to an account is stored on-chain, no information can be extracted about the contents of the account.
Whilst this is a very powerful state model it does introduce some challenges. Namely, if a users account is compromised by a malicious actor and the actor executes a state transition then the original account owner will not be able to reconstruct the current state and will effectively be locked out of their account. This is the data withholding problem. A proposal was made suggesting that we should store the account data on-chain in an encrypted format. This solution enables private accounts however it reintroduces concerns around state bloat. Incase you are wondering why a user would want to recover a compromised account - it would be because they would be using account abstraction and may have (daily) spending limits in place so even if an account is compromised the attacker would not be able to drain all funds without the original owner realising and taking action.
We now propose an alternate solution that allows accounts to be stored off-chain, minimising state bloat, whilst also addressing the data withholding problem. The foundation of this solution is to leverage a data availability layer. When an off-chain account wants to transition the account to a new state they submit a transaction to the rollup, this transaction includes a commitment to the new account state, an account delta which encodes the changes to the account and a zero-knowledge proof attesting to the integrity of the state transition and state delta. The proof will be verified and the new account state commitment will be updated on-chain. The account delta will be posted to a data availability layer which will allow any user to fetch it to construct the new account state - in essence solving the data withholding problem. Whilst this solves the data withholding problem, we do not have privacy as anyone watching the data availability layer can reconstruct the current state of the account. To solve this problem we can encrypt the state delta that we are posting to the data availability layer. This means that only individuals with the encryption key will be able to decrypt the state delta and construct the new state.
This results in the following potential account models:
To simplify the protocol we may want to consider removing model 2, as model 5 is a suitable replacement for it (provided the DA layer has the same trust assumptions as the settlement layer - i.e. using ETH for both). We may also want to remove option 3 as this could lead to loss of accounts which we may want to prevent for our users. I also note that I think it is only required to encrypt the state delta for option 5, not the full account state. A leaner approach would be to support just models 1 and 5.
Data Flow
We will now describe the high level pipeline that I am envision around how the flow of account state diffs will work for off-chain accounts.
A user executes a transaction against an off-chain account producing a commitment to the new account state, an account state diff (optionally encrypted) and a zero-knowledge proof attesting to both the account commitment and the account state diff. The transaction is sent to the Miden rollup operator. The rollup operator includes this transaction in a new block, in doing so they verify the zkp, update the account state commitment on-chain and add a commitment to the account state diff to the block. This means that when a block is produced it will contain a commitment to all of the account state diffs it expects to exist on the data availability layer. The new block is then sent to the settlement smart contract on the settlement layer. The smart contract will verify that the block is valid and then assert that all of the account state diffs which have been committed to in the block have been made available on the data availability layer, after this the state in the smart contract will be updated. Below I have tried to illustrate this flow.
Beta Was this translation helpful? Give feedback.
All reactions