ink

ink

When do we need cryptography in blockchain space?

我觉得主要就是 VDF, accumulator, zkp, PCD 这些。zkp 所属其实又比较复杂，PCD 和 polynomial commitments 中可能使用 ZKP。(bulletproof, DARKs 是 alternative polynomial commitments? Sonic 中也构建了 polynomial commitments?)

对了，还有 randomness，比如 VRF。(对 sharding、leader election 等很重要)

然后里面又有基本工具:

schnorr signature (我感觉我甚至想写一篇 scriptless script is doom...) 感觉也挺有意义, 衍生到各种 DSA 相关。ZEC 他们搞了一堆。

Private_information_retrieval 这个亦有意义，涉及 intersection、交易撮合？
相关概念： PIR、PSI。

stealth address 这些则和很多相关，暂时不感兴趣。

Approaches

  • in Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation:
    • The rapid development of distributed systems raised the natural question of what tasks can be performed by them (especially when faults occur).
      • cryptographic approach
        • inaugurated by Difiie and Hellman [DH], assumes the players are computationally bounded, and further assumes the existence of certain (one-way) functions, that can be computed but not inverted by the player.
          • This simple assumption was ppstulated in [DH] in order to achieve the basic task of secure message exchange between two of the processors, but turned out to be universal! In subsequent years ingenious protocols baaed on the same assumption were given for increasingly harder tasks such as contract signing, secret exchange, joint coin flipping, voting and playing Poker. These results culminated, through the definition of zero-knowledge proofs [GMR], their existence for NP-complete problems [GMW1] in completeness theorems for two-party [Y1] and multi-party [GMW2] cryptographic distributed computation. In particular the results of Goldreich, Micali and Wigdesrson in [GMW2] were the main inspiration to our work. They show, that if (non-uniform) one way functions exist then every (probabilistic) function of n input,s can be computed by n computationally bounded processors in such a way that: (1) If no faults occur, no subset of the players can compute any additional information, and (2) Even if Byzantine faults are allowed, no set of size t < n/2 can either disrupt the computation or compute additional information.
      • The non-Cryptographic (or information-theoretic) approach
        • does not limit the computational power of the processors.
          • To facilitate the basic primitive of secret message exchange between a pair of players, we have secure channels.
            • (For an excellent source of results and problems in the case no secure channels exist, see [BL].

[BL]: M. Ben-Or and N. Linial, Collective coin flipping, FOCS86.
[DH]: W. Diffie and M. E. Helman, New directions in cryptography, IEEE Trans. Inform. Theory, Vol.IT-22,pp.644-654, 1976.
[GMW1] O. Goldriech, S. Micali and A. Wigderson, Proofs that yield nothing but the validity of the assertion, and a methodology of cryptographic protocol design, FOCS86, pp. 174-187.
[GMW2] O. Goldriech, S. Micali and A. Wigderson, How to play any mental game, STOC87, pp. 218-229.
[GMR] S. Goldwasser, S. Micali and C. Rackoff, The
knowledge complexity of interactive proof systems, STOC85, pp. 291-304.

PCD

VDF

VDF 比较全的资料网站: https://vdfresearch.org/, also see: https://blog.priewienv.me/post/verifiable-delay-function-1/ and https://medium.com/@chia_network/chia-vdf-competition-guide-5382e1f4bd39.

VDF 向上可以追溯到 Time-lock Puzzles 和 Timed Commitments。RSW Time-lock Puzzles 和 Timed Commitments 的构造比较像。后者强调 can be forced open by a procedure of determined running time & can prove that the time-lock puzzle has a solution；而前者 cannot verify that the puzzle can be unlocked in the desired time (is only privately verifiable)。

Timed Commitments 和 VDF 主要就是 场景不太一样。

目前最常用的 两种 VDF 的构造是:

  • Pie19
    • fast to create, but large and slow to verify.
    • 另外 poanetwork 中说 Pie19 "Number of iterations must be even and at least 66"
  • Wes19
    • slower to create (but parallelizable), but small, and quick to verify.

BBF18 专门了介绍了他们。其中提到，Pie19 要求 low order assumption，Wes19 要求 adaptive root assumption。Wes19 的要求更严格。

BBBF18 则列了各种 18年及以前的 VDF 相关的协议，并正式提出了 Verifiable Delay Functions (VDF) 的概念。

sloth 也是 Wes19 的 Wesolowski 提出的，在我看来就是 VDF 正式提出之前，VDF 的前身 (sloth 和 VDF 的 properties 还是有点区别，只能算是 pseudo-VDF)。sloth 和前面提到的 Pie19 和 Wes19 的区别是：sloth 利用了 computing square root (也算是 modular exponentiation，而 there is no known algorithm for computing modular exponentiation which is sublinear in the bit-length of the exponent.) 比它的逆运算难（慢）；而 Pie19 和 Wes19 则是利用了 repeated squaring in an RSA group (也可以不用 RSA group 而用别的 GUO 比如 class group)。(额我觉得我这里说的也不太对? sloth 好像和 hash 相关？然后 Wes19&Pie19 用的是 RSW time-lock puzzle? 我感觉都用了 squaring 的难度啊，应该是因为 RSW time-lock puzzle 的性质更好。)

cVDF

cVDF 中提到 Pie19 和 Wes19 中的 assumption 都不对。

Pie19 assumes the Fiat-Shamir heuristic for a proof system with a superconstant number of rounds.

Wes19 assumes the Fiat-Shamir heuristic for a
constant-round argument system.

cVDF 提到自己的 assumption 比起它们没毛病: relies on Fiat-Shamir heuristic for a
constant-round proof system.

(incremental) PoSW vs cVDF

a PoSW enables generating a publicly verifiable proof of some computation (rather than a specific function with a unique output) that is guaranteed to
have taken a long time.

(Incremental) PoSWs do not satisfy (computational) uniqueness, which is a major downside for many applications (see [BBBF18] for several examples).

cVDF enable verifiably outsourcing VDF computation.

incremental PoSW 就是 别人可以接着 PoSW；cVDF 就是别人可以接着 VDF。

RSA Groups assumption

Everyone seems to love VDFs, but the complexity theory around them is a bit underwhelming -- why do they only work against adversaries with a polynomial compute advantage?

A Note on Low Order Assumptions in RSA groups

VRF

JP Aumasson 也提到 the most exciting crypto in real applications 是 threshold oblivious PRFs。

延伸阅读

Expand all Back to top Go to bottom