Ethereum Conflicts Graphed

Dvir David Biton; Roy Friedman; Yaron Hay

REVIEW 3 major objections 4 minor 1 cited by

Ethereum Conflicts Graphed

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ethereum's real transaction conflicts form star-shaped graphs, so color-based scheduling can parallelize them.

desk verdict First large-scale Ethereum conflict-graph measurement with open data, but the read-set construction likely undercounts real read-write conflicts and may manufacture the star-shaped headline result. read the letter →

arxiv 2507.20196 v2 pith:WCPK3TKW submitted 2025-07-27 cs.DC cs.DB

Dvir David Biton , Roy Friedman , Yaron Hay This is my paper · ORCID

classification cs.DCcs.DB MSC 05C15

keywords Ethereumconflictgraphsmartcontractsread-writeconflictscoloringchromaticnumberparallelexecutionblockscheduling

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the transaction-conflict structure of real Ethereum blocks is far friendlier to parallel execution than synthetic workload studies assume. Using call and prestate tracers, it reconstructs read and write sets for transactions in more than two million recent blocks and builds an undirected conflict graph for each block. It finds that these graphs are predominantly star-shaped, with a single hub transaction connected to many leaves, and that their chromatic number almost always sits between $2$ and $5$. If true, color-based scheduling, whose speedup grows with the ratio of longest simple path to chromatic number, becomes an attractive way to speed up Ethereum smart-contract execution.

What carries the argument

The central object is the undirected conflict graph of a block: each transaction is a node, and an edge joins two transactions when one transaction's write set overlaps the other's read set or vice versa; write-write edges are dropped because a multi-versioned store can maintain serializability without tracking them. The argument runs through three graph invariants: the star configuration (a dominant hub with many leaf neighbours, giving small diameter and negative degree assortativity), the chromatic number estimated by the DSATUR greedy coloring algorithm, and the ratio of the longest simple path to the chromatic number, which the target coloring-based scheduler converts into speedup. The low chromatic numbers follow because a star adds many leaves without forcing new colors.

What would settle it

Take a fresh sample of Ethereum blocks, re-run the prestate tracer to build read-write-only conflict graphs, and compute the chromatic number and longest-path-to-color ratio. If most non-trivial blocks require more than five colors, or the median ratio falls below 2, the paper's structural case for color-based parallel execution would collapse; including write-write edges and watching the chromatic number jump toward the number of transactions would likewise show the assumption's weight.

Watch

Extended reading notes

Core claim

The paper claims that if conflicts are defined by read-write and write-read pairs, and write-write conflicts are left to a multi-versioned store, the intra-block conflict graph of Ethereum is not a dense random tangle but a star: one hub transaction attached to many leaves, with negative degree assortativity and a diameter that stays small. The chromatic number, the minimum number of colors needed so that conflicting transactions never share a color, almost always lies between $2$ and $5$ regardless of graph density, while longest simple paths can exceed $500$ nodes in large dense blocks. Consequently the ratio of longest simple path to chromatic number is virtually always above $2$ and approaches $100$ for the largest, densest blocks. The paper concludes that a coloring-based scheduler, whose speedup is proportional to that ratio, would give Ethereum substantial parallel execution gains.

Load-bearing premise

The load-bearing premise is that a multi-versioned store can safely ignore write-write conflicts, so the read-write-only graph is the one that matters; current Ethereum executes serially and has no such store.

Editorial extensions

If this is right

A coloring-based scheduler should outperform arbitrary block-order execution on real Ethereum blocks, since the chromatic number stays low while longest simple paths grow large.
Conflict density is driven by the share of smart-contract transactions rather than block size: dense graphs appear when most transactions invoke contracts, so benchmarks must reproduce that coupling.
The call tracer is too conservative for conflict measurement; only the prestate tracer yields graphs whose coloring is meaningful, so future conflict studies should use prestate-style read/write extraction.
The high ratio of longest simple path to chromatic number, not the raw number of conflicts, is the structural signal that makes parallel execution promising for Ethereum.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's numbers describe a hypothetical execution model, not today's protocol: an actual implementation would first need a multi-versioned state store that makes write-write conflicts harmless, and current Ethereum has none.
Because the prestate tracer treats each address as one object, storage-slot-level conflicts inside popular contracts could be denser than the address-level graphs suggest; a slot-level study would test whether the star shape survives at finer granularity.
A practical test of the claimed speedup is to build a prototype client that executes blocks in color order over a multi-versioned store and compare end-to-end block time against the current serial executor on the same traced blocks.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

What this paper does well is give the first large-scale look at Ethereum's intra-block conflict structure, with public code and data, and the call-tree and value-transfer statistics are useful on their own. The central claim about star-shaped conflict graphs and chromatic numbers of 2–5 is not credible as stated, because the read-set construction in Section V.B subtracts modified addresses from all accessed addresses, which throws away every address a transaction both reads and writes. Since most EVM state updates are read-modify-write, this conflates genuine read-write conflicts with write-write conflicts and drops them out of the RW-only graph. Two transactions that both modify the same contract would have no edge between them, even though the second one reads the first one's write in any serial order. That would lower both density and chromatic number and can manufacture a star-like shape whose hub is write-only. The reader's MV-store caveat is real but secondary; even with multi-versioning, these missing edges are RW conflicts that need ordering.

The comparison with the call tracer is a point in the paper's favor: both tracers yield star-like shapes, which suggests the qualitative finding isn't an artifact of one tracer alone. But the call tracer is described as overly conservative, so the agreement might just mean both methods over-read or under-read in different ways. The authors already collected sub-address-level prestate data; they should use it to recompute read sets without the subtraction.

Elsewhere the paper is honest: the longest path is a Monte Carlo lower bound, the graph coloring is greedy, and the interpretation leans on [11], a self-cited paper, but the measured ratio is independent. Data and code are open, which makes the fix feasible.

Bottom line: this is a serious measurement study with a load-bearing flaw in the definition of the metric being measured. It deserves peer review, but only with a requirement to redo the read sets. If the star finding survives after that, it's a valuable result. If not, the paper still has utility as a benchmark dataset and as a warning that synthetic workloads need to be checked against real traces.

Referee Report

3 major / 4 minor

Summary. The paper traces more than 2 million recent Ethereum blocks using geth's call tracer and prestate tracer, derives per-transaction read and write sets, constructs a conflict graph for each block, and reports a battery of graph metrics: density, diameter, degree distributions, assortativity, clique number, greedy chromatic number, largest connected component, and estimated longest simple path. The headline findings are that Ethereum conflict graphs are predominantly star-shaped, that the chromatic number almost always lies between 2 and 5, and that the ratio of longest simple path to chromatic number is usually above 2 and can approach 100 for large dense blocks. The authors conclude that Ethereum's realized conflict structure is favorable to color-based parallel scheduling. The data and code are released open source.

Significance. If the measured conflict graphs faithfully represent the conflicts that matter for serializability, this is a valuable large-scale empirical contribution: it is the first study of Ethereum intra-block conflict graph structure that I am aware of, it compares two tracing methodologies, and it provides open data and code with no fitted parameters. The paper directly targets the gap between synthetic benchmarks and real blockchain workloads. However, the headline conclusions are conditional on the conflict-graph construction: the read-set subtraction in Section V.B and the address-level aggregation in Section V.B can both distort the graph, so the star-shaped and low-chromaticity findings are not yet established. Because the raw traces contain storage-slot-level detail, the required corrections appear feasible within the scope of the manuscript.

major comments (3)

[V.B] The read-set construction ('We find the read set as the difference of the two sets we gather') removes every address that a transaction both reads and writes. Since the EVM typically reads a storage slot before writing it, two transactions that both read and write the same slot will have no read-set overlap and, once write-write edges are excluded under the multi-versioned-store assumption, no conflict edge at all. The RW-only conflict graphs used in Section VI.E therefore omit genuine read-write conflicts, potentially lowering density and chromatic number and creating the appearance of star graphs whose hub is write-only. This is a load-bearing issue, not just the MV-store caveat: even with multi-versioning, a read of the pre-image of another transaction's write is an RW conflict that must be ordered. Please reconstruct read sets at storage-slot granularity from the raw prestate traces and rerun the main analyses, or explicitly justify why subtracting the write set preserves the RW conflicts that matter for serializability.
[V.B] The analysis treats each address as a single indivisible unit ('for our analysis we treat each address as a single, indivisible unit of potential modification') even though the prestate tracer offers sub-address-level detail. Consequently, transactions that touch disjoint storage slots or different fields of the same popular contract are connected by an edge, which can manufacture hubs and inflate the star topology, maximum degree, and density figures. Because Section VI.D already reports conflict causes at sub-contract granularity, the authors have the data to build slot-level conflict graphs; a comparison between address-level and slot-level graphs is needed to show that the structural findings are not artifacts of aggregation.
[V.C / VI.E.4] The longest-simple-path values come from a Monte Carlo random-walk heuristic whose accuracy is cited only for random graphs. The lower-bound ratio in Figure 16a therefore rests on a lower bound that is itself unvalidated for Ethereum conflict graphs, while the upper bound in Figure 16b uses the largest connected component, which is an extremely loose upper bound for star-like graphs. Since the paper draws its 'highly effective for parallelization' conclusion from this ratio, the authors should either use a stronger longest-path method (for example, branch-and-bound on the largest components, whose sizes are at most a few thousand nodes) or clearly state that the ratio claims are heuristic estimates rather than measured bounds.

minor comments (4)

[VI.E.1] The text reports 'diameter rarely exceeds 5' for graphs that contain many isolated nodes, but the standard diameter of a disconnected graph is undefined or infinite; please state explicitly that the diameter is computed on the largest connected component (or on the graph with isolated nodes removed) and define the convention.
[VII] There is a typo in the Discussion: 'writes-ets' should be 'write sets'; Section II also contains 'In contract' where 'In contrast' is intended.
[VI.E.4] Figure 16 is referenced in the text as 'Figure 16a' and 'Figure 16b' but the caption does not state that the lower bound is conservative (Monte Carlo path divided by greedy coloring) and the upper bound is loose (largest component divided by clique number); please make these definitions explicit in the caption.
[V.C] The description of the Monte Carlo longest-path method says it 'has been shown to yield accurate longest-path estimates for random graphs' and cites [35]; since the conflict graphs here are not random graphs, please temper this claim and describe how the heuristic is validated on the actual data, for example by comparing against exact results on small components.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: measurements are traced and independently computed; self-citation to [11] is interpretive only.

full rationale

The paper's core chain is empirical: traces are collected from Ethereum blocks, read/write sets are derived from tracer output, conflict graphs are built, and graph metrics are computed directly from those graphs. There are no fitted parameters, and the central claims (star-like structure, chromatic number 2-5, ratio of longest path to chromatic number) are measured statistics rather than consequences of an assumed model. The only notable self-citation is [11] (Hay and Friedman, two of the present authors), used to interpret the measured ratio as indicating good parallelization potential for coloring-based scheduling. That interpretation does not feed back into the construction of the conflict graphs or the reported values, so it is not load-bearing in a circular sense. The multi-version-store justification for ignoring write-write conflicts is cited to external work [5] and is an explicit modeling assumption, not an input that forces the observed graph structure. One measurement caveat deserves attention but is not circularity: in Section V.B, the read set is defined as the diffMode=false set minus the diffMode=true set, so an address that a transaction both reads and writes is classified as write-only; this can suppress true read-write edges and may exaggerate star-shaped and low-chromatic structure. That is a validity/accuracy concern about the measured graph, not a case where a derived claim equals its input by construction. The paper also makes data and code available, supporting independent reproduction. Hence the central empirical findings are self-contained; score 2 reflects the minor self-citation rather than a circular step.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities appear; the paper is empirical. The main assumptions are about tracer semantics, address granularity, the multi-versioned execution model, and approximation algorithms for graph metrics.

assumptions (5)

domain assumption Write-write conflicts can be ignored when using a multi-versioned data store while preserving serializability.
Used to build RW-only conflict graphs and to claim low chromatic numbers imply parallelization potential (Section VI.D, citing [5]). Depends on Ethereum-like execution using multiversion concurrency, which is not the current protocol.
domain assumption The difference between prestate tracer diffMode=false and diffMode=true sets yields the read set of a transaction.
Section V.B assumes diffMode=false returns the union of reads and writes and diffMode=true returns writes; the read set is the difference. This underpins every conflict graph.
domain assumption Treating each address as a single conflict unit is a valid simplification.
Section V.B states sub-address detail is available but not used; this overestimates conflicts across different storage slots of the same contract.
domain assumption Archive node re-execution via debug_traceBlockByNumber matches the canonical block execution.
Section V.A relies on an archive node to simulate each block. If the node's client or tracer semantics differ from the canonical execution, the inferred read/write sets and conflict graphs would shift.
standard math Greedy DSATUR coloring and Monte Carlo longest-path estimates provide sufficiently tight bounds on chromatic number and longest path.
Sections V.C and VI.E use these approximations because exact coloring is NP-hard; conclusions about chromatic number 2-5 rely on the bounds being close.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Ethereum Conflicts Graphed." pith.science (2026). https://pith.science/paper/WCPK3TKW

@misc{pith2026250720196,
  author       = {Pith},
  title        = {Pith review of: Ethereum Conflicts Graphed},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WCPK3TKW}},
  note         = {Machine review of arXiv:2507.20196}
}

read the original abstract

Ethereum, a leading blockchain platform, has revolutionized the digital economy by enabling decentralized transactions and the execution of smart contracts. Ethereum transactions form the backbone of its network, facilitating peer-to-peer exchanges and interactions with complex decentralized applications. Smart contracts extend Ethereum's capabilities by automating processes and enabling trustless execution of agreements. Hence, understanding how these smart contracts interact is important in order to facilitate various performance optimizations, such as warming objects before they are being accessed and enabling concurrent execution. Of particular interest to us are the development of the calling graph, as well as the read sets and write sets of invocations within the same block, and the properties of the associated conflict graph that is derived from them. The latter is important for understanding the parallelization potential of smart contracts on Ethereum. We traced upwards of 2 million recent Ethereum blocks using call tracer and prestate tracer, out of a total of 21.4 million blocks at the time of writing. We report on the transactions per block distribution, the structure of call trees in smart contract invocations, the ratio of value-transfer transactions to smart contract invocations, as well as provide a comprehensive study of the structure of blocks' conflict graphs. We find that conflict graphs predominantly show a star like configuration, as well as other noteworthy structural properties.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Remora: Scale-out Deterministic Execution for Smart Contracts
cs.DC 2026-07 conditional novelty 6.5 of 10

Remora scales deterministic smart-contract execution inside a single validator to ~250k TPS via asymmetric dispatch, object versioning with leases, and pre-consensus stateless work plus subgraph scheduling.

Reference graph

Works this paper leans on

3 extracted references · cited by 1 Pith paper

[1]

Ethereum Statistics,

D. D. Biton, “Ethereum Statistics,” 2025, accessed: 2025- 03-24. [Online]. Available: https://huggingface.co/datasets/dbiton/ EthereumStatistics

2025
[2]

Ethgrapher,

——, “Ethgrapher,” 2025, gitHub repository, accessed: 2025-03-24. [Online]. Available: https://github.com/dbiton/EthGrapher

2025
[3]

Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial,

F. B. Schneider, “Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial,” ACM Comput. Surv., vol. 22, no. 4, pp. 299–319, Dec. 1990

1990

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Ethereum Statistics,

D. D. Biton, “Ethereum Statistics,” 2025, accessed: 2025- 03-24. [Online]. Available: https://huggingface.co/datasets/dbiton/ EthereumStatistics

2025

[2] [2]

Ethgrapher,

——, “Ethgrapher,” 2025, gitHub repository, accessed: 2025-03-24. [Online]. Available: https://github.com/dbiton/EthGrapher

2025

[3] [3]

Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial,

F. B. Schneider, “Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial,” ACM Comput. Surv., vol. 22, no. 4, pp. 299–319, Dec. 1990

1990