Skip to content

efficient proof of solvability with characteristic polynomials

Notifications You must be signed in to change notification settings

vadym-f/Sudoku_solvability_proof

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Private verification of Sudoku solution

Sudoku solution verification was introduced in the context of atomic Bitcoin transction:

Bitcoincore article -- Financial Crypto 2016 talk -- QED-it meetup

Informally, a chicken-and-egg problem was resolved this way: if solution is sent first then why pay for it, and if payment is made first then nothing prevents from sending just random bytes. It was shown how to create a hashlock transaction such that payment can be claimed with a hash preimage, and that preimages is verified to be a valid encryption key for a valid solution to the given Sudoku puzzle.

This verification idea could be best demonstrated with a few photos that are "worth a thousand words":

Sudoku verification idea

Actual solution verification was implemented as producing and verifying a zk-SNARK proof.

An alternative verification is introduced with this project, starting from the idea of polynomial set representation. We expect a circuit of reduced complexity, in terms of multiplication gates count.

Polynomial set representation was introduced in the context of communication-efficient "set reconciliation" problem solved by Minsky, Trachtenberg, and Zippel, 2003:

Set reconciliation sourcecode

It was extended into bivariate polynomial representation of graphs, leading to a Schnorr-like proof systems for graph isomorhism and hamiltonicity with "large" non-binary challenges.

In this project, we experiment with a SNARK circuit for set characteristic polynomials as shown on the photos referenced earlier. In particular, we are interested in exact circuit complexity. For other practical purposes, this is a work-in-progress: we need to reorganise by introducing a gadget implementing methods to construct the circuit and assign the witness.

We plan to experiment with SNARK proofs for statements about graphs.

About

efficient proof of solvability with characteristic polynomials

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published