-
New Updates on Proximity Testing with Logarithmic Randomness
소개 이전 글에서, “Proximity Testing with Logarithmic Randomness”라는 논문을 소개했습니다. 이 논문을 읽은 당시에 제가 논문에 있었던 증명의 작은 오류를 찾아 이를 수정하는데 기여하기도 했으며, 그 내용도 이전 글에 소개되어 있습니다. 1월 이후, 해당 논문과 관련된 여러 새로운 발견이 이루어졌습니다. 이 글에서는 1월 이후 Proximity Testing에 대한 추가적인 발전에 대해서 다룹니다. 복습 이전 논문에서 다룬 핵심적인 정리는 다음과 같습니다. For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots,...
-
PS에서 C++ 상속 활용하기
C++에는 클래스가 있고, 클래스에는 상속이 있다는 사실은 대부분 알고 계실 것입니다. 상속의 개념을 Animal, Dog, Cat의 관계로 설명하는 것을 한 번쯤은 보셨을 것입니다. 하지만 실제 PS를 할 때 C++의 상속 개념을 활용하는 경우는 그닥 많지 않습니다. 그러나 상속을 잘 활용하면, PS에서도 더 편하고 깔끔하게 코드를 짤 수 있게 됩니다. 이 글에서는 PS에서 실용적으로 상속을 활용할 수 있는 몇 가지 사례를 소개합니다. 모든 원소에 특정 값 더하기 아래의 쿼리를 해결하는 문제를 생각해봅시다. 배열에 $x$ 추가하기 배열에서...
-
Polymath: Groth16 is Not The Limit
소개 ZKP의 성능을 측정하는 요소에는 여러 가지가 있습니다. Prover와 Verifier의 입장에서 생각해보면, 가장 중요한 것은 아무래도 Prover가 proof를 생성하는데 걸리는 시간 및 리소스 Verifier가 proof를 검증하는데 걸리는 시간 및 리소스 입니다. 하지만, Recursive ZKP나 최종적으로 Verifier가 위치하는 곳이 어디인지 등을 생각해보면, 시간 및 리소스만큼이나 중요한 것이 바로 Proof의 크기, 즉 proof size임을 알 수 있습니다. Proof의 크기 자체가 크면 blockchain 위에 올리는 데 비용이 커지며, 동시에 Recursive ZKP를 하는 overhead도 커지기 때문입니다. 특히, blockchain 위에...
-
Moving Least Squares Projection
Point Based Graphics Point Based Graphics는 컴퓨터 그래픽스의 한 분야로, 기존의 다각형 기반으로 형상을 모델링하는 기법인 Polygon Based Graphics와 달리 점들을 사용하여 3D 객체의 표면을 표현하는 기법입니다. 각 점은 위치 뿐만 아니라 그 지점의 색상과 텍스쳐 등 다양한 속성도 가질 수 있습니다. 여기서 객체를 표현하는데 사용된 점들의 집합을 Point Cloud라고 합니다. 이 Point Cloud가 조밀할수록 더욱 세밀한 형태를 표현할 수 있습니다. Point Based Graphics는 복잡한 형상을 기존 기법보다 더 효율적이고 자세하게 표현할 수 있다는 장점이...
-
Software Combining
Intro 지난 포스트들에서는 구체적인 자료구조 (BST, List 등)을 concurrent하게 어떻게 구현할 수 있을지를 살펴보았다. 이번에는 조금 더 일반적인 트릭인 software combining 에 대해서 알아보자. 표현이 조금 모호할 수 있으나, 이 주제의 관심사는 ‘여러 스레드가 효율적으로 하나의 shared object에 연산을 하는 방법’의 한 갈래로, 한 스레드가 여러개의 스레드의 연산을 한꺼번에 처리해주는 것에 대한 논의이다. 그렇기 때문에 software ‘combining’이라는 이름으로 불린다. 가장 일반적인 논의는 ‘임의의 sequential한 object를 concurrent하게 wrapping하는 법’인 universal construction에 대한 것이 되겠지만, 이번 포스트에서는...