ゼロ知識証明を使用せずに部分証明と存在証明をやってみる

ゼロ知識証明について調べていたら、発行者が作成した証明書の一部だけを公開してプライバシーを守るとか、証明したい部分を伏せて存在を証明することができる、といった解説をよく見かけます。さらに調べていくうちに、なぜかゼロ知識証明を使わずに実現する方法について興味が湧いてきました。

もちろん複雑なことはZK-SNARKやZK-STARKの活用が必須となりますが、大きな実装難易度や計算コストも伴います。最近Symbolのコア開発者もKASANEというSTARK開発に向けて発表がありましたのでどんな仕組みになるのか楽しみですね。

コミュニティからのレポートもあるのでご紹介しておきます。

https://hackmd.io/@Radio-Radio/S1BcJ_T0A

今回はゼロ知識証明を使わずに、ゼロ知識証明の定番ユースケースをsymbol-sdkを使用して実装してみます。速習Symbol方式で実行検証できますので、お試しください。

https://github.com/TGVRock/quick_learning_symbol_v3/blob/main/02_setting.md


```js
// Symbol SDK のインポート
const bundle = await import("https://www.unpkg.com/symbol-sdk@3.2.2/dist/bundle.web.js");
const core = bundle.core;
const sym  = bundle.symbol;

// SHA3-256 ハッシュ関数
const sha3_256 = (await import('https://cdn.skypack.dev/@noble/hashes/sha3')).sha3_256;

async function sha3_256Hash(data) {
    const encoder = new TextEncoder();
    const dataBuffer = encoder.encode(data);
    return sha3_256(dataBuffer);
}

// Uint8Array を16進数文字列に変換
function toHexString(byteArray) {
    return Array.from(byteArray)
        .map((byte) => byte.toString(16).padStart(2, '0'))
        .join('');
}

// 16進数文字列をUint8Arrayに変換
function fromHexString(hexString) {
    const matches = hexString.match(/.{1,2}/g);
    return new Uint8Array(matches.map(byte => parseInt(byte, 16)));
}

// Uint8ArrayをBase64にエンコード
function toBase64(uint8Array) {
    return window.btoa(String.fromCharCode.apply(null, uint8Array));
}

// Base64をUint8Arrayにデコード
function fromBase64(base64String) {
    return Uint8Array.from(window.atob(base64String), c => c.charCodeAt(0));
}

// Merkleツリーを構築する関数
async function buildMerkleTree(leaves) {
    let tree = [leaves];
    while (tree[tree.length - 1].length > 1) {
        const currentLevel = tree[tree.length - 1];
        const nextLevel = [];
        for (let i = 0; i < currentLevel.length; i += 2) {
            if (i + 1 < currentLevel.length) {
                const combined = new Uint8Array([...currentLevel[i], ...currentLevel[i + 1]]);
                nextLevel.push(sha3_256(combined));
            } else {
                nextLevel.push(currentLevel[i]); // 奇数の場合、そのまま持ち上げる
            }
        }
        tree.push(nextLevel);
    }
    return tree;
}

// Merkleプルーフを生成する関数
function getMerkleProof(tree, index) {
    let proof = [];
    let currentIndex = index;
    for (let level = 0; level < tree.length - 1; level++) {
        const isLeftNode = currentIndex % 2 === 0;
        const siblingIndex = isLeftNode ? currentIndex + 1 : currentIndex - 1;

        if (siblingIndex < tree[level].length) {
            proof.push({
                direction: isLeftNode ? 'right' : 'left',
                hash: tree[level][siblingIndex]
            });
        }

        currentIndex = Math.floor(currentIndex / 2);
    }
    return proof;
}

// Merkleルートを計算する関数
async function calculateMerkleRoot(leafHash, proof) {
    let hash = leafHash;

    for (let i = 0; i < proof.length; i++) {
        const siblingHash = proof[i].hash;
        const direction = proof[i].direction;

        if (direction === 'left') {
            hash = sha3_256(new Uint8Array([...siblingHash, ...hash]));
        } else {
            hash = sha3_256(new Uint8Array([...hash, ...siblingHash]));
        }
    }
    return hash;
}

// 1. Issuerが証明書を発行
async function issueCertificate() {
    // キーペアの生成
    const priKey = core.PrivateKey.random();
    const keyPair = new sym.KeyPair(priKey);
    const issuerPublicKey = keyPair.publicKey;

    // 各属性の値
    const attributes = {
        name: "Alice",
        gender: "male",
        birthdate: "1990-01-01",
        address: "1234 Elm Street"
    };

    const attributeKeys = Object.keys(attributes);
    const attributeValues = Object.values(attributes);
    const leaves = await Promise.all(attributeValues.map((value) => sha3_256Hash(value)));

    // Merkleツリーを構築
    const merkleTree = await buildMerkleTree(leaves);
    const merkleRoot = merkleTree[merkleTree.length - 1][0];

    // Merkleルートを署名
    const merkleRootHex = toHexString(merkleRoot);
    const merkleRootBytes = fromHexString(merkleRootHex);
    const signature = keyPair.sign(merkleRootBytes);

    const certificate = {
        attributes: attributeKeys,
        merkleRoot: merkleRootHex,
        signature: toBase64(signature.bytes)
    };

    return { certificate, attributes, merkleTree, issuerPublicKey };
}

// 2. Holderが部分証明書を作成（複数の属性）
async function createPartialProofs(certificate, attributes, merkleTree, attributeNames) {
    const proofs = [];

    for (const attributeName of attributeNames) {
        const index = certificate.attributes.indexOf(attributeName);
        if (index === -1) throw new Error(`属性が存在しません: ${attributeName}`);

        const attributeValue = attributes[attributeName];
        const attributeHash = await sha3_256Hash(attributeValue);

        const merkleProof = getMerkleProof(merkleTree, index);

        proofs.push({
            attributeName,
            attributeValue,
            merkleProof
        });
    }

    return {
        proofs,
        signature: certificate.signature,
        merkleRoot: certificate.merkleRoot
    };
}

// 3. Verifierが部分証明書を検証
async function verifyPartialProofs(partialCertificate, issuerPublicKey) {
    const merkleRootHex = partialCertificate.merkleRoot;
    const merkleRootBytes = fromHexString(merkleRootHex);

    // Issuerの署名を検証
    const verifier = new sym.Verifier(new core.PublicKey(issuerPublicKey.bytes));
    const signature = new core.Signature(fromBase64(partialCertificate.signature));

    const isValidSignature = verifier.verify(merkleRootBytes, signature);
    if (!isValidSignature) {
        console.log("Issuerの署名が無効です");
        return false;
    }

    // 各属性の検証
    for (const proofData of partialCertificate.proofs) {
        const attributeHash = await sha3_256Hash(proofData.attributeValue);

        const calculatedMerkleRoot = await calculateMerkleRoot(attributeHash, proofData.merkleProof);
        const calculatedMerkleRootHex = toHexString(calculatedMerkleRoot);

        if (calculatedMerkleRootHex !== merkleRootHex) {
            console.log(`属性 ${proofData.attributeName} のMerkleルートが一致しません`);
            return false;
        }
    }

    console.log("複数属性の部分証明書が有効です");
    return true;
}

// 4. Holderが属性の存在証明を作成（値を明かさない）
async function createExistenceProof(certificate, attributes, merkleTree, attributeName) {
    const index = certificate.attributes.indexOf(attributeName);
    if (index === -1) throw new Error(`属性が存在しません: ${attributeName}`);

    const attributeHash = await sha3_256Hash(attributes[attributeName]);
    const merkleProof = getMerkleProof(merkleTree, index);

    return {
        attributeName,
        attributeHash: toHexString(attributeHash), // ハッシュ値のみ提供
        merkleProof,
        signature: certificate.signature,
        merkleRoot: certificate.merkleRoot
    };
}

// 5. Verifierが属性の存在証明を検証 
async function verifyExistenceProof(existenceProof, issuerPublicKey) {
    const merkleRootHex = existenceProof.merkleRoot;
    const merkleRootBytes = fromHexString(merkleRootHex);

    // Issuerの署名を検証
    const verifier = new sym.Verifier(new core.PublicKey(issuerPublicKey.bytes));
    const signature = new core.Signature(fromBase64(existenceProof.signature));

    const isValidSignature = verifier.verify(merkleRootBytes, signature);
    if (!isValidSignature) {
        console.log("Issuerの署名が無効です");
        return false;
    }

    // 属性のハッシュを取得
    const attributeHash = fromHexString(existenceProof.attributeHash);

    // Merkleルートを計算
    const calculatedMerkleRoot = await calculateMerkleRoot(attributeHash, existenceProof.merkleProof);
    const calculatedMerkleRootHex = toHexString(calculatedMerkleRoot);

    if (calculatedMerkleRootHex !== merkleRootHex) {
        console.log(`属性 ${existenceProof.attributeName} のMerkleルートが一致しません`);
        return false;
    }

    console.log(`属性 ${existenceProof.attributeName} の存在証明が有効です`);
    return true;
}

// メイン処理
async function main() {
    const { certificate, attributes, merkleTree, issuerPublicKey } = await issueCertificate();

    // Holderが複数の属性の部分証明を作成
    const attributeNamesToProve = ["gender", "birthdate"];
    const partialCertificate = await createPartialProofs(certificate, attributes, merkleTree, attributeNamesToProve);

    // Verifierが部分証明を検証
    const isValidPartial = await verifyPartialProofs(partialCertificate, issuerPublicKey);
    if (isValidPartial) {
        console.log("VerifierはHolderの属性を検証しました:", attributeNamesToProve.join(", "));
    } else {
        console.log("部分証明書の検証に失敗しました");
    }

    // Holderが属性の存在証明を作成（値を明かさない）
    const attributeNameToProve = "address";
    const existenceProof = await createExistenceProof(certificate, attributes, merkleTree, attributeNameToProve);

    // Verifierが属性の存在証明を検証
    const isValidExistence = await verifyExistenceProof(existenceProof, issuerPublicKey);
    if (isValidExistence) {
        console.log(`VerifierはHolderの属性 ${attributeNameToProve} の存在を確認しました`);
    } else {
        console.log("属性の存在証明の検証に失敗しました");
    }
}

main();

```