零知识证明 - zkHack mini挑战赛第一名

这次的挑战赛由两道题目组成。一道题目一个星期的挑战时间。和第一期的挑战不同,这一期的题目都是基于STARK算法。STARK算法,AIR,FRI低阶测试等等技术会在后续的文章仔细介绍。本文先总结一下这次挑战赛的两个题目的解题思路。

Trapdoor Tech获得zkHack mini挑战赛第一名 :)

https://www.zkhack.dev/mini.html

aa.png

这次的挑战赛由两道题目组成。一道题目一个星期的挑战时间。和第一期的挑战不同,这一期的题目都是基于STARK算法。STARK算法,AIR,FRI低阶测试等等技术会在后续的文章仔细介绍。本文先总结一下这次挑战赛的两个题目的解题思路。

第一题:There's something in the AIR

https://www.zkhack.dev/puzzleM1.html

该题需要找到一种方法来骗过基于ZK-STARK和winterfell构建的投票系统。该题实现的电路逻辑如下图:

bb.png

这个是典型的隐私保护的实现。通过Nullifier证明拥有私钥。

解题思路

如果用户Alice能对同一个主题(topic)完成2次有效投票,说明系统中存在一个漏洞使得:

  • 证明者(prover)能产生 > 1 个的nullifier,并基于此构建证据(witness)
  • 验证者(verifier)根据相应的公开输入和证据,无法分辨证明者伪造的nullifier

首先,构造nullifier是在make_signal函数中,并将其作为验证者的输入

//! - A nullifier is computed by hashing a private key together with a hash of the topic - i.e.:
//!   hash(priv_key, hash(topic)) using the same Rp64_256 hash function.

  let nullifier = priv_key.get_nullifier(topic);

  /// Creates a nullifier for the provided topic against this private key.
  ///
  /// A nullifier is computed simply as hash(key, topic).
  pub fn get_nullifier(&self, topic: Digest) -> Digest {
      let key: Digest = self.0.into();
      Rescue::merge(&[key, topic])
  }

但是证明者进行证据的计算过程中,使用12列的执行轨迹, 即State[12..23],来构成nullifier, 不只是私钥和主题。

// prover set the initial state
  // -- nullifier section of the trace --
              state[12] = Felt::new(8);
              state[13] = Felt::ZERO;
              state[14] = Felt::ZERO;
              state[15] = Felt::ZERO;
              state[16] = priv_key[0];
              state[17] = priv_key[1];
              state[18] = priv_key[2];
              state[19] = priv_key[3];
              state[20] = topic[0];
              state[21] = topic[1];
              state[22] = topic[2];
              state[23] = topic[3];

一个合法的nullifier应包括以下3个部分

[12     13       14     15]   [ 16     17   18     19 ]   [   20   21 22   23 ]

nullifier = [8 0, 0, 0, --- 私钥Priv_key----------, -----主题Topic------- ] -- 在执行到第 0 步时

然而,检查验证者的程序时,发现在evaluate_transition函数中没有设置对state[12-15]的验证, 类似的验证可以参考默克尔树验证的部分。

result.agg_constraint(1, hash_init_flag, are_equal(E::from(8u8), next[0]));
      result.agg_constraint(2, hash_init_flag, is_zero(next[1]));
      result.agg_constraint(3, hash_init_flag, is_zero(next[2]));
      result.agg_constraint(4, hash_init_flag, is_zero(next[3]));

答案

可以为state[12-15]设置不同的值来伪造nullifier,例如[16, 0, 0, 0]。

pub fn get_fake_nullifier(&self, topic: Digest) -> Digest {
      let key: Digest = self.0.into();

      let mut state = [Felt::ZERO; 12];
      state[4..12].copy_from_slice(Digest::digests_as_elements(&[key, topic]));
      state[0] = Felt::new(0 as u64);

      // apply the Rescue permutation and return the first four elements of the state
      Rescue::apply_permutation(&mut state);
      Digest::new(state
          [4..8].try_into().unwrap())
  }

同时在证明者产生证据时,将state[12-15]设置为伪造的nullifier所对应的值。

Prover.build_trace()
      |state| {
            ......
              // -- nullifier section of the trace --
              state[12] = Felt::new(0);

第二题:Can you turn up the heat?

https://www.zkhack.dev/puzzleM2.html

本周的题目可以说是 zkHack 有史以来最难的一道题。本题的目标是伪造 STARK 证明,需要解题者对 STARK 证明的整个逻辑步骤有较为清晰的知识。

来回顾一下题目:Alice使用 STARK 电路写了一个斐波那契数列的计算程序,能够同时生成 STARK 证明并验证。某天她收到了一个错误的证明,计算出数列的第32项等于123(实际应为832040)。但这个证明却能通过她的 STARK 验证器。现在我们想要知道该证明是如何被伪造的。

cc.png

dd.png

ee.png

本文首发于:https://mp.weixin.qq.com/s/R_YDF8neGwGpvstx-DYFQg

  • 发表于 2022-03-21 14:10
  • 阅读 ( 675 )
  • 学分 ( 1 )
  • 分类:零知识

0 条评论

请先 登录 后评论
Star Li
Star Li

80 篇文章, 6159 学分