# Team 10
## Hw1
------------Pitcure-----------
------Email Information------
**系統收信時間：2018/10/6/9：52 by TA**
------------Pow---------------
101000100010010110001001000000001111111100100111000001100011000011000001011111001011010000111001000101110001000111100010100011001001111010010010001100011110
------------Score---------------
**e.g. 80 by Team15 (TA)**

=========================
## Propasal

### 題目
實踐在智能合約中的隱私性和加密性，希望能保障交易過程的隱私卻又兼顧能回查的機制。

### 動機
因為比特幣帳本中的金額和公鑰地址都是公開的，如果有有心人士想要追查某個公鑰的交易行為，可以很輕易的就在帳本中被查到，因此有了Zerocash的出現；另一方面，Ethereum則是增加了blockchain的programmability，但是也是無法顧及智能合約及交易的隱私。Privacy和programmability都是兩個重要的方向，所以希望探討有什麼方法可以兼顧區塊鏈的Privacy和programmability。

### Servey
2016年有ㄧ篇paper「 [Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts](https://eprint.iacr.org/2015/675.pdf) 」是透過這篇提出的Hawk compiler對smart contract進行加密，並分成給Manager、Users及Blockchain上執行的部分。這篇的缺點是必須要有Manager的存在，但確實提出了一個兼顧privacy及programmability的想法，也廣泛被討論及應用。

### 實作方法
一方面研究ethereum上如何compile solidity，一方面研究zerocash的zkSNARK，看看在solidity中有哪些function能透過zkSNARK運算，並將可以透過zkSNARK運算的部分運用在smart contract中，且此contract要可以被大家驗證。

========================

# Final Project -- zkSNARK Implementation on Ourchain

## 題目
實踐在智能合約中的隱私性和加密性，希望能保障交易過程的隱私卻又兼顧能回查的機制。

---

## 動機
因為比特幣帳本中的金額和公鑰地址都是公開的，如果有有心人士想要追查某個公鑰的交易行為，可以很輕易的就在帳本中被查到，因此有了**Zerocash**的出現；另一方面，**Ethereum**則是增加了blockchain的programmability，但是也是無法顧及智能合約及交易的隱私。
**Privacy**和**programmability**都是兩個重要的方向，所以希望探討有什麼方法可以兼顧區塊鏈的Privacy和programmability。

---

## Servey
2016年有ㄧ篇paper「 [**Hawk**: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts](https://eprint.iacr.org/2015/675.pdf) 」是透過這篇提出的Hawk compiler對smart contract進行加密，並分成給Manager、Users及Blockchain上執行的部分。這篇的缺點是必須要有Manager的存在，但確實提出了一個兼顧privacy及programmability的想法，也廣泛被討論及應用。

2018年的IEEE International Conference on Blockchain中，「 [**ZoKrates** - Scalable Privacy-Preserving Off-Chain Computations](https://www.ise.tu-berlin.de/fileadmin/fg308/publications/2018/2018_eberhardt_ZoKrates.pdf) 」這篇文章得到了best paper award，除了說明區塊鏈上的隱私仍然是一個重要議題之外，跟Hawk相比，這篇paper提供了[Github](https://github.com/Zokrates/ZoKrates)，而且也不需要第三方Manager的存在，因此符合我們對隱私問題的想法。

我們希望透過實做這篇paper更了解zkSNARK，以及使用zkSNARK解決問題的使用者如何互動，並且希望在Ourchain的系統上實做，而不是像ZoKrates一樣是獨立於blockchain之外的套件。

---

## zkSNARK

整體架構分為三個步驟：1.智能合約轉為一階限制式（R1CS）、2.一階限制式轉為DAP問題、3.將所有數學式轉移至橢圓曲線空間

### 1.智能合約轉為一階限制式（R1CS）
此步驟中，再細分為三個小步驟：

#### 1-1.智能合約化為數學式
首先，將smart contract以數學式子來表示，其中，此數學式子不能有無限迴圈。
#### 1-2.為Flatten
接著，將此數學式拆解為一群簡單式子，每條式子只能有加減乘除運算。
其中，每條式子只能做以下兩種事：
x = y
x = y op z(op可為加減乘除)
#### 1-3.化為R1CS
R1CS是由三個向量a, b, c所化成的，其中有個解向量s，使每行式子滿足
sa * s•b - s•c = 0

#### 註：轉化為R1CS後，若提出者要證明自己知道解，便把answer vector s給礦工，礦工通過a, b, c來驗證

### 2.一階限制式轉為DAP問題
若只是1-3所做出來的R1CS，會有兩個問題：要驗證時，礦工需要將提出者的s帶入每一行flatten後的式子之中，若是很複雜的數學式，則需要花費大量時間在驗證上。此外，目前也還沒有做到加密。此時，我們先解決第一個問題，如何簡化驗證的過程。

#### 2-1.R1CS透過拉格朗日轉換
因為每個flatten後的簡單數學式都有一組(ai, bi, ci)，此時，我們透過拉格朗日式，將n組(a, b, c)化為一組(A, B, C)，其中，若x代入1則會得出(a1, b1, c1)，以此類推直至x=n。

#### 2-2.轉化為DAP
經過2-1的步驟，要驗證時礦工會將(A, B, C)中的x代入1~n，並代入提出者的解向量s來驗證。由此可知，s與(A, B, C)先代入後的式子，其根會是x=1~n，因此，只要定義Z(x) = (x-1)(x-2)(x-3)(x-4)，如果證明A(x) * B(x) - C(x)是Z(x)的倍數，即可驗證成功。

#### 將過第二步驟的轉換，礦工只需驗證一行式子，即A(x) * B(x) - C(x)是Z(x)的倍數，便可以驗證成功。

### 3.將所有數學式轉移至橢圓曲線空間
最後，經過了第二步驟，問題只剩下一個：如何加密。
因為橢圓曲線上有pairing的性質，此性質可以滿足上述的數學式子在加密空間所需要的運算，因此，將所有數學式在橢圓曲線的空間下進行運算，便可得到加密的效果。

### 4.總結zkSNARK於此Final project之應用

#### 最後，整理一下進行此project時如何運用zkkSNARK。經過上述的數學運算後，可以將smart contract化為兩個部分：
#### proof：上述所提到的，提供者所出示的解向量s，用來給礦工驗證是否真的知道解答。
#### verifier：上述所提到的題目，也就是A(x)+B(x)-C(x)=0。

---

## ZoKrates流程圖

參與者：出題者，答題者，礦工
### Off chain
1. **出題者**將一個邏輯化過後的問題給答題者(eg.數獨問題)，出題者也將這個問題寫成high level code
2. **出題者**用ZoKrates把high level code compile後，會產生proving.key、verification.key、variables.inf，這就相當於方便之後使用的zkSNARK的A、B、C的部份。
3. **出題者**將proving.key、verification.key、variables.inf給答題者。
4. **答題者**解完問題之後，把自己的答案及剛出題者給的檔案經過ZoKrates運算，得到自己的proof.json。
5. **出題者**也由剛的verification.key用ZoKrates生成verifier.sol(要上鏈給礦工驗證的合約)。

### On chain
6. **出題者**先將合約(verifier.sol)上鏈(deploy)，變成contract(圖中0xdce....046f)。
7. **答題者**用剛剛產生的proof.json裡數據當作參數呼叫contract 0xdce...046f。
8. **礦工**會執行呼叫的合約，若答題者丟的參數是符合合約的，則用log的方式在contract中產生"Transaction Verified."，表示驗證成功。

#### `Verifier.sol` Example

// This file is MIT Licensed.
//
// Copyright 2017 Christian Reitwiessner
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

pragma solidity ^0.4.14;
library Pairing {
    struct G1Point {
        uint X;
        uint Y;
    }
    // Encoding of field elements is: X[0] * z + X[1]
    struct G2Point {
        uint[2] X;
        uint[2] Y;
    }
    /// @return the generator of G1
    function P1() pure internal returns (G1Point) {
        return G1Point(1, 2);
    }
    /// @return the generator of G2
    function P2() pure internal returns (G2Point) {
        return G2Point(
            [11559732032986387107991004021392285783925812861821192530917403151452391805634,
             10857046999023057135944570762232829481370756359578518086990519993285655852781],
            [4082367875863433681332203403145435568316851327593401208105741076214120093531,
             8495653923123431417604973247489272438418190587263600148770280649306958101930]
        );
    }
    /// @return the negation of p, i.e. p.addition(p.negate()) should be zero.
    function negate(G1Point p) pure internal returns (G1Point) {
        // The prime q in the base field F_q for G1
        uint q = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
        if (p.X == 0 && p.Y == 0)
            return G1Point(0, 0);
        return G1Point(p.X, q - (p.Y % q));
    }
    /// @return the sum of two points of G1
    function addition(G1Point p1, G1Point p2) internal returns (G1Point r) {
        uint[4] memory input;
        input[0] = p1.X;
        input[1] = p1.Y;
        input[2] = p2.X;
        input[3] = p2.Y;
        bool success;
        assembly {
            success := call(sub(gas, 2000), 6, 0, input, 0xc0, r, 0x60)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require(success);
    }
    /// @return the product of a point on G1 and a scalar, i.e.
    /// p == p.scalar_mul(1) and p.addition(p) == p.scalar_mul(2) for all points p.
    function scalar_mul(G1Point p, uint s) internal returns (G1Point r) {
        uint[3] memory input;
        input[0] = p.X;
        input[1] = p.Y;
        input[2] = s;
        bool success;
        assembly {
            success := call(sub(gas, 2000), 7, 0, input, 0x80, r, 0x60)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require (success);
    }
    /// @return the result of computing the pairing check
    /// e(p1[0], p2[0]) *  .... * e(p1[n], p2[n]) == 1
    /// For example pairing([P1(), P1().negate()], [P2(), P2()]) should
    /// return true.
    function pairing(G1Point[] p1, G2Point[] p2) internal returns (bool) {
        require(p1.length == p2.length);
        uint elements = p1.length;
        uint inputSize = elements * 6;
        uint[] memory input = new uint[](inputSize);
        for (uint i = 0; i < elements; i++)
        {
            input[i * 6 + 0] = p1[i].X;
            input[i * 6 + 1] = p1[i].Y;
            input[i * 6 + 2] = p2[i].X[0];
            input[i * 6 + 3] = p2[i].X[1];
            input[i * 6 + 4] = p2[i].Y[0];
            input[i * 6 + 5] = p2[i].Y[1];
        }
        uint[1] memory out;
        bool success;
        assembly {
            success := call(sub(gas, 2000), 8, 0, add(input, 0x20), mul(inputSize, 0x20), out, 0x20)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require(success);
        return out[0] != 0;
    }
    /// Convenience method for a pairing check for two pairs.
    function pairingProd2(G1Point a1, G2Point a2, G1Point b1, G2Point b2) internal returns (bool) {
        G1Point[] memory p1 = new G1Point[](2);
        G2Point[] memory p2 = new G2Point[](2);
        p1[0] = a1;
        p1[1] = b1;
        p2[0] = a2;
        p2[1] = b2;
        return pairing(p1, p2);
    }
    /// Convenience method for a pairing check for three pairs.
    function pairingProd3(
            G1Point a1, G2Point a2,
            G1Point b1, G2Point b2,
            G1Point c1, G2Point c2
    ) internal returns (bool) {
        G1Point[] memory p1 = new G1Point[](3);
        G2Point[] memory p2 = new G2Point[](3);
        p1[0] = a1;
        p1[1] = b1;
        p1[2] = c1;
        p2[0] = a2;
        p2[1] = b2;
        p2[2] = c2;
        return pairing(p1, p2);
    }
    /// Convenience method for a pairing check for four pairs.
    function pairingProd4(
            G1Point a1, G2Point a2,
            G1Point b1, G2Point b2,
            G1Point c1, G2Point c2,
            G1Point d1, G2Point d2
    ) internal returns (bool) {
        G1Point[] memory p1 = new G1Point[](4);
        G2Point[] memory p2 = new G2Point[](4);
        p1[0] = a1;
        p1[1] = b1;
        p1[2] = c1;
        p1[3] = d1;
        p2[0] = a2;
        p2[1] = b2;
        p2[2] = c2;
        p2[3] = d2;
        return pairing(p1, p2);
    }
}
contract Verifier {
    using Pairing for *;
    struct VerifyingKey {
        Pairing.G2Point A;
        Pairing.G1Point B;
        Pairing.G2Point C;
        Pairing.G2Point gamma;
        Pairing.G1Point gammaBeta1;
        Pairing.G2Point gammaBeta2;
        Pairing.G2Point Z;
        Pairing.G1Point[] IC;
    }
    struct Proof {
        Pairing.G1Point A;
        Pairing.G1Point A_p;
        Pairing.G2Point B;
        Pairing.G1Point B_p;
        Pairing.G1Point C;
        Pairing.G1Point C_p;
        Pairing.G1Point K;
        Pairing.G1Point H;
    }
    function verifyingKey() pure internal returns (VerifyingKey vk) {
        vk.A = Pairing.G2Point([0x36a9b45498a229b1e7ef7a361af21449cef67f4033bf39d91294a62efd31063, 0x2b2f60843cf8c8285edafe94d1c8c90cb49a946dcf00a29404500cbe5b66a660], [0xcce23a7622de5f2414862e8a8906044959d650b5d0904c1d25c23f257d56385, 0x29439a979b12f6d4b3c19b810f258e5c8f3ae7d1ac545a998221521c22dca582]);
        vk.B = Pairing.G1Point(0x66bae442a7d739351505139b79a329f791522af668288302333512e25a942a7, 0x1d13058667e13390c8c9ccafb55e8682b7afc8a703e9653cce1367b0453f518a);
        vk.C = Pairing.G2Point([0x2320c7a888cf389e945c5f57525d1b7f90189fd342fee4c8c140529716e497, 0x12e4efee3e5a38f830ebc3ca51b53d6f0882024d5bd729521bc93c2929a2cd5a], [0x3325abcd2278b517b07bfd5d57d34d52329ed49adaf414cdc5fea25177f0e3, 0x1d43c3150f5462421591ae7e48109d46dfcb5a3875bdf4c6e8d6a5dbb40f97a1]);
        vk.gamma = Pairing.G2Point([0x1192784ca0c063e49ae38ecc79b764678075400b03eeb5f1965a62062c94e6a2, 0x36c5437eb88e730852979f57830d9ece62d669e748d479215cc312d272f70a], [0x1f7e574d92ec25adc452d397dc5f33edd18b0716236c985040a568b8bb957259, 0x2455001ee8f3cdf827a470d40294c810ba3a42b1f68501d68549e86d3e8cd629]);
        vk.gammaBeta1 = Pairing.G1Point(0x7d339c78e115ee349142006accb7b7320dc2c1191369503fa48397b94b16756, 0x145b847d12a1cac9aaf3d939f7144e15e4035a5def78980b28270add47721eb0);
        vk.gammaBeta2 = Pairing.G2Point([0x2d3711117424644536ce90a9af91cec40890caff9b0c101c01387d9f6ddd9562, 0x1972c22c162014d4dbf2911dcf0025d38ee1cd5c0d06669de7f29707565ee560], [0x117a23f4e2c1aa6802b2045ba38070548eb4964ea6c5438c6bc9b0a65c7cf5cd, 0x26e4d6e1740c58a9584a9a1e80e93a0b2df442eb219d513e172110446ab98983]);
        vk.Z = Pairing.G2Point([0x264d1e82eeb98b0419bc64251dcc3c80053a857a3d4e60efd87d939f7bb56a4, 0x132d68d5660a51c50cfe30f79f5da0e528c36bf46676fad37b957a063bdd587a], [0x292509f27ea20e5ad51e3eaa87e2f274b9aa93cf7f4e724b79544999d597b814, 0x2a0ecca5f357ea283998fb991c741e8d10c25d83bed7193eb9769bd46a300c08]);
        vk.IC = new Pairing.G1Point[](8);
        vk.IC[0] = Pairing.G1Point(0x12d56433d38c87fb0ec89c37c5805b4e92c737a2180e59c92ee5331f887868bb, 0xb58a805ab1a8781cda46beaf48ec68b763d32a9b7b890ff594cd7efb4feeb25);
        vk.IC[1] = Pairing.G1Point(0x8d1c0ecf1da434b4d2f443d8ce165d3ef3d60cf6523ac8a78b1d69fd019914, 0xb9669eedafa182273c8299d593c931c9a42603c1ae1b2913112436ee1085f57);
        vk.IC[2] = Pairing.G1Point(0x22c9edcd3f20aea632feb1bf02d5ee2832e518b0a0a240584903542cc0b4d715, 0xa8955a9ac9f4d6a937f6afcb108e74917e0a4b12e85f8702b086a549cc16ff8);
        vk.IC[3] = Pairing.G1Point(0x9e08a0442a5ffdf76509c293d8e5fcffc726e372de2b67e462f822817f0e963, 0x426a723f425010bc6171dd7efa2cd5a3021555f3b9e459ae1e43f8ab79e32c0);
        vk.IC[4] = Pairing.G1Point(0x2aa215f26099627aef3461a62e8abc0fedb221194ee4185efca52c952c43671c, 0x4b6b9ecac9240bc15b2e17e8665d8d16765889f1600326fb033190dacc8e5e0);
        vk.IC[5] = Pairing.G1Point(0x205e477944876b5f5c1bf973f0b9f85aa465015b18489ebfe60802906b7d8bc7, 0x25965a95b701aaff11eaf98a1d859f78e3ac91f00f938752a09e3e80afb15b14);
        vk.IC[6] = Pairing.G1Point(0x261d3b70d148ef60ec548116cf38500fd536328d1d19a0e938e41df9eed921f, 0x34c42910a674da5ea3e8767cff7adbcc2d3cdde21b001f785e3b5d9a2acc4c5);
        vk.IC[7] = Pairing.G1Point(0x2375fba59cc725747fc685b24af24a1c81f7c54a05c85d2147d67ccdd906258d, 0x1c11257e4fa3ccf939201849ef069527ebde84f4eecf15181543efaeabb5343);
    }
    function verify(uint[] input, Proof proof) internal returns (uint) {
        VerifyingKey memory vk = verifyingKey();
        require(input.length + 1 == vk.IC.length);
        // Compute the linear combination vk_x
        Pairing.G1Point memory vk_x = Pairing.G1Point(0, 0);
        for (uint i = 0; i < input.length; i++)
            vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.IC[i + 1], input[i]));
        vk_x = Pairing.addition(vk_x, vk.IC[0]);
        if (!Pairing.pairingProd2(proof.A, vk.A, Pairing.negate(proof.A_p), Pairing.P2())) return 1;
        if (!Pairing.pairingProd2(vk.B, proof.B, Pairing.negate(proof.B_p), Pairing.P2())) return 2;
        if (!Pairing.pairingProd2(proof.C, vk.C, Pairing.negate(proof.C_p), Pairing.P2())) return 3;
        if (!Pairing.pairingProd3(
            proof.K, vk.gamma,
            Pairing.negate(Pairing.addition(vk_x, Pairing.addition(proof.A, proof.C))), vk.gammaBeta2,
            Pairing.negate(vk.gammaBeta1), proof.B
        )) return 4;
        if (!Pairing.pairingProd3(
                Pairing.addition(vk_x, proof.A), proof.B,
                Pairing.negate(proof.H), vk.Z,
                Pairing.negate(proof.C), Pairing.P2()
        )) return 5;
        return 0;
    }
    event Verified(string s);
    function verifyTx(
            uint[2] a,
            uint[2] a_p,
            uint[2][2] b,
            uint[2] b_p,
            uint[2] c,
            uint[2] c_p,
            uint[2] h,
            uint[2] k,
            uint[7] input
        ) public returns (bool r) {
        Proof memory proof;
        proof.A = Pairing.G1Point(a[0], a[1]);
        proof.A_p = Pairing.G1Point(a_p[0], a_p[1]);
        proof.B = Pairing.G2Point([b[0][0], b[0][1]], [b[1][0], b[1][1]]);
        proof.B_p = Pairing.G1Point(b_p[0], b_p[1]);
        proof.C = Pairing.G1Point(c[0], c[1]);
        proof.C_p = Pairing.G1Point(c_p[0], c_p[1]);
        proof.H = Pairing.G1Point(h[0], h[1]);
        proof.K = Pairing.G1Point(k[0], k[1]);
        uint[] memory inputValues = new uint[](input.length);
        for(uint i = 0; i < input.length; i++){
            inputValues[i] = input[i];
        }
        if (verify(inputValues, proof) == 0) {
            emit Verified("Transaction successfully verified.");
            return true;
        } else {
            return false;
        }
    }
}

#### `proof.json` Example

{
	"proof":
	{
		"A":["0xec275e3c31cbdfb467a8d83bd37c14aebc395e207c5b965d4ce852ab4966d42", "0x9fb4e1ce67d47ac536f5f0a01bfbf1e5ffaceadecb2fdbac948c7621ccd91bd"],
		"A_p":["0x2e2c2363707ee3861d8b981f1bd76f1a1b8bf3098da10ba62d79cb2dc7504df1", "0x1977704b419700f28246f4316e306c4362665a284fb6c3717fc4010a2ccd822"],
		"B":
			[["0x2a9f802630ca81e638caee028b2fc7aa8472b30cbc2c3aa744e125ae9ea0fa92", "0x22035474150757496dc0803e3d8ad56922e551eed5d3698d4730b26723b00af"], ["0x2a38552d265701ac12446e6124a4b962dc9dbfcfca7eadcd07e1ee2912101f7a", "0x73186ab967f8e325a905cdb53647d35d029cf763ae079cf948fcf091036ae66"]],
		
		"B_p":["0x27013157a6ebe32e99913044fcb0b26328a07c41c0a8019e11f2cc29a5edd0d3", "0xe9e31f9faa824589072b302cdbb54be14a67ae26f1dfa8415fcf8a48682b6d8"],
		"C":["0x2ba12115fa8fedb316ec0614e7fea705fe6febf64437ba50b16afd84f5118cd1", "0xf9cfcbf36e57e743db2a6422e391728060418ce67da2e727ce7c7e70618155b"],
		"C_p":["0x1f71168bd833d664e3b24cdda001fdab14e43b8d65a2faa48059243f40ec03a0", "0x115e1f02027076ff863aaf28ff116a2f97e26a1690de744fd004fa31ca5ff9cd"],
		"H":["0x1656dba2468555c30a7997b12d766a3c36ebfd2c5886d3e54a7259fd77f4cf09", "0xb89b0f876cb4aaead7639cc43007c754daade98ff8effe6da47bc696a7778aa"],
		"K":["0x4ae4a8421987b32159991fce4727f4a2cefa6e3f24c757cbf187148d1aa50f8", "0xf3de8a3278069ddc420f2d2026869f07942c72d20b5220a1a17cfbfb5c78762"]
	},
	"input":[3,4,2,2,3,2,1]
}

> * `proof.json`中的`"input":[3,4,2,2,3,2,1]`：前面6個數字為數獨的public input，而最後的1為程式的return值。
> * 在數獨的情況中，若return 1為數獨確認成功，若return 0為數獨確認失敗。
> 所以在上傳到鏈上之前，我們就能知道會是return 1還是return 0。
> 如果算出來的proof return 0，丟到鏈上後，通過礦工的驗證，還是會顯示"Transaction Verified."，因為礦工只會根據答題者提供的input做運算，並不會判斷是否return 1還是0是通過數獨的題目。
> * 除了可以return 0, 1之外，也可以return其他數字。
---

## 架設Ourchain

### Build the Core

./autogen.sh
./configure --disable-tests
make
make install # optional

### Run the Core
1. 建立一個儲存blockchain data的資料夾
example:

$ mkdir bitdata/

2. 在`bitdata/`資料夾裡面創建一個檔案叫 `bitcoin.conf`
example of `bitcoin.conf`:

rest=1
rpcport=8333
rpcallowip=0.0.0.0/0
rpcuser=user1
rpcpassword=111111
datadir=bitdata

3. 執行 `Bitcoind`:

$ ./src/bitcoind -datadir=bitdata

#### Error 1:

Assertion failed: (consensus.hashGenesisBlock == uint256S("0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f")), function CMainParams, file chainparams.cpp, line 155.
Abort trap: 6

> ### Note:
> [<assert.h>](https://en.wikipedia.org/wiki/Assert.h)
> 如果`assert()` return 0，則程式繼續執行，否則會有"Assertion failed"，並程式且呼叫`abort()`。
> 此情況中:`consensus.hashGenesisBlock` 不等於`uint256S("0x00000005e296bf1ed66666379135961d3521f01a96d4f0d6ed40cae1bdc4faa5")`

#### 解法 1:
* 執行`src/chainparams.cpp`中的`MINE_MAIN_GENESIS`
換言之，註解掉24, 28, 134, 151行。

* 接著再執行一次 `$ make`。
執行 `$ ./src/bitcoind -datadir=bitdata`
程式會根據time跟nouce創造第一個區塊
For example:

$ ./src/bitcoind -datadir=bitdata
Mining main genesis block...

time = 1543817825
nonce = 3365310
hash = 00000074dbb783e722a81d61f085eacc482b446b104568521540b3985249d955
hashMerkleRoot = d9f2a49b88a6a667ec31635b1148378d656eab79ba1bd4736cfe51516464980f

Assertion failed: (false), function CMainParams, file chainparams.cpp, line 146.
Abort trap: 6

* 根據 `src/chainparams.cpp` 第140行:

genesis = CreateGenesisBlock(t, n, 0x1d7fffff, 1, 50 * COIN);

genesis block是由`(t, n, 0x1d7fffff`)決定, 若
`t = time = 1543817825`
`n = nouce = 3365310`
則 `genesis.GetHash()` 為
`hash = "0x00000074dbb783e722a81d61f085eacc482b446b104568521540b3985249d955"`

* 根據剛剛計算出來的`time`, `nonce`, `hash`, `hashMerkleRoot`的結果，修改 `src/chainparams.cpp` 第153-156行。
Example:

genesis = CreateGenesisBlock(1543817825, 3365310, 0x1d7fffff, 1, 50 * COIN);
consensus.hashGenesisBlock = genesis.GetHash();
assert(consensus.hashGenesisBlock == uint256S("0x00000074dbb783e722a81d61f085eacc482b446b104568521540b3985249d955"));
assert(genesis.hashMerkleRoot == uint256S("0xd9f2a49b88a6a667ec31635b1148378d656eab79ba1bd4736cfe51516464980f"));

* 恢復第24, 28, 134及151行
執行 `make` 及 `./src/bitcoind -datadir=bitdata`

#### Error 2:

Error: Unable to bind to 0.0.0.0:8333 on this computer. Bitcoin Core is probably already running.
Error: Failed to listen on any port. Use -listen=0 if you want this.

#### 解法 2:

./src/bitcoind -datadir=bitdata -listen=0

> ### Note:
> 若是在Testnet或Regtest上執行，則修改相對應的271-274行程式及374-377行。
>

### Bitcoin-cli
若能成功執行 `bitcoind` ，則我們可以用 `Bitcoin-cli` 呼叫其他指令。
For example:

$ ./src/bitcoind -datadir=bitdata -listen=0

開啟令一個terminal, 用`getblockchaininfo` 取得blockchain的information:

$ ./src/bitcoin-cli -datadir=bitdata getblockchaininfo
{
  "chain": "main",
  "blocks": 0,
  "headers": 0,
  "bestblockhash": "00000034eec6965551ce80ddb3f94157e33e40b85f9688969c0b8015951dafb3",
  "difficulty": 0.007812381722018924,
  "mediantime": 1543891252,
  "verificationprogress": 2.672102899689912e-09,
  "chainwork": "0000000000000000000000000000000000000000000000000000000002000004",
  "pruned": false,
  "softforks": [
    {
      "id": "bip34",
      "version": 2,
      "reject": {
        "status": false
      }
    }, 
    {
      "id": "bip66",
      "version": 3,
      "reject": {
        "status": false
      }
    }, 
    {
      "id": "bip65",
      "version": 4,
      "reject": {
        "status": false
      }
    }
  ],
  "bip9_softforks": {
    "csv": {
      "status": "defined",
      "startTime": 1462060800,
      "timeout": 1493596800,
      "since": 0
    },
    "segwit": {
      "status": "defined",
      "startTime": 1479168000,
      "timeout": 1510704000,
      "since": 0
    }
  }
}

用 `stop` 停止 `bitcoind`

$ ./src/bitcoin-cli -datadir=bitdata stop

### Generated block & Immature block

#### 問題
在bitcoin中我們可以在`-restest`中透過以下指令：

$ bitcoin-cli -regtest generate 101

在blockchain中產生101個塊，使得第一個塊產生的挖礦獎勵存進錢包。
因為區塊必須經過100個塊的確認(confirmation)之後，該區塊才會被認為是合法的區塊。
在100個確認之前的塊就稱**Immature Block**，在經過100個確認之後的塊就叫**Generated Block**
> 參考文件：[Bitcoin Developer Examples](https://bitcoin.org/en/developer-examples#regtest-mode)

所以在`regtest`模式下必須要產生至少101個塊才會收到挖礦獎勵，在Ourchain中因為挖礦獎勵受到時間限制，所以若要挖100個礦相當費時。

#### 解法
修改區塊須經過100次確認的程式碼
在[bitcoin/src/consensus/consensus.h](https://github.com/bitcoin/bitcoin/blob/78dae8caccd82cfbfd76557f1fb7d7557c7b5edb/src/consensus/consensus.h?fbclid=IwAR2tbnEXsMzTEb4-mnRrTWVAqsKAN9nQHI6ZItY9C5J-G4TscBXIxQEHj5U#L19)中的第18行

/** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
static const int COINBASE_MATURITY = 100;

將此值100改為其他值，即可經過較少次確認而得到挖礦獎勵。

重新執行`$ make`之後，若原本就存了100個塊的資料，那錢包裡面就會多出`(100-COINBASE_MATURITY) * 50.0000`塊錢。

### Ourcontract
參考[Ourcontract.md](https://bitbucket.org/lab408/ourchain-release/src/53f71555e8aba5d6c52d323b4bf40727fce556f7/doc/ourcontract.md)

#### ourcontract-mkdll
使用`ourcontract-mkdll`編譯code成code.o及code.so檔。

$ ourcontract-mkdll contracts vote

> 這步在macOS中有動態連接library的問題，因此無法在macOS中執行contract
>

#### ourcontract-rt
使用`ourcontract-rt`執行`contracts/vote/`中的執行檔，並輸出結果在stdout。

$ ourcontract-rt contracts vote [ARG 1] [ARG 2] ...

#### deploycontract
`deploycontract`是在區塊鏈上放上contract，輸出一個*txid*及*contract address*。

*txid*：此交易的id。
*contract address*：輸出的contract資料夾名稱，**呼叫contract時也是使用此contract address**。

在此步驟已經也可以同時呼叫contract，輸入第一次的arguments。

$ bitcoin-cli deploycontract vote.c [ARG 1] [ARG 2] ...

#### callcontract
`callcontract`呼叫已經在區塊鏈上的contract，輸出一個*txid*。

**在產生區塊(generate)後，該contract的專屬資料夾(以contract address為名)才會出現在contracts資料夾中，且輸出結果也才會出現在contracts/err檔案中**

$ bitcoin-cli callcontract [contract address] [ARG 1] [ARG 2] ...

#### dumpcontractmessage
`dumpcontractmessage`取得呼叫`callcontract`時的output。
若有output則會在`contracts/[txid]/out`檔案中。

$ bitcoin-cli dumpcontractmessage [contract address]

---

## 實作方法

* 為了使用Zokrates套件，我們必須先將想要驗證的事情寫成附檔名為.code的程式，以數讀的例子來說，sudokuchecker.code 程式碼如下：

// Sudoku of format

// | a11 | a12 || b11 | b12 |
// --------------------------
// | a21 | a22 || b21 | b22 |
// ==========================
// | c11 | c12 || d11 | d12 |
// --------------------------
// | c21 | c22 || d21 | d22 |

def checkEquality(field e11,field e12,field e21,field e22) -> (field):
field counter = if e11 == e12 then 1 else 0 fi
counter = counter + if e11 == e21 then 1 else 0 fi
counter = counter + if e11 == e22 then 1 else 0 fi
counter = counter + if e12 == e21 then 1 else 0 fi
counter = counter + if e12 == e21 then 1 else 0 fi
counter = counter + if e21 == e22 then 1 else 0 fi
return counter

// returns 0 for x in (1..4)
def validateInput(field x) -> (field):
return (x-1)*(x-2)*(x-3)*(x-4)

// variables naming: box'row''column'
def main(field a21, field b11, field b22, field c11, field c22, field d21, private field a11, private field a12, private field a22, private field b12, private field b21, private field c12, private field c21, private field d11, private field d12, private field d22) -> (field):

// validate inputs
0 == validateInput(a11)
0 == validateInput(a12)
0 == validateInput(a21)
0 == validateInput(a22)

0 == validateInput(b11)
0 == validateInput(b12)
0 == validateInput(b21)
0 == validateInput(b22)

0 == validateInput(c11)
0 == validateInput(c12)
0 == validateInput(c21)
0 == validateInput(c22)

0 == validateInput(d11)
0 == validateInput(d12)
0 == validateInput(d21)
0 == validateInput(d22)

field counter = 0 // globally counts duplicate entries in boxes, rows and columns

// check box correctness

  // no duplicates
  counter = counter + checkEquality(a11,a12,a21,a22)
  counter = counter + checkEquality(b11,b12,b21,b22)
  counter = counter + checkEquality(c11,c12,c21,c22)
  counter = counter + checkEquality(d11,d12,d21,d22)

// check row correctness

  counter = counter + checkEquality(a11,a12,b11,b12)
  counter = counter + checkEquality(a21,a22,b21,b22)
  counter = counter + checkEquality(c11,c12,d11,d12)
  counter = counter + checkEquality(c21,c22,d21,d22)

// check column correctness

  counter = counter + checkEquality(a11,a21,c11,c21)
  counter = counter + checkEquality(a12,a22,c12,c22)
  counter = counter + checkEquality(b11,b21,d11,d21)
  counter = counter + checkEquality(b12,b22,d12,d22)

// assert counter is 0
counter == 0

return 1

* 之後依照Zokrates documentation的建議進到docker環境，依序執行以下的指令：

# compile
./zokrates compile -i sudokuchecker.code
# perform the setup phase
./zokrates setup
# execute the program
./zokrates compute-witness -a [your sudoku solution]
# generate a proof of computation
./zokrates generate-proof
# export a solidity verifier
./zokrates export-verifier

* 即可生成一個用來做檢驗的智能合約verifier.sol，以及其它相關檔案，然而為了要執行在OurChain上，我們必須把solidity的合約改成C語言的版本，這裡我們目前是用手動編譯，主要需要使用<gmp.h>的library以及幾個橢圓曲線上的運算，程式碼大致如下：

#include<stdio.h>
#include<stdlib.h>
#include<gmp.h>

struct Point
{
	mpz_t x;
	mpz_t y;
};

void Point_Addition(struct Point P,struct Point Q,struct Point* R);
void Point_Doubling(struct Point P,struct Point *R);
void Scalar_Multiplication(struct Point P,struct Point* R, mpz_t m);

void Point_Addition(struct Point P,struct Point Q,struct Point* R)
{
	mpz_mod(P.x,P.x,EC.p);
	mpz_mod(P.y,P.y,EC.p);
	mpz_mod(Q.x,Q.x,EC.p);
	mpz_mod(Q.y,Q.y,EC.p);
	mpz_t temp,slope;
	mpz_init(temp);
	mpz_init_set_ui(slope,0);
	if(mpz_cmp_ui(P.x,0)==0 && mpz_cmp_ui(P.y,0)==0)
		{ mpz_set(R->x,Q.x); mpz_set(R->y,Q.y); return;}
	if(mpz_cmp_ui(Q.x,0)==0 && mpz_cmp_ui(Q.y,0)==0)
		{ mpz_set(R->x,P.x); mpz_set(R->y,P.y); return;}
	if(mpz_cmp_ui(Q.y,0)!=0)
		{mpz_sub(temp,EC.p,Q.y);mpz_mod(temp,temp,EC
			.p);}
	else
		mpz_set_ui(temp,0);
// gmp_printf("\n temp=%Zd\n",temp);
	if(mpz_cmp(P.y,temp)==0 &&
		mpz_cmp(P.x,Q.x)==0)
		{ mpz_set_ui(R->x,0); mpz_set_ui(R->y,0); return;}
	if(mpz_cmp(P.x,Q.x)==0 &&
		mpz_cmp(P.y,Q.y)==0)
	{
		Point_Doubling(P,R);
		return;
	}
	else
	{
		mpz_sub(temp,P.x,Q.x);
		mpz_mod(temp,temp,EC.p);
		mpz_invert(temp,temp,EC.p);
		mpz_sub(slope,P.y,Q.y);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,Q.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
		return;
	}
}

void Point_Doubling(struct Point P,struct Point *R)
{
	mpz_t slope,temp;
	mpz_init(temp);
	mpz_init(slope);
	if(mpz_cmp_ui(P.y,0)!=0)
	{
		mpz_mul_ui(temp,P.y,2);
		mpz_invert(temp,temp,EC.p);
		mpz_mul(slope,P.x,P.x);
		mpz_mul_ui(slope,slope,3);
		mpz_add(slope,slope,EC.a);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,P.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
	}
	else
	{
		mpz_set_ui(R->x,0);
		mpz_set_ui(R->y,0);
	}
}

void Scalar_Multiplication(struct Point P,struct Point* R, mpz_t m)
{
	struct Point Q,T;
	mpz_init(Q.x); mpz_init(Q.y);
	mpz_init(T.x); mpz_init(T.y);
	long no_of_bits,loop;
	no_of_bits=mpz_sizeinbase(m,2);
	mpz_set_ui(R->x,0);mpz_set_ui(R->y,0);
	if(mpz_cmp_ui(m,0)==0)
		return;
	mpz_set(Q.x,P.x);
	mpz_set(Q.y,P.y);
	if(mpz_tstbit(m,0)==1)
		{mpz_set(R->x,P.x);mpz_set(R->y,P.y);}
	for(loop=1;loop<no_of_bits;loop++)
	{
		mpz_set_ui(T.x,0);
		mpz_set_ui(T.y,0);
		Point_Doubling(Q,&T);
		gmp_printf("\n %Zd %Zd %Zd %Zd ",Q.x,Q.y,T.x,T.y);
		mpz_set(Q.x,T.x);
		mpz_set(Q.y,T.y);
		mpz_set(T.x,R->x);
		mpz_set(T.y,R->y);
		if(mpz_tstbit(m,loop))
			Point_Addition(T,Q,R);
	}
}

//todo: pairing computation 

* 轉成附檔名為.c版本的智能合約之後，就可以將此智能合約上鏈，而提供解答的人可以輕鬆將自己的答案轉成C語言版本的int array，礦工即可幫忙驗證答案是否通過verifier.c。

* Future Work:
* 快速從.sol轉成.c的compiler
* verifier.c中的pairing計算
* 目前zokrates是執行在docker環境下，對礦工可能造成不便，應該要能將環境建置的過程寫成程式方便所有礦工建置可執行zokrates的環境。

---
## 實驗結果

### Ethereum Gas
* 為了計算出題者及答題者將問題轉換過後所需要的付出的代價，我們首先實測原來ZoKrates paper中提供的Ethereum的版本。在Ethereum中，發布contract及呼叫contract的人都必須支付叫做**Gas**的費用，Gas是根據contract的bytecode進行計算，因此也代表程式的複雜度。
* 透過Ethereum的Ropsten Testnet實測上鏈的Gas。分為出題者發布contract的**Deploy**及答題者呼叫contract的**Call**操作。
* 另外也把原本未加密的問題(**Original ver.**)跟經過加密過後的問題(**ZoKrates ver.**)進行比較。

| Ethereum Gas | Deploy(Original ver.) | Call(Original ver.) |Deploy(ZoKrates ver.) | Call(ZoKrates ver.) |
| -------- | -------- | -------- |-------- | -------- |
| 4x4 Sudoku checker | 665,093 | 45,866 | 1,889,467|1,883,931|
| if a*a==b | 148,791 | 24,091 |1,732,436|1,664,020|
| if a*a+b==c(2 priv, 1 pub) | ||1,732,500 | 1,663,956 |
| (3 priv, 1 pub) | ||1,733,088 | 1,663,828 |
| (1 priv, 2 pub) | ||1,764,471 | 1,707,757 |
| (1 priv, 3 pub) | ||1,794,992 | 1,751,878 |

> 註：
> 第一個4x4 sudoku checker是將數獨數字當作參數(包含6個public及10個private的input)，在contract中檢驗是否符合行、列、每個方形中的值相加是否相等，且值是否為1-4。
> 第二個(if axa == b)是跟數獨比起來相對簡單的運算，只有一條判斷式。把a跟b當作參數，a為private，b為public(因此只有一個public跟一個private)。
> 第三到六個為測試private input跟public input對gas的差異，測試方式為把(if axa == b)的問題擴張成(if axa + bxb == c)、(if axa + bxb + cxc == d)，讓程式參數量增加，並調整public及private的input的數量。
>

#### 發現：
1. 在原始的版本中，Deploy及Call的Gas根據程式複雜度(運算量)而有大幅的改變，數獨的Gas可以為單一一個if判斷式的好幾倍。但在ZoKrates的版本中，Gas不會差異那麼大，所以此方法可以使**礦工的驗證不受原本程式複雜度的影響**。
2. 但ZoKrates的版本在Deploy及Call的Gas還是**比原來的程式的Gas多了好幾倍**，甚至在[Remix](https://remix.ethereum.org)的JVM中會跑不動，因此必須上Testnet讓真正的礦工挖才能順利執行。
3. 透過調整public及private input數量的實驗發現，**public input的數量越多，Deploy及Call的Gas越大**。從程式中我們也可以發現，我們會對public的input數量做ECC的addition及multiplication，所以**private input全部被轉換成QAP的問題，但public input沒有，所以為了讓public input跟private input產生關聯，必須額外在contract上做運算**。

for (uint i = 0; i < input.length; i++)
            vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.IC[i + 1], input[i]));


### Ourchain Transaction Fee

* `debug.log`檔案中，每次generate塊都會輸出transation fee。紀錄只有一個交易的block的fees。
example:

CreateNewBlock(): total size: 1061 block weight: 4244 txs: 2 fees: 15400 sigops 416

* 若無交易發生但generate區塊時，log為：

CreateNewBlock(): total size: 292 block weight: 1168 txs: 0 fees: 0 sigops 400

* 因為`deploycontract`跟`callcontract`各為一筆交易，所以分別紀錄deploy及call。

| Transaction Fee | Deploy | Call |
| -------- | -------- | -----|
| Sudoku Checker | 54380 | 5620 |
| if a*a==b | 10940 | 5440 |
| ECC addition | 116760 | 5460 |
| ECC multiplication | 113480 | 5260 |
| ECC multiplication * 7 | 139980 | 5260 |

> 表格中的Sudoku Checker及(if axa ==b)皆為未加密的版本
> 因為實做時還缺ECC pairing的程式，因此整個zkSNARK未完整。
> 目前先紀錄原先的版本及試做ECC加法及乘法。

#### 發現：
1. Deploy時費用會隨程式大小而改變，但不確定是否用程式的bytecode計算或是contract的行數計算。
2. Call時Fee幾乎是constant，不隨著呼叫的contract的複雜度而改變，但此情況應該不太合理，程式複雜度攸關礦工需要執行的成本，因此**將來Ourchain的`callcontract`的fee應該往計算程式複雜度的方向前進**。

### zkSNARK Generation Time

* 測試環境：*MacBook Pro (13-inch, 2016, Two Thunderbolt 3 ports)
Processor: 2 GHz Intel Core i5 Memory: 8 GB 1867 MHz LPDDR3*
* 測試程式碼：[example/sudokuckecher.code](https://github.com/Zokrates/ZoKrates/blob/develop/zokrates_cli/examples/sudokuchecker.code)

| ZoKrates time | real | user | sys |
| -------- | ------- | -------- | -------- |
| Compile | ~0m0.069s | ~0m0.040s | ~0m0.020s |
| **Setup** |**~0m0.400s**|**~0m0.380s**|**~0m0.010s**|
| Witness | ~0m0.021s | ~0m0.010s | ~0m0.000s |
| Generate-proof | ~0m0.115s | ~0m0.100s | ~0m0.010s |
| export-verifier | ~0m0.010s | ~0m0.000s | ~0m0.010s |

#### 發現
1. 過程中運算最複雜的是將high level code轉換為QAP的部份，但在鏈下也只要**執行不到1秒的時間**，所以幾乎不算是實做上的overhead。