Snark: zk-SNARK trustless computing

The objective is trustless computing. We have a job provider J, and we have a worker W, with computation c(a,b). J wishes to incentivize W to perform c(a,b). W is assumed malicious. W could perform zero calculation and provide output X. J has no way to verify the validity of X. J rewards W.

Strategy One, J gives computation c(a,b) to W1, W2, W3, till Wn. In order mentioned they provide X, O, O, O, J can assume O is correct. J needs to reward W2, W3, till Wn. This is consensus based trustless computing. J had to reward for each successful result. This is expensive.

Strategy Two, trusted hardware. Trusted hardware ensures execution. Intel SGX is the most widely adopted. Requires pre-compilation of c(a,b) into the enclave. Ensures c(a,b) is trusted. Cloud providers do not currently have SGX mass adoption. This excludes too large of a user base.

Strategy Three, zk-SNARKs (Strategy Three b, zk-STARKs, not currently production ready). Trusted execution. Can be deployable to any system, no hardware limitation, one to one usage.

We will use libsnark and Zokrates to demonstrate how zk-SNARKs can solve trustless computing.

Given function c(a,b) we can define it in as

def main(a,b):
return a+b

Compiled via Zokrates, we receive output

Compiling add.code
Compiled program:
def main(a,b):
return (a + b)
Compiled code written to 'out',
Human readable code to 'out.code'.
Number of constraints: 1

We compute the output for c given a:1 and b:1, with output 2 (easily verifiable visually)

Computing witness for:
def main(a,b):
return (a + b)
Witness: {"a": 1, "b": 1, "~one": 1, "~out_0": 2}

Now we need to generate proof, given a witness of {“a”: 1, “b”: 1, “~one”: 1, “~out_0”: 2} and inputs of 1, 1, 1, 2, we generate

Proof:
A = 0x541fe5245da55a46cecb6652384b5cab34d4041cbd114f1cec80bfcd21da758, 0x15051b8fe37a5adf5b6df604134db9a696b4a505131bbdf608a01e8d07eb20cd
A_p = 0x2ba27b052527b48d516653332b4a19db63dd448a775d81f540b89d536a6ccca3, 0x1400f78265e0fa76828bdd96cfcafb59e6b8eae58492643415f4064f490e4ecc
B = [0x415e735fc50f9f9f9ff1f50229b57e8ac6d6a123b090dc8a3888b68e2af7b5e, 0x2f984d821dcaece59f63157aa273bbdad72d7913a9ab8e6445f1929f5b005a2a], [0x124595fc21a8dbefbfbcbd25e262f2146e01242d7009b8b9d4a508b7ee34b306, 0x1bd8baae63531850c2c8508a637f5586972fb505512e8e72559487bd56177e9c]
B_p = 0x1681530fdd46e99e4dd1aecfef0f6b5db8c89f83a5fa691a3b67327d07997e8a, 0x1de7408fb56976238e1468f1c5243bf3dd6c2bfacfdc0c6d2251f64cf39fd9b8
C = 0xda7717fc9a1de2df4217706f313f2d105dfd73bff5b69958815788f9cc09e72, 0x1df8fc9e1c792fb723178fd59f4543e6c098d724d265894e26ed0bfececb1618
C_p = 0x1366b4f96bc37dea3e80497101594f145f52be9578b8576bb6b95e54ba17b8bf, 0x2b4dcc139165568282c9fe48d6b38fb2d25c66928929f5d69a02c82cef4bca26
H = 0x1830068bbe3a691e5e133d17450bb4abe0933456a565bd7f933011aece318c85, 0x3fa9b65402d42ed268af24396ecd10ed105d43a5695a2ef707f17b60cb34200
K = 0xd884128cb213e3d503cb207081dd1eb1db066e1efde6e1dbd950e10fdc744de, 0x2a34aa7bf099d72a7e12e43eb3f022fa94563472aab301d45f126153e52102c2

The above proof will change based on inputs. If instead we execute c(a,b) as c(2,2) we have witness

Computing witness for:
def main(a,b):
return (a + b)
Witness: {"a": 2, "b": 2, "~one": 1, "~out_0": 4}

And we generate proof

Proof:
A = 0xdd0074a5eb8bef9f93d23e60614ae20940523c0128e0b853f3f7be07310b068, 0x84f182531372f6b6b107bad7347a89565eb6a4d44d834b684ff92c0a91cd6d6
A_p = 0x21fefefe9fe6d5eb1aba42fd6dc446f9086329aa62be45cdd10e910be202f1ce, 0x3bba04f5fe4e292b53504ab5dd516c06bfbd7f0c384760df61ac6d1bfd08a19
B = [0x2102870c6e06616b3a36bc577ff655d8ae58575fafc0a6c30ab6ac5fc70c1752, 0x2ea6d955cdf85efed75b31c0115b0a0427849fc01bc08f17cef568f291bbbc1f], [0x11f96b0d84fa60c28298592fc452c82ecfa82d136fc443ee9bb4bdf5dbcaa508, 0x2737ba58389f11476259b6e60b7f69dccf4d3697294c75468b03f4c3a7452645]
B_p = 0x27d5315a1bd60c20f66b930990148f30cffaf620e5b23b4800723d27c07b3bb, 0x2c58cdf509223714a00a6501c8c41285666fcbc6023ac863fb57775344deb915
C = 0x1727552a09eeef24b2c6de27e9a47764d49dd64c6c40336e20a7ec1eb44a5ca3, 0xc480d98902bc11b1aa58bdf7b77f0cf131750ec508d2615667f1daaa640396b
C_p = 0x2429d278d28b2239bd62567eca8c3a4946f2be24d3b413e1fba1a5dc3500e88, 0x94cfba292c22119c0e7695a39d7fc98c119384ce434e641018070aeae92e198
H = 0x2ec0e277bb480166f69c7802db72d7f4a436800e981ee997117e1e1497c5bd44, 0xa2ef09658b53c6bdffaf60f281f110eb70fc5c599689da30709c94b8c997943
K = 0xb982887647e7233c7a0e596732dc49a7411379a3e8a5bc1c9b7e1539c72cb12, 0x2ce92003ae12da46f0f61a3027ad7684217c91a474a26da6427df16748b15cb9

As part of compiling c(a,b) we generated a verification key

Verification Key
A = [0x541d382d36c3829ea9aac29a2942d4605706920676a6f033f28049d682ae888, 0x78807cf5baf993700c48778a853034775814996d8f362224b17249b7c368182], [0x28dccfd45b25dc98460507fe1e80b637dd6aa31a21723b13c74f6195188150dd, 0x6a5a4cce6a00d2ab4bbab1bf0c1b02ee7a4e179c081f08d749229b1b854878e]);
B = 0x102c0714f154f29573b3bd81fadec3f0326b3a98d3d6644431738abcc0a4c7e, 0x713a60c7619a84330568439b91f5c8107434a9997b51b08855a5d00b9a95a2;
C = [0x82a1aefe424803dc52e79436c6fe725804e3c3dbf015a96443b98c310287c22, 0x26a800643ec7ff7c2afad918d837e4f9f2e21186d4ff5bc7ea1e4a6b9c83863c], [0x9835f892572738a70adbf5a4a85714e586ee70aeeb0da31e8e807ba8b55ac72, 0x1826d31e0e8d3e82e7a4e8661e5dd1111c6960b63771742baa74bfa413ec77a7];
gamma = [0x25c4d9a8dc20c28e8c748458882c65cbebc192baa2d65f1cde2419a397cb0591, 0x2f5a7c2b0833d1852b4183b1c3be8872c81805cf2b493b1ecb042b0d722d45a8], [0x187b417e665b5cade42c881d83094926157fdd5e09638cd510fc1d2654425568, 0x111f855c551bf7be54781df00b1c03740cafe07e235e5a12f789791af7d3463c];
gammaBeta1 = 0x7b0b5dccab3668140841b229939aef6954fb694a971f8fecdca20be198930bd, 0x2aecea0cbb65b5e0c21fc4e20a29d15cda20c9996bb9c1d3afaaf7c4fae184c8;
gammaBeta2 = [0x23271bd4f0bb68462b21a84e13194bff408dc6065e11c1a10c1aa08ff6863d25, 0x1e5ef5da9639e2f93a96628038dbfd2d09673c896cda269dd1c870725be76934], [0x87b354ba5d732413585ffe076cfa0fd53d17b3e95e3ab64ced138206a66123e, 0x2ac5269aed757351e2366325bc1997bd2413a90cec7068863c50495ff8335948];
Z = [0x152db872951f10868fab572c26639afc6dac34cb8da9d5408a5eaccf46a0ab37, 0x23f6b1ece50ed4ecd1221fc237aff6aaf920765b56d64dc327bb3a3f91394f65], [0x1dee23db18fcf5ab722b36baa161ecc5975bb221e54adbb6926ba360d78d4e86, 0x32127bee8abe9254eebbcb6213ff8d3b741624df450f6f32ff607c9eba48e4b];
IC[0] = 0x48abfc5ba0068298599939a60365562bba6278d5b038adf5fb98c0ce3d3bfc0, 0x2b99882e2174a5915c0a4552e095fcc61ca033abe355f905fe0591b8dfa4611f;
IC[1] = 0x2c2cd4404aaa8312a680bde150c635cb2802f300563cc3a2424d2ab33d43dfc6, 0x1e1c067398ca0244b87f90f9111638423457c84e74dff868a5aa0cb66020f94c;
IC[2] = 0x1bb1e80766deb009f56685a20a16a6ccca4c15a638a85e23487bec040b3bbc5b, 0x8d7e9903285bfc1036cd7e59334cfc63e6bddca326d03796d4dcd9217d87727;
IC[3] = 0x23c9f594fe3ebbbdc6bf47e68f09f4239c471f2b0ce488a4ec81e177be61620b, 0x11f45ed8aaea23caf38374b7f8292a15c82683e9e2bd41ae89164abccbb97c45;

Given Proof P, and Inputs I we can use Verification Key VK, to validate Inputs I (public inputs a,b and outputs O) for computation c(a,b)

To understand the above, let us discuss interactive proofs in a practical example. We want to buy item X from you for 1 token ( TK ). You want to make sure we have 1 TK, we show you our wallet address 0xA, you can confirm it contains 1 TK. You are unsure that we are the owner of wallet 0xA, so you use the public key (or wallet address) 0xA to sign message M, that creates hash H. You give us hash H. We use our private key PK to decrypt hash H and read message M, we respond to you with message M (or perhaps instead answer A to question phrased in message M).

Now you have proof that we own 0xA. This was an interactive proof, specifically you provided M and H.

Now, if instead we wanted to preempt your request for proof. We created message M (With the time and your name) which outputs hash H. If we then give you M, H and 0xA, you can confirm that H was created from M by the PK for 0xA. This was a non interactive (or zero knowledge) proof.

Consider this same concept for zk-SNARKs, we can confirm that Verification Key VK is generated by compiling c(a,b), and given inputs I and outputs O the worker W can create a Proving Key that can be used along with VK to confirm the output.

This allows us to achieve verifiable computing in a trustless space.