Compact에서 나눗셈을 구현하는 방법

Compact은 온체인 로직을 효율적이고 안전하게 처리합니다. 나눗셈은 아직 지원되지 않지만, 벡터 뺄셈이나 오프체인 연산과 witness 검증으로 구현할 수 있습니다.

Compact 컴파일러 버전 0.22.0 기준으로, 나눗셈은 아직 사용 가능한 산술 연산에 포함되지 않습니다.

하지만 나눗셈을 구현하거나 나눗셈 결과를 검증하는 두 가지 방법이 있습니다.

The vector solution

⚠️ 경고: 이 방법은 시연 목적으로만 제시합니다. 스마트 컨트랙트에서는 witness 방법을 권장합니다.

첫 번째 방법은 벡터, 뺄셈, 그리고 fold 표현식을 사용하는 것입니다.
나눗셈을 시뮬레이션하는 모듈 예시입니다:

module DivOne {
    export struct DivResult {
        quotient: Uint<128>;
        remainder: Uint<128>;
    }
    // division by subtraction
    export pure circuit div(
        dividend: Uint<128>, 
        divisor: Uint<128>, 
        divLoop: Vector<1000, Uint<1>>
    ): DivResult {
        assert(divisor != 0, "division by zero");

        const [remainder, quotient]: [Uint<128>, Uint<128>] = fold((acc, _) => {
            const [remaining, counter] = acc;
            if (remaining < divisor) {
                return acc;
            } else {
                return [(remaining - divisor), counter + 1 as Uint<128>];
            }
        }, [dividend, 0 as Uint<128>], divLoop);

        return DivResult {
            quotient: quotient,
            remainder: remainder
        };
    }
}

DivOne 모듈은 반복 뺄셈으로 회로 내에서 나눗셈을 완전히 구현합니다.

div 회로는 피제수, 제수, 그리고 divLoop이라는 고정 길이 벡터를 입력으로 받습니다. 이 벡터는 루프 제어 구조 역할을 하며, fold 함수가 최대 1000번까지 반복할 수 있도록 합니다.

참고: divLoop은 무제한 반복을 방지하는 것이 아닙니다. Compact에서는 원래 무제한 반복이 불가능합니다.

각 반복에서 회로는 남은 피제수에서 제수를 빼고 몫을 1씩 증가시킵니다. 나머지가 제수보다 작아지면 중단합니다(반복 자체는 끝까지 진행됩니다). 0으로 나누기를 방지하기 위한 assertion이 루프 전에 포함되어 있습니다.

결과는 몫과 나머지를 모두 담은 DivResult struct로 반환됩니다.

이 접근 방식은 결정론적이고 자체 완결적이지만, 루프 길이에 제한되어 충분히 작은 몫에만 적합합니다.

The witness solution

두 번째 방법은 오프체인에서 나눗셈을 수행하고, 온체인에서 결과의 정확성을 검증하는 것입니다:

module DivTwo {
    export witness divMod(x: Uint<128>, y: Uint<128>): [Uint<128>, Uint<128>];

    export circuit checkDiv(dividend: Uint<128>, divisor: Uint<128>): Boolean {
        const [quotient, remainder] = divMod(dividend, divisor);
        assert(remainder < divisor, "remainder error");
        assert((quotient * divisor) + remainder == dividend, "division error");
        return true;
    }
}

DivTwo 모듈은 실제 나눗셈 연산을 divMod이라는 외부 witness 함수에 위임합니다.

witness는 주어진 입력에 대한 몫과 나머지를 반환하지만, 회로 자체가 직접 계산하지는 않습니다. 대신 checkDiv 회로가 두 가지 핵심 assertion으로 witness가 제공한 값을 검증합니다. 나머지가 제수보다 작은지, 그리고 몫 x 제수 + 나머지가 원래 피제수와 같은지 확인합니다.

이 방법은 반복이 없으므로 DivOne보다 효율적이며, 나눗셈을 오프체인에서 미리 계산할 수 있을 때 특히 유용합니다. 다만 외부 연산과 올바른 witness 값에 의존합니다.

두 접근 방식은 Compact에서 나눗셈 구현 시의 트레이드오프를 잘 보여줍니다. vector 방식은 연산을 통해 정확성을 보장하는 컨트랙트 내 완전한 솔루션이고, witness 방식은 외부 연산과 컨트랙트 내 검증을 결합하여 더 높은 효율을 달성합니다. 어떤 방식을 선택할지는 애플리케이션의 성능 및 신뢰 모델 요구사항에 따라 결정하세요.