Async Verification
Async verification proposes to reduce the amount of work done to verify a block in consensus to perform the lightest weight possible check. To guarantee DoS resistance, we still want to make sure that all included transactions can pay fees, but may be interested to defer exact balance checks, full transaction execution, calculating the merkle root, etc. to be performed after the block has been accepted.
As a result, async verification applies a lighter weight check during consensus and defers full execution to after a block has been irreversibly accepted (which ofc relies on a sufficiently low latency consensus protocol).
This provides two advantages:
- Drastically reduce the latency of block building and execution within consensus
- Ensure we never waste time executing blocks that are eventually rejected by consensus
To implement async verification, we need to define the abbreviated check that nodes will perform in consensus. This should include syntactic verification of the block ie. height, timestamp, etc. and must also include a check to confirm that every transaction included can pay fees.
Assuming some very basic interfaces, we need the following:
type State interface {
GetMinimumBalance(addr codec.Address) uint64
}
type Tx interface {
GetMaxFee() uint64
}
func canPayFees(s State, txs []Tx) error {
totalFees := make(map[codec.Address]uint64)
for _, tx := range txs {
totalFees[tx.Sponsor()] += tx.GetMaxFee()
}
for addr, fee := range totalFees {
if fee > s.GetMinimumBalance(addr) {
return fmt.Errorf("insufficient funds for %s", addr)
}
}
}Max Fee and Min Balance
To be very specific, we don't just need the fee and balance, we need to use the MAX fee and MIN balance. There's a great deal of diversity in how blockchains charge fees and the notion of a max fee vs. actual fee paid is fairly common.
If we want to guarantee that a transaction can pay for the full fee, then we ofc need to guarantee that it can pay at least its maximum fee.
Additionally, the balance of an account can and will change as we execute blocks. Therefore, we can't just read the balance from the state, we need to read the minimum balance.
That motivates a very simple question: why would the minimum balance be different from the actual balance?
Well, there's more than one context that you may verify a block in 👇
Tree of Processing Blocks
To maximize performance, consensus algorithms will typically pipeline, so that they can have some tree of processing blocks, where the last accepted block is the root of the tree. See here for a description of how to implement the Block interface in AvalancheGo.
This means that we may have a tree of processing blocks such as:
G
|
.
.
.
|
L
|
A
/ \
B C
This graph shows L as the last accepted block, so you can see how B could be verified by in two different contexts.
Depending on the path consensus takes, we may verify B while L is the last accepted block, such that it is at depth 2 from the last accepted block. Alternatively, it could be that we accept A before trying to verify B, such that B is at depth 1.
If we perform the full state transition during verify, then we should have the full state at all of the blocks we consider processing and the last accepted block. But if we are using async verification, then we may only have the full state for the last accepted block.
So what happens if I try to issue a transaction that gets included in block B and I receive some additional funds via a transaction in block A?
If a node tries to verify this before executing block A, then it may not know the transfer took place, such that it only sees my balance in block L. If my balance is not high enough as of block L, then attempting to verify the block using only my "current balance" may disagree on the validity of block B.
So we need to adapt async verification to ensure that the network either always agrees on block validity or is guaranteed to eventually agree on block validity.
Balance State
Eventual Agreement
Continuing the above example, one simple way to handle this is to accept it as is. Block B may be invalid when verified at depth 2, but if the network accepts block A, then every node should eventually accept and process it, which would update the state. After block A is accepted, the observed balance would get updated, block B would switch from being considered invalid to valid.
This could happen if, for example, a node builds block B after it has already accepted block A (so it observes the tx as valid), but other nodes attempt to verify it at depth 2 because they receive B before they've accepted A. As long as B is eventually valid, consensus should should resolve this with no issue.
Epoch'd State
Alternatively - we can try to enforce a canonical definition of the minimum balance at a given block, so that nodes always agree on the validity of a block.
We can implement this by defining locked balances that are tied to specific epochs, so that for a given epoch, we have a single locked balance, which cannot be modified throughout that epoch. Then we can simply validate that the sum of all maximum fees within an epoch never exceeds the locked balances for the corresponding addresses.
For an example, see the rough draft of how a verifier could handle a tree of processing blocks relying on an epoch'd version of locked state here:
|
GetBalance(epoch uint64, address codec.Address) (uint64, error) |
.
In the context of DSMR/fortification, epoch'd state has several advantages. Within DSMR, transactions are partitioned to chunk producers ie. transactions from account A must be issued through a subset of validators, so those validators can ensure the transactions have sufficient funds to pay the fees. This means that transaction issuers rely on that subset of validators to reliably include their transactions. If it's only a single validator, then a single validator failure (offline or malicious) could censor transactions from their partition.
To improve censorship resistance, we can increase the number of validators assigned to each partition and regularly rotate those partitions at an epoch boundary.
If we use the design that depends on eventual agreement in the chunk case, then at the epoch boundary, the new chunk producer needs to wait for all chunks from the prior epoch to be confirmed or invalidated before it knows the minimum balance at the start of the new epoch. Additionally, censorship resistance depends on increasing from 1 chunk producer for an address to N and regularly rotating the partitions.
If we use the epoch'd design, then at the epoch rotation, a newly assigned chunk producer can view the minimum balance that was frozen at the end of the prior epoch ie. the locked balance for epoch N is locked as of the end of epoch N-2 instead of N-1.
Async Verification
Async verification proposes to reduce the amount of work done to verify a block in consensus to perform the lightest weight possible check. To guarantee DoS resistance, we still want to make sure that all included transactions can pay fees, but may be interested to defer exact balance checks, full transaction execution, calculating the merkle root, etc. to be performed after the block has been accepted.
As a result, async verification applies a lighter weight check during consensus and defers full execution to after a block has been irreversibly accepted (which ofc relies on a sufficiently low latency consensus protocol).
This provides two advantages:
To implement async verification, we need to define the abbreviated check that nodes will perform in consensus. This should include syntactic verification of the block ie. height, timestamp, etc. and must also include a check to confirm that every transaction included can pay fees.
Assuming some very basic interfaces, we need the following:
Max Fee and Min Balance
To be very specific, we don't just need the fee and balance, we need to use the MAX fee and MIN balance. There's a great deal of diversity in how blockchains charge fees and the notion of a max fee vs. actual fee paid is fairly common.
If we want to guarantee that a transaction can pay for the full fee, then we ofc need to guarantee that it can pay at least its maximum fee.
Additionally, the balance of an account can and will change as we execute blocks. Therefore, we can't just read the balance from the state, we need to read the minimum balance.
That motivates a very simple question: why would the minimum balance be different from the actual balance?
Well, there's more than one context that you may verify a block in 👇
Tree of Processing Blocks
To maximize performance, consensus algorithms will typically pipeline, so that they can have some tree of processing blocks, where the last accepted block is the root of the tree. See here for a description of how to implement the Block interface in AvalancheGo.
This means that we may have a tree of processing blocks such as:
This graph shows
Las the last accepted block, so you can see howBcould be verified by in two different contexts.Depending on the path consensus takes, we may verify
BwhileLis the last accepted block, such that it is at depth 2 from the last accepted block. Alternatively, it could be that we acceptAbefore trying to verifyB, such thatBis at depth 1.If we perform the full state transition during verify, then we should have the full state at all of the blocks we consider processing and the last accepted block. But if we are using async verification, then we may only have the full state for the last accepted block.
So what happens if I try to issue a transaction that gets included in block B and I receive some additional funds via a transaction in block A?
If a node tries to verify this before executing block A, then it may not know the transfer took place, such that it only sees my balance in block L. If my balance is not high enough as of block L, then attempting to verify the block using only my "current balance" may disagree on the validity of block
B.So we need to adapt async verification to ensure that the network either always agrees on block validity or is guaranteed to eventually agree on block validity.
Balance State
Eventual Agreement
Continuing the above example, one simple way to handle this is to accept it as is. Block
Bmay be invalid when verified at depth 2, but if the network accepts blockA, then every node should eventually accept and process it, which would update the state. After blockAis accepted, the observed balance would get updated, blockBwould switch from being considered invalid to valid.This could happen if, for example, a node builds block
Bafter it has already accepted blockA(so it observes the tx as valid), but other nodes attempt to verify it at depth 2 because they receiveBbefore they've acceptedA. As long asBis eventually valid, consensus should should resolve this with no issue.Epoch'd State
Alternatively - we can try to enforce a canonical definition of the minimum balance at a given block, so that nodes always agree on the validity of a block.
We can implement this by defining locked balances that are tied to specific epochs, so that for a given epoch, we have a single locked balance, which cannot be modified throughout that epoch. Then we can simply validate that the sum of all maximum fees within an epoch never exceeds the locked balances for the corresponding addresses.
For an example, see the rough draft of how a verifier could handle a tree of processing blocks relying on an epoch'd version of locked state here:
hypersdk/x/async/tree.go
Line 31 in fffd17c
In the context of DSMR/fortification, epoch'd state has several advantages. Within DSMR, transactions are partitioned to chunk producers ie. transactions from account A must be issued through a subset of validators, so those validators can ensure the transactions have sufficient funds to pay the fees. This means that transaction issuers rely on that subset of validators to reliably include their transactions. If it's only a single validator, then a single validator failure (offline or malicious) could censor transactions from their partition.
To improve censorship resistance, we can increase the number of validators assigned to each partition and regularly rotate those partitions at an epoch boundary.
If we use the design that depends on eventual agreement in the chunk case, then at the epoch boundary, the new chunk producer needs to wait for all chunks from the prior epoch to be confirmed or invalidated before it knows the minimum balance at the start of the new epoch. Additionally, censorship resistance depends on increasing from 1 chunk producer for an address to N and regularly rotating the partitions.
If we use the epoch'd design, then at the epoch rotation, a newly assigned chunk producer can view the minimum balance that was frozen at the end of the prior epoch ie. the locked balance for epoch N is locked as of the end of epoch N-2 instead of N-1.