Topology Registration, Selection, and Comparison for QPoUW

Research
1

When mining Ising models, a miner should be able to submit arbitrary topologies to the network. This opens up a large category of attacks which include submitting topologies with trivial ground state energies or reducible spin clusters and loops.

In order to mitigate these attacks, we propose to evaluate difficulty based on three key criteria:

  • The fraction of the Sherrington-Kirkpatrick ground state energy per spin which constitutes a valid solution
  • The treewidth of the reduced graph after applying known trivial graph family filters, Asano contractions, and other bag decompositions which remove trivial subgraphs from the target topology
  • The fraction of spins in antiferromagnetic clusters

The first constant should be configured as the block difficulty based on the speed at which blocks are minted.

The second constant should be calculated by a node suggesting a topology to the network. If other nodes can confirm the parameter, they can add the topology to their allowed topologies.

The last constant can be calculated upon generation of a nonce or receipt of a consumer graph.

Together, these three constants will fully define the difficulty of any graph, and they can be used to directly compare the difficulty of any chain of topologies.

2

Really interesting proposal! One thing I’m curious about: will this make mining rewards depend even more on raw hardware performance, or are there plans to keep lower-end CPUs competitive? If not, what value do lower-end nodes still bring to the network, and how do you see their role in the long term?

3

Mining is based on compute power (more power == more contribution, which is rewarded accordingly).

Running a public validator will be another way to contribute for low-powered nodes, but that depends on good publicly accessible internet setup.

We are always looking at alternative algorithms that might compete better for CPU but haven’t found any yet.

4

I’m just curious and trying to learn more about the long-term vision. Since Quip aims to become a compute marketplace, could the data gathered during testnet eventually help optimize workload distribution on mainnet? For example, lower-end nodes could handle simpler tasks while more powerful machines focus on harder optimization problems. I feel like that could potentially reduce solving time, avoid wasting computational resources, and allow the network to make better use of all available hardware :smiling_face_with_three_hearts: :smiling_face_with_three_hearts:

Hope it’s okay to ask this here. I feel like these kinds of discussions are a bit hard to have on Discord since they can get pretty technical :sparkling_heart:

5

Agreed, happy to have the discussion here. We are working on a homoiconic format for hybrid quantum and classical programs, with a way to automatically distribute and validate program segments directly from non-volatile memory.

Once this is ready, smaller computers will be able to accept chunks of a larger program and get paid for any chunk they process, as long as there is a partner node of sufficient contiguous RAM to combine and finalize the sharded results.

1 Like
6

I think this is the right direction, but I’d probably frame it as a topology normalization and comparability problem.

If miners can submit arbitrary Ising topologies, then the protocol needs a canonical way to answer one question:

“Is this topology producing comparable work to the rest of the network?”

The three metrics you listed are good candidates, but I think they should be organized into a deterministic validation pipeline:

Canonical topology commitment
Every submitted topology should have a canonical encoding and a topology hash:

topology_id = H(canonical_nodes || canonical_edges || reduction_rules_version)

This prevents two nodes from interpreting the same graph differently.

Reduction phase
Before difficulty is assigned, validators should apply the same reduction rules:

trivial component removal, reducible spin clusters, Asano-style contractions, bag decompositions, and any known polynomial-time subfamilies.

The difficulty should be computed on the reduced graph, not on the raw submitted graph.

Difficulty vector
Instead of treating difficulty as a scalar immediately, define it first as a vector:

D(G) = (energy_fraction, reduced_treewidth, antiferromagnetic_cluster_fraction)

Then map that vector into a scalar only through a protocol-defined function:

difficulty_score = F(D(G))

This makes graph comparison explicit and avoids hidden assumptions.

Validator reproducibility
A topology should only enter the allowed set if independent validators can reproduce the same reduced graph and the same difficulty vector from canonical bytes.

Otherwise, the topology may be interesting computationally, but it should not be consensus-eligible yet.

Anti-gaming invariant
I would define the core invariant as:

accepted_topology(G) => cost_to_solve(G) >= protocol_min_work(difficulty_score)

The goal is not just to reject obviously trivial graphs, but to prevent miners from choosing graph families where the apparent energy threshold is hard while the actual solving cost is low.

This also gives a cleaner path for hardware diversity: miners can submit different topologies, but validators compare them through the same canonical difficulty vector. That seems more robust than requiring one fixed topology forever, while still avoiding “choose-your-own-easy-problem” attacks.

7

Agreed, this is essentially the structure we arrived at in code. There will be a deterministic graph reduction pipeline included with the code, though discovering optimal treewidths is NP so one stage of the pipeline will support random seeds.

If someone is able to reveal a seed that invalidates a topology by finding a more efficient treewidth reduction, then obviously the chain difficulty will be modified in place.

A preview of the code is available in the quip-protocol-py /tutte branch, and I will be committing a new rust suite to a public repo before EOM.

1 Like