zkp_writeup.md

Zero Knowledge Proofs are super interesting. There is a large assortment of literature dedicated to studying commitment schemes, soundness, and completeness.

Thankfully, we can just ignore all that literature and come up with a random number.

In this challenge, we are assuming that the prover (the server that we connect to and query), will commit all of its values before we check a given clause. Since this is a standard 3-SAT problem, the clauses are recorded in conjunctive normal form (a fancy way to say that they are all OR'd together), and each clause must evaluate to True. So, a perfect prover will never have a clause that consists of all Falses. This allows us to write a simple check for a bad prover:

if True not in arr:
  r.sendline('false')
  break

Then, we just need to figure out how many times we need to see the prover give a correct response before we are certain (with 1-p probability) that it is a correct prover. This is a slightly complex analysis involving the number of clauses and literals to find an exact number, but that's a lot of work. Instead, we can make up a number that feels good enough:

else:
  num_correct += 1
  if num_correct >= 25:
    r.sendline('true')
    break
  else:
    r.sendline('next')

The final script includes some boilerplate to read the inputs and makes use of the naughty eval. Please don't judge.

from pwn import *
import random
r = remote('zkp.hsc.tf', 1337)

print(r.readline())
trials = int(r.readline())
for i in range(trials):
  print("starting trial", i)
  literals = int(r.readline())
  clauses = int(r.readline())
  print(literals, clauses)
  num_correct = 0

  while True:
    r.readline()
    r.read()
    r.sendline(str(random.randint(1, clauses))) # send clause number
    arr = eval(r.readline())
    # print(arr, num_correct)
    if True not in arr:
      r.sendline('false')
      break
    else:
      num_correct += 1
      if num_correct >= 25:
        r.sendline('true')
        break
      else:
        r.sendline('next')

r.interactive()