Home Reference Source Test

test/specs/generic/utils/merkle/MerkleProof.spec.js

describe('MerkleProof', () => {
    const missing = [
        BufferUtils.fromAscii('0'),
        BufferUtils.fromAscii('4'),
        BufferUtils.fromAscii('6')
    ];
    const values = [
        BufferUtils.fromAscii('1'),
        BufferUtils.fromAscii('2'),
        BufferUtils.fromAscii('3'),
        BufferUtils.fromAscii('5'),
        BufferUtils.fromAscii('7'),
        BufferUtils.fromAscii('8'),
        BufferUtils.fromAscii('9')
    ];

    it('correctly computes an empty proof', () => {
        const root = MerkleTree.computeRoot([]);
        let proof = MerkleProof.compute([], [values[0]]);
        expect(proof.nodes.length).toBe(1);

        let threw = false;
        let proofRoot = null;
        try {
            proofRoot = proof.computeRoot([values[0]]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);

        proof = MerkleProof.compute([], []);
        expect(proof.nodes.length).toBe(1);
        expect(root.equals(proof.computeRoot([]))).toBe(true);
    });

    it('correctly computes a simple proof', () => {
        const v4 = values.slice(0, 4);
        /*
         * (X) should be the nodes included in the proof.
         * *X* marks the values to be proven.
         *            h6
         *         /      \
         *      h4        (h5)
         *     / \         / \
         *  (h0) h1      h2  h3
         *   |    |      |    |
         *  v0  *v1*    v2   v3
         */
        const root = MerkleTree.computeRoot(v4);
        let proof = MerkleProof.compute(v4, [values[1]]);
        expect(proof.nodes.length).toBe(2);
        expect(root.equals(proof.computeRoot([values[1]]))).toBe(true);

        proof = MerkleProof.compute(v4, []);
        expect(proof.nodes.length).toBe(1);
        expect(root.equals(proof.computeRoot([]))).toBe(true);
    });

    it('correctly computes more complex proofs', () => {
        const v4 = values.slice(0, 4);
        let root = MerkleTree.computeRoot(v4);
        /*
         *            h6
         *         /      \
         *      h4         h5
         *     / \         / \
         *  (h0) h1      h2 (h3)
         *   |    |      |    |
         *  v0  *v1*   *v2*  v3
         */
        let proof = MerkleProof.compute(v4, [values[1], values[2]]);
        expect(proof.nodes.length).toBe(2, 'scenario 1');
        expect(root.equals(proof.computeRoot([values[1], values[2]]))).toBe(true, 'scenario 1');

        /*
         *            h6
         *         /      \
         *      h4        (h5)
         *     / \         / \
         *   h0  h1      h2  h3
         *   |    |      |    |
         * *v0* *v1*    v2   v3
         */
        proof = MerkleProof.compute(v4, [values[0], values[1]]);
        expect(proof.nodes.length).toBe(1, 'scenario 2');
        expect(root.equals(proof.computeRoot([values[0], values[1]]))).toBe(true, 'scenario 2');

        /*
         *            h4
         *         /      \
         *      h3        (h2)
         *     / \          |
         *   h0  h1        v2
         *   |    |
         * *v0* *v1*
         */
        const v3 = values.slice(0, 3);
        root = MerkleTree.computeRoot(v3);
        proof = MerkleProof.compute(v3, [values[0], values[1]]);
        expect(proof.nodes.length).toBe(1, 'scenario 3');
        expect(root.equals(proof.computeRoot([values[0], values[1]]))).toBe(true, 'scenario 3');

        /*
         *            h4
         *         /      \
         *      h3         h2
         *     / \          |
         *  (h0) h1       *v2*
         *   |    |
         *  v0  *v1*
         */
        proof = MerkleProof.compute(v3, [values[1], values[2]]);
        expect(proof.nodes.length).toBe(1, 'scenario 4');
        expect(root.equals(proof.computeRoot([values[1], values[2]]))).toBe(true, 'scenario 4');

        /*
         *                   h6
         *            /               \
         *         (h4)                h5
         *       /      \            /   \
         *     h0        h1       (h2)    h3
         *   /   \     /   \     /   \    |
         *  v0   v1   v2   v3   v4   v5  *v6*
         */
        const v7 = values;
        root = MerkleTree.computeRoot(v7);
        proof = MerkleProof.compute(v7, [values[6]]);
        const test = proof.computeRoot([values[6]]);
        expect(proof.nodes.length).toBe(2, 'scenario 5');
        expect(root.equals(test)).toBe(true, 'scenario 5');

        /*
         *                   h6
         *            /               \
         *          h4                 h5
         *       /      \            /   \
         *    (h0)       h1       (h2)    h3
         *   /   \     /   \     /   \    |
         *  v0   v1  *v2* (v3)  v4   v5  *v6*
         */
        proof = MerkleProof.compute(v7, [values[2], values[6]]);
        expect(proof.nodes.length).toBe(3, 'scenario 6');
        expect(root.equals(proof.computeRoot([values[2], values[6]]))).toBe(true, 'scenario 6');

        /*
         *                   h6
         *            /               \
         *          h4                 h5
         *       /      \            /   \
         *    (h0)       h1        h2    (h3)
         *   /   \     /   \     /   \    |
         *  v0   v1  (v2) *v3* *v4* (v5)  v6
         */
        proof = MerkleProof.compute(v7, [values[3], values[4]]);
        expect(proof.nodes.length).toBe(4, 'scenario 7');
        expect(root.equals(proof.computeRoot([values[3], values[4]]))).toBe(true, 'scenario 7');
    });

    it('correctly computes absence proofs', () => {
        const v4 = values.slice(0, 4);
        let root = MerkleTree.computeRoot(v4);
        /*
         *            h6
         *         /      \
         *      h4         h5
         *     / \         / \
         *   h0 (h1)     h2 (h3)
         *   |    |      |    |
         * *v0*  v1    *v2*  v3
         */
        let proof = MerkleProof.computeWithAbsence(v4, [missing[0], values[2]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(2, 'scenario 1');
        expect(root.equals(proof.computeRoot([values[0], values[2]]))).toBe(true, 'scenario 1');

        /*
         *            h6
         *         /      \
         *      h4         h5
         *     / \         / \
         *   h0 (h1)    (h2) h3
         *   |    |      |    |
         * *v0*  v1     v2  *v3*
         */
        proof = MerkleProof.computeWithAbsence(v4, [missing[0], values[4]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(2, 'scenario 2');
        expect(root.equals(proof.computeRoot([values[0], values[3]]))).toBe(true, 'scenario 2');

        /*
         *            h4
         *         /      \
         *     (h3)        h2
         *     / \          |
         *   h0  h1       *v2*
         *   |    |
         *  v0   v1
         */
        const v3 = values.slice(0, 3);
        root = MerkleTree.computeRoot(v3);
        proof = MerkleProof.computeWithAbsence(v3, [values[4]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(1, 'scenario 3');
        expect(root.equals(proof.computeRoot([values[2]]))).toBe(true, 'scenario 3');

        /*
         *                   h6
         *            /               \
         *          h4                (h5)
         *       /      \            /   \
         *    (h0)       h1        h2     h3
         *   /   \     /   \     /   \    |
         *  v0   v1  *v2* *v3*  v4   v5   v6
         */
        const v7 = values;
        root = MerkleTree.computeRoot(v7);
        proof = MerkleProof.computeWithAbsence(v7, [missing[1]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(2, 'scenario 4');
        expect(root.equals(proof.computeRoot([values[2], values[3]]))).toBe(true, 'scenario 4');

        /*
         *                   h6
         *            /               \
         *          h4                 h5
         *       /      \            /   \
         *    (h0)       h1        h2    (h3)
         *   /   \     /   \     /   \    |
         *  v0   v1  (v2) *v3* *v4* (v5)  v6
         */
        root = MerkleTree.computeRoot(v7);
        proof = MerkleProof.computeWithAbsence(v7, [missing[2]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(4, 'scenario 5');
        expect(root.equals(proof.computeRoot([values[3], values[4]]))).toBe(true, 'scenario 5');

        /*
         *                   h6
         *            /               \
         *          h4                 h5
         *       /      \            /   \
         *     h0        h1        h2    (h3)
         *   /   \     /   \     /   \    |
         * *v0* (v1) *v2* *v3* *v4* (v5)  v6
         */
        proof = MerkleProof.computeWithAbsence(v7, [values[0], missing[1], missing[2]], BufferUtils.compare);
        expect(proof.nodes.length).toBe(3, 'scenario 6');
        expect(root.equals(proof.computeRoot([values[0], values[2], values[3], values[4]]))).toBe(true, 'scenario 6');
    });

    it('correctly serializes and unserializes proof', () => {
        const proof = MerkleProof.compute(values, [values[2], values[6]]);
        const serialization = proof.serialize();
        expect(serialization.byteLength).toBe(proof.serializedSize);
        const proof2 = MerkleProof.unserialize(serialization);
        expect(proof.equals(proof)).toBe(true);
        expect(proof.equals(proof2)).toBe(true);
    });

    it('correctly discards invalid proofs', () => {
        const v4 = values.slice(0, 4);
        /*
         * (X) should be the nodes included in the proof.
         * *X* marks the values to be proven.
         *            h6
         *         /      \
         *      h4        (h5)
         *     / \         / \
         *  (h0) h1      h2  h3
         *   |    |      |    |
         *  v0  *v1*    v2   v3
         */
        const root = MerkleTree.computeRoot(v4);
        let proof = MerkleProof.compute(v4, [values[1]]);

        expect(root.equals(proof.computeRoot([values[0]]))).toBe(false);

        let threw = false;
        let proofRoot = null;
        try {
            proof.computeRoot([]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);

        proof = new MerkleProof(proof.nodes, [MerkleProof.Operation.HASH]);
        threw = false;
        try {
            proofRoot = proof.computeRoot([values[1]]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);

        proof = new MerkleProof(proof.nodes, [MerkleProof.Operation.CONSUME_PROOF, MerkleProof.Operation.CONSUME_PROOF, MerkleProof.Operation.CONSUME_PROOF]);
        threw = false;
        try {
            proofRoot = proof.computeRoot([values[1]]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);

        proof = new MerkleProof(proof.nodes, [MerkleProof.Operation.CONSUME_INPUT, MerkleProof.Operation.CONSUME_INPUT]);
        threw = false;
        try {
            proofRoot = proof.computeRoot([values[1]]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);

        proof = new MerkleProof(proof.nodes, [4]);
        threw = false;
        try {
            proofRoot = proof.computeRoot([values[1]]);
        } catch (e) {
            threw = true;
        }
        expect(threw).toBe(true);
        expect(root.equals(proofRoot)).toBe(false);
    });
});