영지식 증명(zero knowledge proof) 최근 동향

• block 생성하는데 걸리는 기간을 단축하겠다.
• 빔 체인 - user compability 유지
• consensus 부분을 zk로 바꿔서 만든다.
• 증명을 만들어서 집어넣는다는게 최근 동향
• 증명만 온체인으로 보내고, 블록체인 상에서는 verification만 함
• Consensus Layer Roadmap with Vitaik’s roadmap 참고할 것.

계산 - code-based, hash-based 사용

하드웨어 가속기술

• 타원곡선에서 가속해야 하는 부분 → 지수 계산 파트에서 병목 현상이 발생…

• code-based / hash-based에서 가속하는 방법에 대한 발표임

• 속도 문제 해결 → 하드웨어 가속기 만듬(속도가 느리면? 하드웨어 가속하면 된다!)

• 해쉬 기반의 연구

  • 큰 정수(768 비트)
  • multiscalar multiplication에서 엄청 큰 시간 소모가 심함
  • NTT - 동형암호에서 많이 사용하고 있음
  • 현재 고려대 연구팀은 MSM으로 연구..
  • 하드웨어 연산 문제, 메모리 → ON-chip에는 저장 크기가 안되기 때문에 off-chip에 저장이 필요
  • 패턴 optimization 하지 않으면 memory access 하는데 문제가 생김
  • 최적화 요구
  • Multiscalar multiplicatin ← point addition/multipliccation ← modular addition/ multiplication ← addition
  • point addition을 하기 위해서 사용하기 위한 연산기반 - 모듈러연산(나머지 연산)
  • 하드웨어 구현할려면 add부터 시작하게 됨
  • 어떤 종류의 사칙연산도 덧셈으로 구현이 됨
    • 뺄셈은 보수 개념으로 더하고 sign bit 처리하면 되기 때문임

  기본연산

• 하드웨어 가속

  • 논리 설계
  • 덧셈 시 하위 자리수 부터 더해서 carry가 생기면 다음 자리수에 반영해서 연산
  • 리플캐리 adder
    • 문제점 : 가장 상위 자릿수 계산하기 위해서는 이전 자릿수 계산이 다 끝나야 함
    • 속도 엄~~~~~청 느림
    • 하드웨어 병렬성 활용 못하는 단점이 있음
    • 해결책1 : Carry-Lockhead adder :
      • 병렬 연산
      • 캐리만 먼저 계산하다
      • block으로 쪼개서, 연산이 끝나기 전에 캐리가 나올지 여부를 먼저 판단하면,
      • 블록 연산 중 병렬적 연산 가능
    • 성능 최적화하는 것 Prefix adder
    • 전력 소모 최소화 등 다른 지표들을 최적화하기 위해 성능 희생하고 trade-off 고려하여 설계하여 다양한 adder들이 등장함!
    • 곱셈 - 32비트/64비트 곱셈시 하드웨어로 구현시 여러 번의 덧셈을 통해 구현
      • 작은 수 곱셈할때는 괜찮은데, 영지식 증명에서는 몇백 비트씩 구현시 그대로 사용하면 속도도 느리고 하드웨어 사이즈도 커질 수밖에 없음
      • 해결책 : Karatsuba algorithm
        • x, y 곱할때 두개로 나눠서 곱셈을 강도를 줄이고 덧셈으로 치환함
        • 16비트씩 쪼갠 다음에 곱셈하면 16비트씩 곱셈한걸로 줄일 수 있음
        • 재귀로 반복하면 곱셈에 필요한 연산량을 줄여버릴 수 있음

• 타원곡선 가속

  • 하드웨어 구현 시 나눗셈은 비싼연산
  • 나눗셈 하기에는 숫자가 굉장히 크다면 굉장히 어려움
  • 몽고메리 알고리즘 :
    • 나눗셈 짝수일때 한 비트를 shift
    • 홀수면 N을 더해서 짝수로 만들고 shift 연산
  • 나눗셈 대신 시프트 연산과 덧셈을 이용해서 연산을 함
  • -N^-1 mod r인 경우, 재활용이 가능하게 한번만 연산해서 반복문 사용할때 사용하지 않도록 함
    • 수학과 코딩 스킬로 연산량을 줄여버릴 수 있군!
  • point addition : 타원곡선에 선을 긋고 대칭한 점과 더한다!
    • 해결책 : 좌표계 변경
      • Cartesian(데카르트) 시스템 → x,y로 특정점 표현
      • 아핀, 자코비안, extend projective, projective, affine, extended affine
      • 여러 개의 숫자로 좌표를 표현하면 ? 기본적 좌표 자체에 나눗셈을 포함하기에
      • 한번 projective로 표현하면 좌표계 변경시에만 나눗셈 하고 계산 후 최종적 결과물 데카르트 좌표계로 변환할때 나눗셈이 필요
      • 연산 과정에서 나눗셈을이 불필요
        • 문제: 드문 확률로 좌표계 변환 x
        • 0인 경우 → 0으로는 못 나눔
        • 드문 경우까지도 연산이 가능하도록 만들던가, exception case는 cpu로 보내서 처리하던가 할 수 있음
        • 2^26개의 연산을 할때 exception case는 많아야 5개 정도 → 확률적으로는 0에 가까워서 exception case 처리하기 위한 하드웨어 만드는 것보다 → 하드웨어 효율적
        • explic formulas database
      • point addition example(BLS 12-377)
        • barreto-lynn scott bls12-377
        • MSM 끝나고 데카르트 좌표계 구현 → PADD 구현 가능
  • msm 기본 구현
  • pippenger algorithm : 원래는 곱셈 우선, 덧셈 우선(벡터 두개 곱해서 구한 결과를 더한 것) 대신 버킷 단위로 쪼개서 버킷 단위를 더하고 이후 곱셈한게 연산량이 쭌다.
  • scalar를 윈도우별로 쪼갬(예: 12비트를 4비트씩 쪼갬)
  • 버킷을 만들어서, 버킷에 비트들을 넣어놓고 그 다음에 곱셈을 하는 것
  • point multiplication → 덧셈을 여러 번 반복
  • 더해놓고 곱하게 되면 간단해짐 → 곱셈을 해서 G1, G2를 구한다…
  • 시프트 연산을 통해 자릿수 보정을 함
  • 버킷에 들어가는 과정 - accumulation, 곱셈 해서 최종결과 구하기 - aggregation
  • accumulation - hardware, aggregation - cpu
  • aggregation → 데이터 dependency → 병렬화가 잘 안됨

• 고려대팀은 accumilation와 aggregation 병렬화 연산을 진행하고자 함