슈노르 서명 알고리즘으로의 비트코인 알고리즘의 진화는 진보인가? |

抗量子ABC薄荷社区

特邀专栏作者

2021-01-18 01:30

이 기사는 약 6490자로, 전체를 읽는 데 약 10분이 소요됩니다

암호화의 관점에서 Schnorr 서명을 사용하는 것은"대담하고 경솔한" 접근 방식은 "장기 보안"이라는 첫 번째 본질에서 벗어납니다.

AI 요약

펼치기

암호화의 관점에서 Schnorr 서명을 사용하는 것은"대담하고 경솔한" 접근 방식은 "장기 보안"이라는 첫 번째 본질에서 벗어납니다.

역사의 수레바퀴는 앞으로 나아가고 있으며 기술의 발전은 결코 멈추지 않았습니다.이정표인 비트코인 프로토콜이 기술 업그레이드를 시작했습니다. 프로토콜의 기술 업그레이드인 Schnorr Signature(Schnorr Signature) 및 Taproot(Taproot of the tree)가 Bitcoin Core 0.21.0 버전에 통합되었습니다.

비트코인의 미래는 그 어느 때보다 밝아 보이며 이제 용량뿐만 아니라 기능 면에서도 다른 모든 블록체인을 능가할 수 있는 기회가 생겼습니다.

비트코인 ECDSA 타원곡선 서명 알고리즘을 사용했을 때 다중서명 트랜잭션 검증 과정이 매우 번거로웠는데 이제는 트랜잭션 내의 모든 서명과 공개키를 하나의 서명과 공개키로 결합하는 것이 가능해졌습니다. 추적할 수 없고 간단하고 빠릅니까?

사실 이보다 앞서 Satoshi Nakamoto가 Bitcoin 프로토콜을 설계할 때 서명 알고리즘의 서명 길이, 오픈 소스인지, 특허를 보유하고 있는지, 오랫동안 보안 검증을 통과했는지 등 다양한 조건을 고려해야 했습니다. 충분한 시간과 성능. 당시에는 위의 조건을 충족할 수 있는 ECDSA 디지털 서명 알고리즘뿐만 아니라 모든 면에서 ECDSA 못지않은 디지털 서명 알고리즘인 Schnorr Signature도 있었습니다. 그러나 2008년 이전에는 특허 보호 상태였기 때문에 Satoshi Nakamoto가 비트코인 프로토콜을 설계할 때 이 서명 알고리즘을 사용하지 않고 최종적으로 ECDSA(Elliptic Curve Digital Signature Algorithm)를 선택한 이유일 수 있습니다. 곡선 secp256k1은 의 제안으로 선택되었습니다.

10년 후인 2018년 7월, 비트코인 개발자 Pieter Wuille는 bip-schnorr를 작성하고 비트코인의 서명 알고리즘을 schnorr로 변경할 것을 제안했습니다. Schnorr와 ECDSA는 모두 secp236k1 곡선을 이용한 타원 곡선 암호화 알고리즘이지만 암호화 특성상 Schnorr Signature의 장점으로 인해 거의 동일한 보안을 기반으로 다중 서명 트랜잭션을 구성하는 것이 더 편리합니다.

Bitcoin에서 사용되는 Schnorr는 ECDSA에 비해 몇 가지 추가적인 중요한 이점이 있습니다.

더 안전함: 랜덤 오라클 모델에서 Schnorr 서명의 보안성을 증명하는 것은 쉽지만 ECDSA에 대한 그러한 증명은 없습니다.
가단성 문제 없음: ECDSA 서명은 가단성이 있어 제3자가 개인 키를 몰라도 기존 서명을 직접 수정할 수 있으며 이 트랜잭션에 대해 서명을 계속 유효하게 유지할 수 있습니다. 전통적인 트랜잭션 대신 segwit 트랜잭션이 사용된 경우 SegWit이 활성화될 때까지 수정되지 않은 Bitcoin에 대한 가단성 공격이 항상 있었습니다. BIP62 및 BIP66은 이에 대해 자세히 설명합니다.
선형: Schnorr 서명 알고리즘은 선형입니다! 이 기능을 기반으로 보다 효율적이고 프라이빗한 블록체인 시스템을 구축할 수 있습니다. Schnorr 서명을 사용하는 당사자는 해당 키의 서명된 집계를 생성할 수 있습니다. 예를 들어 서명에 N개의 공개 키를 사용하고 ECDSA를 사용하면 N개의 서명이 있고 검증도 N번 수행해야 합니다. Schnorr를 사용하면 선형 특성으로 인해 서명 중첩이 가능하며 최종 중첩 서명만 유지됩니다. 예를 들어, 동일한 트랜잭션의 입력 수에 관계없이 하나의 서명으로 중첩될 수 있으며 한 번의 검증으로 충분합니다.

Schnorr 서명 알고리즘은 성능, 보안, 볼륨, 확장성 등 거의 모든 측면에서 Bitcoin의 기존 서명 알고리즘 ECDSA보다 우수하며 Schnorr Sig는 ECDSA와 동일한 타원 곡선을 사용할 수 있습니다: secp256k1 곡선, 업그레이드된 매우 작은 변화.

물론 Bitcoin 프로토콜의 서명 알고리즘 외에도 Taproot 스크립팅 언어도 Bitcoin을 사용하는 방법을 정의하도록 설계되었습니다. 비트코인 다중 서명 주소는 "다중 서명" ID를 공개할 필요가 없으며 많은 다중 서명 시나리오(온체인 트랜잭션에는 집계된 공개 키와 서명만 필요함)를 지원하여 트랜잭션 바이트, 특히 고주파 작업이 필요한 주소의 경우 체인에서 트랜잭션 수수료를 줄이면 많은 비용을 절약할 수 있습니다.

다음은 보다 일반적인 질문과 답변입니다.

Q&A

Q: m/n 다중 서명에 Schnorr 서명을 사용할 수 있습니까?

A: 물론 가능합니다. Multisig는 n개 서명의 m 패턴일 뿐입니다. 서명 알고리즘에 관계없이.

Q: Schnorr의 그룹 서명 기능은 m of n 서명을 만들거나 시뮬레이션할 수 있습니까?

답: 할 수 없습니다. 그룹에 N개의 공개 키가 있는 경우 해당하는 N개의 서명이 있어야 하며 모두 필수 불가결합니다. 모든 사람이 서명을 생성하면 모두 해시 함수에서 그룹 공개 키 P를 대체합니다.

Q: 서명 메커니즘의 보안을 어떻게 측정합니까?

A: 주로 다음 두 가지에 따라 달라집니다. 1. 서명 알고리즘 자체 2. 타원 곡선. 현재 Schnorr와 ECDSA는 모두 동일한 수준인 secp256k1 곡선을 사용합니다. 서명 알고리즘 자체의 보안과 관련하여 Schnorr는 현재 ECDSA보다 우수한 보안 인증서를 보유하고 있습니다.

슈노르 서명 알고리즘의 BCH 시범 구현

2019년 5월 16일에 BCH는 이미 하드포크 업그레이드를 시작했습니다. 이번 업그레이드의 주요 내용은 슈노르 시그니처 업그레이드에서 가장 기대되는 기능인 슈노르 시그니처 알고리즘과 분리위트니스 복구이며, 분리위트니스 복구 원리는 분리위트니스 주소로 잘못 전송된 BCH를 복구하는 기술이다.

개발자 Mark Lundeberg 사용자는 Schnorr 서명 사용을 시작하기 위해 새 주소를 생성할 필요가 없습니다. 이 업그레이드로 BCH에 가져온 이점은 다음과 같습니다.

1. 서명 데이터의 유효성 향상: 서명이 64바이트 데이터이므로 일반적인 70바이트와 비교하여 트랜잭션은 바이트의 4%를 줄일 수 있습니다 서명 데이터의 유효성(Schnorr 서명은 블록체인 저장 공간을 줄입니다. BCH 네트워크를 더 빠르고 효율적으로 만드는 최소 25%의 대역폭). 그리고 업그레이드 후 Schnorr 서명은 BCH에 일반 결제 채널을 숨길 수 있는 기능을 제공합니다.
2. 개인 정보 보호 개선: 업그레이드 전에 많은 사용자가 개인 정보 보호를 개선하기 위해 의도적으로 여러 서명을 사용하여 트랜잭션을 전송하고 Schnorr 서명은 모든 사용자 서명을 다른 서명과 동일하게 보이게 합니다.이 구조는 거래 개인 정보의 성별을 크게 증가시킵니다. Schnorr가 제공하는 속성과 BCH 개발자 및 지갑과 같은 인프라 제공자가 추가한 일부 확장 기능은 개인 정보 보호 및 확장성을 더욱 향상시킬 것입니다.
3. 스팸 거래 공격에 맞서 싸우기: 과거에 스팸 거래 공격이 있었는데, 공격자들은 가능한 한 많은 거래 공간을 통해 비트코인을 정체시키려 합니다.그들의 방법 중 하나는 여러 소스에서 거래를 자주 전송하여 이 거래가 발생하도록 하는 것입니다. 트랜잭션에는 많은 공간을 차지하는 수십 개의 서명이 포함됩니다. 이것이 ECDSA 서명이 남긴 숨겨진 위험입니다. Schnorr는 이러한 스팸 공격을 피할 수 있습니다. 각 트랜잭션에 하나의 서명만 있으면 블록이 더 많은 트랜잭션을 수용할 수 있고 스패머가 공격을 생성하려면 더 많은 트랜잭션을 보내야 하고 더 많은 사람과 경쟁해야 하므로 공격 비용이 상대적으로 높아집니다. 서명이 차지하는 공간은 일반적으로 트랜잭션의 가장 큰 부분이므로 공격자는 이점이 없습니다.

물론 좋은 면만 볼 수는 없고 모든 것이 부족할 것이고 극단도 반전될 것이다. 특히, 양자컴퓨터의 발전은 일부 비전 있는 사람들이 가능한 한 빨리 해결책을 찾도록 촉발시켰는데, 일부 알고리즘에 대한 양자컴퓨터의 공격에 대처하기 위해 NIST는 2017년 양자 이후 암호 표준화 프로세스를 시작했습니다. -포스트양자암호화재단이 지원하는 반양자 알고리즘 중 하나인 양자서명 방식 추진, 서명 길이가 가장 짧은 서명 반양자 서명 방식-레인보우 서명이 가장 유망하다.

2017년 8월 Jin Liu와 수학자 Jintai Ding 교수는 ABCMint 설립을 준비하고 스위스 취리히 인근 Encryption Valley에 등록했습니다. 디지털 통화 ABC의 기본 서명은 무지개 서명 Rainbow입니다.그들의 비전은 전 세계적으로 반 양자 컴퓨터 크래킹 알고리즘의 연구 및 적용을 지원하는 것입니다.이 연구에는 전 세계 알고리즘의 발견, 크래킹 및 개선에서 수학자를 지원하는 것이 포함됩니다. .알고리즘은 주류 디지털 암호화폐에 적용됩니다.

그들은 ECDSA에서 Schnorr 서명으로 Schnorr 서명을 사용하는 Bitcoin의 제안 BIP340이 Bitcoin의 주요 회귀라고 믿습니다. 우리는 컴퓨터 보안 전문가가 제안하는 알고리즘 선택 및 개선에 대해 낙관적이지 않습니다.수학자가 제안하는 알고리즘 선택 및 개선을 선호합니다.Schnorr 서명에는 큰 문제가 있으며 장기간 테스트를 위해 Litecoin 등에 사용되어야 합니다. 달리다.

대담하고 경솔한" 접근 방식은 "장기 보안"이라는 첫 번째 본질에서 벗어납니다.

암호화의 관점에서 Schnorr 서명을 사용하는 것은"대담하고 경솔한" 접근 방식은 "장기 보안"이라는 첫 번째 본질에서 벗어납니다.

암호화의 관점에서 Schnorr 서명은 주로 다중 서명을 위한 것이며 다중 서명에 적합한 시나리오는 다음과 같아야 합니다. 또는 샤이엔 산 핵무기 기지와 같은 게이트. 탈중앙화 시나리오나 비트코인 전송과 같은 시나리오가 되어서는 안 됩니다.

간단히 말해서: 탈중앙화 자체는 다중 서명에서 벗어납니다.

다음은 몇 가지 간단한 알고리즘입니다.

1 타원 곡선 디지털 서명 알고리즘(ECDSA)

Elliptic Curve Digital Signature Algorithm(ECDSA, Elliptic Curve Digital Signature Algorithm)은 ECC(Elliptic Curve Cryptography)를 사용한 디지털 서명 알고리즘(DSA)의 시뮬레이션입니다. (ECC(Elliptic Curve Cryptography)는 1985년 Neal Koblitz와 Victor Miller가 발명했습니다.) ECDSA는 1992년 Scott과 Vanstone이 디지털 서명 표준(DSS)에 대한 NIST의 요청에 따라 처음 제안했습니다.

비트코인은 현재 ECDSA 타원 곡선 디지털 서명 알고리즘을 사용합니다. 메시지 m에 서명하려면 메시지를 해시하고 이 해시를 숫자로 처리해야 합니다: z = 해시(m). 또한 무작위 또는 무작위 조회 번호 k가 필요합니다. 우리는 난수 생성기를 신뢰하는 것을 좋아하지 않기 때문에(너무 많은 버그, 잘못된 RGN과 관련된 많은 버그가 있음) 일반적으로 RFC6979를 사용하고 서명하려는 비밀과 메시지를 기반으로 결정론적 K 값을 계산합니다.

개인 키 pk를 사용하여 두 개의 숫자로 구성된 메시지 m에 대한 서명을 생성할 수 있습니다. r(임의점의 x 좌표 R = k×G) 및 s = (z+r⋅pk)/k. 그런 다음 공개 키 P = pk×G를 사용하여 점 (z/s)×G+(r/s)×P의 x 좌표가 r과 같은지 확인하여 누구나 서명을 확인할 수 있습니다.

서명 검증에는 반전(1/s) 및 2점 곱셈이 포함되며 이러한 작업은 계산 비용이 많이 듭니다. 비트코인에서는 모든 노드가 모든 트랜잭션을 확인해야 합니다. 즉, 트랜잭션을 브로드캐스트하면 수천 대의 컴퓨터가 서명을 확인해야 합니다. 서명 프로세스가 더 어려워지더라도 확인 프로세스를 단순화하면 매우 유용할 것입니다.

둘째, 각 노드는 각 서명을 개별적으로 확인해야 합니다. m-of-n 다중 서명 트랜잭션 노드인 경우 동일한 서명을 여러 번 확인해야 할 수 있습니다. 예를 들어, 7-of-11 다중서명 입력이 있는 트랜잭션에는 7개의 서명이 포함되며 네트워크의 모든 노드에 대해 7-11개의 서명 확인이 필요합니다. 또한 이러한 트랜잭션은 많은 공간을 차지하며 많은 비용을 지불해야 합니다.

슈노르 서명

Schnorr 서명 알고리즘은 독일의 수학자이자 암호학자인 Claus Schnorr가 제안했습니다. 그리고 1990년에 특허를 신청한 미국 특허 4,995,082호는 2008년 2월에 만료되었습니다. 알고리즘은 현재 무료로 사용할 수 있습니다.

Schnorr 서명은 약간 다르게 생성되며 두 개의 스칼라(r, s) 대신 점 R과 스칼라 s를 사용합니다. ECDSA와 마찬가지로 R은 타원 곡선의 임의의 점입니다(R=K×G). 서명의 두 번째 부분은 약간 다르게 계산됩니다.

s = k + hash(P,R,m) ⋅ pk 여기에서 pk는 개인 키이고 P = pk×G는 공개 키이고 m은 메시지입니다. 그런 다음 이 서명은 s×G = R + 해시(P,R,m)×P를 확인하여 확인할 수 있습니다.

이 방정식은 선형이므로 방정식은 서로 더하고 뺄 수 있으며 여전히 유효하며 Schnorr 서명에 대한 몇 가지 큰 이점을 제공합니다.

3 Schnorr 서명의 일괄 검증

비트코인 블록체인의 블록을 확인하려면 블록의 모든 서명이 유효한지 확인해야 합니다.

ECDSA 서명 알고리즘의 경우 각 서명을 개별적으로 확인해야 합니다. 즉, 블록에 1000개의 서명이 있는 경우 총 약 3000개의 무거운 계산 작업에 대해 1000개의 반전과 2000개의 점 곱셈을 계산해야 합니다.

그리고 Schnorr 서명을 사용하여 모든 서명 확인 방정식을 합산하여 일부 컴퓨팅 성능을 절약할 수 있습니다. 1000개의 서명이 있는 블록의 경우 다음을 확인해야 합니다.

(s1+s2+…+s1000)×G=(R1+…+R1000)+(hash(P1,R1,m1)×P1+hash(P2,R2,m2)×P2+…+hash(P1000,R1000,m1000)×P1000)

여기에는 많은 추가 기능(컴퓨팅 성능이 거의 무료임)과 1001포인트 곱셈이 있습니다. 각 서명에 대해 하나의 무거운 계산을 계산해야 합니다.

4 Schnorr 서명을 위한 주요 집계

우리는 비트코인을 안전하게 유지하고 싶기 때문에 비트코인을 제어하기 위해 적어도 2개의 다른 개인 키를 사용하고 싶을 것입니다. 예를 들어, 하나는 노트북이나 휴대폰에, 다른 하나는 하드웨어 지갑/콜드 월렛에 있습니다. 따라서 그 중 하나가 손상되더라도 여전히 비트코인을 제어할 수 있습니다.

현재 2-of-2 다중 서명 스크립트를 통해 이를 수행하므로 트랜잭션에 두 개의 개별 서명이 포함되어야 합니다. schnorr 서명을 사용하면 한 쌍의 개인 키(pk1,pk2)를 사용하고 공유 공개 키 P=P1+P2=pk1×G+pk2×G에 해당하는 공유 서명을 생성할 수 있습니다. 이 서명을 생성하려면 각 장치에서 임의의 숫자(k1,k2)를 선택하고 임의의 지점 Ri=ki×G를 생성하고 이를 추가하여 공개 해시(P,R1+R2,m)를 계산한 다음 각 장치에서 s1 및 s2를 가져옵니다(si = ki + hash(P,R,m) ⋅ pki). 그런 다음 이러한 서명을 합산하고 (R, s) = (R1+R2, s1+s2) 쌍을 공유 공개 키 p의 서명으로 사용할 수 있습니다. 다른 사람은 집계된 서명인지 알 수 없으며 일반 schnorr 서명과 똑같이 보입니다.

이 구성에는 3가지 문제가 있습니다. 첫째, 사용자 인터페이스 관점에서 트랜잭션을 생성하려면 여러 라운드의 통신을 수행하고 공개 R을 계산한 다음 서명해야 합니다. 두 개의 개인 키를 사용하면 콜드 지갑에 대한 단일 액세스로 수행할 수 있습니다. 온라인 지갑에서 서명되지 않은 트랜잭션을 준비하고 k1을 선택한 다음 서명되지 않은 트랜잭션과 함께 R1=K1×G를 기록합니다. 그런 다음 이 데이터를 콜드 월렛으로 전송하고 서명합니다. 우리는 이미 R1을 가지고 있기 때문에 한 번에 콜드 월렛에서 트랜잭션에 서명할 수 있습니다. 콜드 월렛에서 R2와 s2를 가져와 온라인 월렛으로 다시 전송합니다. 온라인 지갑은 이전에 선택한 (k1, R1)으로 트랜잭션에 서명하고 서명을 결합하고 서명된 트랜잭션을 브로드캐스트합니다. 이것은 지금 우리가 있는 곳과 매우 유사하지만 세 번째 개인 키를 추가하면 모든 것이 더 복잡해집니다. 전 세계의 서로 다른 보안 위치에 저장된 10개의 개인 키로 제어되는 재산이 있고 거래를 해야 한다고 가정해 보겠습니다. 현재는 이 모든 위치를 한 번만 통과하면 되지만 키 집계를 사용하는 경우 두 번 수행하여 모든 RI를 조립한 다음 서명해야 합니다. 이 경우 집계 없이 개별 서명을 유지하는 것이 더 낫습니다. 그런 다음 3라운드의 통신이 필요합니다.

난수 ki와 그에 상응하는 Ri=ki×G를 선택하고 모든 사람에게 해시 ti=hash(Ri)만 알려주십시오. 그러면 다른 난수를 배운 후에도 마음이 바뀌지 않을 것입니다.
모든 숫자를 모아 공통 R을 계산하십시오.
징후;

두 번째 문제는 알려진 악성 키 공격입니다. 논문과 이 기사 모두에 잘 설명되어 있으므로 자세히 설명하지 않겠습니다. 아이디어는 장치 중 하나(예: 온라인 지갑)가 해킹되어 공개 키가 (p1-p2)인 것처럼 가장하면 개인 키 pk1로 공유 자금을 제어할 수 있다는 것입니다. 간단한 해결책은 장치를 설정할 때 해당 개인 키로 공개 키에 서명해야 한다는 것입니다.

세 번째 중요한 질문이 있습니다. 결정적 k로 서명할 수 없습니다. 쉽게 공격할 수 있는 방법이 있습니다. 결정론적 K를 사용하면 해커가 개인 키를 얻을 수 있습니다. 공격은 다음과 같을 것입니다. 누군가 우리 노트북을 해킹하고 두 개의 개인 키(예: pk1) 중 하나를 완전히 제어했습니다. 비트코인은 pk1과 pk2의 통합 서명이 필요하기 때문에 안전하다고 느낄 수 있습니다. 그래서 우리는 평소처럼 트랜잭션을 수행하려고 노력하고, 서명되지 않은 트랜잭션과 R1 값을 준비하고 하드웨어 지갑으로 전송하고 거기에서 서명합니다. 그런 다음 (r2, s2)를 반환하고 ... 온라인 지갑에 문제가 발생하여 서명 및 브로드캐스트할 수 없습니다. 다시 시도하지만 이번에는 해킹된 컴퓨터가 또 다른 임의의 값 R1'을 사용합니다. 하드웨어 지갑으로 동일한 트랜잭션에 다시 서명하고 값(r2, s2)을 해킹된 컴퓨터로 다시 가져옵니다. 그런 다음 나쁜 일이 발생하여 비트코인이 손실되었습니다.

이 공격에서 해커는 동일한 트랜잭션에 대한 유효한 서명 쌍을 얻습니다. (R1, s1, R2, s2) 및 (R1', s1', R2, s2'), 여기서 R2는 동일하지만 R = R1 +R2와 R'=R1'+R2는 다르므로 해커가 두 번째 개인 키를 계산할 수 있습니다. s2-s2'=(hash(P,R1+R2,m)-hash(P,R1 '+R2, m))⋅pk2 및 pk2=(s2-s2')/(해시(P,R1+R2,m)-해시(P,R1'+R2,m)). 이것이 키 집계의 가장 불편한 기능이라고 생각합니다. 키 집계를 사용하려면 모든 곳에서 좋은 난수 생성기가 필요합니다.

# Rainbow #

Rainbow는 UOV(Unbalanced Oil-Gooseberry) 서명 체계를 기반으로 하는 계층 구조의 다변량 서명 체계입니다. Rainbow 계층에 의해 부과된 추가 구조는 체계를 더 많은 암호화 기술에 노출하지만 체계의 효율성을 높입니다. Rainbow는 빠른 서명 및 확인과 매우 짧은 서명을 제공하지만 매우 큰 공개 키를 사용합니다.

Rainbow를 선택하면 선정된 서명 체계의 다양성이 증가하지만 키 크기가 매우 크기 때문에 Rainbow는 현재 FIPS 186-4에 나타나는 알고리즘을 대체하는 범용 서명 알고리즘으로 적합하지 않습니다. 특히 공개 키가 크면 인증서 체인이 매우 커집니다. 그러나 일부 애플리케이션은 키를 자주 보낼 필요가 없습니다. 이러한 응용 프로그램을 위해 Rainbow는 작고 빠른 서명을 제공합니다.