New blockchain consensus algorithm - "collect partition vote 3sat"- ANONYMOUS

[watashi-kokoto]

It is thought that a consensus on who receives coin can be reached via a numerical method. The mechanism is completely zero knowledge - no knowledge to who sends coin to who is revealed.

A large set of candidate creditors is collected into a merkle tree by a miner (collect)

Creditors and debitors pubkeys are shuffled by a miner into two sets (partition).

Creditors vote bit by bit on in which partition their debitors are, and debitors vote bit by bit where the creditors are (vote).

Miners solve the system of linear equations, to determine the set of  which creditors just received a coin (matrix).

If a solution is found (the set of creditors is solved) creditors are credited coins and all debitors are debited a coin (goto collect).

Otherwise the next shuffling - voting - solving round occurs (goto partition)

As you can see there is no relationship who send coin to whom, it's like a full coinjoin (like mimblewimble).

Another advantage all public keys own exactly 0 or 1 coins, so there is anonymity for amounts.

But it's far from completion.

[watashi-kokoto]

Let me go into a little more detail. Let's assume there is a way to sign a bit using a pubkey, there is a blockchain, there is 4 people who already own 4 coins on the blockchain. The system works as follows:

The 4 people who own coins are the initial 4 debitors, denoted by their pubkeys x y w z.

They want to send 4 coins to 4 other people, and there are 4 additional users (scammers).
Together the 4 receivers and 4 scammers are the 8 creditors. Denoted by their pubkeys a, b, c, d, e, f, g, h.

The debitors want to send coin to these creditors:

Code:

x -> d
y -> e
w -> g
z -> f

as you can see a, b, c, h are the scammers.

What first happens is collect & partition. The miner collects the 8 creditor pubkeys into a block and mines that. The miner randomly splits creditors into two halves:

Code:

a b c d | e f g h

x y | z w

What next happens is vote. Everyone votes in which half the counterparty is.

Code:

4 debitors vote:
x y | z w
< >   > >
8 creditors vote:
a b c d | e f g h
> < > <   < > > >

What next happens is matrix. A system of linear equations is built from all prior knowledge about who sends / receives coins from whom. This system has the more equations the more times is the algorithm repeated. Because it has more equations if eventually has a solution. The solution is the set of people who receive coins.

But nobody knows (not even miner) that X send coin to D except X and D.

[watashi-kokoto]

Turns out i was wrong about the matrix part. It is not a system of linear equations that is produced but a set of boolean formulae with 3 clauses. This is the famous 3SAT problem that can be solved using off the shelf solvers. What's funny that once miner solves it, it adds the solution to block. And verifier need not to resolve - just in polynomial time check the solution is ok.