每周算法

343. 整数拆分 - 力扣(LeetCode) (leetcode-cn.com)

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2:

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于 58。

/*大体思路
暴力解法,通过穷举所有可能,找到那个最大乘积。
优化:将其中重复的部分记录下来,减少重复的计算
*/
class Solution {
public:
    std::unordered_map<int,int> proList;
    int backTrace(int n){
        if(n == 1)
            return 1;
        if(proList.find(n) != proList.end())
            return proList[n];
        proList[n] = n-1;
        int lift ,a11 , a1 , a2 , a22 , sum ;
        for(int i = 1 ; i <= n/2 ; i++){
            lift = n - i;
            a11 = backTrace(i);
            a22 = backTrace(lift);
            a1 = i > a11?i:a11;
            a2 = lift > a22?lift:a22;
            sum = a1 * a2;
            if(sum > proList[n])
                proList[n] = sum;
        }
        return proList[n];
    }
    int integerBreak(int n) {
        return backTrace(n);
    }
};
/*
解题思路:
动态规划方式
dp[n]  当输入为n的时候的最大值
dp[n] = max(max(dp[m],m)*max(dp[n-m] , n-m))
dp[0] =0 dp[1] = 1 则我们只需要顺序的求出dp[n]即可
*/
class Solution {
public:
    int integerBreak(int n) {
        // dp[n]  代表 输入为n 时候的最大值
        // dp[n] = max(dp[m]*dp[n-m])
       	std::vector<int> vecData;
	    vecData.resize(n+1);
	    vecData[0] = 0 ;
	    vecData[1] = 1 ;
	    for( int i = 2 ; i <= n ; i++){
		    vecData[i] = i-1;
		    for( int j = 1 ; j <= i/2 ; j++){
                vecData[i] = max(max(vecData[j],j)*max(vecData[i-j],i-j) ,vecData[i]);
		    }
	    }
		return vecData[n];
    }
};

每周论文阅读之solana白皮书

solana白皮书

概要

本文提出了一种新的基于历史证明(PoH)的区块链体系结构—一种验证事件之间顺序和时间流逝的证明。PoH用于将不可靠的时间段编码到一个分类账中,这仅仅是一个附加的数据结构。当与其他的一致性算法(如工作量证明(PoW)或利害关系证明(PoS))一起使用时,PoH可以减少拜占庭故障转移和复制状态机中的消息传递开销,从而减少消息的最终确认时间。本文还提出了两种利用PoH账本的时间保持特性的算法—一种可以从任意大小的分区中恢复的PoS算法和一种高效的流式副本证明(PoRep)。PoRep和PoH的结合提供了一种在时间(顺序)和存储时间方面防止伪造分类账的方法。在 1gbps 网络上对该协议进行了分析,结果表明,在目前的硬件环境下,每秒吞吐量可达710k。

区块链是容错复制状态机的实现。当前公开可用的区块链(btc 、 eth)不依赖于时间,或者对参与者保持时间的能力做了很弱的假设。网络中的每个节点通常依赖于自己的本地时钟,但是并不知道网络中的任何其他参与者的时钟。缺少可信的时间源意味着,当使用消息时间戳来接受或拒绝消息时,不能保证网络中的每个其他参与者都会做出完全相同的选择。这里介绍的PoH旨在创建一个具有可验证时间排序的分类账,即事件和消息排序之间的持续时间。因此,网络中的每个节点都将能够在没有信任的情况下依赖于账本中记录的时间排序。

网络设计

如下图所示,在任何给定时间,系统节点被指定为领导者,用来生成历史证明序列,从而提供网络全局读取一致性和可验证的时间流逝。领导者对用户消息进行排序,以便系统中的其他节点能够有效地处理这些消息,从而最大限度地提高吞吐量。它对存储在RAM中的当前状态执行事务,并将事务和最终状态的签名发布到称为验证器的复制节点。验证者在他们的州副本上执行相同的事务,并公布他们的州计算签名作为确认。公布的确认书作为共识算法的投票。

在非分区状态下,在任何给定的时间,网络中都有一个领导者。每个验证器节点具有与领导者相同的硬件功能,并且可以被选为领导者,这是通过基于PoS的选举来完成的。后面会详细介绍了模拟PoS算法的选择。根据CAP定理,在发生分区时,一致性几乎总是高于可用性。在大分区的情况下,本文提出了一种从任意大小的分区恢复网络控制的机制。

Proof of History

历史证明是一个计算序列,它可以提供一种方法,以密码方式验证两个事件之间的时间流逝。它使用一个cryptographical secure函数,这样就不能从输入中预测输出,必须完全执行才能生成输出。该函数在单个内核上按顺序运行,以前的输出作为当前输入,定期记录当前输出,以及调用它的次数。然后,通过检查单独核心上的每个序列段,外部计算机可以并行地重新计算和验证输出。通过将数据(或某些数据的散列)附加到函数的状态中,可以将数据时间戳到该序列中。状态、索引和数据被附加到序列中时的记录提供了一个时间戳,可以保证数据是在序列中生成下一个哈希之前的某个时间创建的。这种设计还支持水平缩放,因为多个生成器可以通过将它们的状态混合到彼此的序列中来在彼此之间进行同步。

Description

POH系统工作流程如下。

对于加密哈希函数,如果不运行该函数(如sha256、ripemd等),就无法预测其输出。则从某个随机起始值运行该函数,并将其输出作为下一个输入再次传递给同一个函数。记录函数被调用的次数和每次调用的输出。选择的起始随机值可以是任何字符串,比如当天的《纽约时报》头条。

image-20210612175824665

其中hashN表示实际的哈希输出。只需每隔一段时间发布散列和索引的一个子集。

image-20210612175958113

只要选择的哈希函数是抗冲突的,这组哈希就只能由一个计算机线程按顺序计算。这源于这样一个事实:如果不从起始值实际运行算法300次,就无法预测索引300处的散列值将是什么。因此,我们可以从数据结构中推断,real time在索引0和索引300之间传递。在下图的示例中,hash 62f51643c1在计数510144806912上生成,hash c43d862d88在计数510146904064上生成。根据前面讨论的PoH算法的属性,我们可以信任在计数510144806912和计数510146904064之间传递的实时性。

image-20210612180219425

Timestamp for Event

此哈希序列还可用于记录在生成特定哈希索引之前创建的某个数据段。使用 combine函数 将该数据段与当前索引处的当前哈希组合。数据可以是任意事件数据的加密唯一散列。combine函数可以是简单的数据附加,也可以是任何抗冲突的操作。下一个生成的哈希表示数据的时间戳,因为它只能在插入特定数据段之后生成。

image-20210612180437376

image-20210612180508355

Hash336是根据hash335的附加二进制数据和照片的sha256来计算的。照片的索引和sha256被记录为序列输出的一部分。因此,任何验证此序列的人都可以重新创建对序列的更改。验证仍然可以并行进行,因为初始过程仍然是顺序的,所以我们可 以判断进入序列的事情一定是在计算未来散列值之前的某个时间发生的。

image-20210612180708290

在上表表示的序列中,photograph2是在hash600之前创建的,photograph1是在hash336之前创建的。将数据插入哈希序列会导致序列中所有后续值的更改。只要所使用的散列函数是抗冲突的,并且数据是附加的,就不可能在计算上预先计算任何未来的序列,而这些序列是基于什么样的数据将被集成到序列中的先验知识。混合到序列中的数据可以是原始数据本身,也可以只是数据的散列以及伴随的元数据。在下图的示例中,输入cfd40df8。。。被插入历史证明序列。插入时的计数为510145855488,插入时的状态为3d039eef3。所有未来生成的哈希值都会被序列的这种变化所修改,这种变化由图中的颜色变化来表示。观察此序列的每个节点都可以确定插入所有事件的顺序,并估计插入之间的实时性。

image-20210612181112929

Verification

多核计算机可在比生成序列所需时间少得多的时间内验证序列的正确性。

image-20210612181432031

给定一定数量的核,比如一个拥有4000核的现代GPU,验证器可以将散列序列及其索引拆分为4000个片,并并行地确保每个片从起始散列到片中最后一个散列都是正确的。如果生成序列的预期时间是:

image-20210612181601395

验证序列是否正确的预期时间是:哈希总数(每个核心每秒的哈希数*可验证的核心数)在图4中的示例中,每个核心能够并行验证序列的每个片段。由于所有的输入字符串都被记录到输出中,加上它们所附加的计数器和状态,验证器可以并行地复制每个片段。红色散列表示序列被数据插入修改。

Horizontal Scaling

通过将每个生成器的序列状态混合到其他生成器,可以同步多个历史证明生成器,从而实现历史证明生成器的水平缩放。这种缩放是在没有分片的情况下完成的。两个生成器的输出都是重建系统中事件的完整顺序所必需的。

image-20210612181849647

给定生成器A和B,A从B(hash1b)接收一个数据包,该数据包包含来自生成器B的最后一个状态,以及从生成器A观察到的最后一个状态生成器B。生成器A中的下一个状态散列依赖于生成器B中的状态,因此我们可以得出hash1b发生在hash3a之前的某个时间。这个属性可以传递,所以如果三个生成器通过一个公共生成器同步,那么A↔ B↔ C、 我们可以跟踪A和C之间的依赖关系,即使它们不是直接同步的。通过周期性地同步生成器,每个生成器可以处理一部分外部通信量,因此整个系统可以处理大量要跟踪的事件,但由于生成器之间的网络延迟,以牺牲实时精度为代价。全局顺序仍然可以通过选取某个确定性函数对同步窗口内的任何事件进行排序来实现,例如通过哈希本身的值。在下图中,两个生成器相互插入输出状态并记录操作。颜色变化表明来自对等方的数据修改了序列。混合到每个流中的生成哈希以粗体突出显示。同步是可传递的。A↔ B↔ 在a和C到B之间有一个可证明的事件顺序。以这种方式扩展是以可用性为代价的。10× 可用性为0.999的1 gbps连接的可用性为0.99910=0.99。

image-20210612182144146

Consistency

用户希望能够强制执行生成序列的一致性,并通过将他们认为有效的序列的最后一次观察输出插入到他们的输入中来抵抗攻击。

如果一个恶意的PoH生成器能够同时访问所有事件,或者能够生成一个更快的隐藏序列,那么它就可以生成第二个事件顺序相反的隐藏序列。为了防止这种攻击,每个客户端生成的事件本身都应该包含客户端从其认为有效的序列中观察到的最新哈希。因此,当客户机创建“Event1”数据时,他们应该附加他们观察到的最后一个散列。

image-20210612183004029

当序列被发布时,Event3将引用hash30a,如果它不在该事件之前的序列中,则序列的使用者知道它是一个无效序列。然后,部分重新排序攻击将被限制为客户端观察到事件和输入事件时生成的哈希数。然后,客户机应该能够编写这样的软件:在最后一次观察到的哈希和插入的哈希之间的短时间内,不假定顺序是正确的。为了防止恶意PoH生成器重写客户端事件散列,客户端可以提交事件数据和最后观察到的散列的签名,而不仅仅是数据。

image-20210612183417167

验证此数据需要签名验证,并在此之前按哈希序列查找哈希。

Verify:

(Signature,PublicKey,hash30a,event3 data)=event3 Verify(Signature,PublicKey,event3)

Lookup(hash30a,PoHSequence)

在下图中,用户提供的输入依赖于hash 0xdeadbeef。。。在插入前的某个时间存在于生成的序列中。蓝色的左上箭头表示客户端正在引用以前生成的哈希。clients消息仅在包含哈希0xdeadbeef….的序列中有效。。。。序列中的红色表示序列已被客户端数据修改。

image-20210612183634575

overhead

每秒4000个哈希将产生额外的160千字节的数据,并且需要访问具有4000个内核的GPU,大约需要0.25-0.75毫秒的时间进行验证。

Proof of Stake Consensus

Description

POS 这个具体实例是为快速确认历史证明生成器生成的当前序列、投票和选择下一个历史证明生成器以及惩罚任何行为不端的验证器而设计的。该算法依赖于消息最终在一定的超时时间内到达所有参与节点。

Terminology

债券相当于工作量证明中的资本支出。矿工购买硬件和电力,并将其交付给工作量证明区块链中的单个分支机构。债券是一种代币,验证者在验证交易时将其作为抵押品。大幅削减了股权证明系统中无利害关系问题的拟议解决方案。当为指定分支发布投票证明时,该分支可以销毁验证器绑定。这是一种经济激励,旨在阻止验证者确认多个分支。

超级多数超级多数是32个RD的验证者通过他们的债券进行加权。超级多数票表明网络已达到,至少有31个网络成员会恶意投票让这个分支机构无效。这将使攻击的经济成本达到代币市值的31%。

Bonding

债券交易收取一定数量的代币,并将其转移到用户身份下的债券账户。债券账户中的代币不能消费并且必须保留在帐户中,直到用户删除它们。用户只能删除已超时的过期硬币。在当前的大多数利益相关者确认了顺序之后,债券才有效。

Voting

预计历史证明生成器将能够在预定义的时间段内发布状态的签名。每个保税身份必须通过公布自己的国家签字来确认该签字。投票是简单的赞成票,没有反对票。如果大多数绑定身份在超时时间内投票,则此分支将被接受为有效。

Unbonding

缺少N张选票意味着这些硬币已经过时,不再有资格投票。用户可以发出解除绑定的事务来删除它们。N是一个基于过时投票与活动投票比率的动态值。N随着过时票数的增加而增加。在网络分区较大的情况下,这允许较大的分支比较小的分支恢复得更快。

Elections

当检测到PoH生成器故障时,将选择新的PoH生成器。具有最大投票权或最高公钥地址(如果有平局)的验证器被选为新的PoH生成器。新序列需要超多数的确认。如果新的领导者在超级多数确认可用之前失败,则选择下一个最高的验证器,并且需要一组新的确认。

若要切换投票,验证程序需要在更高的PoH序列计数器上进行投票,并且新的投票需要包含要切换的投票。否则,第二次投票将是可削减的。投票转换的设计应该使它只能在没有绝对多数的高度发生。一旦PoH生成器建立,就可以选择一个二级来接管事务处理职责。如果存在次要故障,则在主要故障期间它将被视为下一个先导。

该平台的设计使辅助生成器成为主生成器,如果检测到异常或按照预先定义的时间表,则提升低秩生成器。

Election Triggers

PoH生成器的设计具有一个标识,标识生成的序列。fork只能在PoH生成器身份被破坏的情况下发生。检测到分叉是因为两个指定的历史记录已以相同的PoH身份发布。 硬件故障、bug或PoH生成器中的故意错误可能导致它生成无效状态并发布与本地验证程序结果不匹配的状态签名。验证者将通过流言蜚语发布正确的签名,这一事件将引发新一轮的选举。任何接受无效状态的验证器都将被切断其绑定。 网络超时将触发选举。 当验证程序对两个独立的序列进行投票时,就会出现倾斜。恶意投票的证明将从流通中移除保税代币,并将其添加到采矿池中。包含竞争序列上的先前投票的投票不符合恶意投票的证明资格。这次投票并没有削减债券,而是取消了目前在竞争序列上投下的一票。如果对PoH生成器生成的无效哈希进行投票,也会发生倾斜。生成器将随机生成一个无效状态,这将触发回退到辅助服务器。 可以提出并批准二级和低级别的历史证明生成器。一个建议被强制转换到一次生成器序列上。一个建议被强制转换到一次生成器序列上。提案中包含一个暂停时间,如果议案在暂停时间前获得过半数表决通过,则认为次议长当选,并将如期接管职务。通过在生成的序列中插入指示将发生切换的消息,或者插入无效状态并强制网络回退到辅助设备,主设备可以执行到辅助设备的软切换。如果一个中学当选,而初选失败,中学将被视为选举中的第一个后备队。

Availability

处理分区的CAP系统必须选择一致性或可用性。我们的方法最终会选择可用性,但是因为我们有一个客观的时间度量,所以一致性是通过合理的人工超时来选择的。

POS验证器将一定数量的代币锁定在一个赌注中,这样他们就可以对一组特定的交易进行投票。锁定硬币是一种输入到PoH流中的交易,就像任何其他交易一样。要投票,PoS验证器必须对状态哈希进行签名,因为它是在将所有交易处理到PoH分类账中的特定位置后计算出来的。此投票也作为一项交易输入到PoH流中。此投票也作为一项交易输入到PoH流中。通过查看PoH分类账,我们可以推断出每次投票之间经过了多少时间,如果发生分区,每个验证器不可用的时间有多长。为了处理具有合理人工时间范围的分区,我们提出了一种动态方法来取消不可用的验证器。当验证器的数目较高且超过32个时,解列过程可以很快。在完全取消不可用验证者的赌注之前,必须生成到分类帐中的哈希数较低,并且不再计算它们以获得一致意见。当验证者的数目低于32个RD但高于21时,取消赌注计时器较慢,在取消标记丢失的验证器之前,需要生成更多的散列。在一个大的分区中,比如缺少21个或更多验证器的分区,解列过程非常慢。事务仍然可以输入到流中,并且验证者仍然可以投票,但是直到生成了非常大量的散列并且取消了不可用的验证者之后,才能实现完全的32 rds共识。网络恢复活跃度的时间差允许我们作为网络的用户在时间范围内选择一个我们想要继续使用的分区。

Recovery

在我们提出的系统中,账本可以从任何故障中完全恢复,也就是说,世界上任何人都可以随机选取账本中的任何一个点,通过添加新生成的哈希和事务来创建一个有效的fork。如果这个fork中缺少所有的验证器,任何额外的债券都需要很长时间才能生效,而这一分支机构也需要很长时间才能达成2/3的超多数共识。因此,在零可用验证器的情况下进行完全恢复需要在分类账中附加大量的哈希值,只有在所有不可用的验证器都被取消之后,任何新的债券才能验证分类账。

Finality

PoH允许网络的验证者在一定程度上确定这些事件发生的时间的情况下观察过去发生的事情。由于PoH生成器正在生成消息流,所有验证器都需要在500毫秒内提交其状态签名。这个数字可以根据网络状况进一步减少。由于每个验证都被输入到流中,因此网络中的每个人都可以验证每个验证者是否在所需的超时时间内提交了他们的投票,而不必直接观察投票。

Attacks

PoS验证器只是确认PoH生成器生成的状态散列。对他们来说,有一种经济激励,就是不做任何工作,只批准每一个生成的状态散列。为了避免这种情况,PoH生成器应该以随机间隔注入一个无效的散列。任何支持这项法案的选民都应该被砍掉。当散列产生时,网络应该立即提升二次选择的PoH生成器,每个验证器都需要在一个小的超时时间内做出响应,例如500毫秒。超时时间应设置得足够低,以使恶意验证者观察到另一验证者投票并以足够快的速度将其投票输入流的概率很低。

与PoH生成器合谋的验证器将提前知道何时将生成无效散列,并且不会对其投票。这种情况实际上与PoH身份拥有更大的股权没有区别。PoH生成器仍然需要做所有的工作来生成状态散列。

Streaming Proof of Replication

Filecoin提出了复制证明的一个版本。这个版本的目标是对复制证明进行快速的流式验证,这是通过跟踪历史证明生成序列中的时间来实现的。复制并不是一种共识算法,而是一种有用的工具,用于说明以高可用性存储区块链历史或状态的成本。

Algorithm

CBC模式:(密码分组链接模式) 如图7所示,CBC加密按顺序加密每个数据块,使用先前加密的块对输入数据进行异或运算。每个复制标识通过对已生成的历史证明序列的哈希进行签名来生成密钥。这将关键与复制者身份和特定的历史证明序列联系起来。只能选择特定哈希(见第6.5节散列选择)数据集逐块完全加密。然后,为了生成一个证明,密钥被用来为一个伪随机数产生器播种,该产生器从每个块中随机选择32个字节。

将发布根、密钥和生成的选定哈希。复制节点需要以N个哈希值发布另一个证明,因为它们是由历史证明生成器生成的,其中N大约是加密数据所需的时间的21。历史证明生成器将发布特定的哈希,以便在预定的时间段内进行复制证明。replicator节点必须选择下一个发布的哈希来生成证明。同样,对散列进行签名,并从块中选择随机切片来创建merkle根,经过一段时间的N个证明之后,使用新的CBC密钥对数据进行重新加密。

加密前要与当前块异或的上一个加密块数据

确保加密只能按顺序进行,并且可以流式传输

image-20210613111043361

image-20210613111139275

Verification

对于N个核,每个核可以对每个身份进行流加密。所需总空间为2blocks ∗ Ncores,因为上一个加密块是生成下一个加密块所必需的。然后可以使用每个核心生成从当前加密块派生的所有证明。验证证明的总时间应等于加密所需的时间。证明本身从块中消耗很少的随机字节,因此要散列的数据量明显低于加密块的大小。可同时验证的复制标识数等于可用核心数。现代的GPU有3500+个内核可供使用,尽管时钟速度只有CPU的21-31倍。

Key Rotation

没有密钥旋转,相同的加密复制可以为多个历史证明序列生成廉价的证明。密钥会定期轮换,并且每个复制都会使用一个与唯一的历史证明序列相关联的新密钥重新加密。旋转需要足够慢,以便在GPU硬件上验证复制证明是切实可行的,因为每个核心的速度比cpu慢。

Hash Selection

历史证明生成器发布一个哈希,供整个网络用于加密复制证明,并用作快速证明中字节选择的伪随机数生成器。哈希在大约等于时间21的周期计数器上发布对数据集进行加密需要时间。每个复制标识必须使用相同的哈希,并使用哈希的签名结果作为字节选择的种子或加密密钥。每个复制器必须提供证明的时间段必须小于加密时间。否则,复制程序可以流式传输加密并删除每个证明。恶意生成器可以将数据注入此哈希之前的序列,以生成特定的哈希。

Proof Validation

历史证明节点不应验证提交的复制证明。预计它将跟踪复制者身份提交的待处理和验证证明的数量。当复制者能够通过网络中的绝大多数验证者对证明进行签名时,证明将被验证。验证由复制者通过p2p八卦网络收集,并作为一个包含网络中绝大多数验证程序的数据包提交。此数据包在历史证明序列生成的特定哈希之前验证所有证明,并且可以同时包含多个复制者标识。

还有很多没有理解透 未完待续