Cuckoo Cycle: a new memory-hard proof-of-work system

[tromp]

I am a bit of a java boy myself and will admit to having tried to convert your code already.. and failed.. ha!

It's quite obfuscated.. with lots of 2 letter variables, pointers and no comments!   (I'm a bit comments OCD..)

What perturbed me is that there are literally only 20 or 30 lines of pertinent code, so I thought it would be easy.

Is there any chance you could just write a very simple pseudo code explanation ? I would convert that to java. (and SHARE of course)

I have looked through the pdf but that too is just a bit - gruesome..

The code will be easier to understand if you read the paper. try to get through the gruesome...
The algorithm repeatedly generates edges (u,v) and follows paths from u and v.
These paths are stored in arrays us[] and vs[], with nu and nv used as path length.
The edge is actually stored in us[0] (same as *us in c) and vs[0] (same as *vs).

Why don't you fork my repo and translate all the code into java as best as you can.
Then allow other people to contribute. When I have time, I'll look over your progress and
help fix it up...

[tromp]

Cuckoo Cycle won't work as a cpu-only PoW.

I addressed your (mistaken) criticism in your thread.

[spartacusrex]

The code will be easier to understand if you read the paper. try to get through the gruesome...
The algorithm repeatedly generates edges (u,v) and follows paths from u and v.
These paths are stores in arrays us[] and vs[], with nu and nv used as path length.
The edge is actually stored in us[0] (same as *us in c) and vs[0] (same as *vs).

Already a bit clearer..

[tromp]

I will write a Java version eventually, but it's pretty low on my list of priorities,
and I'm busy with many other things. Perhaps you can find some other Java programmer
to port it sooner. I will have more time in March...

Notice any changes to https://github.com/tromp/cuckoo lately :-?

The verifier is done; I should have the solver ported soon as well.

[spartacusrex]

Excellent!!

Thank you..

It's playtime :-)

[tromp]

The verifier is done; I should have the solver ported soon as well.

Try "make java" on the latest version...

[dga]

At John's request, I've taken a look at this and scribbled up my initial comments.

They might be wrong!  Please take them in the spirit of continuing the discussion, not as the final word.

http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html

I'll post an addendum to the blog post (and here) with anything that's shown to be wrong.

[tromp]

At John's request, I've taken a look at this and scribbled up my initial comments.
They might be wrong!  Please take them in the spirit of continuing the discussion, not as the final word.
http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html
I'll post an addendum to the blog post (and here) with anything that's shown to be wrong.

Dave has shown my algorithm is not as tmto-hard as I thought it was.
Excellent work, Dave!


For now, I amended my README at https://github.com/tromp/cuckoo with the following


UPDATE: Dave Anderson proposed an alternative algorithm on his blog

http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html

that uses significantly less memory than mine at potentially less than an order of magnitude slowdown. I hope to soon implement his algorithm and quantify the "tomato" (his pronouncable spelling of tmto, or time-memory trade-off).

[dga]

At John's request, I've taken a look at this and scribbled up my initial comments.
They might be wrong!  Please take them in the spirit of continuing the discussion, not as the final word.
http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html
I'll post an addendum to the blog post (and here) with anything that's shown to be wrong.

Dave has shown my algorithm is not as tmto-hard as I thought it was.
Excellent work, Dave!


For now, I amended my README at https://github.com/tromp/cuckoo with the following


UPDATE: Dave Anderson proposed an alternative algorithm on his blog

http://da-data.blogspot.com/2014/03/a-public-review-of-cuckoo-cycle.html

that uses significantly less memory than mine at potentially less than an order of magnitude slowdown. I hope to soon implement his algorithm and quantify the "tomato" (his pronouncable spelling of tmto, or time-memory trade-off).

Baseline:  My code uses 10x less memory and runs 2x slower (on a laptop instead of an i7).  At 6x less memory, it should have speed parity.  Could be optimized substantially - I sent you some very hacked up code.  Happy to post it publicly if anyone's interested, but it's trashy - I just wrote it as a proof of concept for the pre-filtering before invoking the cycle finder.  But it gets the point across.

But, more generally:  I think it's great that you've put the proposal document out publicly for comment before it's adopted.  That's the right place to start.  But I think it should be taken one step farther.  Consider the approach Colin Percival used in developing scrypt:  A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness.  I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use, but the care that went into scrypt's theoretical evaluation is worth modeling.  I think there are some very serious approaches that might keep time linear or sublinear and reduce memory to sublinear -- but whether or not one person can think of an attack is not the right approach for determining whether the idea is resistant to attack.  I put some time into thinking about this one because there seemed to be increasing interest in it, but I _really_ hope that the takeaway from this is not "oh, it's what Dave says it is", but "hey, we need to kick the tires of this in a more formal and careful way, by trying to prove that it's _right_."

I realize that's not an easy task.   But security is hard.

  -Dave

[tromp]

But, more generally:  I think it's great that you've put the proposal document out publicly for comment before it's adopted.  That's the right place to start.  But I think it should be taken one step farther.  Consider the approach Colin Percival used in developing scrypt:  A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness.  I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use, but the care that went into scrypt's theoretical evaluation is worth modeling.  I think there are some very serious approaches that might keep time linear or sublinear and reduce memory to sublinear -- but whether or not one person can think of an attack is not the right approach for determining whether the idea is resistant to attack.

Additionally, the designer (me in this case) is probably in a bad position to find attacks
because they want the neat algorithm with nice properties that they found to be the optimal one,
and this wishful thinking clouds their mind...

Back to the drawing board...

[tromp]

But, more generally:  I think it's great that you've put the proposal document out publicly for comment before it's adopted.  That's the right place to start.  But I think it should be taken one step farther.  Consider the approach Colin Percival used in developing scrypt:  A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness.  I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use"

Cuckoo Cycle is no less safe to deploy than either prime-based or hash-cash proofs-of-work.
It needs a minimum amount of work, namely computing millions of siphashes.
Dynamic difficulty adjustment will take care of as-yet-undiscovered optimizations to the
current (and new) algorithm.

It's true I haven't done anywhere near as thorough a job as Colin. My hat off to him.
My notion of tmto-hardness is stronger than his though.
I aim to require a barrier that polynomial trade-offs can not cross
(but phrased in concrete terms rather than quantified formulas and big-Oh notations).

The least I can do is encourage the search for a disproof.
As the current README shows:

"Cuckoo Cycle remains tmto-hard assuming at least one bit per nonce is required.
 I offer a $1000 bounty for an implementation using less, with at most 100x slowdown."

I know, that's a very modest sum. And much less than was offered for Momentum.
But then I've seen what happened with that one...

PS: concerning social good. I'd love for a "research coin" to come out that can serve as a laboratory for new ideas, maybe one running only on testnet. It could perhaps be based on NXT source code, with a PoS/PoW hybrid instead of pure PoS, and Myriad's support for multiple PoW algorithms...

[dga]

But, more generally:  I think it's great that you've put the proposal document out publicly for comment before it's adopted.  That's the right place to start.  But I think it should be taken one step farther.  Consider the approach Colin Percival used in developing scrypt:  A PoW for serious consideration in a cryptocurrency needs a stronger proof of hardness.  I don't put things like Riecoin and Primecoin in this batch, because their goal is social good more than a particular technical goal of memory use"

Cuckoo Cycle is no less safe to deploy than either prime-based or hash-cash proofs-of-work.
It needs a minimum amount of work, namely computing millions of siphashes.
Dynamic difficulty adjustment will take care of as-yet-undiscovered optimizations to the
current (and new) algorithm.

That depends on the reason someone is deploying it.  If someone is deploying a PoW because they desire only a minimum computational amount of work, of course it's safe to deploy something that has a fallback to iterated sha256/hashcash.

But that's not why someone would look at CC:  They'd look at it because they want something with memory requirements that grow in some way that they believe can be used to bias the hash against certain technologies for implementation (e.g., ASICS).

So while your statement is true, it's not necessarily the right truth.  Is Cuckoo Cycle better or worse than adaptive scrypt-N?  Is it better than a variant of Invictus's Momentum PoW that has an adaptive N factor?

Neither of us knows the answer to this question.  There is a chance that it's stronger.  But there's also a very real chance that the requirement to find a cycle, instead of a simple collision, will mean that the approach can yield to something with sublinear memory requirements and, in fact, underperform compared to Momentum in its memory requirements.

That is why I'm being cautionary about this.

It's true I haven't done anywhere near as thorough a job as Colin. My hat off to him.
My notion of tmto-hardness is stronger than his though.
I aim to require a barrier that polynomial trade-offs can not cross
(but phrased in concrete terms rather than quantified formulas and big-Oh notations).

The least I can do is encourage the search for a disproof.
As the current README shows:

"Cuckoo Cycle remains tmto-hard assuming at least one bit per nonce is required.
 I offer a $1000 bounty for an implementation using less, with at most 100x slowdown."

I know, that's a very modest sum. And much less than was offered for Momentum.
But then I've seen what happened with that one...

PS: concerning social good. I'd love for a "research coin" to come out that can serve as a laboratory for new ideas, maybe one running only on testnet. It could perhaps be based on NXT source code, with a PoS/PoW hybrid instead of pure PoS, and Myriad's support for multiple PoW algorithms...

Sure, but again:  The best way to design a strong algorithm in a security context is not to generate ideas until you find one you cannot disprove.  It's to start from things that are known to be hard and to base the security of your algorithm upon the hardness of those things.

I've already told you how to modify the algorithm I explained to use 1/2 bit per nonce with a 4x slowdown.  The idea generalizes to using 1/k memory for a > k^2 slowdown.  This is a good tradeoff, but it's not the be-all-end-all.  It does require some very careful compressed representation of the bitvector, but this stuff is known and there are fast implementations available -- see, for example, the SDSL:  https://github.com/simongog/sdsl-lite

[tromp]

Neither of us knows the answer to this question.  There is a chance that it's stronger.  But there's also a very real chance that the requirement to find a cycle, instead of a simple collision, will mean that the approach can yield to something with sublinear memory requirements and, in fact, underperform compared to Momentum in its memory requirements.

We know finding two incident edges in a graph is (way) easier than finding a 42-cycle.
So I don't know what you mean by underperform.

Sure, but again:  The best way to design a strong algorithm in a security context is not to generate ideas until you find one you cannot disprove.  It's to start from things that are known to be hard and to base the security of your algorithm upon the hardness of those things.

I feel that unnecessarily limits the PoW landscape. And could have left prime-based
PoWs out in the cold as well.

I've already told you how to modify the algorithm I explained to use 1/2 bit per nonce with a 4x slowdown.  The idea generalizes to using 1/k memory for a > k^2 slowdown.  This is a good tradeoff, but it's not the be-all-end-all.

Are you referring to this paragraph of your blog?
"(There is a way to slightly reduce the memory demands:  Split the bit vector in half, and record the live bits only for the first half across multiple iterations of the test, using the full second half.  Then store this bit vector in a compact way, and perform the computation on the second half.  This doesn't extend very far past a factor of two reduction, but it does require only a roughly linear increase in the amount of computation and could possibly get the storage needed down to about 300MB for 2^32.)"

[dga]

Neither of us knows the answer to this question.  There is a chance that it's stronger.  But there's also a very real chance that the requirement to find a cycle, instead of a simple collision, will mean that the approach can yield to something with sublinear memory requirements and, in fact, underperform compared to Momentum in its memory requirements.

We know finding two incident edges in a graph is (way) easier than finding a 42-cycle.
So I don't know what you mean by underperform.

I mean that the statement you said there is not necessarily true!  Let's try phrasing it as a question:

Given a fixed hash rate budget and desired rate of finding blocks,
does it require more or less memory to solve the problem of finding a single colliding pair in a large sparse graph,
or to find a length-L cycle in a smaller, more dense graph?

Note the difference in those two problems:  In order to have a non-negligible probability of finding a large cycle, your problem requires a much more dense graph than a problem such as Momentum.  Furthermore, it induces a relationship between the elements in the graph that is not present in Momentum.  In M, you can approximately analyze it by looking at the independent collision probability.  That's not necessarily the case in CC.

This is why I keep mentioning sampling.  Consider this statement:

Given L=42 in the cuckoo cycle problem with N < 2^32,
if a graph G contains an L-cycle,
a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 / 1,000,000.
Math edit:  Replaced 10% with x% -- there is some x for which this is true.

You can go check the math yourself - it's just a binomial with p=x%.

Does this mean anything?  I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum!  For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds?  With some reasonable probability, you'd extend into one of the cycles.  Not guaranteed, but it doesn't have to be guaranteed - I can always start over.
[/quote]

Sure, but again:  The best way to design a strong algorithm in a security context is not to generate ideas until you find one you cannot disprove.  It's to start from things that are known to be hard and to base the security of your algorithm upon the hardness of those things.

I feel that unnecessarily limits the PoW landscape. And could have left prime-based
PoWs out in the cold as well.

Not at all.  The primes have an entirely different goal.  The point is that you're advertising cuckoo cycle as having a certain set of desirable properties.  Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.  Some people want memory.  Some people want fuzzy teddy bears.  (grin).  For the advertised properties, there needs to be a stronger proof.

I'm not trying to prescribe what choice or properties any coin should pick from a PoW.  That's an entirely different question.

I've already told you how to modify the algorithm I explained to use 1/2 bit per nonce with a 4x slowdown.  The idea generalizes to using 1/k memory for a > k^2 slowdown.  This is a good tradeoff, but it's not the be-all-end-all.

Are you referring to this paragraph of your blog?
"(There is a way to slightly reduce the memory demands:  Split the bit vector in half, and record the live bits only for the first half across multiple iterations of the test, using the full second half.  Then store this bit vector in a compact way, and perform the computation on the second half.  This doesn't extend very far past a factor of two reduction, but it does require only a roughly linear increase in the amount of computation and could possibly get the storage needed down to about 300MB for 2^32.)"
[/quote]

Yes.  It's non-trivial to "store this bit vector in a compact way" but it can be done.  See the SDSL link I provided, for example.

[tromp]

Given L=42 in the cuckoo cycle problem with N < 2^32,
if a graph G contains an L-cycle,
a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 / 1,000,000.
Math edit:  Replaced 10% with x% -- there is some x for which this is true.
You can go check the math yourself - it's just a binomial with p=x%.

You need about 33% for 1 in a million odds of less than 2 L-cycle edges in your sample.

Does this mean anything?  I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum!  For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds? With some reasonable probability, you'd extend into one of the cycles.  Not guaranteed, but it doesn't have to be guaranteed - I can always start over.

To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.

Not at all.  The primes have an entirely different goal.  The point is that you're advertising cuckoo cycle as having a certain set of desirable properties.  Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.

So you're saying I mismarketed Cuckoo Cycle. I could have said.

Let's have a PoW based not on number-theoretical, but on graph-theoretical structures.
Existence of a certain small-size subgraph in a large random graph makes for an easily
verifiable PoW. We could look for cliques, or for ... cycles!

Then you'd be fine with it?!

Yes.  It's non-trivial to "store this bit vector in a compact way" but it can be done.  See the SDSL link I provided, for example.

In the first round of full U and V trimming, you pass through a state of the bit vector
having about half 0s and half 1s. At that point it's completely incompressible.
Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach)
it would be practically infeasible to compress.

[tromp]

Given L=42 in the cuckoo cycle problem with N < 2^32,
if a graph G contains an L-cycle,
a random sample of x% of the edges in the graph will contain at least two edges in that L-cycle with probability > 999,999 / 1,000,000.
Math edit:  Replaced 10% with x% -- there is some x for which this is true.
You can go check the math yourself - it's just a binomial with p=x%.

You need about 33% for 1 in a million odds of less than 2 L-cycle edges in your sample.

Does this mean anything?  I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum!  For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds? With some reasonable probability, you'd extend into one of the cycles.  Not guaranteed, but it doesn't have to be guaranteed - I can always start over.

To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.

Not at all.  The primes have an entirely different goal.  The point is that you're advertising cuckoo cycle as having a certain set of desirable properties.  Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.

So you're saying I mismarketed Cuckoo Cycle. I could have said.

Let's have a PoW based not on number-theoretical, but on graph-theoretical structures.
Existence of a certain small-size subgraph in a large random graph makes for an easily
verifiable PoW. We could look for cliques, or for ... cycles!

Then you'd be fine with it?!

Yes.  It's non-trivial to "store this bit vector in a compact way" but it can be done.  See the SDSL link I provided, for example.

In the first round of full U and V trimming, you pass through a state of the bit vector
having about half 0s and half 1s. At that point it's completely incompressible.
Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach)
it may be too impractical to compress.

[tromp]

Let's have a PoW based not on number-theoretical, but on graph-theoretical structures.
Existence of a certain small-size subgraph in a large random graph makes for an easily
verifiable PoW. We could look for cliques

Actually, that could be quite interesting. Since proof size grows quadratically with clique size,
you'd want to limit it to cliques of size 10 (giving proofs of 45 nonces).
One can set the desired probability of finding such a clique (in the range 1% to 50%)
and figure out what number of edges in a large random graph makes that happen.

As with Cuckoo Cycle, edge trimming could be successfully applied:
repeatedly count vertex degrees (using 4-bit counters) and remove all
edges incident to a vertex of degree < k-1, where k is the clique size.
Perhaps this even keeps up a high enough reduction rate that
you can afford to keep going until either nothing or a clique is left...

We could make the following little table of "scientific" coins/PoWs:

                              chain-structure         cluster-structure
number-theoretic       primecoin                riecoin
graph-theoretic         cuckoo cycle            cliquecoin

[dga]

Does this mean anything?  I don't know -- but it tells me *immediately* that the problem requires a different kind of analysis than what you would do for Momentum!  For example, what if you started by sampling lg(n) edges and then growing and pruning that set through 42 rounds? With some reasonable probability, you'd extend into one of the cycles.  Not guaranteed, but it doesn't have to be guaranteed - I can always start over.

To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.

To quote myself back:  "Not guaranteed, but ... can always start over."  In other words, you can settle for a 20% chance if you're willing to run the sampling test a few times, if it saves you enough memory.

Remember, part of the game is that you have to take the entire context of the search process into account:  An attacker can change the random seed, as well, at some modest cost.  The definition of the problem is to find a cycle, not the cycle.  Again - time/memory.  There are a lot of different ways to try to exploit such a tradeoff.  This gets back to the issue I emailed you with about searching for a biased initial distribution.  Neither of us knows whether or not it would work.

Not at all.  The primes have an entirely different goal.  The point is that you're advertising cuckoo cycle as having a certain set of desirable properties.  Someone shopping for a PoW wants a certain set of properties - some people want the social/scientific good of primes.

So you're saying I mismarketed Cuckoo Cycle. I could have said.

Let's have a PoW based not on number-theoretical, but on graph-theoretical structures.
Existence of a certain small-size subgraph in a large random graph makes for an easily
verifiable PoW. We could look for cliques, or for ... cycles!

Then you'd be fine with it?!

Your writeup of Cuckoo Cycle, as of Mar 28 09:28, said:

"We introduce the very first proof-of-work system that is both verify-trivial and tmto-hard."

Period.  There were no qualifiers attached to that statement.  No conjectures, no conditionals, until section 10, where you note that it's a conjecture. 

Yes - if you said "We introduce the first Proof-of-Work scheme based upon graph-theoretical structures.  We hypothesize but have not proved that this PoW may lead to certain memory-hardness properties" I'd be totally fine with it, because it would be an accurate description of what you've done.

Yes.  It's non-trivial to "store this bit vector in a compact way" but it can be done.  See the SDSL link I provided, for example.

In the first round of full U and V trimming, you pass through a state of the bit vector
having about half 0s and half 1s. At that point it's completely incompressible.
Even with a 10% vs 90% distribution (that takes at least 2 full rounds to reach)
it would be practically infeasible to compress.

ok - one last spoonful and I'm done:

Create a bitvector representing the first half of the nonces.  Call it the "lower half".
Iterate on this bitvector using the full nonce state *multiple times* until you have eliminated all candidates in the "lower half" bitvector that you can relative to the full set of candidates in the lower half (some of which are being eliminated) and all candidate nonces in the "upper half" (which you're not eliminating because you don't have memory).

Then, in piecewise fashion, identify a size-appropriate subset of the specific incident edges on the lower half that are causing problems -- in other words, which nonces in the "upper half" are causing collisions in the "lower half" that prevent you from discarding some of the lower-half entries?

For that small subset (of size << 1/2N -- let's say 1/8th N), do the same process:  Eliminate them relative to your now-sparsified lower half and the complete upper half.  This should allow you to eliminate more of the lower-half edges.  Repeat until the lower-half is sufficiently sparse that you can represent it in reasonable compressed space, and move on to the upper half.

Is it awesome?  No.  Have I thought about it for more than 5 minutes?  No.  Could an expert come up with a drastically better algorithm?  Probably.

Stop trying to defend your algorithm for a few minutes and start trying to attack it.  Your goal in this should not be to try to refute individual objections, because that process can go on forever, fruitlessly.  Refute categories of objections based upon sound reasoning and theoretical analysis of the difficulty of the underlying problem!

I'm done.

[tromp]

To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.

To quote myself back:  "Not guaranteed, but ... can always start over."  In other words, you can settle for a 20% chance if you're willing to run the sampling test a few times, if it saves you enough memory.

That's why I mentioned 50%. Settling for 20% or 50% makes little difference.
You can settle for 0.1% and still the log(n) doesn't cut it.

The definition of the problem is to find a cycle, not the cycle.

Again, this makes no difference except for small constant factors, since you expect to
find about only 3 cycles on average.

Your writeup of Cuckoo Cycle, as of Mar 28 09:28, said:

"We introduce the very first proof-of-work system that is both verify-trivial and tmto-hard."

Period.  There were no qualifiers attached to that statement.  No conjectures, no conditionals, until section 10, where you note that it's a conjecture.  

Yes - if you said "We introduce the first Proof-of-Work scheme based upon graph-theoretical structures.  We hypothesize but have not proved that this PoW may lead to certain memory-hardness properties" I'd be totally fine with it, because it would be an accurate description of what you've done.

You're right. I was wrong to claim hardness without proof.
I rewrote the README and shall rewrite the paper as well when I have time,
possibly dropping the hardness hypothesis.

Create a bitvector representing the first half of the nonces.  Call it the "lower half".
Iterate on this bitvector using the full nonce state *multiple times* until you have eliminated all candidates in the "lower half" bitvector that you can relative to the full set of candidates in the lower half (some of which are being eliminated) and all candidate nonces in the "upper half" (which you're not eliminating because you don't have memory).
Then, in piecewise fashion, identify a size-appropriate subset of the specific incident edges on the lower half that are causing problems -- in other words, which nonces in the "upper half" are causing collisions in the "lower half" that prevent you from discarding some of the lower-half entries?
For that small subset (of size << 1/2N -- let's say 1/8th N), do the same process:  Eliminate them relative to your now-sparsified lower half and the complete upper half.  This should allow you to eliminate more of the lower-half edges.  Repeat until the lower-half is sufficiently sparse that you can represent it in reasonable compressed space, and move on to the upper half.

Thanks for elaborating on how to pass the incompressibility threshold.
Rephrasing, you paint half the edges red and half blue, and eliminate red leaf-edges.
Now remaining red edges are separated from the leaves by blue edges.
So you identify a small fraction of these separating blue edges that touch a remaining red edge,
and paint them purple. Identifying some leaf purple edges let's you eliminate some
more green edges. Choose different red edges to paint purple and repeat.
If necessary, try to identify blue edges separated by two red edges from a leaf
by recursing deeper.

[Willisius]

I think this is really interesting, if only because I think the PoW problem hasn't been solved for good.