=nil; Foundation을 위한 Placeholder 증명 시스템을 구축할 때, 우리는 Aztec 연구자들의 Plookup 논문 에 기반한 조회 인수를 사용합니다. 우리는 Plookup 기술을 시작점으로 삼고 복잡한 논리를 가진 큰 PLONK 회로를 작성하기 위한 몇 가지 실질적인 개선을 했습니다.
조회 인수를 통해 증명자는 소수 필드에 대한 어떤 테이블(이하 할당 테이블)이 특정 제약 조건을 만족함을 증명할 수 있습니다. 할당 테이블에서 계산된 일부 셀(조회 입력)은 할당 테이블에서 계산된 값 목록(조회 테이블)에 속합니다.
조인 앤 스플릿 알고리즘
Plookup 기술의 핵심은 정렬 알고리즘입니다. 우리는 그것을 조인 앤 스플릿 이라고 부르는데, 그것은 두 단계를 포함하기 때문입니다.
- join — 특수 재정렬 알고리즘을 사용하여 조회 테이블 열이 입력 열과 결합되어 하나의 큰 벡터로 만들어집니다.
- 분할 — 구성된 벡터가 다시 원래 크기의 부분으로 분할됩니다.
단일 조회 테이블과 단일 입력 열의 경우는 Plookup 논문에 자세히 설명되어 있습니다. 하지만 우리의 사용 사례에는 충분하지 않았습니다. 우리는 효율적으로 패킹된 조회 테이블과 임의의 행과 열에 적용되는 조회 제약 조건이 많이 필요했고, 각 (input, table) 쌍에 대해 조회 인수를 반복하고 싶지 않았습니다.
그래서, 우리는 두 개 이상의 열을 조인할 수 있도록 조인-분할 알고리즘을 수정했습니다. 이를 통해 동일한 행에 적용되더라도 여러 개의 조회 제약 조건을 사용할 수 있고, 행 대신 열을 할당 테이블에 추가하여 전체 할당 테이블 행 양보다 크기가 크더라도 큰 조회 테이블을 사용할 수 있습니다. 할당 테이블 행과 열 양 사이의 균형은 최상의 프로버 성능과 검증 비용에 대한 완벽한 균형을 찾는 데 도움이 됩니다.
선택기 열
원래 문서에는 같은 행이나 이웃 행에 배치된 값의 튜플을 조회하는 기술이 포함되어 있습니다. 이는 임의의 요인을 사용하여 열의 선형 조합을 구성합니다. 이 접근 방식을 조회 테이블과 입력 열에 대한 다항식 사용과 결합하여 선택기 열에 대한 전체 지원을 달성했습니다. 이제 회로 설계자는 정확히 어떤 행이 제약을 받고 어떤 행이 조회 테이블에 저장되도록 예약되는지 관리할 수 있습니다.
Plookup 논문은 또한 다중 조회 테이블 지원 기술을 설명합니다. 그들은 각 조회 테이블을 고유 식별자와 태그 열에 연결하여 어떤 행에 어떤 식별자가 있는 조회 테이블이 포함되어 있는지 표시하는 것을 제안합니다. 입력에 대한 태그 열은 표시된 행에 어떤 제약 조건이 적용되는지 표시하는 데 도움이 됩니다. 태그 열은 각각 조회 테이블과 입력 열에 대해 구성된 무작위 선형 조합의 일부여야 합니다. 이 접근 방식은 분명히 제한적입니다. 조회 테이블 크기의 합계는 전체 테이블 행의 양보다 작아야 합니다.
우리는 검색 테이블 식별자 사용을 우리의 선택자 열 구성 및 대형 검색 테이블 알고리즘과 결합했습니다. 이러한 수정을 통해 검색 테이블은 검색 인수 제한에 관계없이 저장되고 사용될 수 있지만 최상의 회로 설계에 따라 사용할 수 있습니다. 그것은 우리의 검색 인수를 보편적이고 유연한 도구로 만들었습니다.
수정 사항에 대한 자세한 설명은 HackMD 페이지에서 확인할 수 있습니다. 의견을 공유해 주세요!
