applied ZK constructions 1

Group membership

without nullifiers

• zkmessage -> hash(secret), set membership
• heyanon -> signature verification, merkle path

Signup phase

vivekab joins with thier eth public key 0x414e...

database :
vivekab -> ox414e

Messaging Phase

vivekab generates this zk proof :

component prove:
	public input pks[n] // database에 있는 pk들
	public input message

	private input pk
	private input signature_of_message

	(pk - pks[0])*(pk - pks[1]) === 0 // 데이터 베이스에 있는지 확인

	verify(signature_of_message, pk) === 1

	prove([0x414e.., 0x15a9..], "hi", 0x414e.., sign("hi", vivek_secret_key))

위 코드에서 pubkey를 데이터베이스에 있는지 확인하므로써 group membership을 확인할 수 있고,
verify에서 적법한 사용자가 사인을 했는지 확인할 수 있음

improvement

전체 pubkey를 넣는 대신에, merkle_root를 활용할 수 있음
그러면 single value와 merkle path를 넣으면 된다.(merkle root검증)

with nulifiers

• semaphore -> hash(secrets), merkle paths, nullifiers
• tornado cash -> hash(secrets), merkle paths, nullifiers
• stealthdrop -> signatures, merkle paths, nullifiers -> it didn't work

nullifier를 사용하면 한 번 증명된 상태를 다시 사용할 수 없게 할 수 있다

semaphore

그래서 세마포어 에서는 메시지를 보팅할때, 널리파이어를 한번 검증하도록 한다.

component prove:
	public input merkle_root
	public input message # "yes"
	public input external_nullifier # hash("does..")

	private input n1 # identity_nulifier
	private input t1 # identity_trapdoor
	private input merkle_path[logn]

	merkle_leaf <== hash(n1, t1)
	hash(hash(merkle_leaf, merkle_path[0]), merkle_path[1])... == merkle_root

	public output nullifier_hash
	nulifier_hash <== hash(n1, external_nullifier)

prove(merkle_root=0x59.., "Yes", "does ...", nullifier1, trapdoor1, merkle_path)

nullifier는 사용자의 고유식별자 역할을 하는 n1과 external_nullifier를 해시한 결과로 생성됨

external_nullifier는 특정 행동에 따라 다르게 설정되는 값으로, 메시지의 해시 값일 수 있다. 따라서 동일한 사용자가 같은 메시지에 대해 여러 번 투푷는 것을 방지할 수 있다.

각 투표는 nullifier_hash값을 생성하고, 이 값이 데이터 베이스에 기록되면, 또 동일한 nullifier_hash가 다시 제출 되었을때, 이미 투표한 것으로 간주되어 추가적인 투표가 허용되지 않는다.

prove(merkle_root, "yes", "dooes...", nullfier1, trapdoor1, merkle_path)

nullifier는 사용자의 컴퓨터에서 생성되는 256 bit 랜덤 값이다
1/2^256 정도의 확률로 colision 발생할 수 있다.
하지만 secret value를 모른다면 collision이 발생했는지 verify할 수 없다

signature verification과 nullifier를 섞고 싶다면?

stealthdrop

signature가 deterministic하지 않아서 계속 사용할 수 있는 문제가 생김(왜?)
같은 메시지에 대해 여러번 시도를 하면 계속 달라서 둘 다 valid해짐

properties of an anonymous nulifier

• Unique
• Deterministic
• Verifiable without secret key
• Non interactive (unlike tornado.cash or semaphore)

Ideas that will and won't work

deterministic ECDSA signature
nullifier = hash(message, public key) 라면?
nullifier = hash(message, secret key)
nullifier = hash(message, public key)^ secret key -> DDH-VRH

So..
we want a deterministic function of a user's secret key, that can be verified with only their public key, and keeps them anonymous

solution

if your eth keypair is (sk, pk = g^sk) and public message is m

signature :
public : hash(m, pk)^sk <-- nullifier
private :
c = hash2(g, pk, hash(m, pk), hash(m, pk)^sk, g^r, hash(m, pk)^r)
s = r + sk * c
pk = g^sk
g^r (optional output)
hash(m, pk)^r (optional output)

여기서 sk를 제외한 모든 것을 알고 있더라도, sk를 reverse engineer해서 알수는 없다
익명성을 보장하면서 deterministic한 nullifier를 얻기 위해, hash(message, public key)^ secret key와 같은 방식을 통해 공개키 만으로 검증 가능하고, 비밀키를 노출하지 않는 방식으로 nullifier를 생성하는 방안

user proves in SNARK :

g^(r + sk * c) / (g^sk)^c = g^r
hash(m, g^sk)^(r + sk * c) / (hash(m, pk)^sk)^c = hash(m, pk)^r
c = hash2(g, g^sk, hash(m, g^sk), hash(m, pk)^sk, g^r, hash(m, pk)^r)
pk is in anonymity set (merkle proof)

new stealthdrop

stealthdrop에서 이더리움 상에서 바로 signature를 사용하지 못하는 이유는 일반적인 서명처럼 공개적으로 검증되면 익명성이 깨질 수 있기 때문이다.
일반적인 서명의 경우 공개키와 메시지에 의해 검증 가능하므로, 누구든 활동을 추적할 수 있다.
따라서 stealthdrop은 plume_signature라는 방식으로 signature를 SNARK로 검증하여 이더리움 상에서 익명성을 유지할 수 있도록 설계했다

withdraw phase

	public input merkle_root

	private input pk, c, s
	public input plume_signature_of_message

	private input merkle_path[logn]

	hash(hash(pk, merkle_path[0]), merkle_path[1]...) === merkle_root

	verify(plume_signature_of_message, pk, c, s, "stealthdropt out") === 1
	#nullifier === plume_signature_of_message

prove(merkle_root=0x59.., nalin.eth.., c, s, plume_signature_ofmessage, merkle_path)

Group membership (on Ethereum, with nullifiers)

• stealthdrop
• plume nullifiers

그렇다면 어떻게 이미 존재하는 것을 가지고 증명할 수 있을까?

Groups in the wild

zk email

DKIM Scheme

user y just needs to provide any email header from e.g. x@twitter.com to y@mit.edu
NO ONE, not even the mailserver or keystroke tracker, can determine who it is

Proof

어떤게 public private input이고 서킷이 체크하는 것은 무엇일까? 여기서 prove하고자 하는 것은 무엇일까?

• zk proof public
  sender domain (and/or receiver domain)
  the RSA modulus
  masked email body

• zk proof private
  the dkim signature from the mail server
  the length of the pre-hashed message data
  the raw message data

• zk circuit checks
  sha256's and RSA both verify
  the sender/receiver domains are well-structured in the message (regex)

• Contract checks
  sender domain == verify@twitter.com
  clamined RSA Key == DNS-fetched/cached RSA key