Athena Specification Proposal

Amira · August 26, 2024, 2:05pm

Athena Transaction Format:

Alice wants to send a transaction to Bob. Alice has only an Athena account and funds and no L1 account. An Athena transaction has the following fields:

address from: The address of the sender account
address to: The address of the recipient account
uint256 value: The Athena coins value to send to the recipient account.
uint64 nonce:protects against replays and out-of-order execution.
uint64 max_fee optional: The premium amount sender is willing to spend for this transaction (includes both storage and execution cost)
uint256 L1_storage_gas_price p_j optional: the premium price that the sender of tx_j is willing to pay for each gas unit upon being included in a relay transaction that will be put into the L1 storage.

Transaction Submission:

User (Alice) Initiates Transaction: Alice, creates an Athena transaction using her wallet. This transaction includes details like the receiver’s address, the amount to send, the nonce, any necessary signatures, and maximum spending (max_fee) Alice is willing to pay for this transaction.
Wallet estimates transaction cost: The wallet gathers current execution price and storage fee from the network. The wallet then estimates transaction cost (storage fee is paid to miner and execution fee to executor).
Wallet compares transaction cost to max_fee defined by Alice. In the case where
cost < max_fee transaction is approved otherwise transaction fails.
In the successful case, Wallet sends Alice’s transaction to the relay mempool where it will be stored as an unconfirmed transaction.
Relays gather transactions that users submit to the relays mempool in order to submit them to L1.
In the case this value is dynamic and depends on current gas price required for transaction execution. then the wallet can fetch this price directly from the network, it can automatically include the correct L1_storage_gas_price when preparing the transaction on behalf of the sender. This eliminates the need for the sender to manually compute or estimate this value and include it in the transaction.
The wallet might also offer an interface where the sender can see the L1_storage_gas_price and choose to adjust it (e.g., by adding a premium) if they want to prioritize their transaction. This also applies to max_fee which can be dependent on the wallet estimation of cost which is then displayed to user who confirms the maximum amount they are willing to pay.

In the context of Athena transactions, max_fee plays a role similar to that of a GasLimit in Ethereum. It represents the total budget the sender is willing to allocate for the transaction, covering both storage and execution costs. The execution of a transaction is constrained by the funds available in max_fee after deducting storage costs. If the transaction requires more fees than this maximum value, it will fail.

Initial Transactions Collection

Relays start by gathering transactions that users submit to the relays mempool (This is a different one from the L1 mempool). Users submit their transactions to the relay’s mempool. This mempool is separate from the L1 mempool and is specific to the relay, serving as a holding area for transactions waiting to be processed. Another option would be users submit transactions in wallets which then submit transactions to specific relays.

Option 1 (Relay Gathers from Mempool): This is a more traditional approach where relays actively manage a pool of pending transactions and select the most appropriate ones based on a set of predefined criteria which we explain later. It allows relays to optimize their bundles but requires effective mempool management.
Option 2 (Direct Submission by Wallet): This approach streamlines the process by allowing transactions to be sent directly to a relay. It can reduce delays but may lead to more transaction rejections if relays are selective or if certain relays become overloaded. Wallets can choose relays with low enough relay’s gas price or with one that does not exceed L1_storage_gas_price p_{j} specified by user to increase chance of transaction being approved by relay and included in UCB.

Now that a relay chooses an Athena transaction tx_j,

First of all, Relays parse these transactions (format check, Deserialization) to extract:

max_fee: uint64
value: uint256
L1_storage_gas_price p_j: uint256

Relays decide which transactions they take from the mempool to put in their bundles. Relays keep track of the mempool and the current state in order to get the most recent current balance of the user’s account and based on that decide which transactions have the necessary funds to pay storage fees to the relay. Relays use the “conservative-balance heuristic” method and decide their own risk level.

Relay’s Transaction Filtering Process

The relay uses a conservative approach to ensure that only transactions that are likely to succeed are included in the final bundle. Here’s how this process works:

For each transaction tx_j, the relay calculates the Total Cost using the formula:

Total Cost = Value + Current Execution Price + Storage Fee
This formula gives the total amount of funds that must be available in the user’s account to cover both the transfer and the execution + storage cost of the transaction.
The relay compares the calculated Total Cost against the Current Balance of the sender’s account.
If Total Cost \leq Current Balance , the transaction is considered valid for inclusion in the bundle.
Transactions that do not meet the requirement are excluded from the final bundle.
Optionally, the relay may apply a Safety Multiplier to the Total Cost for additional buffer before comparing it to the Current Balance.

Bundles

Once transactions are validated, the transaction IDs are included in bundles while the transactions themselves are gossiped separately as independent objects.

L1 transaction format (bundle)

In addition to the standard transaction format, we support a new format called “bundle transaction”. Each bundle submitted by relays is considered as a single L1 transaction. The bundle transaction specifies a list T of Athena-only transactions (tx1,tx2,…,txn), such that for 1jn and txj is an Athena transaction whose format is already detailed above.

address relay_id: The unique identifier for the relay submitting the bundle.
struct signed_payload: Contains the signed list of Athena transaction IDs (tx_1, tx_2, …, tx_n) included in this bundle.
List athena_transaction_ids
uint256 max_storage_fee: The maximum fee the relay is willing to pay for including the bundle.
Map<Address, uint256> current_balance_hint: is a mapping of each principal (user) address included in the bundle to a conservative estimate of their balance. This balance hint helps the relay ensure that each transaction has enough funds to be processed successfully.

Miners on L1 are responsible for including the transaction data in a block, ensuring its permanence on the blockchain.

1. Storage Fee

Is the cost associated with storing the transaction data on the Layer 1 (L1) blockchain.
The relay prepays the storage fee to the miners, covering the cost of storing the transaction data on L1. By adding max_storage_fee Field to the Bundle, the relay protects itself from being forced to pay more than it has budgeted for, even in the event of a dishonest Hare majority attack.

p_j is referred to as the L1_storage_gas_price. This is the price that the sender of the transaction txj is willing to pay for each gas unit required for storing the transaction data on L1.
This price is directly related to the cost of storing the transaction tx_j on L1.
The relay bundle transaction specifies its own gas price p_{gs}. This gas price is the price per gas unit that the relay transaction will pay to L1 miners for processing the transaction.
- Storage Fee Calculation: The storage cost for tx_j is calculated as
  p_j * x where x represents the number of consumed gas units.
  If p_j is not provided, p_{min} is used instead.
- The required amount for storage is deducted from the max_fee of tx_j.

2. Execution Price

Execution Cost: The cost associated with executing the transaction within Athena, which includes the computational resources needed to process the transaction.

The executors are responsible for processing the transactions within Athena. They perform the actual computation required by the transaction.

Payment: The relay pays the execution cost to the executors. This payment compensates them for the computational work they perform to execute the transaction.

p_{min} is the execution price used for executing the transaction $tx_j$. It is calculated as the minimum of the relay’s gas price p_{gs} (set by the relay bundle transaction) and p_j (the L1_storage_gas_price specified by tx_j ).
- Execution cost: If tx_j consumes x gas units during execution, the total execution cost is
  x*p_{min} . This price is used to determine how much the Athena executors will earn for processing (executing) the transaction tx_j.

To prevent a malicious relay transaction from mounting a griefing attack by specifying a very high p_{gs} and thereby making each tx_j pay a very high fee to the Athena executors, we use p_{min}=min(p_j,p_{gs}) as the gas price that the Athena executors earn by executing tx_j .
If the total execution cost exceeds the remaining amount in max_fee after storage costs are deducted, then tx_j is aborted and does not get executed. (so basically
x*p_{min} + x* p_j \leq max_fee

The max_fee also protects from griefing attacks and thus protects tx_j from paying very high fees.
The sender of the transaction ultimately funds both the storage and execution costs through the max_fee.

The relay acts as an intermediary, distributing the funds to the appropriate parties:

Storage Fee: Paid to L1 miners.
Execution Fee: Paid to Athena executors.

Bundles

Once transactions are validated, the transaction IDs are included in bundles while the transactions themselves are gossiped separately as independent objects.

L1 transaction format (bundle)

In addition to the standard transaction format, we support a new format called “bundle transaction”. Each bundle submitted by relays is considered as a single L1 transaction. The bundle transaction specifies a list T of Athena-only transactions (tx_1,tx_2,......,tx_n), such that for 1\leq j \leq n and tx_j is an Athena transaction whose format is already detailed above.

address relay_id: The unique identifier for the relay submitting the bundle.
struct signed_payload: Contains the signed list of Athena transaction IDs (tx_1, tx_2, ..., tx_n) included in this bundle.
List<Hash> athena transaction ids
uint256 max_storage_fee: The maximum fee the relay is willing to pay for including the bundle.
Map<Address, uint256> current_balance_hint : is a mapping of each principal (user) address included in the bundle to a conservative estimate of their balance. This balance hint helps the relay ensure that each transaction has enough funds to be processed successfully.

The relay bundle transaction specifies its own gas price p_{gs}. The relay transaction also specifies the fee that it pays (to the L1 miners) includes the amount max_storage_fee

Submission to UCB

Once a transaction bundle is ready, the relay is responsible for submitting it to the L1 blockchain. Any relay can create a bundle transaction. The UCB contains all the signed relay bundles and a separate list of deduplicated and shuffled transaction IDs from all accepted relay bundles in the block. This list serves as a reference table.
Instead of including the full transaction IDs in bundles, only the indices are stored.
To determine which transaction an index refers to, indices are mapped back to transaction IDs using the reference table stored in the UCB.

Deduplication

The Hare protocol, which is also used for L1 transactions, is employed to recognize and remove duplicate transactions. The Hare participants, acting as a committee, collectively determine which transactions are duplicates and ensure that only unique transactions are included in the final block.

Details:

Each relay submits a bundle as an L1 transaction. However, instead of including the full Athena transactions, the relay bundle contains only the transaction IDs.
These transaction IDs correspond to the Athena transactions that the relay intends to include in the UCB.
The full transaction data for each ID in the bundle is gossiped separately across the network as independent objects.
This means that the Hare participants will receive the transaction IDs through the relay bundles and the corresponding transaction data through the gossip network.

Before proceeding to the shuffle and block creation, Hare participants verify that the full transaction data corresponding to each transaction ID in the relay bundles has been received through the gossip network. If any transaction data is missing or cannot be verified, the associated transaction ID is dropped and excluded from the final block.

Identifying and Removing Duplicates

All transaction IDs from the collected relay bundles are aggregated into a single list. These bundles contain lists of transaction IDs submitted by different relays.
Example: Suppose the bundles include the following transaction IDs:

Bundle 1: (tx_{id_{dave}},tx_{id_{eve}})
Bundle 2: (tx_{id_{fred}}, tx_{id_{greg}}, tx_{id_{eve}})
Bundle 3: (tx_{id_{harry}},tx_{id_{dave}})

Aggregated List: (tx_{id_{dave}},tx_{id_{eve}},tx_{id_{fred}},tx_{id_{greg}},tx_{id_{eve}},tx_{id_{harry}},tx_{id_{dave}})

The Hare participants identify duplicate transaction IDs within the aggregated list: (tx_{id_{dave}},tx_{id_{eve}}) and remove them, ensuring each transaction ID appears only once in the final list.

Shuffling Process Using Coin Tossing

The shuffling ensures that transactions are randomly distributed across relays, which helps to further prevent duplication and reduce the storage burden. After shuffling, each transaction is linked to only one relay.

The Hare participants, acting as a committee, initiate a coin tossing protocol to generate randomness. Each participant performs a virtual coin toss, producing a sequence of binary outcomes (0 or 1). Example:
Participant 1: 1010, Participant 2: 1100, Participant 3: 0110, Participant 4: 1001
The binary sequences from all participants are shared and combined using XOR to produce a final random number 1001 which can be interpreted as the decimal number 9. With the random number generated, the Hare participants apply a shuffling algorithm (e.g., Fisher-Yates shuffle) to reorder the transaction IDs.
(tx_{id_{greg}},tx_{id_{eve}},tx_{id_{harry}},tx_{id_{fred}},tx_{id_{dave}})
Each transaction is assigned a new index based on its position in the shuffled order.

Bundle Compression:
Each relay transaction originally references a set of transaction IDs. After shuffling, these references are replaced with their corresponding indices from the deduplicated list.

Post-Shuffle Example:

Relay 1 initially referenced T_1= (tx_{id_{dave}},tx_{id_{eve}}), after shuffling and compression, it stores the indices T_1=(4,1)

Bundle Overhead

The relay bundle overhead depends on the number of included transactions. Using indices instead of full transaction IDs significantly lowers the bundle overhead. Let’s take the example of n=1000 transactions and calculate overhead in both cases:

Using Transaction IDs: Given:
- Base Overhead \beta : 84 bytes (fixed component that may include headers, metadata, etc)
- Transaction ID Size \gamma : 20 bytes per transaction
- Number of Transactions: n=1000

overhead = \beta + (\gamma *n) = 84 + (20*1000) =20084 bytes
So, the bundle overhead using transaction IDs for 1,000 transactions is 20,084 bytes.

Using Indices: Given:
- Base Overhead \beta : 84 bytes
- Index Size \zeta : 2 bytes per transaction
- Number of Transactions: n=1000

overhead = \beta+ (\zeta *n) = 84+ (2*1000) = 2084 bytes

So, the bundle overhead using indices for 1,000 transactions is 2,084 bytes.

UCB Construction

The construction of the UCB involves a series of steps designed to ensure that only valid, executable, and financially viable transactions are included in the final block:

1. Transaction Ordering:

All transactions in the UCB are ordered according to a predefined method (TBD)

2. Cumulative Max Relay Fee Calculation:

The Cumulative Max Relay Fee Calculation protocol is designed to ensure that the total fees required by all transactions from a given principal (account) do not exceed the balance that has been conservatively estimated by the relays. This protocol helps in determining which transactions should be included in the final UCB and prevents relays from losing money on transactions that might not pay their fees.

Definitions and Variables:

Let 𝑇={𝑡𝑥_1,𝑡𝑥_2,…,𝑡𝑥_𝑛} be the set of transactions from a principal 𝑋 in a given UCB.
Let 𝑅={𝑟_1,𝑟_2,…,𝑟_𝑚} be the set of relays that include transactions from 𝑋 in their bundles.
Let MRF(𝑡𝑥_𝑖) be the max relay fee associated with transaction 𝑡𝑥_𝑖.
Let CBH(𝑟_𝑗) be the current balance hint provided by relay 𝑟_𝑗 for principal 𝑋.
Let CS(𝑖) be the cumulative sum of max relay fees after processing transaction 𝑡𝑥_𝑖.

Cumulative Sum Calculation:

For each transaction tx_i in the ordered transactions list:
CS(i)=CS(i−1)+MRF(tx_i)
Let’s assume they are ordered as tx_1,tx_2,…,tx_n.
For each relay r_j that included tx_i in its bundle:
- If CS(i)≤CBH(r_j), the transaction tx_i remains eligible to be included in the block under relay r_j.
- If CS(i)>CBH(r_j), then:
  - The transaction tx_i is removed from relay r_j's bundle because the cumulative fees now exceed the balance hint provided by r_j.
  - If tx_i is removed from all relay bundles, it is dropped from the block entirely.

Cumulative Sum Calculation with Prioritized Relay Fees:

TBD

Cumulative Sum Calculation and Max Storage Fee Enforcement:

TBD

Attack Vectors

Griefing attack and prevention

A griefing attack in the context of the Athena and its relay system is a type of malicious activity where an attacker (malicious relay) deliberately manipulates the transaction processing system to cause disruption, increase costs, or force transaction failures for other users or relays, without necessarily gaining a direct financial benefit. The goal of the attacker is to degrade the performance or reliability of the network, often by exploiting how fees and transaction costs are handled.

Scenario 1: Griefing with a High p_{gs}

Description:

In this scenario, a malicious relay submits a transaction with an excessively high gas price p_{gs}. The intention is to force the other transactions within the same bundle (which use
p_{gs} as part of their execution cost calculation) to pay significantly higher execution fees than they normally would.

Risk:

If p_{gs} is set very high by the malicious relay, it can cause the total execution cost to exceed the remaining balance in max_fee after storage costs are deducted, leading to the abortion of legitimate transactions tx_j.

Prevention:
By setting the effective gas price p_{min} as p_{min}=min(p_{gs},p_j), the protocol ensures that the transaction doesn’t automatically default to the higher p_{gs} , which limits the impact of a maliciously inflated gas price.
The max_fee mechanism provides an upper limit on the total cost that the sender is willing to pay for the transaction. If the execution cost (including the gas price) exceeds this cap, the transaction is aborted before incurring excessive fees, protecting the user from paying more than intended.

Scenario 2: Griefing with Multiple Draining Transactions

Description:

In this scenario, an adversarial relay that is cooperating with a malicious user (or playing the role of both) submits multiple transactions designed to drain the balance of an Athena account. These transactions are included in the relay bundle, and because other honest relays don’t see the adversarial relay’s transactions beforehand, they may include transactions without getting paid.

Risk:

The account’s balance could be drained by the malicious transactions, making it more likely that subsequent transactions included by honest relays will fail due to insufficient funds, thus resulting in unpaid relay fees.

Prevention:

Prioritizing Relay Fees: Deduct relay fees from accounts before executing the transactions themselves. This ensures that relays are paid first, even if the transaction later fails due to insufficient funds for execution.

Dishonest Hare Majority attack and prevention

The Dishonest Hare Majority Attack is a scenario where a majority of the participants in the Hare consensus protocol collude to manipulate the transaction processing and fee allocation to relays. The dishonest majority can include transactions in the block that were not part of the bundles submitted by certain honest relays.

Risk:

This is particularly damaging because relays prepay these storage fees at Layer 1 (L1), expecting to be reimbursed through the transaction fees. When they are forced to pay for unwanted transactions, they may not be reimbursed, leading to a direct financial loss.

Prevention Strategies:
To protect against this type of manipulation, the protocol can implement either one of these safeguards:

Max Storage Fee Cap:

Introduce a max storage fee cap that limits the total amount a relay is willing to pay for storage fees. This cap would protect relays from being overcharged, even if the dishonest majority tries to allocate additional storage costs to them. This what was previously suggested by adding the field max_storage_fee to the bundle.

Prioritizing Relay Fees:

Implement a mechanism where relay fees are deducted before any other transaction costs, ensuring that relays are compensated first, reducing the risk of financial loss. This is the same prevention mechanism which was suggested to protect from “Griefing with Multiple Draining Transactions attack”. Both attacks can result in financial losses for honest relays, but the scope and impact differ.

noam · September 9, 2024, 11:11am

Why/how are the fee fields in the transaction optional?

Are max fee fields in the transaction absolute or per gas unit? If they’re absolute, who decides the per-gas-unit fee rate? If they’re per-unit, what does it mean that the wallet calculates the cost and compares to the user’s preference?

When you say:

Do you mean that the wallet doesn’t send the transaction and advises the user to set a higher fee, or that this is determined after the transaction is published? It sounds from the next point like you mean the former, worth clarifying.

What does the following mean?

Isn’t this something the user decides and the smeshers can decide to accept or reject? Again, worth clarifying. Maybe you mean something like “minimally acceptable L1_storage_gas_price based on recent blocks”?

Also requires some clarification. I can imagine a scenario where a borderline fee transaction is in the mempool, and a relay needs to decide on what storage price to offer L1 smeshers, leaving him different amounts of fee for execution. So possibly, a transaction that doesn’t have enough additional fee in one layer might have enough in the next layer, when the storage fee is lower. That’s not a “failure”, is it?

I don’t fully understand the difference between the two options for relays… In both cases they keep a mempool, but in option 1 transactions are broadcast over gossip and in option 2 they’re submitted via an api? I don’t understand the differences explained.

In general, when you describe relay behavior, this is the “recommended” or “default” behavior, as there’s no enforcement of this and relays can choose to do whatever they want, right?

Why is value important for relays to verify? If there’s not enough balance to cover the “value” then the relay still gets paid and this is “the user’s problem”, no?

This doesn’t make sense to me… If another transaction emptying the account surprisingly appears before this block, then no safety multiplier will be enough and otherwise, this is not required. Can you describe a scenario where this is useful so we can talk about the probability of that scenario / ability to detect it in advance?

Duplicate? What’s the difference, other than the signature?

I don’t understand the benefit of including this in the transaction… should be internal to the relay.

In the end, the relay pays the L1 storage fee and is repaid in Athena. Why do we even involve the user in the decision how much to pay there? If one relay pays more for storage and therefore gets less fees left over, while another relay has better estimates and can get away with paying less - why can’t they “pocket the difference”?

This also includes the state storage cost (not transaction storage, but account state). We should say that here.

To be continued…

Topic		Replies	Views
Athena Transactions journey Research vm-design , athena	15	409	August 14, 2024
Proposed Athena design Research agenda , vm-design	9	182	October 7, 2024
Athena blockchain design and integration Research risc-v , vm-design , athena	4	105	June 14, 2024
Committee-Based Adjudication of Athena Challenges Research incentives , vm-design , athena	2	117	June 15, 2024
General Abstract Resources Research account-abstraction , vm-design	7	71	August 1, 2024

Athena Specification Proposal

Athena Transaction Format:

Transaction Submission:

Initial Transactions Collection

Relay’s Transaction Filtering Process

Bundles

L1 transaction format (bundle)

1. Storage Fee

2. Execution Price

Bundles

L1 transaction format (bundle)

Submission to UCB

Deduplication

Identifying and Removing Duplicates

Shuffling Process Using Coin Tossing

Bundle Overhead

UCB Construction

1. Transaction Ordering:

2. Cumulative Max Relay Fee Calculation:

Definitions and Variables:

Cumulative Sum Calculation:

Cumulative Sum Calculation with Prioritized Relay Fees:

Cumulative Sum Calculation and Max Storage Fee Enforcement:

Attack Vectors

Griefing attack and prevention

Scenario 1: Griefing with a High p_{gs}​

Scenario 2: Griefing with Multiple Draining Transactions

Dishonest Hare Majority attack and prevention

Related topics

Scenario 1: Griefing with a High p_{gs}