• BTC

    Bitcoin

  • $3978.56466317

  • 0.34%

  • ETH

    Ethereum

  • $135.314231583

  • 0.13%

  • XRP

    XRP

  • $0.3040934924

  • 0.06%

  • LTC

    Litecoin

  • $59.339885087

  • 0.3%

  • EOS

    EOS

  • $3.7515202342

  • 1.99%

  • BCH

    Bitcoin Cash

  • $160.254779177

  • 0.78%

  • BNB

    Binance Coin

  • $16.156375977

  • 3.58%

  • USDT

    Tether

  • $1.0100980163

  • 0.4%

  • XLM

    Stellar

  • $0.1033127129

  • 0.76%

  • ADA

    Cardano

  • $0.0617157803

  • 3.25%

  • TRX

    TRON

  • $0.0226087394

  • 0.65%

  • BSV

    Bitcoin SV

  • $64.3654757016

  • 0.08%

  • XMR

    Monero

  • $52.837180455

  • 1.14%

  • MIOTA

    IOTA

  • $0.2962877861

  • 0.95%

  • DASH

    Dash

  • $89.6704953138

  • 0.45%

  • MKR

    Maker

  • $721.577661057

  • 0.24%

  • NEO

    NEO

  • $9.0266207141

  • 0.36%

  • ONT

    Ontology

  • $1.1716514726

  • 1.89%

  • ETC

    Ethereum Classic

  • $4.7002749589

  • 0.33%

  • XEM

    NEM

  • $0.0495276049

  • 0.3%

  • XTZ

    Tezos

  • $0.6674568903

  • 2.59%

  • ZEC

    Zcash

  • $55.2007389404

  • 0.73%

  • VET

    VeChain

  • $0.0055527399

  • 1.68%

  • WAVES

    Waves

  • $2.7061978056

  • 0.08%

  • BAT

    Basic Attention Token

  • $0.2152253536

  • 4.6%

  • USDC

    USD Coin

  • $1.0115410641

  • 0.13%

  • DOGE

    Dogecoin

  • $0.0020501883

  • 0.53%

  • OMG

    OmiseGO

  • $1.638506849

  • 1.93%

  • QTUM

    Qtum

  • $2.4989680719

  • 0.23%

  • CRO

    Crypto.com Chain

  • $0.0504009963

  • 6.54%

  • BTG

    Bitcoin Gold

  • $12.363578258

  • 0.25%

  • TUSD

    TrueUSD

  • $1.0186115004

  • 0.49%

  • DCR

    Decred

  • $18.7154750166

  • 2.06%

  • LSK

    Lisk

  • $1.523191876

  • 0.68%

  • ZRX

    0x

  • $0.2944953305

  • 5.52%

  • ZIL

    Zilliqa

  • $0.0191025461

  • 0.44%

  • RVN

    Ravencoin

  • $0.0519443237

  • 6.74%

  • REP

    Augur

  • $14.9923470082

  • 0.55%

  • LINK

    Chainlink

  • $0.4632681959

  • 2.47%

  • MXM

    Maximine Coin

  • $0.0973880784

  • 0.2%

  • BTS

    BitShares

  • $0.0592331856

  • 2.23%

  • ICX

    ICON

  • $0.3163779197

  • 1.13%

  • HOT

    Holo

  • $0.0011027764

  • 0.97%

  • DGB

    DigiByte

  • $0.0122206257

  • 0.9%

  • BCN

    Bytecoin

  • $0.0007559356

  • 0.36%

  • STEEM

    Steem

  • $0.4341086919

  • 4.26%

  • NANO

    Nano

  • $0.9554122857

  • 0.71%

  • BTT

    BitTorrent

  • $0.0007435868

  • 1.8%

  • ENJ

    Enjin Coin

  • $0.1637849333

  • 2.91%

  • BCD

    Bitcoin Diamond

  • $0.8155044332

  • 0.29%

  • KCS

    KuCoin Shares

  • $1.3634658259

  • 3.06%

  • HT

    Huobi Token

  • $2.4522668174

  • 1.99%

  • PAX

    Paxos Standard Token

  • $1.0146331038

  • 0.23%

  • AE

    Aeternity

  • $0.4566167992

  • 0.83%

  • KMD

    Komodo

  • $1.0122152932

  • 0.11%

  • XVG

    Verge

  • $0.0071337761

  • 0.72%

  • NPXS

    Pundi X

  • $0.0006208677

  • 0.67%

  • BTM

    Bytom

  • $0.1064190075

  • 1.94%

  • SC

    Siacoin

  • $0.0025933242

  • 0.83%

  • IOST

    IOST

  • $0.0083620141

  • 1.83%

  • THETA

    THETA

  • $0.1087452192

  • 0.15%

  • STRAT

    Stratis

  • $0.9302064716

  • 1.69%

  • ABBC

    ABBC Coin

  • $0.2004178676

  • 10.99%

  • AOA

    Aurora

  • $0.0134579445

  • 3.72%

  • DAI

    Dai

  • $0.997472337

  • 1.14%

  • GNT

    Golem

  • $0.0818316557

  • 1.85%

  • INB

    Insight Chain

  • $0.2236349445

  • 0.4%

  • SNT

    Status

  • $0.0224362668

  • 1.05%

  • PPT

    Populous

  • $1.4363095066

  • 2.94%

  • ARDR

    Ardor

  • $0.0758249147

  • 0.93%

  • PAI

    Project Pai

  • $0.050768266

  • 4.6%

  • ARK

    Ark

  • $0.6397916298

  • 5.01%

  • REPO

    REPO

  • $0.5978780869

  • 0.15%

  • XIN

    Mixin

  • $147.469595585

  • 1.82%

  • R

    Revain

  • $0.1319837904

  • 0.23%

  • CNX

    Cryptonex

  • $1.1284327165

  • 0.15%

  • GUSD

    Gemini Dollar

  • $1.0120335109

  • 0.39%

  • GXC

    GXChain

  • $1.0127647317

  • 1.72%

  • DGTX

    Digitex Futures

  • $0.0799938727

  • 1.88%

  • FCT

    Factom

  • $6.2506425506

  • 2.04%

  • HC

    HyperCash

  • $1.3447160881

  • 0.68%

  • MAID

    MaidSafeCoin

  • $0.1255542478

  • 0.16%

  • WAX

    WAX

  • $0.0589420328

  • 2.67%

  • ETN

    Electroneum

  • $0.0059839424

  • 0.64%

  • WTC

    Waltonchain

  • $1.2964357022

  • 6.87%

  • MANA

    Decentraland

  • $0.0506060373

  • 0.78%

  • PIVX

    PIVX

  • $0.9254450163

  • 6.54%

  • MCO

    Crypto.com

  • $3.3013258981

  • 4.71%

  • LOOM

    Loom Network

  • $0.0682286839

  • 1.77%

  • QASH

    QASH

  • $0.1456856785

  • 0.74%

  • LRC

    Loopring

  • $0.0613868837

  • 2.87%

  • WICC

    WaykiChain

  • $0.2610754554

  • 10.53%

  • ELF

    aelf

  • $0.1750016091

  • 0.14%

  • XZC

    Zcoin

  • $6.8627114831

  • 4.25%

  • THR

    ThoreCoin

  • $548.693978776

  • 1.72%

  • QBIT

    Qubitica

  • $16.1759390028

  • 7.01%

  • MOAC

    MOAC

  • $0.7103786733

  • 0.99%

  • POWR

    Power Ledger

  • $0.1107848949

  • 2.32%

  • ENG

    Enigma

  • $0.581091216

  • 35.4%

  • WAN

    Wanchain

  • $0.4039611463

  • 6.99%

Và Quantum Computing đã ra đời, Blockchain sẽ đến hồi kết?

Discussion in 'Trao Đổi Công Nghệ' started by TungNobi, Jan 12, 2019.

  1. Sự ra đời của máy tính lượng tử liệu sẽ giết chết Bitcoin? Và hôm nay nó đã ra đời. Thậm chí IBM còn thương mại hóa nó với cái tên Q System One.

    [​IMG]

    Tuy nhiên, vấn đề không đơn giản thế. Thực ra mình hoài nghi cái-mà-IMB-gọi-là-máy-tính-lượng-tử, bài này mình trình bày vài hiểu biết liên quan đến toán học trong việc giải quyết bài toán P chọi NP và tầm quan trọng của bài toán này trong mật mã học hiện đại cũng như toàn bộ ngành khoa học máy tính nói chung.

    Bắt đầu bằng thuật toán tạo số ngẫu nhiên


    Nếu bạn là dân IT chắc sẽ biết đến bộ sách đồ sộ "The Art of Computer Programming" của Knuth. Ông dành hẳn cả một chương lớn để bàn về việc làm thế nào để tạo ra được một số ngẫu nhiên. Thực ra vấn đề không chỉ tồn tại trong toán học mà nó cũng thể hiện mối liên hệ mật thiết với triết học trong câu hỏi đến nay vẫn chưa ai dám trả lời quả quyết: "Trên đời có thứ gì là ngẫu nhiên không?". Chính quy luật nguyên nhân-hệ quả của triết học, đã đặt ra cho toán học một ranh giới chưa thể bước qua, người ta chỉ có thể chấp nhận nó với tên gọi "thuật toán tất định".

    Thuật toán tất định ràng buộc rằng: đầu ra (output) hoàn toàn có thể dự đoán được thông qua đầu vào (input). Nghĩa là chẳng có gì là ngẫu nhiên cả. Cái mà chúng ta nghĩ rằng có một con số ngẫu nhiên tạo ra chẳng qua chỉ vì chúng ta "muốn như thế". Vì thực tế, nó đã được biết trước bởi input và thuật toán mất rồi. Nhân đây, cũng nói thêm về hai "mẹo" tạo số ngẫu nhiên mà chúng ta có được cho đến nay:

    - dựa vào "số ngẫu nhiên" trước đó và xem nó như một input để sinh ra những con "số ngẫu nhiên" sau này
    - sử dụng một phần cứng đặt biệt để tạo số ngẫu nhiên (seed).

    Đọc vào chắc bạn sẽ hình dung đến cấu trúc của blockchain, cấu trúc dữ liệu Linked List. Bản chất là các khối được liên kết với nhau thông qua hash.

    KPI quan trọng nhất cho công việc tạo ra một số ngẫu nhiên là làm cho nó "không thể nào dự đoán được". Người ta cố gắng thêm "muối", thêm "đường" ùm bà lằng vào để không ai có đủ khả năng dò ra nỗi input của bài toán. Nhưng cuối cùng phải thừa nhận rằng, chỉ cần biết được thuật toán, thì gần như biết được tất cả. Nhưng nói vậy bằng thừa, vấn đề hóc búa đáng quan tâm hơn là: "Liệu có tồn tại một sức mạnh tính toán nào đủ khả năng giải ngược bài toán từ output ra input trong thời gian mà chúng ta có thể chấp nhận được hay không?".

    Thế là sau nhiều thế kỉ tìm kiếm, người ta bắt đầu để ý tới khái niệm "máy tính lượng tử", và kì vọng sẽ mở ra những chân trời mới cho toán học và sự phát triển của nhân loại.

    Cho đến bài toán P chọi NP


    Khi đối diện với một bài toán bất kỳ trong mọi lĩnh vực, ở đây xét riêng về toán học, người ta không chỉ quan tâm bài toán ấy giải được hay không giải được, mà còn quan tâm mất bao lâu nếu giải được, nghĩa là quan tâm đến "độ khó" của bài toán. Giả sử, private key của ví bitcoin là một số biểu diễn bởi 256 bit. Vậy thì về lý thuyết thì ta sẽ có 2^256 private key. Nếu bạn là hacker và chơi trò "vét cạn" thì số lần thử chọn của bạn có thể lên đến 10^77 lần. Con số này gần với số ngôi sao chúng ta quan sát được (quá khủng khiếp và phi thực tế!).

    Diễn giải theo ngôn ngữ toán học, độ phức tạp được phân theo lớp. Trong đó, lớp P bao gồm những bài toán giải được trong thời gian đa thức, và nó được coi là lớp các bài toán có thể giải được trong thực tế, mà trên đây mình dùng chữ trong thời gian "chấp nhận" được. Còn lớp NP là lớp các bài toán có thể kiểm tra được lời giải đúng hay sai trong thời gian đa thức.

    Ví dụ, trò chơi sodoku là một bài toán thuộc lớp NP. Dưới góc độ lập trình, nó vô cùng khó khăn để giải quyết, nhưng để kiểm tra xem bảng sokudo đó có lời giải hay không thì chỉ cần một em bé lớp 2 phân biệt được các con số từ 0 đến 9.

    Câu hỏi đặt ra là: P = NP hay P khác NP. Nếu P = NP thì có nghĩa là bài toán nào có khả năng kiểm tra lời giải cũng có khả năng tìm ra lời giải. Tức là mọi bài toán thực tế (là bài toán mà ta có thể kiểm tra xem một lời giải là đúng hay sai) đều giải được dễ dàng. Nếu hôm nào đó, một "siêu anh hùng" xuất hiện và chứng minh P = NP thì không chỉ nhận được 1 triệu đô từ viện Clay (giải thưởng hiện tại) mà còn thay đổi toàn bộ nhận thức của nhân loại về bảo mật. Giao thức bảo mật với Public key hoàn toàn vô nghĩa và nhảm nhí. Về phương diện nào đó, siêu anh hùng giữ bí mật của riêng mình thì có thể "tạo ra bitcoin" muốn bao nhiêu cũng được. Điều đó không đáng sợ bằng, tất cả các giao dịch Internet đặt trong tình trạng bất ổn vì hoàn toàn có thể "cướp" được dễ dàng.

    "máy tính lượng tử" đã xuất hiện?


    Mình bỏ qua cách mà truyền thông tung hô, vì nó chỉ mang ý nghĩa marketing chứ không giải quyết nỗi lo sợ của chúng ta. Nếu giả sử tồn tại một mô hình máy tính hoàn toán khác với mô hình máy tính hiện tại và đủ khả năng giải quyết các bài toán NP trong thời gian đa thức, thì có hai trường hợp xảy ra.

    - Người ta bí mật kiểm soát nó và kiểm soát luôn cả khái niệm "cái gì mới thật sự là bí mật" trên internet.
    - Người ta công khai nó và toàn bộ ngành mật mã học phải định nghĩa lại rất nhiều thứ. Blockchain với cái xương sống là hàm băm sẽ phải chuyển hóa thành "một cái gì đó" mới mẻ hơn.

    Bài viết này không phải phim khoa học viễn tương, mọi thứ đang phát triển quá nhanh và cứ như đang rành rành ngay trước mắt chúng ta.
     
    admin, Mr.S, Good Boy and 2 others like this.
    TungNobi

    TungNobi Moderator

  2. Thích Đu Đỉnh

    Thích Đu Đỉnh Tôm Tép

    Thích Đu Đỉnh
    Không hiểu bác đang nói cái quái gì cả :( cuối cùng là sao, bitcoin sẽ chết à?
     
    #2
    TungNobi likes this.
  3. TungNobi

    TungNobi Moderator

    TungNobi
    Èo, trong bài em có nói câu nào là bitcoin sẽ chết đâu :)
     
    #3
  4. Truong Dat Long

    Truong Dat Long Tôm Tép

    Truong Dat Long
    Vậy từ kết thúc có ý gì vậy..mình không hiểu
     
    #4
  5. TungNobi

    TungNobi Moderator

    TungNobi
    Trên lý thuyết và cả thực tế, không ai chứng minh được P = NP, cơ chế bảo mật và hệ thống blockchain vẫn bình an vô sự.
     
    #5
    Good Boy likes this.
  6. Durex

    Durex Tôm Tép

    Durex
    Cái này còn dài lắm bạn, có khi 5-8 năm nữa
     
    #6
    Mr.S, Good Boy and TungNobi like this.
  7. TungNobi

    TungNobi Moderator

    TungNobi
    Hiện tại mình biết không có một mô hình tính toán nào đủ khả năng giải quyết NP cả, xa hơn hơn nữa là NP-complete. Nên blockchain vẫn an toàn. chưa chuyển hóa được đâu. 5-8 năm thì đúng là chưa nói gì được.
     
    #7
    admin, Mr.S, Good Boy and 1 other person like this.

Share This Page